遗传算法求解多旅行商问题的相对解空间分析  

Analysis on the relative solution space for MTSP with genetic algorithm

作　　者：赵新超[1] 郭赛 ZHAO Xinchao;GUO Sai(School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China)

机构地区：[1]北京邮电大学理学院,北京100876

出　　处：《智能系统学报》2018年第5期760-768,共9页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金项目(61375066;11671052;71772060)

摘　　要：首先介绍了多旅行商问题的模型,并指出遗传算法解决多旅行商问题的关键是染色体编码方案的设计,为了减少冗余解带来的代价,本文给出了传统的两种染色体编码方案(单染色体和双染色体),以及最新的两段式染色体编码方案;接着引入相对解空间概念,以此定量地给出不同染色体方案对应解空间的相对大小关系;基于相对解空间概念,本文分析了3种染色体编码方案对应的解空间在极限意义下的相对大小关系,并分析了旅行商数与城市数在不同情形下解空间的近似相对大小关系。本文对搜索空间定量分析的理论结果对工程问题的求解提供了科学的指导意义。This paper introduces the concept of multiple traveling salespersons problem(MTSP)and a chromosome encoding design method for solving the MTSP using genetic algorithm.In order to reduce the cost of redundant solution,two traditional chromosome design methods(single and double chromosome designs)are proposed,as well as the current two-part chromosome encoding design.Then the concept of relative solution space is introduced to quantitatively compare the relative size order of spaces for different solutions.Then on based on the relative solution space,the relative size order of the solution spaces of three chromosome-encoding designs are analyzed under an infinite limit.Subsequently,the relative size order of the solution spaces is analyzed individually when the relationship presents different situations between the number of travelers and the number of cities.The theoretical results of the quantitative analysis on the search space given in this paper are of great significance in guiding engineering applications and solving practical problems.

关 键 词：多旅行商问题 遗传算法 染色体编码 相对解空间 STIRLING公式 

分 类 号：O224[理学—运筹学与控制论] TP18[理学—数学]