优化算法学习笔记——蚁群算法

DomDomm · 发表于 2022-4-16 13:48

这是学习笔记，学习素材来自网络、教材、论文等，这里给整合起来，形成自己的电子笔记，会标明出处。
Part1：来自：https://baijiahao.baidu.com/s?id=1718855574152266530&wfr=spider&for=pc
Day1

算法基本原理

   模拟蚂蚁群体觅食的蚁群算法成为一种主要的群智能算法。对于觅食的蚂蚁群体，可以在没有提示的情况下找到食物和巢穴之间的最短路径。并且能够根据和环境的变迁，自适应地找到新的最优路径。
根本原因是：蚂蚁在寻找食物的过程中，能在其走过的路径上释放一种特殊的物质----信息素，随着时间的推移，这种信息素会逐渐地挥发，而对于后来的蚂蚁，选择某条路径的概率与该路径上信息素的浓度成正比。当某一条路径上通过的蚂蚁越多的时候，这条路径上的信息素的浓度就会累积越大，后来的蚂蚁选择此路径的概率也就越大。路径上蚂蚁越多，导致信息素浓度越高，从而会吸引更多的蚂蚁，从而形成一种正反馈机制，通过这种机制，最终蚁群可以发现最短路径。
   在觅食的初始阶段，环境中没有信息素，所以蚂蚁选择哪条路径完全是随机的。之后选择路径就会受到信息素的影响。这里需要说明的时是，信息素是一种生物体内分泌的化学物质，会随着时间的推移而挥发，如果每只蚂蚁在单位距离上留下的信息素浓度相同，则对于越短的路径，信息素的残留浓度就会越高，这被后来的蚂蚁选择的概率也就越大。而经过的蚂蚁越多，由于群体中的正反馈机制，路径上信息素的浓度也就越大，最终会导致整个蚁群寻找到最短路径。

  举个例子：从A到B有三条路径可选，每条路径分配一只蚂蚁，记为1,2,3。三条路径的长度为：2*L(ADB)=L(ACB)，3*L(ADB)=L(AEB)。所有蚂蚁的行走速度相同。假设蚂蚁沿着ADB从A到B，需要4个单位时间；

      所以在t取不同值的时候：
      t=4：蚂蚁1到达B，蚂蚁2走了一半路程，蚂蚁3走了1/3路程。
      t=8：蚂蚁1返回A，蚂蚁2到达B，蚂蚁3走了2/3路程。
      ……
      t=48：蚂蚁1往返6趟，蚂蚁2往返3趟，蚂蚁3往返2趟。
      在不考虑信息素挥发的条件下，三条路径上信息素浓度之比：
      D(ADB):D(ACB):D(AEB)=6:3:2。
   按照蚁群寻找路径的正反馈机制：按照信息素的指导，蚁群在路径ADB上指派6只蚂蚁，在路径ACB上指派3只蚂蚁,在路径AEB上指派2只蚂蚁。若继续寻找，则按照正反馈机制，最终所有蚂蚁都会选择最短的路径ADB,而放弃其他两条路径。
数学模型的建立

   在对实际的蚁群进行建模的过程中，需要解决：蚁群中蚂蚁个体的建模问题，信息素的更新机制，以及整个蚁群的内部机制
   a. 信息素的更新机制：
   信息素的更新方式有两种，一种是挥发，也就是所有路径上的信息素以一定的比率减少。另一种是信息素的增强，给有蚂蚁走过的路径增加信息素。
   b. 蚂蚁个体的建模问题：
   虽然单个蚂蚁可以构造出问题的可行解，但是蚂蚁个体之间需要通过协作才能找出待优化问题的最优解或者次优解，而信息素就是蚂蚁之间进行互相协作的媒介。信息素的蒸发机制使得对过去的寻优历史有一定的遗忘度，避免使后来的蚂蚁在搜索中受到较差解的影响。
      TSP问题：在一张地图上有n个城市，一名推销员需要不重复的一次走过n个城市进行推销，求解他按照怎样的路径，才能使走过的距离最短。
      解法：假设城市i的坐标为： ${{c}_{i}}=({{x}_{i}},{{y}_{i}})，i=1,2,3\ldots n$   ，城市i和城市j之间的距离可表示成： ${{d}_{ij}}=\sqrt{{{({{x}_{i}}-{{x}_{j}})}^{2}}+{{({{y}_{i}}-{{y}_{j}})}^{2}}}$ 。为每只蚂蚁设置一个禁忌表（程序中Tabu矩阵，初始值置0），记录其走过的城市（防止重复走过城市），禁忌表中第一个位置是蚂蚁初始时刻所在的城市，当所有城市都加入禁忌表的时候，表示蚂蚁走完了所有的城市，完成一次周游。令 ${{\tau }_{ij}}$ 为城市ij之间的信息素的量，初始时刻其取值为： ${{\tau }_{ij}}(0)=c$ （c为常数）
   假设在（t，t+n）时刻所有蚂蚁完成一次周游，则在t+n时刻城市ij之间的信息素含量可以表示为： ${{\tau }_{ij}}(t+n)=(1-\rho )\centerdot {{\tau }_{ij}}(t)+\Delta {{\tau }_{ij}}$

