2024年智能优化算法—蚁群算法（Python实现）_python智能算法

每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。

根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。

那么，蚂蚁究竟是怎么找到食物的呢？

在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。

蚂蚁如何找到最短路径的？

这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。

5  基本蚁群算法及其流程

---

5.1  蚁群算法公式

蚁群算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。实验结果表明，ant-cycle模型比ant-quantity和ant-density模型有更好的性能。这是因为ant-cycle模型利用全局信息更新路径上的信息素量,而ant-quantity和ant-density模型使用局部信息。

5.2 蚁群算法程序概括

(1)参数初始化

在寻最短路钱，需对程序各个参数进行初始化，蚁群规模m、信息素重要程度因子α、启发函数重要程度因子β、信息素会发因子、最大迭代次数ddcs_max，初始迭代值为ddcs=1。

(2)构建解空间

将每只蚂蚁随机放置在不同的出发地点，对蚂蚁访问行为按照公式计算下一个访问的地点，直到所有蚂蚁访问完所有地点。

(3)更新信息素

计算每只蚂蚁经过的路径总长Lk,记录当前循环中的最优路径，同时根据公式对各个地点间连接路径上的信息素浓度进行更新。

(4)判断终止

迭代次数达到最大值前，清空蚂蚁经过的记录，并返回步骤2。

5.3 流程图

6 案例实现

---

6.1 案例1

求解函数：的最小值，其中x的取值范围为[-5，5], y的取值范围为[-5, 5]。这是一个有多个局部极值的函数。

6.2 Python实现

import numpy as np

from tqdm import tqdm#进度条设置

import matplotlib.pyplot as plt

import matplotlib as mpl

import matplotlib; matplotlib.use(‘TkAgg’)

mpl.rcParams[‘font.sans-serif’] = [‘SimHei’] # 指定默认字体

mpl.rcParams[‘axes.unicode_minus’] = False # 解决保存图像是负号’-'显示为方块的问题

#蚁群算法求函数极值====

#===适应度函数=

def func(x,y):

value = 20np.power(xx-yy,2)-np.power(1-y,2)-3np.power(1+y,2)+0.3

return value

#===初始化参数

m=20 #蚂蚁个数

G_max=200 #最大迭代次数

Rho=0.9 #信息素蒸发系数

P0=0.2 #转移概率常数

XMAX= 5 #搜索变量x最大值

XMIN= -5 #搜索变量x最小值

YMAX= 5 #搜索变量y最大值

YMIN= -5 #搜索变量y最小值

X=np.zeros(shape=(m,2)) #蚁群 shape=(20, 2)

Tau=np.zeros(shape=(m,)) #信息素

P=np.zeros(shape=(G_max,m)) #状态转移矩阵

fitneess_value_list=[] #迭代记录最优目标函数值

#随机设置蚂蚁初始位置

for i in range(m):#遍历每一个蚂蚁

X[i,0]=np.random.uniform(XMIN,XMAX,1)[0] #初始化x

X[i,1]=np.random.uniform(YMIN,YMAX,1)[0] #初始化y

Tau[i]=func(X[i,0],X[i,1])

step=0.1; #局部搜索步长

for NC in range(G_max):#遍历每一代

lamda=1/(NC+1)

BestIndex=np.argmin(Tau) #最优索引

Tau_best=Tau[BestIndex] #最优信息素

#计算状态转移概率=

for i in range(m):#遍历每一个蚂蚁

P[NC,i]=np.abs((Tau_best-Tau[i]))/np.abs(Tau_best)+0.01 #即例最优信息素的距离

#=位置更新====

for i in range(m): # 遍历每一个蚂蚁

#=局部搜索==

if P[NC,i]<P0:

temp1 = X[i, 0] + (2 * np.random.random() - 1) * step * lamda # x(2 * np.random.random() - 1) 转换到【-1,1】区间

temp2 = X[i,1] + (2 * np.random.random() - 1) * step * lamda #y

#=全局搜索==

else:

temp1 = X[i, 0] + (XMAX - XMIN) * (np.random.random() - 0.5)

temp2 = X[i, 0] + (YMAX - YMIN) * (np.random.random() - 0.5)

#=边界处理=

if temp1 < XMIN:

temp1 =XMIN

if temp1 > XMAX:

temp1 =XMAX

if temp2 < XMIN:

temp2 =XMIN

if temp2 > XMAX:

temp2 =XMAX

#判断蚂蚁是否移动(选更优=

if func(temp1, temp2) < func(X[i, 0], X[i, 1]):

X[i, 0] = temp1

X[i, 1]= temp2

#=更新信息素====

for i in range(m): # 遍历每一个蚂蚁

Tau[i] = (1 - Rho) * Tau[i] + func(X[i, 0], X[i, 1]) #(1 - Rho) * Tau[i] 信息蒸发后保留的

index=np.argmin(Tau)#最小值索引

value=Tau[index]#最小值

fitneess_value_list.append(func(X[index,0],X[index,1])) #记录最优目标函数值

#打印结果=

min_index=np.argmin(Tau)#最优值索引

minX=X[min_index,0] #最优变量x

minY=X[min_index,1] #最优变量y

minValue=func(X[min_index,0],X[min_index,1]) #最优目标函数值

print(‘最优变量x’,minX,end=‘’)

print(‘最优变量y’,minY,end=‘\n’)

print(‘最优目标函数值’,minValue)

plt.plot(fitneess_value_list,label=‘迭代曲线’)

plt.legend()

plt.show()

