求解TSP问题的贪心遗传算法

提出贪心遗传算法。通过构建“基因库”形成好的“基因片断”,从而生成高性能的初始种群;依据贪心选择的原则指导遗传操作,实施贪心交叉操作和贪心变异操作;移民操作向种群引进新的遗传物质,克服了封闭竞争缺点,并且可以避免早熟收敛。贪心遗传算法可以大大加快搜索的速度,仿真结果表明算法是十分有效和实用的。

Following the principle of greedy selection, the greedy genetic algorithm is proposed in this paper. A gene bank is constituted. The  initial population is formed based on the gene bank. Greedy crossover is adopted to produce a new child for its sufficiently utilizing the local  information of individuals. The two exchange local search of greedy mutation is also employed to improve the individual performance. In the process  of evolution, new individuals immigrate to the population every a few generations. This procedure prevents premature convergence of the population  and leads to an open competition. The simulation results of TSP show its excellent efficiency.

“973”高技术基金资助项目(2002CB312200)