针对NSGA-II算法求解多目标TSP问题的易出现未成熟收敛、计算时间复杂度高且稳定性不够等不足，通过设计面向多目标TSP问题的新型定向交叉算子，并采用权重聚合方法将标准化后的多目标空间转化为单目标空间，借助贪心策略重组基因来增加算法的收敛速度而减少交叉次数；与此同时，利用定向交叉思想，寻找多目标空间上的边界解来增强算法的分布性和对新空间的探索能力，最终实现算法优化效率的提升。通过在多目标TSP标准测试数据集上的仿真实验，结果表明新型定向交叉能有效地均衡寻优过程中收敛性与分布性，在优化效率上明显好于改进前的算法。

【关键词】多目标TSP问题 定向交叉 NSGA-II 贪心策略 收敛性 分布性

1 新型定向交叉在NSGA-II求解多目标TSP问题中的应用

在2002年，Deb等学者在NSGA基础上提出了快速带精英策略的NSGA-II算法。主要改进之处有：首先，设计了基于合并父代种群和子代种群的精英保留策略；其次，通过快速非支配排序策略降低算法计算复杂度；再者，采用拥挤距离策略代替适应度共享策略来实现更具可操作性的非支配个体排序方法。

1.1 遍历路径的编码

根据多目标TSP优化问题的特点，采用自然编码方式，一条n个城市的遍历路径表示为，其中表示第i个城市的序号，取值为从1到n不重复的自然数。例如{1， 3， 6， 8， 5， 7， 4， 2， 9}，表示城市路线为{1-3-6-8-5-7-4-2-9-1}。

遍历路径是一个首尾相连的回路，因此会存在冗余路径。例如路径{1-3-6-8-5-7-4-2-9}和路径{3-6-8-5-7-4-2-9-1}表达同一条路径，所以在初始化和交叉过程中，为排除冗余路徑，在实现时始终保持城市1为首位，以便减小重复搜索，提高搜索效率，保证解集的覆盖度。

1.2 不同优化目标的归一化

多目标TSP优化问题不同于传统的单目标TSP优化问题，拥有多个目标函数，且往往相互冲突，无法同时达到最优。与此同时函数值之间难以比较，所以导致很多在解决单目标TSP优化问题的有效算法，在面对多目标TSP问题时难以发挥，为了解决这个问题，采用标准化的思想，将不同的目标函数值，投影到0到1之间，从而进行组合比较。

遍历全连通图，获取每一个目标的最大值和最小值FMax（j）和FMin（j），将两城市之间不同代价距离映射到0到1之间。

1.3 新型定向交叉算子

交叉操作是进化算法中最重要的遗传操作之一，直接关系到算法优化效率。针对NSGA-II算法求解多目标TSP问题的易出现未成熟收敛、计算时间复杂度高且稳定性不高等不足，通过设计面向多目标TSP问题的新型定向交叉算子，交叉方向随着迭代次数改变，快速生成目标之间一定比例的解，并在此基础上生成新的个体，将多目标问题在交叉时转化为单目标问题，大大减少进化算法中生成劣解后代数量，大幅提高运算效率。

实际操作中，将两条父类染色体拆分为基因片段（包含两个城市的集合），将多目标参数按照一定比例结合，构造基因片段之间的评价标准，用贪心的策略进行重组，考虑到父类遍历路径片段的重复情况，重组时无法生成符合要求的合理遍历路径，在合成遍历路径时，再次运用贪心策略，将未包含的路径片段添加到合理遍历路径中。

下面，假设城市数量为5，目标数量为2。例如两条父类遍历路径分别为：{1-5-2-4-3}和{1-2-5-4-3}。首先，将其拆分为路径片段：{（1-5）， （5-2）， （2-4）， （4-3）， （3-1）}和{（1-2）， （2-5）， （5-4）， （4-3）， （3-1） }；然后，将每一个路径片段的单个目标值f1，f2按照权重参数p∈[0，1]组合，生成新的目标值f，即为f=f1*（p）+f2*（1-p）；根据新生成的f将以上路径片段根据权重从小到大进行排序，假如排序后得到的有序序列为： （1-5）， （5-2）， （2-5）， （2-4）， （4-3）， （4-3）， （3-1）， （3-1）， （1-2）， （5-4）；接着，采用贪心策略，从头取出互不冲突的路径片段，组合生成符合要求的合理遍历路径，即为{（1-5）， （5-2）， （2-4）， （4-3）， （3-1）}路径片段集，对应的遍历路径为{1-5-2-4-3}。在实验中发现，解集两端的延展性较差，所以给出1/3的迭代次数，进行解集两端的收敛，保证解集的完整性。

2 结束语

根据多目标TSP优化问题的特点，针对NSGA-II算法求解多目标TSP问题的易出现未成熟收敛、计算时间复杂度高且稳定性不高等不足，通过设计面向TSP问题的新型定向交叉算子，并采用权重聚合方法将标准化后的多目标空间转化为单目标空间，借助贪心策略重组基因来增加算法的收敛速度而减少交叉次数；与此同时，利用定向交叉思想，寻找多目标空间上的边界解来增强算法的分布性和对新空间的探索能力，最终实现算法优化效率的提升。最后通过在单目标和多目标TSP优化问题的仿真实验，验证了新型定向交叉算子的有效性，大大地提高了NSGA-II算法求解多目标TSP问题的效果。下一步将针对解集的完整性和分布性，进一步优化定向交叉算子的细节设计，进一步提高交叉操作的适用性。

参考文献

[1]陈国良，王煦法，庄镇泉等.遗传算法及其应用[M].北京：人民邮电出版社，2001.

[2]公茂果，焦李成，杨咚咚，马文萍.进化多目标优化算法研究[J].软件学报，2009（02）：271-289.

[3]王辉.用遗传算法求解TSP问题[J].计算机与现代化，2009（07）：12-15，25.

[4]雷玉梅.基于改进遗传算法的大规模TSP问题求解方案[J].计算机与现代化，2015（02）：34-39.

[5]游道明，陈坚.用蚁群算法解决多目标TSP问题[J].小型微型计算机系统，2003，24（10）：1808-1811.

作者简介

刘胜军（1974-），男，安徽省和县人。计算机专业硕士学位。主要研究方向为机器学习、数据挖掘等。

耿焕同（1973-），男，安徽省绩溪县人。教授，博士生导师。主要研究方向为计算智能与约束多目标优化、气象资料预处理。

作者单位

1.安徽中科大国祯信息科技有限责任公司 安徽省合肥市 230008

2.南京信息工程大学滨江学院 江苏省南京市 210044