蚁群算法在多目标TSP问题中的应用研究

刘争艳，江洁莉，李　絮

（阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037）

蚁群算法在多目标TSP问题中的应用研究

刘争艳，江洁莉，李絮

（阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037）

鉴于蚁群算法在处理组合优化问题中的优势，本文针对多目标TSP问题，对蚁群算法进行深入研究，探索多目标环境下蚁群算法的运行机制，同时构建多目标蚁群算法框架，并设计优化算子。仿真实验结果验证了本文算法的可行性与有效性。

蚁群算法；Pareto最优；多目标优化；旅行商问题

蚁群算法是受自然界中蚂蚁觅食行为的启发，由意大利学者Marco Dorigo等人于1991年提出的一种启发式仿生优化算法。由于具有分布式控制，正反馈自催化机制以及潜在的并行性等特点，蚁群算法被越来越多的应用到各类优化问题中，并在求解诸如旅行商问题（Traveling Salesman Problem，TSP）之类的组合优化问题中效果显著［1-4］。前期我们对蚁群算法进行了一些研究，并应用到单目标TSP问题的求解中，取得了良好的效果［5］。然而，现实世界中的很多问题通常不止一个优化目标，往往是由相互冲突的多个目标组成，以具体的TSP问题为例，现实中需要考虑的常常不止路程最短这一个目标，还要同时考虑诸如时间最少、费用最省、风险最小等方面的目标［6］。因此，对多目标TSP问题进行研究更具有现实意义。

1　多目标TSP问题

TSP问题可叙述如下：某旅行商要经过n个城市并回到原出发城市，除起点外，每个城市都必须且只允许经过一次，要求寻找所有城市之间一条最短的路径。……