CAJ | 학술논문

旅行商问题(TSP)是一个经典组合优化方面的问题.本文基于原始数据进行域规则的数据预处理,提出了一种对传统路径编码,以及诸算子改进的遗传算法.改进的遗传算法的数据预处理将根据地图区域化特点进行网格区域划分处理,且采用提前培育的局部优秀基因块,再与整体相结合完成分阶段初始化.同时,区域划分必然存在邻近区域,进而有了对于诸算子的发生位置的指导以及发生概率的影响.研究实现结果表明,通过对城市数据进行规则的预处理以及配套的策略相结合,可提高遗传算法的收敛速度和精确度.
여행상문제(TSP)시일개경전조합우화방면적문제.본문기우원시수거진행역규칙적수거예처리,제출료일충대전통로경편마,이급제산자개진적유전산법.개진적유전산법적수거예처리장근거지도구역화특점진행망격구역화분처리,차채용제전배육적국부우수기인괴,재여정체상결합완성분계단초시화.동시,구역화분필연존재린근구역,진이유료대우제산자적발생위치적지도이급발생개솔적영향.연구실현결과표명,통과대성시수거진행규칙적예처리이급배투적책략상결합,가제고유전산법적수렴속도화정학도.
Traveling salesman problem (TSP) is a classic combinatorial optimization problem.Based on the domain preprocessing of primary data,the paper proposes a genetic algorithm by encoding traditional path and im-proving these operators.Data preprocessing of the improved genetic algorithm makes the processing of the grid di-vision according to the regional characteristics of maps,nurtures the local excellent genetic blocks in advance,and then combines with the overall cities to finish the staged initialization.At the same time,there must be adjacent ar-eas after the processing of regional division,which gives the guidance of the position and the occurrence probabili-ty in these operators.The research results show that the genetic algorithm can improve the convergence speed and accuracy through the combination of the rules for urban data preprocessing and related strategies.