硕士基于tsp问题的蚁群算法优化及并行策略研究—-毕业论文设计.doc

SelectionParagraphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPointselectionParagraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesTSelectionParbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbagraphFoLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPointse11111111111111111111111111111111lectionParagraphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPoctionParagraphFormatLineSpaci2222222222222222222222ngLinesToPoints2SelectionParagraphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPointselectionParagraphFccccccccccccccccccccccccccccccccccccccccccccccccccccccccormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPoctionParagraSelec

学校代码：10491 研究生学号：12003566

中国地质大学
硕士学位论文

基于TSP问题的蚁群
算法优化及并行策略研究

硕 士 生：张 礼
学科专业：计算机应用技术
指导教师：罗忠文 副教授

二○○六年五月

A Dissertation Submitted to China University
of Geosciences for the Degree of Master of Engineering

The Research on Optimization and
Parallelization Strategies of Ant Colony Algorithm
for Solving Traveling Salesman Problem

Master Candidate：Zhang Li
Major：Computer Application Technology
Supervisor：Associate Prof. Luo Zhongwen

China University of Geosciences
Wuhan 430074 P. R. China

研究生学位论文原创性声明

我以诚信声明：本人所呈交的硕士学位论文是在罗忠文副教授的指导下，开展研究工作所取得的研究成果。文中关于TSP问题的蚁群算法新的优化策略是在罗忠文老师的指导下独立完成；算法运行数据结果、为确定各个关键参数的分析及其设定数据系本人研究和测试所得；文中蚁群算法的并行策略及算法的展望系本人独立完成，不包含他人研究成果。所引用他人之思路、方法、观点、认识均已在参考文献中明确标注，所引用他人之数据、图件、资料均已征得所有者同意，并且也有明确标注，对论文的完成提供过帮助的有关人员也已在文中说明并致以谢意。

学位论文作者（签字）：
签字日期： 年 月 日

作者简介

张礼，男，1979年9月出生，2000年7月本科毕业于上海交通大学热能工程及其自动化专业，2003年9月进入中国地质大学（武汉）攻读计算机应用技术专业硕士学位。
在读研期间，主要学习了算法设计与分析、高级计算机体系结构、组合数学、Visual C++、科学社会主义、自然辩证法、英语（含专业英语）等十几门课程，总学分34.5分，平均分为84.7分。
在攻读硕士学位期间，曾在武汉中地数码科技股份有限公司（教育部GIS工程中心）进行实习，参与了多个软件项目的开发，主要从事国土资源部门基于MAPGIS平台的应用软件的研发，参与开发的项目有：湖南省衡阳市国土资源局国土资源电子政务系统、基于MAPGIS并内嵌RedOffice的公文流转开发等。
2005年5月份，开始进入蚁群算法领域，并研究算法的优化及并行策略。
在校期间，已发表论文十余篇，其中核心期刊一篇；以第一作者身份发表的论文主要有：（一部分公开期刊从略）
1、基于MAPGIS工作流及RedOffice的公文流转开发. 商场现代化（核心期刊）. 2005年9月号，第20期（总第443期）.
2、电子政务发展现状及策略分析. 中国学术论坛. 2005年第1期.
3、蚁群算法的一种优化策略. 知识与创新. 2005年第11期.
4、Oracle应用系统性能优化. 学位（理论版）. 2005年第2期.
5、用SVG技术实现基于Web的GIS. 知识与创新. 2005年第11期.
6、GML、VML和SVG的比较. 经营与管理（增刊）. 2005年增刊第082号.
7、下一代网络NGN标准概述. 知识与创新. 2006年第2期.

基于TSP问题的蚁群算法优化及并行策略研究

硕士生：张礼 导师：罗忠文 副教授

摘 要

