基于贪心策略的混合遗传算法在TSP中的实现

由于标准遗传算法初始种群是随机产生的,可能导致算法的收敛速度较低,并陷入局部最优解.为了解决这一问题,提出了一种改进的遗传算法.改进后的遗传算法先用贪心算法产生初始种群,使算法能够更快地达到最优解.选择操作时采用竞标赛方法,在每代进化结束后立即采取了末尾淘汰机制,从而使适应度高的个体被选中的概率增大.并用模拟退火算法改善其局部搜索,通过仿真实验可以看到,提出的邻近倒位变异以及新的非零递减自适应函数可以进一步提高算法的运行效率.

Hybrid Genetic Algorithm Based on Strategy of Greedy for TSP

Because of the randomicity created by the initial population of simple genetic algorithm, the constringency speed of the algorithm may be relatively low, and sometimes fall in local optimized result. An advanced genetie algorithm is introduced in order to solve the problem. By adopting greedy algorithm to the production of initial population, the algorithm can reach the best result quickly. By adopting the way of the tournament selection and the mechanism for washing out worst after every generation evolution, the proba-bility of selecting the individual with good fitness is heightened. And introducing simulated anneaing algorithm improves the local search condition. A adjacent reversal operation and nonzero descending self-adaptation function are simultaneously introduced,which is proved to be effective by the simulation.