10.3 蚁群算法概述（1）
蚁群算法由Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
10.3.1 基本原理
蚁群算法（ACO）是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称为信息素的物质，其在觅食过程中能够感知这种物质的强度，从而指导自己的行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。
某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的概率也就越高，由此构成了正反馈过程，从而逐渐逼近最优路径，找到最优路径。
蚂蚁觅食的运行轨迹模式如图10-12所示。蚂蚁以信息素作为媒介而间接进行信息交流，判断洞穴到食物地点的最佳路径。
图10-12 蚂蚁觅食的运行轨迹模式
当蚂蚁从食物地点走到洞穴，或者从洞穴走到食物地点时，都会在经过的路径上释放信息素，从而形成一条含有信息素的路径。蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。
人工蚂蚁的搜索主要包括以下3种智能行为。
● 蚂蚁利用信息素进行相互通信：蚂蚁在所选择的路径上会释放一种叫作信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。
● 蚂蚁的记忆行为：一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。
● 蚂蚁的集群活动：通过一只蚂蚁的运动很难到达食物地点，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素也就越多，导致信息素浓度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素浓度；而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。
10.3.2 程序设计
蚁群算法不仅利用了正反馈原理，在一定程度上可以加快进化过程,而且是一种本质并行的算法，个体之间不断进行信息交流和传递，有利于发现较好解。
根据上一节对蚁群算法的介绍，编写蚁群算法MATLAB源程序：
clear all %%%%%% 初始化 %%%%%% Ant = 300; % 妈蚁数量 Times = 80; % 蚂蚁移动次数 Rou = 0.9; % 信息素挥发系数 P0 = 0.2; % 转移概率常数 Lower_1 = -1; % 设置搜索范围 Upper_1 = 1; Lower_2 = -1; Upper_2 = 1; for i = 1 : Ant % 随机设置蚂蚁的初始位置 X(i, 1) = (Lower_1 + (Upper_1 - Lower_1) * rand); X(i, 2) = (Lower_2 + (Upper_2 - Lower_2) * rand); Tau(i) = F(X(i, 1), X(i, 2)); end step = 0.05; f = '-(x .^ 4 + 3 * y .^ 4 - 0.2 * cos(3 * pi * x) - 0.4 * cos(4 * pi * y) + 0.6)'; [x, y] = meshgrid(Lower_1 : step : Upper_1, Lower_2 : step : Upper_2); z = eval(f); figure(1); subplot(1, 2, 1); mesh(x, y, z); hold on; plot3(X(:, 1), X(:, 2), Tau, 'k*') hold on; text(0.1, 0.8, -0.1, '蚂蚁的初始分布位置'); xlabel ('x'); ylabel ('y'); zlabel('f(x,y)'); for T = 1 : Times lamda = 1 / T; [Tau_Best(T), BestIndex] = max(Tau); for i = 1 : Ant P(T, i) = (Tau(BestIndex) - Tau(i)) / Tau(BestIndex); % 计算状态转移概率 end for i = 1 : Ant if P(T, i) < P0 % 局部搜索 temp1 = X(i, 1) + (2 * rand - 1) * lamda; temp2 = X(i, 2) + (2 * rand - 1) * lamda; else % 全局搜索 temp1 = X(i, 1) + (Upper_1 - Lower_1) * (rand - 0.5); temp2 = X(i, 2) + (Upper_2 - Lower_2) * (rand - 0.5); end %越界处理 if temp1 < Lower_1 temp1 = Lower_1; end if temp1 > Upper_1 temp1 = Upper_1; end if temp2 < Lower_2 temp2 = Lower_2; end if temp2 > Upper_2 temp2 = Upper_2; end %%% if F(temp1, temp2) > F(X(i, 1), X(i, 2)) % 判断蚂蚁是否移动 X(i, 1) = temp1; X(i, 2) = temp2; end end for i = 1 : Ant % 更新信息量 Tau(i) = (1 - Rou) * Tau(i) + F(X(i, 1), X(i, 2)); end end subplot(1, 2, 2); mesh(x, y, z); hold on; x = X(:, 1); y = X(:, 2); plot3(x, y, eval(f), 'k*'); hold on; text(0.1, 0.8, -0.1, '蚂蚁的最终分布位置'); xlabel('x'); ylabel('y'); zlabel('f(x,y)'); [max_value, max_index] = max(Tau); maxX = X(max_index, 1); maxY = X(max_index, 2); maxValue = F(X(max_index, 1), X(max_index, 2));
设定目标函数如下：
function [F] = F(x1, x2) F = -(x1 .^ 4 + 3 * x2 .^ 4 - 0.2 * cos(3 * pi * x1) - 0.4 * cos(4 * pi * x2) + 0.6);
运行程序得到蚂蚁算法运行前后蚂蚁的位置变化示意图，如图10-13所示。
图10-13 蚂蚁算法运行前后蚂蚁的位置变化示意图