许多实际工程问题可以抽象为相应的组合优化问题，TSP问题是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法可以求解出TSP问题的最优解；但是对现有的计算机来说，让它在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的算法应运而生了，本文所描述的蚁群算法（AC）也在其中。
目前已出现了很多的启发式算法，而蚁群算法作为一种新型的启发式算法，已成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度，同时按照路径上的信息素浓度来选择下一步的路径：好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径；最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。
首先，本文简要介绍了几种启发式算法并引出蚁群算法，并对蚁群算法基本原理、几种算法模型和相应的数学公式作了详细阐述，同时对前人的研究结果进行了引用；此外针对蚁群算法的缺陷，还描述了前人对算法所作的一些典型的优化：如蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS、具有变异特征的蚁群算法等。
然后，文章对蚁群算法中的关键参数的设置进行了深入的研究。对参数α、β、ρ、m的作用作了理论上的研究，对它们的最优化配置进行了分析；同时针对以往参数设定的不便，提出了一种全新的、比较适当的参数设置方案：通过将蚁群算法的参数设置问题描述成均匀设计中多因素多水平的试验设计，它能用较少的试验很快设置出参数值，并可使蚁群算法获得较优的运行性能。
接着，本文提出了建立在蚁群系统算法ACS基础上的一种新的优化策略：采用新方案进行关键参数设置，以克服以往的参数设置困难、不准确的缺点；通过引入遗传算法中用到的杂交算子，使前面蚂蚁所留信息素尽量少对后面的蚂蚁产生误导，增强算法的搜索能力；通过全局最小信息素浓度的设置，来扩宽算法的搜索空间；采用更高效的信息素更新和路径选择机制，以加快算法的收敛速度，使其更容易收敛到全局最优解。并对该优化策略进行了初步实验，证明了其有效性和可行性，也为蚁群算法的优化提供了一个新途径。
在此之后，文章对蚁群算法的并行策略进行了初步的探讨，深入分析了两种不同的并行策略：同步策略和部分异步策略；另外，还提出了一种新的模式学习并行蚁群算法，并对它进行了具体的介绍。
最后，本文对改进后的蚁群算法、以及蚁群算法的并行策略进行了总结性的阐述；同时对蚁群算法的进一步优化提出了自己的设想：引入种群入侵算子（也叫外变异算子）、权函数等；并对蚁群算法的研究前景进行了展望。

关键词：TSP问题；蚁群算法；关键参数设置；优化策略；并行策略

The Research on Optimization and
Parallelization Strategies of Ant Colony Algorithm
for Solving Traveling Salesman Problem

Master Candidate：Zhang Li Supervisor：Prof. Luo Zhongwen

Abstract

Many actual engineering problems can be regarded as combination optimization problems，and TSP（Traveling Salesman Problem） is a typical combination optimization problem，it has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking，the enumeration can get the best answer of TSP；but to all computers nowadays，it is hardly to obtain the best answer in such huge researching space by using common enumeration. So all kinds of algorithms emerged because of demand，the ant colony algorithm（AC） described in this paper is one of them.
Presently many heuristic algorithms appeared，and AC algorithm is a class of heuristic algorithms that have been successfully applied to solving TSP. Ants reinforce pheromone intensities of better paths by excreting chemical substance（namely pheromone），synchronously they select next paths according to pheromone intensities：more ants will select better paths，and more pheromones will be laid over better paths；at last all ants will focus on the best path. This is a form of behavior called autocatalytic behavior，it is the key to the success of AC algorithm.
Firstly，this paper introduces briefly several heuristic algorithms and educes AC algorithm，expounds fundamental、several models、corresponding mathematic formula，synchronously refers to other investigation conclusion；also describes some typical optimizations aiming at shortcomings of AC algorithm：for example，ant colony system algorithm（ACS，namely ACO）、max-min ant system algorithm（MMAS）、ant colony system algorithm with mutation features etc.
Then，the paper investigates the settings of important parameters about AC algorithm. Study theoretically the functions of parameters（viz. α、β、ρ、m），analyses their optimum settings；at the same time，it presents a kind of scheme：uniform design method is used to convert the problem of parameter establishment into experimental design of multi-factor and multi-level，it can obtain conveniently all parameters，and shows good performance effectiveness.
Afterwards，a new optimization strategy based on ACS algorithm is provided：a new method is used to set important parameters for overcoming former defects；a crossover operator used in genetic algorithm is contained in the optimization strategy for increasing researching ability of algorithm；setting the minimal pheromone intensity for expanding researching space；adopting new pheromone updating and path selecting methods for quickening constringency speed of algorithm. In addition，we demonstrate the feasibility and efficiency of new optimization strategy by means of experimental study，and also provide a new approach of optimization about AC algorithm.
Whereafter，the parallelization strategies of AC algorithm are discussed，and analyze two kinds of parallelization strategies：synchronous parallel algorithm and asynchronous parallel algorithm；moreover，recommend concretely a new algorithm：parallel model-learning AC algorithm.
Finally，this paper summarizes the improvements and parallelization strategies of AC algorithm；and provides synchronously my own imagination about the farther optimization of AC algorithm：introducing reproduction in-break operator（namely external mutation operator）；furthermore，indicates the investigation future of AC algorithm.

