Modified extremal optimization with efficient initial configurations and extended probability distributions-based evolutionary mechanism

作者：Zeng G^*; Zhang Z; Dai Y; Zheng C

来源：ICIC Express Letters, Part B: Applications , 2012, 3(6): 1631-1636.

• Evolutionary mechanism
• Extremal optimization
• Initial configurations
• Probability distributions
• Travelling salesman problem

It has been recognized that some combinatorial optimization problems with highly degenerate states are difficult to solve in terms of many existing optimization algorithms. This paper presents a modified extremal optimization (EO) framework to deal with these problems. It starts from making use of the recently discovered statistical property to generate the initial configurations by so-called 'kth-nearest-neighbor search (kNNS)' and then further explores the complex configuration spaces by a modified EO approach. The proposed approach applies a more general probability distributions-based evolutionary mechanism than the original algorithm. The experimental results on some well-known hard instances of traveling salesman problem (TSP) have demonstrated that the proposed method may provide better performance than other physics-inspired algorithms, such as simulated annealing, τ-EO and self-organized algorithm. Furthermore, even for the same evolutionary mechanism, in average, the proposed algorithms with NNS-based initial configurations are superior to those with random initial configurations.

• 出版日期2012
• 单位浙江大学