蚁群算法

蚁群算法目录1蚁群算法基本思想........................................................................................................................................................11.1蚁群算法简介.........................................................................................................................................................11.2蚁群行为分析.........................................................................................................................................................11.3蚁群算法解决优化问题的基本思想.....................................................................................................................21.4蚁群算法的特点.....................................................................................................................................................22蚁群算法解决TSP问题...............................................................................................................................................32.1关于TSP.................................................................................................................................................................32.2蚁群算法解决TSP问题基本原理........................................................................................................................32.3蚁群算法解决TSP问题基本步骤........................................................................................................................53案例................................................................................................................................................................................63.1问题描述.................................................................................................................................................................63.2解题思路及步骤.....................................................................................................................................................63.3MATLB程序实现...................................................................................................................................................73.1.1清空环境.........................................................................................................................................................73.2.2导入数据.........................................................................................................................................................73.3.3计算城市间相互距离.....................................................................................................................................73.3.4初始化参数.....................................................................................................................................................73.3.5迭代寻找最佳路径.........................................................................................................................................73.3.6结果显示.........................................................................................................................................................73.3.7绘图.................................................................................................................................................................711蚁群算法基本思想1.1蚁群算法简介蚁群算法（antcolonyalgrothrim，ACA）是由意大利学者多里戈（DorigoM）、马聂佐（ManiezzoV）等人于20世纪90初从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来的一种新型的模拟进化算法。该算法用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些系统优化中的困难问题，其算法的基本思想是模仿蚂蚁依赖信息素，通过蚂蚁间正反馈的方法来引导每个蚂蚁的行动。蚁群算法能够被用于解决大多数优化问题或者能够转化为优化求解的问题，现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面。蚁群算法是群智能理论研究领域的一种主要算法。1.2蚁群行为分析EABCDFd=3d=2m=20t=0EABCDFd=3d=2m=10m=10t=121.3蚁群算法解决优化问题的基本思想用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息量较多，随着时间的推进，较短路径上积累的信息浓度逐渐增高，选择该路径的蚂蚁个数愈来愈多。最后，整个蚂蚁会在正反馈的作用下集中到最佳路径上，此时对应的便的待优化问题的最优解。1.4蚁群算法的特点（1）采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解；（2）每个个体可能通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的EABCDFd=3d=2m=10t=7m=10EABCDFd=3d=2m=10t=9m=10EABCDFd=3d=2m=20T8m=20蚂蚁释放的信息素与路径长度成反比路径上信息素浓度越大，路径被选概率越大3实时变化，个体间通过环境进行间接通讯；（3）搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率；（4）启发式的概率搜索方式不容易陷入局部最优，易于寻找到最优解。2蚁群算法解决TSP问题2.1关于TSPG=(N,E)，N={1,2,3,…,n}，E={(i,j)|i,j∈N}城市之间的距离nnijd)(目标函数nliilldwf11)(，其中),,,(21niiiw为城市1,2,3,..n的一个排列，11iin。2.2蚁群算法解决TSP问题基本原理1．初始假设蚂蚁群体中蚂蚁数量为m；城市个数为n；城市i与城市j之间的距离为）njidij,...3,2,1,(；t时刻城市i与城市j连接路径上的信息浓度为)(tij。初始时刻，各城市间连接路径上的信息浓度相同，可设为0)0(ij。2.转移概率计算t时刻蚂蚁k从城市i转移到城市j的概率为)(tPkij，其计算公式为kkallowsisisijijKijallowsallowstttPk0][)]([][)]([)(，，其中：4)(tij为启发函数，ijijdt/1)(，表示蚂蚁从城市i转移到城市j的期望程度；）（mkallowk,...,3,2,1为蚂蚁k待访问城市的集合，开始时，kallow中有(n-1)个元素，即包括除了蚂蚁k出发城市的其他所有城市，随意时间的推进，kallow中元素不断减少，直到为空，即表示所有的城市均访问完毕；为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市。3.信息素更新信息素更新包括信息素的挥发和信息素增强（释放信息素）。蚂蚁释放信息素的三种模型：（1）antcyclesystem模型,0i/其他访问城市只蚂蚁从城市第，jkLQkkij其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；kL为第k只蚂蚁经过路径的长度。（2）antquanlitysystem模型,0i/其他访问城市只蚂蚁从城市第，jkdQijkij（3）antdensitysystem模型,0i其他访问城市只蚂蚁从城市第，jkQkij一般用antcyclesystem模型计算释放的信息浓度，即蚂蚁经过的路径越短，释放的信息素浓度越高。信息素挥发（evaporation）过程是信息素痕迹的浓度