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

摘要：

首先介绍了多旅行商问题的模型,并指出遗传算法解决多旅行商问题的关键是染色体编码方案的设计,为了减少冗余解带来的代价,本文给出了传统的两种染色体编码方案(单染色体和双染色体),以及最新的两段式染色体编码方案;接着引入相对解空间概念,以此定量地给出不同染色体方案对应解空间的相对大小关系;基于相对解空间概念,本文分析了3种染色体编码方案对应的解空间在极限意义下的相对大小关系,并分析了旅行商数与城市数在不同情形下解空间的近似相对大小关系.本文对搜索空间定量分析的理论结果对工程问题的求解提供了科学的指导意义.

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

所属期刊栏目：13

分类号：O224;TP18(运筹学)

资助基金：国家自然科学基金项目61375066,11671052,71772060

在线出版日期：2018-09-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：760-768