带有分级思想的自适应遗传算法

Self-adaptive Genetic Algorithm with Classification

为了平衡演化算法的搜索效果和效率,在自适应遗传算法中引入分级思想,即根据种群中个体适应值的相似性对其进行分级,使得优秀个体和较差个体充分发挥各自的职能。然而,过早收敛也是遗传算法亟待解决的问题之一,因此对遗传算法中的选择操作进行改进,定义了一种新的选择机制:一方面是在选择过程中引入一个新的参数——成活率,以有效地避免算法过早收敛;另一方面结合模拟退火中的参数——温度,通过变异杂交生成虚拟种群,以有效扩大搜索空间,保持种群多样性。实验结果表明,利用新算法处理TSP问题能够产生高质量的解,并能有效解决过早收敛问题。

Aiming at the balance of search results and search speed of evolutionary algorithm, we proposed a search strategy to classify the individuals by the similarity of their fitness. This differentiated respective function of individuals in search process. Nevertheless,premature convergence was one of GA-difficulties. So,an improved selection mechanism in GA was used to deal with the mentioned drawback. On the one hand,a new parameter named success ratio which is higher setting causes higher selection pressure. It could keep the algorithm from premature convergence. On the other hand, another parameter T the same as the simulated annealing algorithm＇s temperature was recommended. While mutation and crossover happened,a virtual population could be generated according to this parameter for enlargeing the search space and keeping the diversity of generation. Finally, experimental results on benchmark problems of TSP show that the new method is capable of producing highest quality solutions and preventing premature convergence efficiently.