CAJ | 학술논문

应用遗传算法求解旅行商问题时,极易破坏已经发现的较短线路片段.为此,引入基因簇以便保护较短的线路片段,基于P2P设计了TSP求解遗传算法P2PTSPGA.在交叉和变异操作的过程中,基因簇完整地遗传到下一代;在获得第一个近优解后粉碎基因簇,以避免算法陷入局部最优.使用CHN144找到了当前最优路径,并使用TSPLIB进行了串行和并行试验.TSP225实验获得了最短环路路径3859,优于目前已经公布的结果3916.实验表明,P2PTSPGA具有较高的求解性能,并具备5000左右城市的持续寻优能力.
응용유전산법구해여행상문제시,겁역파배이경발현적교단선로편단.위차,인입기인족이편보호교단적선로편단,기우P2P설계료TSP구해유전산법P2PTSPGA.재교차화변이조작적과정중,기인족완정지유전도하일대;재획득제일개근우해후분쇄기인족,이피면산법함입국부최우.사용CHN144조도료당전최우로경,병사용TSPLIB진행료천행화병행시험.TSP225실험획득료최단배로로경3859,우우목전이경공포적결과3916.실험표명,P2PTSPGA구유교고적구해성능,병구비5000좌우성시적지속심우능력.
When a genetic algorithm is used to solve a TSP (Traveling Salesman Problem), it is very possible of destroying shorter paths found before. While the gene clusters are introduced to protect shorter paths mentioned above, this paper presents a P2P based TSP solving genetic algorithm P2PTSPGA. The gene clusters are totally past down to their offspring of the chromosomes during the genetic operations, and are smashed after the first near optimum is found in order to prevent from falling into a local optimum. In the experiments for CHN144 and for instances in TSPLIB, the current optimal solution is found for CHN144 by our P2PTSPGA, and the solution 3859 for TSP225 is found better than the up-to-date best result 3916. Our experiments show that the P2PTSPGA has a high performance in solving TSPs and own an ability of searching optimal tours for 5000-city TSPs.