一种基于基因库求解TSP的单亲遗传算法  

A Partheno Genetic Algorithm Based on Gene Pool for TSP

作　　者：张建萍[1] 刘希玉[2] 

机构地区：[1]滨州学院计算机科学技术系,山东滨州256603 [2]山东师范大学管理与经济学院,山东济南250014

出　　处：《计算机仿真》2010年第8期198-200,315,共4页Computer Simulation

基　　金：国家自然科学基金资助项目(6037405);山东省滨州学院"青年人才创新工程"科研基金项目(BZXYQNLG200711);山东省自然科学基金重大项目(Z2004G02)

摘　　要：研究商品流通路线问题,TSP是组合优化问题的典型代表。针对TSP问题提出了一种改进的遗传算法。以引入"基因库"为基础,为了寻找出最优路径,提出一种只使用变异算子和选择算子繁殖后代的单亲遗传算法(PGA),并设计了一种新的组合算子作为算法的主搜索算子。算法利用基因库指导单亲遗传演化的进化方向,利用设计的组合算子来增强算法的搜索能力,从而很好地仿真了自然界的进化过程。计算结果证明,基因库的PGA算法具有较高的求解质量和求解效率,尤其是在求解Lin318 TSP问题时获得了优于目前最好解最短路径,可为设计提供有效的参考。Traveling Salesman Problem（TSP） is a typical representative of combinatorial optimization problems.An improved Genetic algorithm is proposed for solving TSP.This Partheno-genetic algorithm employs only mutation and selection operators to produce the offspring.A new combinatory operator is designed by combining the gene pool operator with inversion operator which ensures its strong searching capability.The gene pool directs the single-parent evolution and enhances the evolutionary speed.This algorithm simulates the recurrence of nature evolution process.Experiments based on 4 instances selected from TSPLIB are used to test the performance of this algorithm.They prove that it can reach the satisfying optimization at a faster speed.Especially,for the KroA100,the best path it found is better than any other available one.

关 键 词：旅行商问题 基因库 组合算子 单亲遗传算法 

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