$\rho$ 表示时间段（t，t+n）之间信息素的挥发系数。（程序中为0.25）
则 $1-\rho$ 表示信息素的剩余量。挥发系数取值范围(0,1)

$\Delta {{\tau }_{ij}}$ 表示在时间段(t,t+n)之间信息素的增加量，其计算方式如下所示：   $\Delta {{\tau }_{ij}}=\sum\limits_{k=1}^{m}{\Delta \kappa _{ij}^{k}}$

$\Delta \kappa _{ij}^{k}$ 表示第k只蚂蚁在本次迭代中留在路径ij之间的信息素的量，计算方式如下所示：

Q是正常数，LK表示蚂蚁k在周游中经过的路径。
在t时刻，蚂蚁k从城市i转移到城市可的概率可以由以下方式计算得到：

${{\eta }_{ij}}$ 是一个启发式因子， ${{\eta }_{ij}}=\frac{1}{{{d}_{ij}}}$ 表示蚂蚁从城市i转移到城市j的期望程度。
（程序中 $\alpha$ 为信息素的重要程度取1， $\beta$ 为启发式因子的重要程度取5）

${{J}_{k}}(i)$ 表示在城市i处蚂蚁k可以选择走的城市的集合。
路径i,j信息素含量越高，蚂蚁选择该路径的概率越大，而路径i.j之间的距离越大吗，启发式因子就越小，则蚂蚁选择该路径的概率就越小，蚂蚁选择路径i，j的概率与上述两个因素都有关系。Matlab代码见下：
Matlab程序解读

（设置断点，F5和F10配合使用调试程序，观察每个变量的数据，可以更好地理解程序）
信息素矩阵：Tau
初始状态全部为1，表示每两个城市之间的信息素。

城市	1	2	3	……	31
1
2
3
……
31

禁忌表：Tabu
初始状态全为0，表示50只蚂蚁是否去过31个城市。

1	2	3	……	31
1
2
3
……
49
50

clear；
clc;
C = [1304 2312; % 城市坐标
3639 1315;
4177 2244;
3712 1399;
3488 1535;
3326 1556;
3238 1229;
4196 1044;
4312 790;
4386 570;
3007 1970;
2562 1756;
2788 1491;
2381 1676;
1332 695;
3715 1678;
3918 2179;
4061 2370;
3780 2212;
3676 2578;
4029 2838;
4263 2931;
3429 1980;
3507 2376;
3394 2643;
3439 3201;
2935 3240;
3140 3550;
2545 2357;
2778 2826;
2370 2975];
[M,N] = size(C); % M为问题的规模 M个城市，二维坐标。M=31
distance = zeros(M,M); % 用来记录任意两个城市之间的距离 M行M列全为0
% 求任意两个城市之间的距离
for m=1:M
for n=1:M
distance(m,n) = sqrt(sum((C(m,:)-C(n,:)).^2)); %任意两个城市之间的距离填到表格
end
end

%% 信息初始化
m = 50; % 蚂蚁的个数一般取10-50
alpha = 1; % 信息素的重要程度一般取【1,4】
beta = 5; % 启发式因子的重要程度一般取【3,5】
rho = 0.25; % 信息素蒸发系数
G = 150;  %迭代次数从150开始减
Q = 100; % 信息素增加系数
Eta = 1./distance; % 启发式因子
Tau = ones(M,M); % 信息素矩阵存储着每两个城市之间的信息素的数值  初始值为1
Tabu = zeros(m,M); % 禁忌表，记录每只蚂蚁走过的路程
gen = 1;%迭代次数下限值设为1
R_best = zeros(G,M); % 各代的最佳路线
L_best = inf.*ones(G,1); % 每一代的最佳路径的长度初始假设为无穷大

