蚁群算法在MATLAB中的实现

中图分类号：TP301文献标识码：A文章编号：1009－2552（2011）06－0115－04

蚁群算法在MATLAB中的实现

杜利峰，牛永洁

（延安大学计算中心，延安716000）

要：蚁群算法是近年来兴起的一种新型仿生优化算法，具有其他进化算法不可比拟的优势。以旅行商问题为例，首先描述了蚁群算法的工作原理，然后给出了该算法在MATLAB中实现的摘

详细步骤，最后分别以17，21，24，48，51，70为城市规模进行了算法验证，给出了算法运行的最优结果、最差结果、平均结果及运行时间与结果图。算法的实现为在其他领域中的应用和进一步的改进提供了基础，同时也弥补了其他资料中很少涉及实现应用的不足。关键词：旅行商问题；蚁群算法；信息素；路径；实现

ImplementationofantcolonyalgorithminMATLAB

DULi-feng，NIUYong-jie

（ComputingCenter，Yan’anUniversity，Yan’an716000，China）

Abstract：Antcolonyalgorithmistheriseinrecentyears，itwithunparalleledadvantagewhichotherevolutionaryalgorithmswithout．Thetravelingsalesmanproblemasanexample，theworkingprincipleofantcolonyalgorithmwasdescribed，theimplementationofthedetailedstepsinMATLABwaslisted，finallythealgorithmwasverifiedbycitydimensionsof17，21，24，48，51，70，theoptimal，worst，averageresultandaveragerunningtimeandfigureoftheseresultswerelisted．Algorithmisimplementedasinotherareasoftheapplicationandprovidesabasisforfurtherimprovements，aswellasotherinformationtomakeupforthedeficienciesarerarelyinvolvedinimplementation．

Keywords：travelingsalesmanproblem；antcolonyoptimization；pheromone；path；implementation

0引言

细阐述了蚁群算法在MATLAB中的实现过程。

ACO）是蚁群优化算法（antcolonyoptimization，

意大利学者Dorigo等人在20世纪90年代通过模拟

［1］

蚁群觅食行为而提出的一种新型进化算法。该算法是继神经网络、遗传算法、模拟退火算法、粒子

免疫算法等仿生搜索算法以后的又一种应群算法、

用于组合优化问题的启发式搜索算法。由于蚁群算

法采用分布式并行计算机制，具有较强的鲁棒性，容易与其它算法结合等优点，一经提出，立即受到各个

展开了对其的研究。目前蚁群算领域学者的重视，

法已经被广泛的应用于求解旅行商问题（traveling

salesmanproblem，TSP）［2］、定量构效方法（QSAR）类

［7］

［3］

1问题描述与算法思想

旅行商问题又被称为旅行推销员问题、货郎担

问题。它是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。旅行商问题已经被证明是一个NP难问题，具有O（n！）的时间复杂度，使用传统的算法较难解决。

在蚂蚁寻找食物的过程中，总能找到一条从蚁穴到距离很远的食物之间的最短路径。每个蚂蚁事先并不知道食物在什么位置，只是在本身能够看得见的局部范围内搜索，在搜索过程中将以一定的概

收稿日期：2010－11－30

作者简介：杜利峰（1974－），女，本科，实验师，研究方向为数据挖

掘、智能算法。

、网络路径最优问题

［4］

、聚类

［5－6］

、分

等领域。但对蚁群算法的具体实现却较少有

文献提及，本文以TSP问题为解决问题的目标，详

—115—