ACO蚁群算法（附MATLAB源码）

优化算法之蚁群算法ACO：

蚁群算法（Ant colony optimization），简称ACO是一种用来寻找优化路径的概率型算法。它由Marco Dorigo在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该算法应用于其他组合优化问题，如旅行商问题、指派问题、车辆路由问题、图着色问题和网络路由问题等。

---

ACO特点：

优点：

1. 采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。
2. 每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。
3. 搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率。
4. 启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。

缺点：

1. 收敛速度慢。
2. 种群多样性与收敛速度的矛盾。

---

实现过程：

蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，开始时两条路上的蚂蚁数量差不多：当蚂蚁到达终点之后会立即返回，距离短的路上的蚂蚁往返一次时间短，重复频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多，会吸引更多蚂蚁过来，会留下更多信息素。而距离长的路正相反，因此越来越多的蚂蚁聚集到最短路径上来。

蚂蚁具有的智能行为得益于其简单行为规则，该规则让其具有多样性和正反馈。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环，是一种创新能力；正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智能行为涌现，如果多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态；如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。

---

主代码段：

%% 蚁群算法（ant colony optimization,ACO）



%清空变量



clear




close all




clc



 



[ graph ]  = createGraph();



 



figure 



subplot(1,3,1)



drawGraph( graph); 



%% 初始化参数



maxIter = 100;



antNo = 50;



tau0 = 10 * 1 / (   * mean( (:)  )  );  



tau = tau0 * ones(  , ); % Phromone matirx 



eta = 1./ ;  % 每个边的可取性



rho = 0.5; % 蒸发率



alpha = 1;  % Phromone指数参数



beta = 1;  % Desirability exponetial paramter



%% 循环



bestFitness = inf;



bestTour = [];




for t = 1 : maxIter



    % Create Ants 



    colony = [];



    colony = createColony( graph, colony , antNo, tau, eta, alpha,  beta);



    % Calculate the fitness values of all ants 



    for i = 1 : antNo 

出图：