%% 开始迭代计算
while gen<G
% 将m只蚂蚁放到n个城市上
random_pos = [];
for i=1:(ceil(m/M)) % m只蚂蚁随即放到M座城市 ceil函数：朝正无穷方向取整
random_pos = [random_pos,randperm(M)]; % random_pos=[1~31 + 1~31] 将每只蚂蚁放到随机的城市在random_pos 中随机选择m个数，代表蚂蚁的初始城市
end
Tabu(:,1) = (random_pos(1,1:m))&#39;; % 第一次迭代每只蚂蚁的禁忌表
%50只蚂蚁放在31个城市上，每个城市1~2只蚂蚁

for i=2:M % 从第二个城市开始
for j=1:m % 每只蚂蚁
visited = Tabu(j,1:(i-1)); % 在访问第i个城市的时候，第j个蚂蚁访问过的城市
% visited=visited(1,:);
unvisited = zeros(1,(M+1-i)); % 待访问的城市
visit_P = unvisited; % 蚂蚁j访问剩下的城市的概率
count = 1;
for k=1:M % 这个循环是找出未访问的城市
if isempty(find(visited==k)) %还没有访问过的城市如果成立。则证明第k个城市没有访问过 find函数找到两个值相等的位置
unvisited(count) = k;
count = count+1;
end
end
% 计算待选择城市的概率
for k=1:length(unvisited) % Tau(visited(end),unvisited(k))访问过的城市的最后一个与所有未访问的城市之间的信息素
visit_P(k) = ((Tau(visited(end),unvisited(k)))^alpha)*(Eta(visited(end),unvisited(k))^beta);  %按照公式
end
visit_P = visit_P/sum(visit_P); % 访问每条路径的概率的大小
% 按照概率选择下一个要访问的城市
% 这里运用轮盘赌选择方法这里也可以选择选择概率最大的路径去走，这里采用轮盘赌选择法。

Pcum = cumsum(visit_P); %cumsum（A)返回一个向量，第m行的元素是A中第1行到第m行所有元素累加之和。
selected = find(Pcum>=rand);
to_visited = unvisited(selected(1));
Tabu(j,i) = to_visited; % 添加到禁忌表
end
end

if gen>=2
Tabu(1,:) = R_best(gen-1,:);
end
% 记录m只蚂蚁迭代的最佳路线
L = zeros(1,m);
for i=1:m
R = Tabu(i,:);
L(i) = distance(R(M),R(1)); % 因为要走一周回到原来的地点
for j=1:(M-1)
L(i) = L(i)+distance(R(j),R(j+1));
end
end
L_best(gen) = min(L); % 记录每一代中路径的最短值
pos = find(L==L_best(gen));
R_best(gen,:) = Tabu(pos(1),:); % 最优的路径

%%更新信息素的值
Delta_Tau = zeros(M,M);
for i=1:m % m只蚂蚁
for j=1:(M-1) % M座城市
Delta_Tau(Tabu(i,j),Tabu(i,j+1)) = Delta_Tau(Tabu(i,j),Tabu(i,j+1)) + Q/L(i); % m只蚂蚁的信息素累加这里采用的是论文中ant-cycle模型
end
Delta_Tau(Tabu(i,M),Tabu(i,1)) = Delta_Tau(Tabu(i,M),Tabu(i,1)) + Q/L(i);
end
Tau = (1-rho).*Tau+Delta_Tau; % 更新路径上的信息素含量
% 禁忌表清零
Tabu = zeros(m,M);

