Study on probability distributions for evolution in modified extremal optimization |
| |
Authors: | Guo-Qiang Zeng Wei-Jie Mao |
| |
Institution: | State Key Laboratory of Industrial Control Technology & Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou, 310027, China |
| |
Abstract: | It is widely believed that the power-law is a proper probability distribution being effectively applied for evolution in τ-EO (extremal optimization), a general-purpose stochastic local-search approach inspired by self-organized criticality, and its applications in some NP-hard problems, e.g., graph partitioning, graph coloring, spin glass, etc. In this study, we discover that the exponential distributions or hybrid ones (e.g., power-laws with exponential cutoff) being popularly used in the research of network sciences may replace the original power-laws in a modified τ-EO method called self-organized algorithm (SOA), and provide better performances than other statistical physics oriented methods, such as simulated annealing, τ-EO and SOA etc., from the experimental results on random Euclidean traveling salesman problems (TSP) and non-uniform instances. From the perspective of optimization, our results appear to demonstrate that the power-law is not the only proper probability distribution for evolution in EO-similar methods at least for TSP, the exponential and hybrid distributions may be other choices. |
| |
Keywords: | Extremal optimization (EO) Probability distributions Evolution Self-organized criticality (SOC) Self-organized algorithm (SOA) Traveling salesman problems (TSP) |
本文献已被 ScienceDirect 等数据库收录! |
|