6.3 结果

最优变量x 5.0最优变量y 5.0

最优目标函数值 -123.7

6.4 案例2

6.5 Python实现

#导入相关库=========

import pandas as pd

import numpy as np

from tqdm import tqdm#进度条设置

import matplotlib.pyplot as plt

import matplotlib; matplotlib.use(‘TkAgg’)

from pylab import *

mpl.rcParams[‘font.sans-serif’] = [‘SimHei’]

mpl.rcParams[‘axes.unicode_minus’] = False

#=定义函数====

#===目标函数=

def calc_f(X):

“”“计算粒子的的适应度值，也就是目标函数值，X 的维度是 size * 2 “””

A = 10

pi = np.pi

x = X[0]

y = X[1]

return 2 * A + x ** 2 - A * np.cos(2 * pi * x) + y ** 2 - A * np.cos(2 * pi * y)

#惩罚项函数==

def calc_e(X):

“”“计算蚂蚁的惩罚项，X 的维度是 size * 2 “””

ee = 0

“”“计算第一个约束的惩罚项”“”

e1 = X[0] + X[1] - 6

ee += max(0, e1)

“”“计算第二个约束的惩罚项”“”

e2 = 3 * X[0] - 2 * X[1] - 5

ee += max(0, e2)

return ee

#=子代和父辈之间的选择操作==

def update_best(parent,parent_fitness,parent_e,child,child_fitness,child_e):

“”"

针对不同问题，合理选择惩罚项的阈值。本例中阈值为0.00001

:param parent: 父辈个体

:param parent_fitness:父辈适应度值

:param parent_e ：父辈惩罚项

:param child: 子代个体

:param child_fitness 子代适应度值

:param child_e ：子代惩罚项

:return: 父辈 和子代中较优者、适应度、惩罚项

“”"

规则1，如果 parent 和 child 都没有违反约束，则取适应度小的

if parent_e <= 0.00001 and child_e <= 0.00001:

if parent_fitness <= child_fitness:

return parent,parent_fitness,parent_e

else:

return child,child_fitness,child_e

规则2，如果child违反约束而parent没有违反约束，则取parent

if parent_e < 0.00001 and child_e >= 0.00001:

return parent,parent_fitness,parent_e

规则3，如果parent违反约束而child没有违反约束，则取child

if parent_e >= 0.00001 and child_e < 0.00001:

return child,child_fitness,child_e

规则4，如果两个都违反约束，则取适应度值小的

if parent_fitness <= child_fitness:

return parent,parent_fitness,parent_e

else:

return child,child_fitness,child_e

#=初始化参数====

m=20 #蚂蚁个数

G_max=200 #最大迭代次数

Rho=0.9 #信息素蒸发系数

P0=0.2 #转移概率常数

XMAX= 2 #搜索变量x最大值

XMIN= 1 #搜索变量x最小值

YMAX= 0 #搜索变量y最大值

YMIN= -1 #搜索变量y最小值

step=0.1 #局部搜索步长

P=np.zeros(shape=(G_max,m)) #状态转移矩阵

fitneess_value_list=[] #迭代记录最优目标函数值

#=初始化蚂蚁群体位置和信息素====

def initialization():

“”"

:return: 初始化蚁群和初始信息素

“”"

X = np.zeros(shape=(m, 2)) # 蚁群 shape=(20, 2)

Tau = np.zeros(shape=(m,)) # 信息素

for i in range(m): # 遍历每一个蚂蚁

X[i, 0] = np.random.uniform(XMIN, XMAX, 1)[0] # 初始化x

X[i, 1] =np.random.uniform(YMIN, YMAX, 1)[0] # 初始化y

Tau[i] = calc_f(X[i])#计算信息素

return X,Tau

#=位置更新==

def position_update(NC,P,X):

“”"

:param NC: 当前迭代次数

:param P: 状态转移矩阵

:param X: 蚁群

:return: 蚁群X

“”"

lamda = 1 / (NC + 1)

=位置更新====

for i in range(m): # 遍历每一个蚂蚁

=局部搜索=

if P[NC, i] < P0:

temp1 = X[i, 0] + (2 * np.random.random() - 1) * step * lamda # x(2 * np.random.random() - 1) 转换到【-1,1】区间

temp2 = X[i, 1] + (2 * np.random.random() - 1) * step * lamda # y

=全局搜索=

else:

temp1 = X[i, 0] + (XMAX - XMIN) * (np.random.random() - 0.5)

temp2 = X[i, 0] + (YMAX - YMIN) * (np.random.random() - 0.5)

=边界处理=

if (temp1 < XMIN) or (temp1 > XMAX):

temp1 = np.random.uniform(XMIN, XMAX, 1)[0] # 初始化x

if (temp2 < YMIN) or (temp2 > YMAX):

temp2 = np.random.uniform(YMIN, YMAX, 1)[0] # 初始化y

#=判断蚂蚁是否移动(选更优）=

#子代蚂蚁

children=np.array([temp1,temp2])#子代个体蚂蚁

感谢每一个认真阅读我文章的人，看着粉丝一路的上涨和关注，礼尚往来总是要有的：

①　2000多本Python电子书（主流和经典的书籍应该都有了）

②　Python标准库资料（最全中文版）

③　项目源码（四五十个有趣且经典的练手项目及源码）

④　Python基础入门、爬虫、web开发、大数据分析方面的视频（适合小白学习）

⑤ Python学习路线图（告别不入流的学习）

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化学习资料的朋友，可以戳这里无偿获取

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！