Modified Genetic Algorithm Based on State-space Model and Its Convergence Analysis

DOI编号  10.7641/CTA.2020.90986
2020,37(10):2115-2122

 作者 单位 邮编 齐战 长沙理工大学 410114 李茂军 长沙理工大学 410114 莫红 长沙理工大学 肖雨荷 长沙理工大学 刘芾 长沙理工大学

基于状态空间模型遗传算法(GABS)是一种新型实数编码进化算法, 在工程优化问题中取得良好的应用效 果. 针对GABS缺乏有效的数学模型及理论依据, 研究并建立了GABS的吸收态马尔可夫过程模型, 从可达状态集的 角度对GABS 进行分析并证明GABS 不是全局收敛的. 基于此提出了一种扩张可达状态集的改进型GABS (MGABS), 改进方法的两种变异策略不仅扩张了算法的可达状态集、提高了种群多样性, 而且加快了算法的收敛速 度与精度, 并证明了MGABS 具有全局收敛性. 最后利用经典测试函数验证了其综合性能明显优于其他三种算法, 为算法在工程中的应用提供了理论依据.

Genetic algorithm based on state-space model (GABS) is an innovative real-coded simulated evolutionary algorithm, which has good results in solving engineering optimization problems. The GABS has no theoretical foundation as a support. We therefore established a mathematical model based on absorbing Markov processes for GABS. The analysis of GABS from the perspective of attaining-state set indicated that GABS is not globally convergent. A modified genetic algorithm based on state-space model (MGABS) was therefore proposed. There are two mutation strategies in MGABS, which not only expand the attaining-state set and enrich the population diversity, but also accelerate the convergence speed and accuracy. The conclusion that MGABS has global convergence was obtained. Finally, 16 benchmark functions were taken as case study to verify the global convergence of MGABS. The results show that the MGABS has obvious advantages over the other three algorithms in terms of comprehensive performance. This paper therefore provides theoretical basis for the application of algorithm in engineering.