CAJ | 학술논문

提出了一种加入了禁忌表、并且采用了新的温度控制机制的用于求解TSP问题的模拟退火算法.新算法增加了搜索结束阶段进行"爬坡"移动的概率,吸收了禁忌搜索具有较强局部搜索能力的优点和模拟退火算法产生优质解的能力,并且对问题的依赖性低于传统的模拟退火算法.对标准的TsPLib中不同国家的城市数据进行测试的实验结果表明,新的算法比传统的模拟退火算法在求解TSP问题上有更快的收敛速度,在解的质量上也有一定程度的提高.
제출료일충가입료금기표、병차채용료신적온도공제궤제적용우구해TSP문제적모의퇴화산법.신산법증가료수색결속계단진행"파파"이동적개솔,흡수료금기수색구유교강국부수색능력적우점화모의퇴화산법산생우질해적능력,병차대문제적의뢰성저우전통적모의퇴화산법.대표준적TsPLib중불동국가적성시수거진행측시적실험결과표명,신적산법비전통적모의퇴화산법재구해TSP문제상유경쾌적수렴속도,재해적질량상야유일정정도적제고.
Based on the existing simulated annealing algorithm,the paper proposes a hybrid tabu-smiulated approach which introducing a new cooling schedule to solve Traveling Salesman Problem.With this new temperature control scheme,a higher chance of an uphill move is given at the end of search.Combined with the excellent local search ability of tabu search and the fine solution quality of simulated annealing, the proposed approach is less dependent on the specific information of problem compared with conventional simulated annealing.The performance of proposed approach is evaluated and favorably compared with the conventional simulated annealing.Numerical results of Benchmark TSPLib illustrate that this algorithm has better convergence speed and easy to find out the best answer.