基于文化混合优化算法的旅行商问题求解  

A hybrid culture algorithm optimization strategy for traveling salesman problem

作　　者：马晗 常安定[1] 陈童 李江杰 MA Han;CHANG An-ding;CHEN Tong;LI Jiang-jie(College of Mathematical and Physics,Chang’an University,Xi’an 710064,China)

机构地区：[1]长安大学理学院

出　　处：《计算机工程与科学》2019年第7期1273-1278,共6页Computer Engineering & Science

摘　　要：为更好地求解TSP问题,将遗传算法与模拟退火算法结合并纳入文化算法体系,提出一种求解旅行商问题的文化混合优化算法。该算法空间可分为独立并行的两部分:种群空间和信度空间。种群空间按照遗传退火混合算法实现进化,并将进化中的较优个体提供给信度空间,信度空间提取并利用较优个体所包含的信息来引导种群进化。通过求解TSP标准测试问题,将文化混合优化算法所求得的最优路径与其他优化算法所求结果相比,算法偏差均可降低0.6%~13.01%,表明了文化混合优化算法求解TSP问题的有效性与优越性。Combining the genetic algorithm and simulated annealing algorithm with the culture algorithm,we design a hybrid culture optimization algorithm to solve the traveling salesman problem(TSP).The strategy contains two parts:the population space and the reliability space.The population space evolves according to the hybrid genetic annealing algorithm and sends optimal individuals to the reliability space.The reliability space extracts the information contained by the optimal individuals to guide population evolution.Experiments on TSP benchmark show that compared with other optimization algorithms,the hybrid cultural optimization strategy can reduce the deviation rate of the result to be 0.6%to 13.01%when obtaining the optimal path.Experiments verify the effectiveness and superiority of the hybrid cultural optimization strategy for solving the TSP.

关 键 词：旅行商问题 遗传算法 模拟退火算法 METROPOLIS准则 文化算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]