万字长文带你了解蚁群算法及求解复杂约束问题【源码实现】 |
您所在的位置：网站首页 › 蚁群算法求解tsp问题python › 万字长文带你了解蚁群算法及求解复杂约束问题【源码实现】 |
万字长文带你了解蚁群算法及求解复杂约束问题【源码实现】
|
蚁群算法
蚁群算法是一种源于大自然生物世界的新的仿生进化算法，由意大利学者M. Dorigo, V. Maniezzo和A. Colorni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法"。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选择。其根本原因是蚂蚁在寻找食物时,能在其走过的路径.上释放一种特殊的分 泌物一信息素 (也称外激素)，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来蚂蚁选择该路径的概率也就越高，从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。 蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。 蚂蚁在运动过程中，能够在它所经过的路径.上留下信息素进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此来指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 真实蚁群觅食过程为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在自然界中，蚁群在寻找食物时，它们总能找到一- 条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。蚁群算法的信息交互主要是通过信息素来完成的。蚂蚁在运动过程中，能够感知这种物质的存在和强度。初始阶段，环境中没有信息素的遗留，蚂蚁寻找事物完全是随机选择路径，随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响，其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径。同时，信息素是一种挥发性化学物，会随着时间的推移而慢慢地消逝。如果每只蚂蚁在单位距离留下的信息素相同，那对于较短路径上残留的信息素浓度就相对较高，这被后来的蚂蚁选择的概率就大,从而导致这条短路径上走的蚂蚁就越多。而经过的蚂蚁越多，.该路径.上残留的信息素就将更多，这样使得整个蚂蚁的集体行为构成了信息素的正反馈过程，最终整个蚁群会找出最优路径。 若蚂蚁从A点出发，速度相同，食物在D点，则它可能随机选择路线ABD 或ACD。假设初始时每条路线分配一只蚂蚁， 每个时间单位行走一步。 图所示为经过8个时间单位时的情形:走路线ABD的蚂蚁到达终点;而走路线ACD的蚂蚁刚好走到C点，为一半路程。 图2表示从开始算起，经过16个时间单位时的情形:走路线ABD的蚂蚁 到达终点后得到食物又返回了起点A，而走路线ACD的蚂蚁刚好走到D点。  假设蚂蚁每经过一-处所留下的信息素为1个单位，则经过32个时间单位后， 所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物。此时ABD的路线往返了2趟，每一处的信息素为4个单位:而ACD的路线往返了一趟，每一处 的信息素为2个单位，其比值为2: 1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁(共2只)，而ACD路线上仍然为一只蚂蚁。再经过32个时间单位后，两条线路.上的信息素单位积累为12和4，比值为3: 1。若按以上规则继续,蚁群在ABD路线上再增派-一只蚂蚁(共3只),而ACD 路线.上仍然为一只蚂蚁。再经过32个时间单位后，两条线路上的信息素单位积累为24和6，比值为4: 1。若继续进行，则按信息素的指导，最终所有的蚂蚁都会放弃ACD路线，而选择ABD路线。这也就是前面所提到的正反馈效应。信息素的更新方式有两种: 一是挥发，也就是所有路径上的信息素以一定的比率减少，模拟自然蚁群的信息素随时间挥发的过程:二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。
蚁群算法流程
以TSP问题为例 
我自己画的下面算例的流程图 求函数f(x, y)=20(x^2- y^2) -(1-y)^2 -3(1 +y)^2+ 0.3的最小值，其中x的取值范围为[-5，5], y的取值范围为[-5, 5]。这是一个有多个局部极值的函数. matlab版代码 %%%%%%%%%%%%%%%%%%%%蚁群算法求函数极值%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有变量 close all; %清图 clc; %清屏 m=20; %蚂蚁个数 G_max=200; %最大迭代次数 Rho=0.9; %信息素蒸发系数 P0=0.2; %转移概率常数 XMAX= 5; %搜索变量x最大值 XMIN= -5; %搜索变量x最小值 YMAX= 5; %搜索变量y最大值 YMIN= -5; %搜索变量y最小值 %%%%%%%%%%%%%%%%%随机设置蚂蚁初始位置%%%%%%%%%%%%%%%%%%%%%% for i=1:m X(i,1)=(XMIN+(XMAX-XMIN)*rand); X(i,2)=(YMIN+(YMAX-YMIN)*rand); Tau(i)=func(X(i,1),X(i,2)); end step=0.1; %局部搜索步长 for NC=1:G_max lamda=1/NC; [Tau_best,BestIndex]=min(Tau); %%%%%%%%%%%%%%%%%%计算状态转移概率%%%%%%%%%%%%%%%%%%%% for i=1:m P(NC,i)=(Tau(BestIndex)-Tau(i))/Tau(BestIndex); end %%%%%%%%%%%%%%%%%%%%%%位置更新%%%%%%%%%%%%%%%%%%%%%%%% for i=1:m %%%%%%%%%%%%%%%%%局部搜索%%%%%%%%%%%%%%%%%%%%%% if P(NC,i) |
还有些相关术语，自己见代码吧。这个代码简单。这个代码都看不懂，我劝你放弃挣扎，躺平。
【本文地址】
今日新闻 |
推荐新闻 |