蚁群算法及其应用研究进展

第２５卷第８期

２００８年８月

计算机应用与软件

ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ

Ｖ０１．２５Ｎｏ．８Ａｕｇ．２００８

蚁群算法及其应用研究进展

倪庆剑

摘要

邢汉承张志政王蓁蓁

（东南大学计算机科学与工程学院江苏南京２ｌ００９６）

蚁群算法作为一种仿生进化算法，是受到真实蚁群觅食机制的启发而提出的。首先介绍了蚁群算法的基本原理和工作

机制，然后分别就蚁群算法的理论和应用的研究现状进行了综述，主要包括蚁群算法的参数设置，蚁群算法的改进，蚁群算法的收敛性以及蚁群算法在组合优化问题和连续优化问题中的应用，并进一步给出了它们的研究重点和发展方向，最后是关于蚁群算法的研究展望和面临的挑战，提出了蚁群算法研究中值得探讨的一些课题。关键词

群智能方法蚁群算法优化问题

ＡＮＴＣＯＬＯＮＹ

ＡＬＧＯＲＩＴＨＭ

Ｎｉ

ＡＮＤＩＴＳ

ＡＰＰＬＩＣＡＴＩｏＮＳ：ＲＥＶＩＥＷ

ＺｈａｎｇＺｈｉｚｈｅｎｇ

ＡＮＤＰＲｏＧＲＥＳＳ

ＸｉｎｇＨａｎｃｈｅｎｇ

（＆＿Ｉｌｏｏｆ旷ｃｏ唧姚ｒｓ啦，ｍ

Ｔｈｅ朋ｔｃｏｌｏｎｙａｌｇｏ而ｔｈｍｉｓ

Ｑｉｎｄｉａｎ

ｎ，ｌｄ西讲ｎ唧ｉ，ｌｇ，ＳＤ以ｋ删№妙．№彬增２ＪＤＤ粥，，缸７咿Ⅱ，仇ｉ尬）

ｐｒｏｂｌｅ衄，ｗｈｉｃｈ

ｉｓ

ＷａｎｇＺｈｅｎｚｈｅｎ

Ａｂｓｔｒａｃｔａｌ

ａｎｔ

ａ

ｍｅｔａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｆｈｏｐｔｉｍｉｚａｔｉｏｎ

ａｎｔ

ｉ璐ｐｉｒｅｄｂｙｆｏｍｇｉｎｇｍｅｃｈａｎｉｓ脚ｏｆ

ｃｕｎ＿ｅｎｔ

ｒｅ－

ｃｏｌｏｎｉｅ８．Ｔｈｅ

ｂ∞ｉｃｐｒｉｎｃｉｐｌｅａｎｄｗｏｒｋｉｎｇｍｅｃｈａｎｉｓｍｏｆ

ａｒｅ

ｃｏｌｏｎｙａ１９０ｒｉｔｈｍａ弛ｆｉ碍ｔｌｙ

ａｒｅ

ｉｎｔｒｏｄｕｃｅｄ，卸ｄ

ｍｓｅａｒｃｈｅ８ｉｎｔｈｅｏｒｉｅ８

ａｎｄａｐｐｌｉｃａｂｏｎｓｏｆ如ｔｃｏｌ∞ｙａｌｇｏｒｉｔｈｍ

ａ１８０ｏＶｅｎｒｉｅｗｅｄｒｅｓｐｅｃｔｉｖｅｌｙ，ｗｈｉｃｈ

ｒｅｌａｔｅｄｔｏ

ｔｈｅｃｏｎｆｉｇｕｍｔｉｏｎｏｆｐａｒａｍｅｔｅ璐，ｉｍｐｒｏＶｅｍｅｎｔｓ，

Ａｔ

ｔｈｅｓａｍｅ

ｃｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓａｎｄａｐｐｌｉｃａｔｉｏｎｓｉｎ

ｄｙｎａｍｉｃ

ｃ伽ｂｉｎａｔｏｒｉａｌ

ｏｐｔｉｍｉｚａｔｉｏｎｐｍｂｌｅｍｓａｎｄｃｏｎｔｉｎｕｏｕｓｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．

ｏｎ

ｔｉｍｅ，ｆｕｒｔｈｅｒｆｂｃｕｓｉｎｇａｒｅ船ａｎｄｅｘｐｌｏｉｔａｔｉｏｎｄｉｒｅｃｔｉｏ珊ａｒｅｐ陀ｓｅｎｔｅｄ．Ｆｉｎａｌｌｙ，∞ｍｅｒｅｍａｒｋｓ

