遗传算法求解多模态优化问题的动力性

Dynamical Behavior of Genetic Algorithms on Multi-modal Optimization

多模态函数一般存在多个局部极值解,局部极值解处适应值的大小很大程度上影响了它们被遗传算法搜索到的概率.为了弄清楚这种影响机制,通过分析基因池遗传算法的无限种群动力系统,刻画了双峰函数局部极值解的适值差与系统不动点之间的解析关系,进一步分析推广了理论结果的适用范围.最后,提出针对多模态优化问题的两阶段遗传算法,给出了应用理论结果改善遗传搜索性能的范例,实验结果表明该算法对多模态函数的搜索性能有明显改善,从侧面证明了理论结果在实际应用中的正确性.

There is more than one local optimum in multi-modal landscapes. The values of local optima can influence their opportunities to be exploited by GAs. By analyzing the infinite population dynamical system using the gene pool GA and the BINEEDLE fitness function, we characterize the analytic relation between the fall of local optima and the fixed points in the infinite population dynamical system of the gene pool GA. Further analysis shows that the relation is still held in more common cases. Enlightened by the result, we derive a method to improve GAs for the multi-modal landscapes and get satisfying effect. The experiment results also prove the correctness of the theory in this paper.