蚁群优化算法：智能优化算法理论与应用

蚁群优化算法最早是由意大利学者Marco Dorigo受到真实蚁群的觅食机制的启发，于1991年在其博士论文中提出的一种新的进化计算方法。后期工作则是Marco Dorigo与其合作同事们在比利时布鲁塞尔自由大学研究期间陆续展开。

早期的研究成果大多是该研究团队在欧洲的一些小型专业研讨会及其会议录上所发表的，世界各地对此了解并不多。最早在正规专业期刊上发表这方面成果的是：Colorni（Marco Dorigo的博士生导师）等学者发表于《比利时运筹学学报》1994年第l期上的“Ant System for Job-shop Scheduling”，Colorni等学者发表于《国际运筹学汇刊》1996年第l期上的“Heuristics From Nature for Hard Combinatorial Optimization Problems”，以及Dorigo等学者发表于《IEEE系统、人、控制论汇刊》1996年第l期上的“Ant System：Optimization by a Colony of Cooperating Agents”。此后，蚁群优化算法逐渐引起了世界众多国家专家学者的关注，使其应用领域得到了快速拓广。1998年10月，首届蚂蚁优化国际研讨会于比利时布鲁塞尔自由大学召开。此后，几乎每年都召开一次这样的国际会议并出版会议录，吸引了来自世界各个国家的同行，还为蚁群优化算法开设了专题小组讨论和研习班。进入21世纪后的最近几年，Nature曾多次对蚁群Chinese Journal of Nature的研究成果进行报道，Future Generation Computer Systems和IEEE Transactions on Evolutionary Computation也分别于2000年和2002年出版了蚁群优化算法特刊。如今，在国内外许多学术会议和期刊上，蚁群优化算法已经成为一个备受关注的研究热点和前沿性课题，其研究人员和研究成果均成几何级数增长。

蚁群优化算法自提出以来，以旅行商问题（Traveling salesman problem，TSP）为测试基准，与其他一些常用启发式方法作了一系列的比较。对若干典型的对称型和非对称型TSP问题，先后采用了模拟退火法、遗传算法、神经网络、进化规划、遗传退火法、插入法、禁忌搜索法、边交换法等多种算法进行求解，除了Lin-Kernighan的局部改进法之外，蚁群优化算法优于其他的所有方法。在TSP问题之后，蚁群优化算法求解了经典的二次分配问题（QAP），测试数据来自著名的二次分配问题算例库QAPLIB，所得结果也相当令人满意。随后，工件排序、图着色、车辆调度、大规模集成电路设计、通讯网络中的负载平衡等一系列问题相继得到测试、求解和应用。

在标准的蚁群优化算法问世后不久，人们就开始对其设计了各种改进措施。首先出现的是将蚁群优化算法与Q学习算法结合而成的Ant-Q算法，其中利用了多个人工蚂蚁的协同效应。其后，德国学者Stützle和Hoos提出了最大最小蚂蚁系统（Max-Min ant system，MMAS），在求解TSP中获得了更好的效果。在此基础上，Bilchev等学者又提出了一种连续型蚁群优化算法，在求解问题时先利用遗传算法对解空间进行全局搜索，然后再使用蚁群优化算法对所得结果进行局部优化。Dré等学者提出了一种基于密集非递阶的连续交互式蚁群优化算法（continuous interacting ant colony algorithm，CIACA），该算法通过修改信息素的留存方式和行走规则，以及运用信息素交流和直接通讯来指导蚂蚁寻优。(www.xing528.com)

国内，1997年11月，吴庆洪等学者受到遗传算法中变异算子的启发，提出了一种具有变异特征的蚁群优化算法，这是国内学者对蚁群优化算法所作的最早改进。高尚等学者基于网格划分策略，并利用网格每一点的信息提出了一种连续域蚁群优化算法。在此基础上，段海滨等学者提出了一种基于网格划分策略的自适应连续域蚁群优化算法。Li等学者将遗传算法中的编码方法、精英策略融入到蚁群优化算法中，提出了一种连续域自适应蚁群优化算法。陈崚等学者将所求问题解的每个分量的可能值组成一个动态的候选组，并记录候选组中每个可能值的信息量，进而提出了一种基于交叉变异操作的求解连续域优化问题的蚁群优化算法。杨勇等学者提出了一种嵌入确定性搜索蚁群优化算法，该算法在全局搜索过程中利用信息素强度和启发式函数确定蚂蚁的移动方向，而在局部搜索过程中嵌入了确定性搜索，以提高寻优精度、加快收敛速度。张勇德等学者将信息素交流和基于全局最优经验指导这两种寻优方式相结合，提出了一种用于求解带有约束条件的多目标函数优化问题的连续域蚁群优化算法，即保存当前发现的所有非支配解，再用这些解来指导蚂蚁朝着分布较为稀疏的区域进行寻优，既保证了解的分布性能，又提高了算法的收敛速度。

回顾蚁群优化算法自创立以来20年的发展历程，目前人们对蚁群优化算法的研究已由当初单一的TSP领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究，并且在蚁群优化算法的硬件实现上取得了突破性进展，同时在蚁群优化算法的模型改进及与其他智能优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的智能优化算法展现出前所未有的勃勃生机，并已经成为一种完全可以与遗传算法相媲美的智能优化算法。