求解旅行商问题的搜寻者遗传算法
|
摘要
针对简单遗传算法易陷入局部最优及收敛速度慢的不足,提出一种改进遗传算法-基于启发式策略的搜寻者遗传算法.首先将搜寻者优化算法中的模糊思想和近邻策略相结合改进变异算子,增强种群多样性,避免陷入局部最优;然后针对路径优化问题基于启发式策略设计反转算子,使得路径中不存在交叉边,加快收敛速度;最后将改进遗传算法用于求解旅行商问题.结果表明,改进遗传算法的求解精度和求解效率明显优于基本遗传算法.
Aiming at the problems of local optimization and low convergence rate of simple genetic algorithm, an improved genetic algorithm——seeker genetic algorithm with heuristic strategy was proposed. Firstly, fuzzy thought in seeker optimization algorithm and the nearest neighbor strategy are used to improve the mutation operator, and improved diversity of the population and avoided the local optimal. Then, this paper designed inversion operator based on the heuristic strategy for the path optimization problem, so that there is no cross edge in the path, and accelerated convergence speed. Finally, the improved genetic algorithm is used to solve the TSP problem. Results show that the proposed algorithm is better than simple genetic algorithm in both accuracy and efficiency of optimization.
Aiming at the problems of local optimization and low convergence rate of simple genetic algorithm, an improved genetic algorithm——seeker genetic algorithm with heuristic strategy was proposed. Firstly, fuzzy thought in seeker optimization algorithm and the nearest neighbor strategy are used to improve the mutation operator, and improved diversity of the population and avoided the local optimal. Then, this paper designed inversion operator based on the heuristic strategy for the path optimization problem, so that there is no cross edge in the path, and accelerated convergence speed. Finally, the improved genetic algorithm is used to solve the TSP problem. Results show that the proposed algorithm is better than simple genetic algorithm in both accuracy and efficiency of optimization.
引文
[1] Holland J H. Adaptation in natural and artificial system[M]. Ann Arbors The University of Michigan Press, 1975.
[2] Dong G,Guo W W,Tickle K.Solving the traveling salesman problem using cooperative genetic ant systems[J]. Expert Systems with Applications, 2012, 39(5):5006-5011.
[3]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2002.
[4]张晓玲,左国超,杨健.用一种含启发式变异策略的遗传算法求解TSP[J].计算机应用与软件,2010,27(3):237-240.
[5] Liu F, Zeng G. Study of genetic algorithm with reinforcement learning to solve the TSP[M]. Pergamon Press, Inc,2009.
[6]刘菲,吕世辉,赵中华.基于多步强化变异算子的混合遗传算法[J].计算机工程与应用,2011,47(29):46-48.
[7]郑明,卓慕瑰.四点三线遗传算法求解旅行商问题[J].计算机工程与应用,2017, 53(14):148-154.
[8]周鹏.求解TSP的启发式顺序交叉算子[J].计算机工程与设计,2007, 28(08):1896-1897.
[9]戴朝华.搜寻者优化算法及其应用研究[D].成都:西南交通大学,2009.
[10] Zhang X X, Chen W R, Dai C H. Dynamic multi-group self-adaptive differential evolution algorithm with local search for function optimization[J]. Acta Electronica Sinica, 2010, 38(8):1825-1830.
[11] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories[C]//Internatio nal Conference on Data Engineering. San Jose:IEEE Computer Society, 2002:673.
[12]何健,张宏军,王之腾,等.一种基于近邻策略求TSP问题的改进演化算法[J].计算机与现代化,2012(08):1-5.
[13]吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015(10):1861-1867.
[14]标准TSP测试库[EB/OL].(2008-08-06)[2017-07-30]. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/.
[15]冀俊忠,黄振,刘椿年.一种快速求解旅行商问题的蚁群算法[J].计算机研究与发展,2009, 46(6):968-978.
[16]王迎,张立毅,费腾,等.求解TSP的带混沌扰动的模拟退火蚁群算法[J].计算机工程与设计,2016,37(4):1067-1070.
[17]费腾,张立毅,白煜,等.基于DNA的改进人工鱼群算法[J].天津大学学报(自然科学与工程技术版),2016, 49(6):581-588.
[18]周永权,黄正新.求解TSP的人工萤火虫群优化算法[J].控制与决策,2012, 27(12):1816-1821.
[2] Dong G,Guo W W,Tickle K.Solving the traveling salesman problem using cooperative genetic ant systems[J]. Expert Systems with Applications, 2012, 39(5):5006-5011.
[3]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2002.
[4]张晓玲,左国超,杨健.用一种含启发式变异策略的遗传算法求解TSP[J].计算机应用与软件,2010,27(3):237-240.
[5] Liu F, Zeng G. Study of genetic algorithm with reinforcement learning to solve the TSP[M]. Pergamon Press, Inc,2009.
[6]刘菲,吕世辉,赵中华.基于多步强化变异算子的混合遗传算法[J].计算机工程与应用,2011,47(29):46-48.
[7]郑明,卓慕瑰.四点三线遗传算法求解旅行商问题[J].计算机工程与应用,2017, 53(14):148-154.
[8]周鹏.求解TSP的启发式顺序交叉算子[J].计算机工程与设计,2007, 28(08):1896-1897.
[9]戴朝华.搜寻者优化算法及其应用研究[D].成都:西南交通大学,2009.
[10] Zhang X X, Chen W R, Dai C H. Dynamic multi-group self-adaptive differential evolution algorithm with local search for function optimization[J]. Acta Electronica Sinica, 2010, 38(8):1825-1830.
[11] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories[C]//Internatio nal Conference on Data Engineering. San Jose:IEEE Computer Society, 2002:673.
[12]何健,张宏军,王之腾,等.一种基于近邻策略求TSP问题的改进演化算法[J].计算机与现代化,2012(08):1-5.
[13]吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015(10):1861-1867.
[14]标准TSP测试库[EB/OL].(2008-08-06)[2017-07-30]. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/.
[15]冀俊忠,黄振,刘椿年.一种快速求解旅行商问题的蚁群算法[J].计算机研究与发展,2009, 46(6):968-978.
[16]王迎,张立毅,费腾,等.求解TSP的带混沌扰动的模拟退火蚁群算法[J].计算机工程与设计,2016,37(4):1067-1070.
[17]费腾,张立毅,白煜,等.基于DNA的改进人工鱼群算法[J].天津大学学报(自然科学与工程技术版),2016, 49(6):581-588.
[18]周永权,黄正新.求解TSP的人工萤火虫群优化算法[J].控制与决策,2012, 27(12):1816-1821.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |