Spatial evolution character of multi-objective evolutionary algorithm based on self-organized criticality theory

• Published in: Physica A 2012-11, Vol.391 (22), p.5490-5499
• Main Authors: Li, Jun-fang, Zhang, Bu-han, Liu, Yi-fang, Wang, Kui, Wu, Xiao-shan
• Format: Article
• Language: English
• Subjects: Algorithms; Displays; Evolution; Evolutionary algorithms; Immune systems; Incentives; Matthew effect; Multi-objective evolutionary algorithm; Optimization; Power-law distribution; Scale-free characteristic; Self-organized criticality; Spatial evolution character; Strategy
• ISSN: 0378-4371; 1873-2119
• DOI: 10.1016/j.physa.2012.06.032

This paper analyzes the spatial evolution character of multi-objective evolutionary algorithms using self-organized criticality theory. The spatial evolution character is modeled by the statistical property of crowding distance, which displays a scale-free feature and a power-law distribution. We propose that the evolutional rule of multi-objective optimization algorithms is a self-organized state transition from an initial scale-free state to a final scale-free state. The target is to get close to a critical state representing the true Pareto-optimal front. Besides, the anti-Matthew effect is the internal incentive factor of most strategies. The final scale-free state reflects the quality of the final Pareto-optimal front. The speed of the state transition reflects the efficiency of the algorithm. We simulate the spatial evolution characters of three typical multi-objective evolutionary algorithms representing three fields, i.e., Genetic Algorithm, Differential Evolution and the Artificial Immune System algorithm. The results prove that the model and the explanation are effective for analyzing the evolutional rule of multi-objective evolutionary algorithms. ► We model the spatial evolution character of MOEA using self-organized criticality. ► The statistical property of crowding distance displays a scale-free feature. ► The statistical property of crowding distance shows a power-law distribution. ► The evolutional rule of MOEA is a self-organized state transition process. ► The anti-Matthew effect is the internal incentive factor of most strategies.