Finite Markov chain analysis of classical differential evolution algorithm

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:268

Article

Hu, ZhongBo^1,2  Xiong, ShengWu¹  Su, QingHua^1,2  Fang, ZhiXiang³ 

[1] Wuhan Univ Technol, Sch Comp Sci & Technol, Wuhan 430070, Peoples R China

[2] Hubei Engn Univ, Sch Math & Stat, Xiaogan 432000, Hunan, Peoples R China

[3] Wuhan Univ, State Key Lab Informat Engn Surveying Mapping & R, Wuhan 430072, Peoples R China

关键词: Convergence in probability;    Continuous optimization;    Differential evolution algorithm;    Markov chain;   

DOI  :  10.1016/j.cam.2014.02.034

来源: Elsevier

【 摘 要 】

Theoretical analyses of algorithms are important to understand their search behaviors and develop more efficient algorithms. Compared with the plethora of works concerning the empirical study of the differential evolution (DE), little theoretical research has been done to investigate the convergence properties of DE so far. This paper focuses on theoretical researches on the convergence of DE and presents a convergent DE algorithm. First of all, it is proved that the classical DE cannot converge to the global optimal set with probability 1 by using the property that it cannot escape from a local optimal set. Inspired by the characteristics of the elitist genetic algorithm, this paper proposed a modified DE to overcome the disadvantage. The proposed algorithm employs two operators that assist it in escaping from a local optimal set and enhance the diversity of the population. And it is then verified that the proposed algorithm is capable of converging to global optima with probability 1. The theoretical research of this paper is undertaken in a finite discrete set, and the analysis tool used is the Markov chain. The numerical experiments are conducted on a deceptive function and a set of benchmark functions. The experimental results support the theoretical analyses on the convergence performances of the classical and modified DE algorithm. (C) 2014 Elsevier B.V. All rights reserved.

【 授权许可】

Free