CAJ | 학술논문

TSP问题不仅描述旅行商周游城市的问题，也是许多工程领域中复杂问题的抽象形式，找到一种有效的TSP问题求解方案具有十分重要的意义。针对大规模TSP问题中最小回路代价的求解问题，提出一种基于遗传算法的大规模TSP问题的求解方案，采用分而治之的思想，并对传统遗传算法的初始化和遗传算子进行改进，提高了算法性能。多个数据集上的实验结果证明了提出的算法能够优化收敛结果，一定程度上解决过早收敛的问题。
TSP문제불부묘술여행상주유성시적문제，야시허다공정영역중복잡문제적추상형식，조도일충유효적TSP문제구해방안구유십분중요적의의。침대대규모TSP문제중최소회로대개적구해문제，제출일충기우유전산법적대규모TSP문제적구해방안，채용분이치지적사상，병대전통유전산법적초시화화유전산자진행개진，제고료산법성능。다개수거집상적실험결과증명료제출적산법능구우화수렴결과，일정정도상해결과조수렴적문제。
TSP not only describes the problem of travelling around a number of cities, but also stands for a number of problems in some other fields.Thus, it is meaningful to find an effective solution to large-scale TSP.As for the solution to find the minimum distance of a loop consisting of a large number of cities in TSP, in this paper, we propose such a new solution based on genetic al-gorithms.It adopts the idea of dividing and ruling, and utilizes a genetic algorithm based on improved initialization method and genetic operators to improve its performance.Experimental results across multiple datasets illustrate the proposed algorithm per-forms well in optimizing convergence result and solving the problem of premature convergence to some extent.