贪心遗传算法求解组合优化问题

许多问题最终可以归结为求解一个组合优化问题,GA是求解组合优化问题的一个强有力的工具,但遗传算法在应用中常出现收敛过慢和封闭竞争问题,本文提出贪心遗传算法。该算法的初始种群建立、交叉和变异等过程,都引入贪心选择策略指导搜索;移民操作向种群引进新的遗传物质,克服了封闭竞争缺点。贪心遗传算法可以避免早熟收敛并改进算法的性能,算法搜索起步阶段的效率是非常高的,本文通过TSP问题仿真试验证明了算法的有效性,在较少的计算量下,得到令人满意的结果。

Genetic algorithms often suffer from the shortcomings of slow convergence and enclosure competition. A novel greedy genetic algorithm(GGA) is proposed for combination optimization problems. Based on greedy policies, the procedure of population initialization, crossover and mutation operator produce a fitter child, for it sufficiently utilizes the local information of individuals. In the process of evolution, new individuals immigrate to the population every a few generations. All these procedures are designed to prevent premature convergence and refine the performance of genetic algorithm(GA). The simulation results of TSP show its excellent efficiency, especially during the early generation of GGA. Initial experiments demonstrated the basic promise of the approach. This work shows how GGA and GA can be usefully combined, thus pointing to a new and promising approach to combination optimization problems.

973计划课题 (2002CB312200 );;国家“十五”攻关重点专项基金项目(2001BA206A)资助