浅谈蚁群算法.pdf

蚁群算法报告学院:专业:学号:姓名:目录第一部分：蚁群算法原理介绍 (3)1.1蚁群算法的提出 (3)1.2蚁群算法的原理的生物学解释 (3)1.3蚁群算法的数学模型 (3)1.4蚁群算法实现步骤 (5)第二部分：蚁群算法实例--集装箱码头船舶调度模型 (6)2.1集装箱码头船舶调度流程图 (6)2.2算例与MATLAB编程的实现 (6)2.2.1算法实例 (6)2.2.2 Matlab编程 (8)第三章：MATLAB 优化设计工具箱简介 (14)3.1M ATLAB优化工具箱 (14)3.1.1优化工具箱功能： (15)3.2M ATLAB 优化设计工具箱中的函数 (15)3.2.2 方程求解函数 (15)3.2.3最小二乘（曲线拟合）函数 (16)3.2.4 使用函数 (16)3.2.5 大型方法的演示函数 (16)3.2.6 中型方法的延时函数 (16)3.4优化函数简介 (17)3.4.1优化工具箱的常用函数 (17)3.4.2 函数调用格式 (17)3.5模型输入时所需注意的问题 (19)第一部分：蚁群算法原理介绍1.1蚁群算法的提出蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现于人类的日常生活环境中。

受到自然界中真实蚁群集体行为的启发，意大利学者M.Dorig 。

于20世纪90年代初，在他的博士论文中首次系统地提出了一种基于蚂蚁种群的新型优化算法—蚁群算法}28}(Ant Colony Algorithm, ACA)，并成功地用于求解旅行商问题，自1996年之后的五年时间里，蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域得到了迅速拓宽。

1.2蚁群算法的原理的生物学解释据观察和研究发现，蚂蚁倾向于朝着信息激素强度高的方向移动。

因此蚂蚁的群体行为便表现出了一种信息激素的正反馈现象。

当某条路径上经过的蚂蚁越多，该路径上存留的信息激素也就越多，以后就会有更多的蚂蚁选择它。

蚁群算法（ACO）解决TSP问题⼀、蚁群算法1.基本原理蚁群算法（Ant Colony Optimization，ACO）是⼀种基于种群寻优的启发式搜索算法，有意⼤利学者M.Dorigo等⼈于1991年⾸先提出。

该算法受到⾃然界真实蚁群集体在觅⾷过程中⾏为的启发，利⽤真实蚁群通过个体间的信息传递、搜索从蚁⽳到⾷物间的最短路径等集体寻优特征，来解决⼀些离散系统优化中的困难问题。

经过观察发现，蚂蚁在寻找⾷物的过程中，会在它所经过的路径上留下⼀种被称为信息素的化学物质，信息素能够沉积在路径上，并且随着时间逐步挥发。

在蚂蚁的觅⾷过程中，同⼀蚁群中的其他蚂蚁能够感知到这种物质的存在及其强度，后续的蚂蚁会根据信息素浓度的⾼低来选择⾃⼰的⾏动⽅向，蚂蚁总会倾向于向信息素浓度⾼的⽅向⾏进，⽽蚂蚁在⾏进过程中留下的信息素⼜会对原有的信息素浓度予以加强，因此，经过蚂蚁越多的路径上的信息素浓度会越强，⽽后续的蚂蚁选择该路径的可能性就越⼤。

通常在单位时间内，越短的路径会被越多的蚂蚁所访问，该路径上的信息素强度也越来越强，因此，后续的蚂蚁选择该短路径的概率也就越⼤。

经过⼀段时间的搜索后，所有的蚂蚁都将选择这条最短的路径，也就是说，当蚁巢与⾷物之间存在多条路径时，整个蚁群能够通过搜索蚂蚁个体留下的信息素痕迹，寻找到蚁巢和⾷物之间的最短路径。

蚁群算法中，蚂蚁个体作为每⼀个优化问题的可⾏解。

⾸先随机⽣成初始种群，包括确定解的个数、信息素挥发系数、构造解的结构等。

然后构造蚁群算法所特有的信息素矩阵每只妈蚁执⾏蚂蚊移动算⼦后，对整个群体的蚂蚁做⼀评价，记录最优的蚂蚁。

