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

A Novel Greedy Genetic Algorithm for Traveling Salesman Problem

作　　者：魏英姿[1] 赵明扬[1] 黄雪梅[1] 胡玉兰[2] 

机构地区：[1]中国科学院沈阳自动化所机器人学重点实验室,沈阳110016 [2]沈阳工业学院,沈阳110168

出　　处：《计算机工程》2004年第19期19-20,34,共3页Computer Engineering

基　　金："973"高技术基金资助项目(2002CB312200)

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

关 键 词：贪心遗传算法 贪心交叉算子 贪心变异算子 旅行商 建筑块 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]