Some modifications of low-dimensional simplex evolution and their convergence

Abstract

Low-dimensional simplex evolution (LDSE) is a real-coded evolutionary algorithm for global optimization. In this paper, we introduce three techniques to improve its performance: low-dimensional reproduction (LDR), normal struggle (NS) and variable dimension (VD). LDR tries to preserve the elite by keeping some of its (randomly chosen) components. LDR can also help the offspring individuals to escape from the hyperplane determined by their parents. NS tries to enhance its local search capability by allowing unlucky individual search around the best vertex of m-simplex. VD tries to draw lessons from recent failure by making further exploitation on its most promising sub-facet. Numerical results show that these techniques can improve the efficiency and reliability of LDSE considerably. The convergence properties are then analysed by finite Markov chains. It shows that the original LDSE might fail to converge, but modified LDSE with the above three techniques will converge for any initial population. To evaluate the convergence speed of modified LDSE, an estimation of its first passage time (of reaching the global minimum) is provided.

Keywords:

• global optimization
• evolutionary algorithm
• genetic algorithm
• low dimensional
• variable dimension
• Markov chain

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China (Grant No. 90916028) and a Grant-in-Aid for 21st Century COE Frontiers of Computational Science in Japan.