Key Words：Traveling Salesman Problem；Ant Colony algorithm；Settings of important parameters；Optimization strategies；Parallelization strategies

目 录

第一章 绪 论 1
§1.1 引 言 1
§1.2 本文的研究内容 1
1.2.1 蚁群算法的基础性理论研究 2
1.2.2 蚁群算法的优化策略研究 2
1.2.3 蚁群算法的并行策略研究 2
§1.3 本文的创新之处 2
§1.4 本文的组织 3
第二章 蚁群算法基础理论 4

§2.1 TSP问题简介及其解法 4
2.1.1 TSP问题的定义及传统解法 4
2.1.2 现代启发式算法 4
§2.2 蚁群算法概述 5
2.2.1 群体智能简介 5
2.2.2 蚁群算法的定义 5
2.2.3 蚁群算法的基本原理 6
2.2.4 算法的数学模型表述 7
2.2.5 蚁群算法的伪码表述 9
2.2.6 蚁群算法的实验结果 10
§2.3 蚁群算法的特征及优缺点 11
2.3.1 算法特征 11
2.3.2 算法的优点 11
2.3.3 算法的缺陷 11
§2.4 蚁群算法已有的改进及优化策略 12
2.4.1 蚁群系统算法（ACS） 12
2.4.2 最大最小蚁群系统算法（MMAS） 13
2.4.3 具有变异特征的蚁群算法 13
第三章 蚁群算法中关键参数的设置 15
§3.1 各个关键参数的介绍及设置 15
3.1.1 启发式因子 15
3.1.2 信息素残留度ρ 17
3.1.3 蚂蚁总个数m 18
§3.2 基于均匀设计的关键参数设置 19
3.2.1 传统的参数设置方法的缺陷 19
3.2.2 基于均匀设计的关键参数设置 19
第四章 蚁群算法优化的一种新策略 23
§4.1 蚁群算法优化的理论基础 23
4.1.1 路径选择机制 23

4.1.2 信息素更新机制 23
§4.2 蚁群算法优化的新策略 24
4.2.1 算法优化的初步设想 24
4.2.2 优化的途径（在已有改进型算法ACS的基础上） 24
4.2.3 优化后的算法描述 27
4.2.4 实验及结果分析 29
第五章 蚁群算法的并行策略 31
§5.1 蚁群算法的两种并行策略 31
5.1.1 同步的并行策略 31
5.1.2 部分异步的并行策略 32
5.1.3 两种并行策略的比较 33
§5.2 蚁群算法并行的新策略 35
5.2.1 算法的基本思想 35
5.2.2 模式的获取 36
5.2.3 模式学习并行蚁群算法描述 36
第六章 结论与展望 38
§6.1 结 论 38
6.1.1 蚁群算法优化策略 38
6.1.2 蚁群算法并行策略 38
§6.2 展 望 39
6.2.1 对优化策略的展望 39
6.2.2 对并行策略的展望 39
致 谢 40
参考文献 41

SelectionParagraphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPointselectionParagraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesTSelectionParbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbagraphFoLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPointse11111111111111111111111111111111lectionParagraphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPoctionParagraphFormatLineSpaci2222222222222222222222ngLinesToPoints2SelectionParagraphFormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPointselectionParagraphFccccccccccccccccccccccccccccccccccccccccccccccccccccccccormatLineSpacingLinesToPointsSelectionParagraphFormatLineSpacingLinesToPoctionParagraSelec

2006.5 中国地质大学硕士学位论文 43

