摘 要：遗传算法在TSP 问题的解决过程中发挥着较为重要的作用。本文从遗传算法的基本原理与算法步骤入手，简述遗传算法的基本原理及遗传算法的基本步骤，然后对基于遗传算法的TSP 问题解决方式进行了分析，包括TSP 问题建模、TSP 问题遗传算法设计、编码方式、算子选择、单点交叉、变异算子、其他参数等，最后从选择因子分析和算法测试分析两方面对基于遗传算法的TSP 问题实验进行了探究。
关键词：遗传算法；TSP 问题；遗传操作
中图分类号：TP18 文献标识码：A 文章编号：2096-4706（2019）04-0010-03
Exploration of Solving TSP Problem Based on Genetic Algorithms
YUE Pengqi
（Liaoning Normal University Haihua College，Shenyang 110167，China）
Abstract：Genetic algorithm plays an important role in solving TSP problem. This paper starting with the basic principles and steps of genetic algorithm，briefly describes the basic principles and steps of genetic algorithm，and then analyses the solution of TSP problem based on genetic algorithm，including TSP problem modeling，genetic algorithm design of TSP problem，coding method，operator selection，single point crossover，mutation operator，other parameters，etc. ，finally，the experiment of TSP based on genetic algorithm is explored from two aspects of selection factor analysis and algorithm test analysis.
Keywords：genetic algorithm；TSP problem；genetic operation
参考文献：
[1] Chvátal V，Cook W，Dantzig G B，et al.Solution of a Large-Scale Traveling-SalesmanProblem [J].50Years of Integer Programming1958-2008，2010.
[2] John J. Grefenstette. Proceedings of the First International Conference on Genetic Algorithms and their Applications [M].S.l.：Taylor and Francis，2013.
[3] 邓慧允，张清泉. 蚁群算法与遗传算法在TSP 中的对比研究 [J]. 山西师范大学学报（自然科学版），2017，31（3）：34-37.
[4] 蒋然. 改进遗传算法在TSP 问题中的应用 [J]. 软件导刊，2016，15（12）：127-129.
[5] 陆游，何嘉. 基于并行优化与访存优化遗传算法的TSP 问题求解方法 [J]. 四川文理学院学报，2017（2）：11-17.
[6] 李月. 基于遗传算法的免疫算法对TSP 问题的改进与研究[J]. 中国传媒大学学报（自然科学版），2017（4）：58-63.
[7] 饶卫振，王新华，金淳，等. 一类求解TSP 构建型算法的通用改进策略 [J]. 中国科学：信息科学，2015，45（8）：60-79.
[8] 史小明. 浅谈MATLAB 下的遗传算法优化软件设计 [J].数字技术与应用，2017（6）：146+149.
[9] 宋海声，吕耕耕，刘岸果. 一种基于分层模型的TSP 构建算法 [J]. 微型机与应用，2017，36（6）：13-15+21.
[10] 伍建伟，刘夫云，李峤.MATLAB 遗传算法函数ga 优化实例 [J]. 机械工程与自动化，2017（2）：61-63.
[11] 武海峰. 基于Matlab 的遗传算法程序设计探讨 [J]. 电脑迷，2017（1）：4.
[12] 袁明珠.Matlab 遗传算法工具箱在约束非线性惩罚函数中的应用 [J]. 软件工程，2017，20（1）：37-39.
[13] 姚明海，王娜，赵连朋. 改进的模拟退火和遗传算法求解TSP 问题 [J]. 计算机工程与应用，2013，49（14）：60-65.
[14] 赵功勋，郭海滨，苏利. 基于遗传算法的工程项目资源均衡优化及其MATLAB 实现[J]. 工程经济，2016，26（12）：59-64.
[15] 宗德才，王康康. 一种混合局部搜索算法的遗传算法求解旅行商问题 [J]. 计算机应用与软件，2015，32（3）：266-270+305.
作者简介：岳鹏齐（1997.04-），男，汉族，辽宁锦州人，本科在读，研究方向：计算机科学与技术。