第1章 绪章

1.1 引言

随着科学技术的进步，人类生存空间不断扩大，认识世界和改造世界的范围不断拓宽，各领域不断涌现大量的大规模、非线性、强约束的复杂优化问题。问题的计算复杂性给优化方法带来新的挑战。虽然经典优化方法的理论相对完备，然而这些方法一般只适用于具有特殊结构的优化问题。例如，单纯形算法仅适用于线性规划，不能用于非线性问题；梯度下降法假设待求解的问题是连续可微的[1]。在第二次世界大战中，美国数学家冯·诺伊曼（Von Neumann）等提出了蒙特卡罗（Monte Carlo）方法[2]，并利用刚刚诞生的电子计算机进行模拟计算，有效地解决了原子弹研制过程中出现的大量问题。人们认识到利用计算机进行“采样”可以求解优化问题。蒙特卡罗方法启发人们重新认识优化，并致力于探索新型优化方法。

自20世纪80年代以来，尤其是在最近20年，一些与经典的数学规划截然不同的、试图通过模拟自然界中的自适应优化现象求解复杂优化问题的新型智能优化算法相继出现，如遗传算法、人工免疫算法、模拟退火算法、人工神经网络、蚁群算法、粒子群优化算法等[3],[4]，这些智能优化算法大大丰富了优化技术，也为那些传统最优化技术难以处理的优化问题提供了新的极具竞争力的解决方案。

在众多智能优化算法中，蚁群算法是最成功的算法之一[5]。该算法由意大利学者Dorigo等于20世纪90年代初提出，蚁群算法模拟蚂蚁觅食行为，将习得的信息保存在信息素场中，在产生解时，它利用问题相关的启发信息和习得的信息，而在信息加工时利用历史解信息更新信息素场，信息素场又反馈指导蚁群产生更好的解。

蚁群算法首先用于求解著名的旅行商问题（Traveling Salesman Problem, TSP），并获得了很好的计算效果[6]。此后该算法逐渐引起了国内外学者的关注，他们对该算法做了许多改进并且将其应用于更为广泛的领域，取得了一系列令人鼓舞的成果[5]。1999年，Dorigo等将其进一步发展成一种通用的优化技术——蚁群算法（Ant Colony Optimization, ACO），并将所有符合ACO框架的算法统称为蚁群算法[7]，从而为ACO的理论研究和算法设计提供了统一的框架。目前，蚁群算法的应用范围涉及城市给水排水问题[8]、卫星调度[9]、机器人领域[10～14]、电力系统[15～18]、故障诊断[19]、系统辨识[20]、数据挖掘[21～25]、图像处理[26～28]、航迹规划[29],[30]、空战决策[31]、岩土工程[32]、化学工业[33]、生命科学[34]、布局优化[35]、控制参数优化[36],[37]等科技和工程领域[38],[39]。