第一章 绪 论
§1.1 引 言
优化问题是人们在改造世界时经常会遇到的一类普遍问题，人们日常生活中对自己行为的指导实际上就是对某些利益的最大化过程：当我们考虑一个优化问题时，目标就是要得到最好的可能的解，即最优解。组合优化问题是最常见的优化问题之一，许多实际工程问题可以抽象为相应的组合优化问题，如：集成电路的综合布线、电信网络路由、网络导航、交通网络中的最佳路径选择等问题。
TSP问题是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。传统解法对小搜索空间的TSP问题适用，而且有的算法获得精确解的性质也正是人们所期望的。一般说来，这些方法有：迪杰斯特拉（dijkstra）算法、弗诺伊德（Floyd）算法、其它的算法（如局部搜索的梯度法）等。
但传统算法仅能运用于小问题集，因为随着问题集增大，算法时间复杂度也会呈现指数级的增加，使我们不能在有效的时间内完成任务，所以它们并不具推广性。
于是许多求TSP问题近似解的新算法应运而生，启发式算法便是其中之一。而蚁群算法（AC）是由意大利学者Macro Dorigo等人在20世纪90年代提出来的[1]，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解TSP问题。
蚁群算法在解决TSP问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并且容易出现停滞。为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS等；这些改进在一定程度上提高了算法的有效性，但效果并不明显。如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。
另外，人们也注意到：改进后的蚁群算法在解决大型的TSP问题时，关键参数的设置和信息素的更新将花费很长的时间。而由于蚁群算法中蚂蚁的个体行为具有内在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。如何进行并行处理，亦即并行策略的研究，是目前蚁群算法研究的又一个热点。
§1.2 本文的研究内容
本文的研究内容可以概括为三部分，即：蚁群算法的基础性理论、蚁群算法的优化策略、蚁群算法的并行策略。而蚁群算法的优化策略研究这部分内容，又可以划分为两个子块，即：蚁群算法关键参数的设置和在ACS算法基础上所作的改进
1.2.1 蚁群算法的基础性理论研究
这部分内容主要是讨论几种启发式算法并深入蚁群算法领域，对它的基本原理、几种算法模型和相应的数学公式作具体了解，同时对前人的研究成果进行引用；此外针对蚁群算法的缺陷，还会研究前人对算法所作的一些典型的优化：如蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS、具有变异特征的蚁群算法等。
1.2.2 蚁群算法的优化策略研究
这是研究的第二部分内容，它又可以划分为两个子块，即：蚁群算法关键参数的设置和在ACS算法基础上所作的改进。
1.2.2.1 关键参数的设置
这一块内容属于优化策略研究的一部分，它对关键参数α、βρ、m的作用作理论上的探讨，对它们的最优化配置进行分析；同时针对以往参数设定的不便，尝试提出一种全新的、比较适当的参数设置方案，使蚁群算法获得较优的运行性能。
1.2.2.2 在ACS算法基础上所作的改进
这一子块属于优化策略研究的另一部分内容，也是优化策略研究的最核心、最重要的部分。它将提出建立在蚁群系统算法ACS基础上的一种新的优化策略，并通过对该优化策略进行初步实验来证明其有效性和可行性。
1.2.3 蚁群算法的并行策略研究
这部分内容将对蚁群算法的并行策略进行初步的探讨，深入分析两种不同的并行策略：同步策略和部分异步的策略；另外，还会提出一种新的并行策略（模式学习并行蚁群算法），并会对它进行具体的介绍。
§1.3 本文的创新之处
本文的创新之处主要在蚁群算法的优化策略研究这一部分。具体的说，可以分为两点：一是提出了一种对关键参数α、β、ρ等进行合理设置的方案；二是设计了一套基于ACS算法基础上的优化策略，它对原ACS算法的诸多方面进行了改进。这些创新也为蚁群算法的优化提供了一个新的途径。
另外，创新之处在蚁群算法的并行策略研究这部分也有体现，主要是在蚁群算法中引入了一种模式学习并行策略。
§1.4 本文的组织
本文共分为六章，其章节组织如下：
第一章为绪论，引出TSP问题和蚁群算法，并简要介绍本文的研究内容、创新之处及全文的组织；
第二章详细介绍蚁群算法的基础性理论及其相关的概念、术语，包括算法已有的、典型的优化策略分析；
第三章对算法参数α、β、ρ、m的作用及其设置进行了理论研究，并提出了相关的参数设置方案，以克服以往参数设置困难、不准确的缺点。
第四章对算法的优化策略进行了研究，描述了算法的一种新优化策略，它在ACS算法的基础上作了许多的改进，并对其实现过程中遇到的相关难点和重点进行了讨论，同时对该优化策略进行了实验来证明其有效性和可行性。
第五章主要讨论了蚁群算法两种不同的并行策略，并具体介绍了一种新的模式学习并行蚁群算法。
第六章对全文的研究内容及成果进行了总结，并提出了对进一步研究工作的设想与展望。

