第２章基本蚁群优化算法及已有的改进算法

第２章基本蚁群优化算法及已有的改进算法

受自然界蚁群觅食行为的启发，ＤｏｒｉｇｏＭ等人首次提出了模拟进化算法——蚂蚁系统ＡＳ，开创了蚁群算法研究的先河，并用它求解ＴＳＰ问题，其实验显示ＡＳ算法具有极强的发现较好解的能力。然而，ＡＳ也存在着一些不足之处，如收敛速度慢、易陷入停滞等。对此，许多学者也纷纷提出一些改进的蚁群算法，如蚁群系统ＡＣＳ，最大一最小蚂蚁系统ＭＭＡＳ，具有变异特征的蚁群算法等等。

本章首先介绍了ＡＳ算法的基本模型，然后讨论了几种ＡＳ的改进算法。２．１蚂蚁系统（ＡＳ）模型与实现

２．１．１旅行商问题

旅行商问题（即ＴＳＰ）是一个经典的组合优化问题，ｎ个城市的ＴＳＰ问题求解可描述为访问ｎ个城市各一次且最后回到出发点的最短路径。具体地讲，给定一个城市集合Ｖ＝｛ｑ，屹，．．．，％｝，每个城市坼∈Ｖ用其对应的坐标点“，乃）表示，ｄｏ＝√（一一ｘ，）２一（Ｍ—Ｙｊ）２（ｊ，ｊ＝ｌ，２，…，聍）表示城市ｖ与城市巧之间的欧氏距离，ＴＳＰ问题的一个解就是遍历所有ｎ个城市后回到出发点的一个全连通图，可表示为Ｇ（ｎ，彳），彳＝｛％＝（ｖｉ，’，『）｜０＜ｆ，＿，≤刀，ｉ≠办是城市间两两相连的一组边。ＴＳＰ问题分为对称型和非对称型。在对称型ＴＳＰ问题中吃＝元，ＶＥ，Ｖ，∈Ｖ：而在非对称型ＴＳＰ问题中，至少存在～对ｖ，，■∈Ｖ，使得ｄ：５『≠吃。本文主要研究对称ＴＳＰ问题。

２．１．２蚂蚁系统

蚁群算法ＡＳ是蚁群优化算法ＡＧＯ中最基本的算法，它最初被用来解决城市旅行商（ＴＳＰ）问题。下面以ｎ个城市的ＴＳＰ问题为例，简要介绍ＡＳ算法。设ｍ是蚁群中蚂蚁的数量，ｄｔ，（ｆ，，∈Ⅳ＝（１’‘，．２．．，胛））表示城市ｉ与城市ｊ之间的欧氏距离，口｛『表示城市ｉ与城市ｊ之间的路径，％（ｆ）表示ｔ时刻在口｛『上信息素浓度，并设初始时刻各条路径上的信息素浓度均为Ｃ（常数）。蚂蚁ｋ（１≤ｋ≤ｍ）在自