for i=1:(M-1)
plot([C(R_best(gen,i),1),C(R_best(gen,i+1),1)],[C(R_best(gen,i),2),C(R_best(gen,i+1),2)],&#39;bo-&#39;);
hold on;
end
plot([C(R_best(gen,n),1),C(R_best(gen,1),1)],[C(R_best(gen,n),2),C(R_best(gen,1),2)],&#39;ro-&#39;);
title([&#39;最短路径：&#39;,num2str(L_best(gen))]);
hold off;
pause(0.05);
gen = gen+1;
end
figure(2);
plot(L_best);
title(&#39;路径长度变化曲线&#39;);
xlabel(&#39;迭代次数&#39;);
ylabel(&#39;路径长度数值&#39;);结果：

Python程序解读

运行结果不对，再检查一下。
import numpy as np
import matplotlib.pyplot as plt
import pylab

coordinates = np.array([[1304.0, 2312.0], [3639.0, 1315.0], [4177.0, 2244.0], [3712.0, 1399.0], [3488.0, 1535.0],
                     [3326.0, 1556.0], [3238.0, 1229.0], [4196.0, 1044.0], [4312.0, 790.0], [4386.0, 570.0],
                     [3007.0, 1970.0], [2562.0, 1756.0], [2788.0, 1491.0], [2381.0, 1676.0], [1332.0, 695.0],
                     [3715.0, 1678.0], [3918.0, 2179.0], [4061.0, 2370.0], [3780.0, 2212.0], [3676.0, 2578.0],
                     [4029.0, 2838.0], [4263.0, 2931.0], [3429.0, 1980.0], [3507.0, 2376.0], [3394.0, 2643.0],
                     [3439.0, 3201.0], [2935.0, 3240.0], [3140.0, 3550.0], [2545.0, 2357.0], [2778.0, 2826.0],
                     [2370.0, 2975.0]])  # 城市坐标

def getdistmat(coordinates):
num = coordinates.shape[0]
distmat = np.zeros((31, 31))  # 打印一个31行31列的二维数组
for i in range(num):
      for j in range(i, num):
         distmat[j] = distmat[j] = np.linalg.norm(coordinates - coordinates[j])
return distmat  # distmat[j] = distmat[j]表示城市i和j距离

distmat = getdistmat(coordinates)  # 二维数组，表示城市之间的距离
numant = 50  # 蚂蚁个数
numcity = coordinates.shape[0]  # 城市个数 shape[0]输出二维数组【numpy】的行数。
alpha = 1  # 信息素重要程度因子
beta = 5  # 启发函数重要程度因子
rho = 0.25  # 信息素的挥发速度
Q = 100  # 信息素强度
iter = 1
itermax = 150
etatable = 1.0 / (distmat + np.diag([1e10] * numcity))  # 启发函数矩阵，表示蚂蚁从城市i转移到矩阵j的期望程度
pheromonetable = np.ones((numcity, numcity))  # 信息素矩阵       31行31列的二维数组。元素都是1
pathtable = np.zeros((numant, numcity)).astype(int)  # 路径记录表 50行31列的二维数组，目前都为0
# distmat = getdistmat(coordinates)  # 城市的距离矩阵
lengthaver = np.zeros(itermax)  # 各代(各个循环)路径的平均长度       # 一维数组，itermax个0
lengthbest = np.zeros(itermax)  # 各代及其之前遇到的最佳路径长度 # 一维数组，itermax个0
pathbest = np.zeros((itermax, numcity))  # 各代及其之前遇到的最佳路径长度       # itermax(250)行numcity(52)列的二维矩阵

while iter < itermax:  # 循环1-150次
# 1、随机产生各个蚂蚁的起点城市
if numant <= numcity:  # 1.1、城市数比蚂蚁数多
      #  permutation()：随机排列序列，生成一个0-52的一维数组,[:numant]去除前numant个分配给pathtable中的第0列
      pathtable[:, 0] = np.random.permutation(range(0, numcity))[:numant]
else:  # 1.2、蚂蚁数比城市数多，需要补足
      pathtable[:numcity, 0] = np.random.permutation(range(0, numcity))[:]  # 先将城市全部取出，剩下的蚂蚁随机分配
      # 剩下numant - numcity个蚂蚁，将分配给他们的城市数分配在他们的第0列
      pathtable[numcity:, 0] = np.random.permutation(range(0, numcity))[:numant - numcity]
length = np.zeros(numant)  # 计算各个蚂蚁的路径距离，还未走,都是0.
# 2、各个蚂蚁进行路径选择
for i in range(numant):
      visiting = pathtable[i, 0]  # 当前所在的城市，将[i,0]位置的值赋值给visiting
      unvisited = set(range(numcity))  # 未访问的城市,以集合的形式存储{}
      unvisited.remove(visiting)  # 删除元素；利用集合的remove方法删除存储的数据内容
      # 3、循环numcity-1次，访问剩余的numcity-1个城市，循环为一只蚂蚁访问所有城市的过程
      for j in range(1, numcity):
         # 每次用轮盘法选择下一个要访问的城市
         listunvisited = list(unvisited)    # 列表,即为一维数组。
         probtrans = np.zeros(len(listunvisited)) # 创建一个【未被访问城市个数】一维数组,s元素全为0
         for k in range(len(listunvisited)):
            probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]], alpha) \
                           * np.power(etatable[visiting][listunvisited[k]], beta)
         cumsumprobtrans = (probtrans / sum(probtrans)).cumsum() # cumsum()将probtrans数组中的值进行累加求和
         cumsumprobtrans -= np.random.rand()
         k = listunvisited[(np.where(cumsumprobtrans > 0)[0])[0]]  # python3中原代码运行bug，类型问题；鉴于此特找到其他方法
         # 通过where（）方法寻找矩阵大于0的元素的索引并返回ndarray类型，然后接着载使用[0]提取其中的元素，用作listunvisited列表中
         # 元素的提取（也就是下一轮选的城市）
         pathtable[i, j] = k  # 添加到路径表中（也就是蚂蚁走过的路径)，第i号蚂蚁第j步走的城市。
         unvisited.remove(k)  # 然后在为访问城市set中remove（）删除掉该城市
         length += distmat[visiting][k] # 当前所在城市visiting到城市k的距离，length[]用于存储各个蚂蚁走的路径长度，一维数组。
         visiting = k
      length += distmat[visiting][pathtable[i, 0]]  # 蚂蚁的路径距离包括最后一个城市和第一个城市的距离  TSP问题，访问所有城市后又回到了原点
      # 包含所有蚂蚁的一个迭代结束后，统计本次迭代的若干统计参数
# 4、从当前循环中找出最小路径和最小路径长度并保存
lengthaver[iter] = length.mean() # 各代(各个循环)路径的平均长度
if iter == 0:
      lengthbest[iter] = length.min()                   # length[]记录的是当前循环，每个蚂蚁走出的路径长度
      pathbest[iter] = pathtable[length.argmin()].copy() # length.argmin()显示length[]中最小值的下标
else:
      if length.min() > lengthbest[iter - 1]:             # 当前循环中的最小路径不是最优值
         lengthbest[iter] = lengthbest[iter - 1]
         pathbest[iter] = pathbest[iter - 1].copy()
      else:
         lengthbest[iter] = length.min()
         pathbest[iter] = pathtable[length.argmin()].copy()
# 5、更新信息素
changepheromonetable = np.zeros((numcity, numcity))
for i in range(numant):
      for j in range(numcity - 1):
         # 更新蚂蚁i从城市j到j+1路径的信息素
         changepheromonetable[pathtable[i, j]][pathtable[i, j + 1]] += Q / distmat[pathtable[i, j]][
            pathtable[i, j + 1]]  # 计算信息素增量
      # 最后一个城市到第一个城市途径的信息素增量
      changepheromonetable[pathtable[i, j + 1]][pathtable[i, 0]] += Q / distmat[pathtable[i, j + 1]][pathtable[i, 0]]
# 带入计算信息素公式，更新完毕，本次循环结束
pheromonetable = (1 - rho) * pheromonetable + changepheromonetable  # 计算信息素公式
iter += 1  # 迭代次数指示器+1
print(&#34;iter:&#34;, iter)

# 做出平均路径长度和最优路径长度
fig, axes = plt.subplots(nrows=2, ncols=1, figsize=(12, 10))
axes[0].plot(lengthaver, &#39;k&#39;, marker=u&#39;&#39;)
axes[0].set_title(&#39;Average Length&#39;)
axes[0].set_xlabel(u&#39;iteration&#39;)

axes[1].plot(lengthbest, &#39;k&#39;, marker=u&#39;&#39;)
axes[1].set_title(&#39;Best Length&#39;)
axes[1].set_xlabel(u&#39;iteration&#39;)
fig.savefig(&#39;average_best.png&#39;, dpi=500, bbox_inches=&#39;tight&#39;)
plt.show()

# 作出找到的最优路径图
bestpath = pathbest[-1] # 每次更新后，pathbest[-1]的最后一行，就是最优路径了
plt.plot(coordinates[:, 0], coordinates[:, 1], &#39;r.&#39;, marker=u&#39;$\cdot$&#39;)
plt.xlim([-100, 2000])
plt.ylim([-100, 1500])

for i in range(numcity - 1):
m = int(bestpath)
n = int(bestpath[i + 1])
plt.plot([coordinates[m][0], coordinates[n][0]], [coordinates[m][1], coordinates[n][1]], &#39;k&#39;)  # k为黑色
plt.plot([coordinates[int(bestpath[0])][0], coordinates[int(n)][0]],
      [coordinates[int(bestpath[0])][1], coordinates[int(n)][1]], &#39;b&#39;)  # 最后一个城市与第一个城市连线。 b为蓝色
ax = plt.gca()
ax.set_title(&#34;Best Path&#34;)
ax.set_xlabel(&#39;X axis&#39;)
ax.set_ylabel(&#39;Y_axis&#39;)

plt.savefig(&#39;best path.png&#39;, dpi=500, bbox_inches=&#39;tight&#39;)
plt.show()<hr/>Day2

轮盘赌算法原理

		自动登录	找回密码
密码			立即注册

优化算法学习笔记——蚁群算法

本帖子中包含更多资源