第二章 蚁群算法基础理论
§2.1 TSP问题简介及其解法
2.1.1 TSP问题的定义及传统解法
TSP问题的英文名为traveling salesman problem，中文译为货郎担问题，或旅行商问题。它的定义很简单：即一个货郎要走访n个城市，每个城市必须经过一次且只能经过一次，最后回到出发的城市就算完成了一次旅行，问如何能找到一条最短的路径。TSP问题是作为所有组合优化问题的范例而存在的，它已成为测试新算法的标准问题。
TSP问题又可分为对称的TSP问题和非对称的TSP问题（ATSP）两种，从A点到B点的距离与从B点到A点的距离相比较，若距离总相等则为对称的TSP问题，否则为非对称的TSP问题。如果它俩的数据结构用图来表示，则前者是一个无向图，后者是一个有向图；若用邻接矩阵来表示的话，则前者是一个对称阵，而后者是一个非对称阵。
TSP问题的传统解法可分为两类：一类为全局搜索法，另一类为局部搜索法。
全局搜索法可以方便地运用于小搜索空间的TSP问题，而且它所获得的是精确解，此类方法如：迪杰斯特拉（dijkstra）算法：求从某个节点到其余各节点的最短路径；弗诺伊德（Floyd）算法：求每对节点间的最短路径。
而局部搜索法，它在局部搜索中，由当前的解求得下一个的可能解（下一代解），并比较下一代解和当前解的关系，选取较好者取代当前解，从而反复迭代，它所获得的是局部最优解，此类方法如：梯度法和不动点法。梯度法计算函数的梯度或近似值，然后朝梯度方向进行搜索；不动点法先构造辅助函数，然后再进行迭代，从而发现不动点来获得最终的解。
由于算法时间复杂度的原因，全局搜索法不适于大搜索空间的TSP问题；而局部搜索法，它为避免陷入局部最优，扩大邻域的大小是必然的，但随着邻域增大，对于NP难度问题，算法的复杂性也会呈现出指数次方的增加。
综上所述，传统方法虽然有其可供学习借鉴的地方，但它不适用于大搜索空间的TSP问题，推广性较差，我们需要另外的新方法来克服传统方法的缺陷。
2.1.2 现代启发式算法
针对传统解法的缺点，具有较强鲁棒性的现代启发式算法出现了，它不仅适用于TSP问题，而且还可适用于许多其它的问题，这样的性质显然更适合实际问题处理，其推广性很强。
NP难度问题的时间复杂度是不能改变的，因此现代启发式方法把重点放在了避免局部优化上，比较典型的启发式算法有：模拟退火算法、禁忌算法、基于群体的算法等。
模拟退火算法（Simulated annealing）是一个典型的启发式算法，算法中有当前点Vc，根据该点评价其邻域中的某一点Vn，如果Vn较好，则用其代替Vc；否则会按照概率p来替换Vc。
其中：p = e-｜f(Vn)-f(Vc)｜/T （公式2-1）；
该概率公式由晶体结晶的物理过程得到，其与初始值无关，算法求得的解与初始解状态S（算法迭代的起点）无关。模拟退火算法具有渐近收敛性，已在理论上被证明是一种收敛于全局最优解的全局优化算法，而且具有并行性。
而禁忌算法，它在每次迭代中，也是由某当代点的邻域来得到下一代最优可能点；不同的是，该算法保存有一个禁忌表，在禁忌表中出现的点不允许出现在下一代点中，这样就可以避兔算法陷入局部最优。
基于群体（population）的算法是又一种很重要的启发式算法，该类算法属于概率算法，候选解作为群体中的个体被保存下来。例如：演化算法、粒子群算法以及下文即将介绍的蚁群算法都属于这类算法。
§2.2 蚁群算法概述
2.21 群体智能简介
在某群体中若存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为即称为群体智能（Swarm Intelligence）。
群体中的简单个体是指具有简单能力（如搬运、通信等）的个体，这种能力可以用某一简单的功能函数来表示；简单合作是指个体只能与其邻近的个体进行某种简单的协同动作（如几只蚂蚁共同搬动一个物体），或通过改变环境间接的与其它个体之间进行简单通信（如一只蚂蚁将信息素留在环境中，为其它蚂蚁提供了一种可选择路径的信息）。
群体智能是近年来人工智能研究的一个热点课题，它对于没有集中控制并且不提供全局模型的问题，提供了一种复杂的分布式解决方案。科学家们受社会性昆虫群体智能的启发，通过对其行为的模拟，已得出了一系列用于解决传统复杂问题的新方法，蚁群算法便是其中很具有代表性的一种。
2.2.2 蚁群算法的定义
20世纪90年代，意大利学者M.Dorigo等人在新型算法研究的过程中，通过模拟自然界蚂蚁的觅食过程：即通过信息素（pheromone）的相互交流从而找到由蚁巢至食物的最短路径，提出了一种基于信息正反馈原理的新型模拟进化算法——蚁群算法（Ant Colony algorithm）。
蚁群算法是继遗传算法、人工神经网络等算法之后的又一种启发式算法，它的基本原理借鉴了这样一个客观事实：蚂蚁由自组织的合作能力所产生的群体智能来寻找路径，它被认为是用于解决组合优化问题的又一种新方法。
2.2.3 蚁群算法的基本原理
蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地搜索新的最佳路径。蚂蚁是如何做到这一点的呢？
原来，单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物——信息素（Pheromone），而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多（当然，随着时间的推移会逐渐减弱后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程，其原理是一种正反馈机制。
这里我们可以用一个图来说明蚂蚁觅食的最短路径选择原理，如图2-1所示。