之后算法根据信息素更新算⼦更新信息素矩阵，⾄此种群的⼀次选代过程完成。

整个蚂蚁群体执⾏⼀定次数的选代后退出循环、输出最优解。

2.术语介绍（1）蚂蚁个体。

每只蚂蚁称为⼀个单独的个体，在算法中作为⼀个问题的解。

（2）蚂蚁群体。

⼀定数量的蚂蚁个体组合在⼀起构成⼀个群体，蚂蚁是群体的基本单位。

蚁群算法理论：生物学家发现，蚁群在外出寻找食物时，总能合理运用最短的时间，找到蚁穴与食物最短的路径。

蚁群中的每一只蚂蚁都是一个单独的个体，蚁群算法理论：生物学家发现，蚁群在外出寻找食物时，总能合理运用最短的时间，找到蚁穴与食物最短的路径。

蚁群中的每一只蚂蚁都是一个单独的个体，他们在寻找食物时，能够在自己所走的线路上留下信息(一种化学成分的信息，可以帮助蚂蚁判断这条路走过了多少只蚂蚁)，如果有2条路，都能够从蚁穴到达食物源，当蚂蚁来到“十字路口”他们会判断这2条路那一条路走过的蚂蚁更多，然后选择自己认为的最短的路线。

在寻到食物的过程中每一只蚂蚁都在不断斧正自己路线是否是最短的。

蚁群算法理论运用到seo优化Maoseomao经常听说这样的一句话：“做seo就是比的资源，言外之意就是比的外链的质量和数量”。

那么我们如何把蚁群算法理论运用到seo外链获取上面呢?下面笔者做一个对比，大家就能明白如何利用蚁群算法理论了：蚁群：蚁群都有一个共同的目标-获得最近的食物。

Seo：获得更多，更好质量的外链。

蚁群：拥有几百万，甚至几千万的蚂蚁个体同时协作。

Seo：至少拥有5个以上的seo外链专员。

蚁群：能够在其路过的地方留下信息素。

Seo：5个seo外链专员可以有一个负责人，记录这5个seo外链专员的工作，并且时时刻刻做到相互沟通。

蚁群：食物与蚁穴比较长的路线慢慢会被抛弃掉。

Seo：外链效果查的方法慢慢被抛弃掉。

蚁群：食物与蚁穴最近的线路会被蚁群采用。

Seo：做外联效果好的方法慢慢被5个seo外链专员采用。

蚁群：最后在最短的时间，把最美味的食物运回蚁穴中。

Seo：最短的时间，比高出对手一倍的速度增加高质量的外链，获得关键词排名前10名。

总结：通过以上对比，我想大家应该知道这个蚁群算法理论该如何运用了。

网络推广在运用这个蚁群算法理论的过程中我们需要注意的几点：1.蚂蚁是一个群体，他们每一只蚂蚁的共同目标是：“寻找到食物与蚁穴最短的路线，更快的把食物运回蚁穴”;seo外链专员的共同目标：“寻找自己所做优化网站相关的更高质量的，更多的外链”。

一、引言蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。

它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。

蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。

寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。

若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。

最基本的蚁群算法见第二节。

目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。

本文将终点介绍随机蚁群算法。

二、基本蚁群算法（一）算法思想各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。

当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。

假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。

当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。

因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。

蚁群算法的基本思想如下图表示：图1 等概率选择图2 最优路径图3 最优比重（二）算法描述基本蚁群算法的算法简单描述如下：1．所有蚂蚁遇到障碍物时按照等概率选择路径，并留下信息素；2．随着时间的推移，较短路径的信息素浓度升高；3．蚂蚁再次遇到障碍物时，会选择信息素浓度高的路径；4．较短路径的信息素浓度继续升高，最终最优路径被选择出来。

蚁群优化算法的JA V A实现收藏蚁群算法简介蚁群算法是群智能算法的一种，所谓的群智能是一种由无智能或简单智能的个体通过任何形式的聚集协同而表现出智能行为，它为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础，比如常见的蚂蚁觅食，大雁南飞等行为。

蚁群算法是模拟自然界中蚂蚁觅食的一种随机搜索算法，由Dorigo等人于1991年在第一届欧洲人工生命会议上提出[1] 。