ｔｈｅｆｕｔｕｒｅｔｒｅｎｄｓａｎｄｃｈａｌｌｅｎｇｅｓｆａｃｅｄ鹊ｗｅｌｌ

鹤ｅｘｉｓｔｉＩｌｇｐｒｏｂｌｅｍ８ｒｅＪａｔｅｄｔｏ卸ｔｃｏｌｏｎｙａＪｇｏｄｔｈｍａｍｄｉｓｃｕｓｓｅｄａｎｄｃ∞ｃｌｕｄｅｄ．

Ｋｅｙｗｏｒｄｓ

Ｓｗａ肋ｉｎｔｅＵｉｇｅｎｃｅＡｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ

０ｐｔｉｍｉｚａｔｉｏｎｐｍｂｌｅｍ

本文就蚁群算法的理论和应用研究现状进行了综述，勾画

Ｏ

引言

Ｃｏｌｏｎｙ

了当前蚁群算法研究领域的热点及发展趋势。

Ａｌｇｏｒｉｔｈｍ）是由意大利学者Ｄｏｒｉｇｏ

１

蚁群算法（Ａｎｔ

蚁群算法的基本原理

真实蚁群通过在觅食路径上释放信息素（Ｐｈｅｒｏｍｏｎｅ）最终

等…人在２０世纪９０年代受到真实蚁群的觅食机制的启发而提出的一种新的进化计算方法。最早的蚁群算法是蚂蚁系统（ＡｍＳｙｓｔｅｍ），研究者们根据不同的改进策略对蚂蚁系统进行改进并开发了不同版本的蚁群算法，并成功地应用于优化领域。

蚁群算法具有分布式计算，无中心控制和分布式个体之间间接通信的特征，易于与其它优化算法相结合，蚁群算法通过简单个体之间的协作表现出了求解复杂问题的能力，已被广泛应用于求解优化问题。蚁群算法相对易于实现，且算法中并不涉及复杂的数学操作，其处理过程对计算机的软硬件要求也不高，因此对它的研究在理论和实践中都具有重要的意义。

目前国内外的许多研究者和研究机构都开展了对蚁群算法理论和应用的研究。比利时布鲁塞尔自由大学的ＩＲｌＤＩＡ实验室，瑞士的ＩＤｓＩＡ等都是目前在蚁群算法研究领域较为活跃的机构。总的来说，蚁群算法已成为国际计算智能领域关注的热点课题。蚁群算法作为群智能方法中的一种，是每年一度的ＩＥＥＥＳｗａｍＩｎｔｅｌｌｉｇｅｎｃｅｓｙｍｐｏｓｉｕｍ中的重要内容。１９９８年在布鲁塞尔召开了第一届蚁群优化和群智能国际研讨会，此后该会每两年召开一次。虽然目前蚁群算法没有形成严格的理论基础，但其作为一种新兴的进化算法已在智能优化等领域表现出了强大的生命力。

收稿日期：２００６一１２一１９。国家自然科学基金（９０４１２０１４）资助。倪庆剑，博士生，主研领域：群智能方法，机器学习。

可以在蚁穴和食物源之间找到一条最短路径，蚁群算法正是通过模拟真实蚁群的这一特征工作的。

１．１真实蚁群的觅食机理

蚂蚁是一种社会性昆虫，蚂蚁之间可以相互协作完成复杂的任务。单个蚂蚁的行为较为简单，但是由简单个体所组成的蚂蚁群体却表现出了极为复杂的行为。真实蚁群在觅食时能够在蚁穴和食物之间找到一条最短路径忙ｏ，并且在环境变化时，比如出现新的障碍物时，蚁群可以相互协作找到一条新的最短路径。

蚁群在觅食路径上释放信息素，单个蚂蚁通过感知路径上的信息素强度按概率选择下一步的行进方向，而蚂蚁之间则通过感知和释放信息素完成了间接的信息传递。当觅食路径上有了新的障碍物时，信息素轨迹暂时被隔断，此时蚂蚁随机地选择下一步的行进方向，而恰好选择了障碍物附近新的最短路径的那些蚂蚁将最先重构起连续的信息素轨迹，久而久之，选择短路

万方数据