图2-1 蚁群觅食原理
如图2-1（a）所示，我们假设A点是食物，而E点是蚂蚁的巢穴，当A、E两点间没有任何障碍物阻挡时，蚂蚁不存在路径选择的问题，这种情况最简单：由于两点间直线距离最短，蚂蚁们搬运食物时，会以直线的形式往返爬行。
但在图2-1（b）中的情形有所变化，若某时刻忽然有一个障碍物出现在蚂蚁经过的路径中，原有的路径被切断，那么从A点到E点的蚂蚁就必须在B点决定应该往左还是往右走，而从E点到A点的蚂蚁也必须在D点决定选择走哪条路径；这种决定会受到各条路径上以往蚂蚁留下的信息素浓度（即残留信息素浓度）的影响。如果往右走的路径上的信息素浓度比较大，那么右边的路径被蚂蚁选中的可能性也就大一些；但是对障碍出现后第一个到达B点或D点的蚂蚁而言，因为没有信息素的影响，所以它们选择向左或者向右的可能性是一样的，（b）图所表示的正是此时的情况。
若以从A点到E点的蚂蚁为例进行说明（对于从E点到A点的蚂蚁而言，过程也基本是一样的），由于路径BCD比路径BHD要短，因此选择BCD路径的第一只蚂蚁要比选择BHD的第一只蚂蚁早到达D点；此时，从D点向B点看，路径DCB上的信息素浓度要比路径DHB上的信息素浓度大。因此从下一时刻开始，从E点经D点到A点的蚂蚁，它们选择DCB路径的可能性要比选择DHB路径的可能性大得多，从而使路径BCD（或DCB）上信息素浓度与路径BHD（或DHB）上信息素浓度的差变大；而信息素浓度差变大的结果是选择路径BCD（或DCB）的蚂蚁进一步增加，这又导致信息素浓度差进一步加大。
如图2-1（c）所示，随着时间的推移，几乎所有的蚂蚁都会选择路径BCD搬运食物，而我们同时也会发现：BCD路径也正是事实上的最短路径。
这种蚁群寻径的原理可简单理解为：对于单个的蚂蚁来说，它并没有要寻找到最短路径的主观上的故意；但对于整个蚁群系统来说，它们又