求解多目标旅行商问题的蚁群算法研究

摘要

多目标优化旅行商问题(TSP)在评价解时拥有多个复杂的标准。没有任何偏好信息，帕累托(PARETO)优化在这些解中建立一个偏序关系，并且算法的输出结果变成一个非支配解集而不是一个单解。近些年来，为了解决多目标旅行商问题，已经提出了多种蚁群优化算法;这些多目标蚁群优化算法(MOACO)针对多目标环境的特征，已经提出了多种设计理念。 目前对多目标蚁群算法的研究主要集中在如何利用优化过程中获取的成功经验进一步强化正反馈机制，但该种方式难于避免算法的早熟收敛问题。针对该问题本文从获取优化过程中的失败教训并将其应用于强化负反馈机制的角度对多目标蚁群算法进行了研究，通过为蚂蚁提供多样化的信息有效指导其觅食过程。本文的工作主要体现在以下三个方面:首先采用箱线图、H-指标和Kruskal-Wallis测试对目前已知的多目标蚁群算法进行比较分析，通过分析发现MOEA/D-ACO算法的性能比其他算法要好，而且信息素更新方式的不同，对算法的影响很大;然后在好的算法(MOEA/D-ACO)的基础上，结合负反馈机制提出了NMOACO/D算法;将蚂蚁群体分成多个组，对每组申请一个正反馈信息素矩阵的同时申请一个负反馈信息素矩阵;利用每次迭代得到的最差解更新每组的负反馈信息素矩阵。通过将NMOACO/D算法与其他已知算法比较发现，NMOACO/D算法的稳定不好;针对该问题，提出了自适应机制的SNMOACO/D算法;由于更新素更新方式的不同对算法影响不同，提出了三种信息素更新策略;在聚集信息素时，自适应调整三种信息素重要性系数。 为了验证提出算法的有效性，在不同规模问题上对提出的算法进行了测试并与相关算法的比较，结果表明MOEA/D-ACO在已知的算法中性能比较好但是稳定性不好，并且NMOACO/D算法比MOEA/D-ACO算法的性能好但是稳定性同样不好，SNMOACO/D算法比NMOACO/D算法的稳定性要好。

目录

声明

摘要

第1章引言

1．1研究背景与意义

1．2多目标旅行商问题

1．3多目标蚁群优化算法模型

1．4研究现状与动态

1．5本文工作及组织结构

第2章相关多目标蚁群算法比较分析

2．1多目标蚁群算法(MOACO)

2．1．1多目标蚁群优化算法(MOACO)中构造解组件

2．1．2 MOACO算法中信息素更新组件

2．1．3 MOACO算法多群组件

2．1．4多目标蚁群优化(MOACO)算法框架

2．2基于分解的多目标蚁群算法

2．2．1问题定义

2．2．2多目标优化问题(MOP)的分解

2．2．3 MOEA／D-ACO算法

2．2．4 MOACO／D算法

2．3多目标蚁群算法的评价机制

2．3．1评价机制所需的相关理论基础

2．3．2评价机制中相关工具介绍

2．3．3质量指标

2．4实验比对分析

2．4．1参数设置

2．4．2 bTSP问题的实验比对分析

2．5本章小结

第3章融合负反馈信息的多目标蚁群优化算法

3．1 NMOACO／D算法基本思想

3．2 NMOACO／D算法模型

3．3 NMOACO／D算法描述

3．4实验比较分析

3．4．1参数调整

3．4．2 NMOACO／D算法的收敛性分析

3．4．3基于H-指标算法的比较

3．4．4近似Pareto前沿

3．5本章小结

第4章自适应信息素选择多目标优化算法

4．1 SNMOACO／D算法基本思想

4．2 SNMOACO／D算法模型

4．2．1多群体的设定

4．2．2概率状态转移(PSW)

4．2．3更新正反馈信息素

4．3 SNMOACO／D算法描述

4．4实验结果比较与分析

4．4．2 SNMOACO／D算法的性能分析

4．5本章小结

第5章结论与展望

5．1主要贡献与结论

5．2未来研究展望

参考文献

附录

致谢

攻读硕士期间科研及发表论文情况