蚁群算法的生物原理通过观察发现，蚁群在觅食的时候，总能找到一条从蚁巢到食物之间的一条最短的路径。

这个现象引起了生物学家的注意，根据研究，原来是蚂蚁在行进的过程中，会分泌一种化学物质——信息素，而蚂蚁在行进时，总是倾向于选择信息素浓度比较高的路线。

这样，在蚁巢和食物之间假如有多条路径，初始的时候，每条路径上都会有蚂蚁爬过，但是随着时间的推迟，单位时间内最短的那条路上爬过的蚂蚁数量会比较多，释放的信息素就相对来说比较多，那么以后蚂蚁选择的时候会大部分都选择信息素比较多的路径，从而会把最短路径找出来。

蚁群算法正是模拟这种蚁群觅食的原理，构造人工蚂蚁，用来求解许多组合优化问题。

有关蚁群算法的详细信息，可参考[2]——[5]。

蚁群算法的JA V A实现我个人认为利用JA V A编写一些计算密集型的算法不是一个好的选择。

本身一些算法是要要求高效率的，但是我感觉JA V A语言的性能不够，所以编写算法最好用c，其次也可以用c++。

当然，这仅是一家之言，欢迎拍砖。

此处使用JA V A的原因是为了演示算法的框架，给出一种思路，如果需要c++的参考，可以参考,如果需要c的代码，可以上http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html, 这个可以看作是ACO的官方网站了，里面的内容比较多。

算法说明算法以求解TSP问题为例，用来演示ACO的框架。

算法设定了两个类，一个是ACO，用来处理文件信息的读入，信息素的更新，路径的计算等；另一个是ant，即蚂蚁的信息。

§2.3蚁群算法§2.3.1 蚁群算法的思想蚁群算法是受生物界中蚂蚁觅食行为启发而来。

生物界中的蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能够随环境的变化而变化去搜索新路径，产生新选择，其机理在于蚂蚁在其走过的路径上释放一种信息素，信息素承载着路况信息，蚂蚁在行进过程中能够感知这种信息素的存在和其强度，并指导自己的行进方向，使蚂蚁倾向于向信息素强度高的方向爬行。

这无疑非常适合动态航迹规划问题。

蚁群算法最重要的特点就是创造性地使用了启发信息，即通过引入信息素播撒机制[14]，将之前搜索到的最优解用于指导后续的搜索。

在蚁群算法的众多改进算法中，对信息素播撒机制的改进是研究者最为关注的一点。

蚁群算法与其他搜索算法相结合，来改进蚁群算法是一条重要途径。

§2.3.2 蚁群算法模型一只蚂蚁的智力是很有限的，但很多蚂蚁之间通过一些信息激素进行协同作用，实现蚂蚁之间的信息交流，其效果往往令人惊讶。

下面将简单的介绍一下蚂蚁群是怎样通过信息素进行协同作用的，并如何最终找到从蚁穴到食物的最短路径。

在图2.6中，A为出发点（即蚁穴），B为食物源，从图上可见蚂蚁要获得食物有两条路可走，我们可以很容易的比较出路径A-C-B较路径A-D-B长，然而蚂蚁是不知道这一点的。

现在假设有两只蚂蚁1和2，在蚂蚁1和2向食物移动的方向上有两条路径可以选择，在初始条件下，两条路径上的信息素量都为零，因此两只蚂蚁选择两条路径的概率均为0.5，在这里，假设蚂蚁1选择了路径A-C-B，蚂蚁2选择了路径A-D-B，在此强调两只蚂蚁的行走速度是一样的。

很明显，选择短路径的蚂蚁2将先到达B点，当蚂蚁2要返回时，要选择信息素气味重的路径，由于此时蚂蚁1还在路上，故蚂蚁2选择了原路返回，当蚂蚁2到达A点时，假设的蚂蚁3出发，根据蚂蚁会选择信息素气味较重的路径这一原理，蚂蚁3选择路径A-D-B，因为此路径已经有两次蚂蚁通过的经历，如此由大量的蚂蚁组成的群体便表现出一种信息正反馈现象，即随着路径A-D-B上通过蚂蚁数量的增加，后来的蚂蚁选择此路径的概率就越大，而这正是两点之间的最短路径。