简介

 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

 这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。

符号说明

符号	含义
$n$	蚂蚁个数
$\rho$	信息素挥发系数，通常取0.9
$P0$	转移概率常数，通常取0.8
$pher{o}_i^d$	第d次迭代，第i只蚂蚁的信息素浓度
$p_i$	第i只蚂蚁的转移概率

核心思想

 单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

流程图

文章使用到的测试函数

一元函数：$$y=abs(xsin(x)cos(2x)-2xsin(3x)+3xsin(4x)),x\in [0,50]$$参考最大值为：$max(y)=219.501$

二元函数：$$y=-(x_1^2+x_2^2-x_1{x}_2-10x_1-4x_2+60)$$参考最大值为：$max(y)=-8.0$

基本步骤

 对于简单的函数求解最值的问题，蚁群算法的的基本操作可以分为三步：
（1）根据信息素浓度计算蚂蚁的转移概率。信息素浓度越大，转移概率越高。计算转移概率的方式：$$P_i=pher{o}_i/max(pher{o}_0,pher{o}_1,...,pher{o}_n)$$

（2）根据转移概率判断蚂蚁的搜索方式（转移方式）。转移概率大于一个转移概率常数时说明此只蚂蚁距离最优解较近，需要进行局部搜索；反之需要进行全局搜索。

（3）更新信息素浓度。$$pher{o}_i^{d+1}=\rho pher{o}_i^d+newphero$$其中，$newphero$使用当前蚂蚁的适应度计算。

注意：信息素应为非负值，因为需要通过挥发系数来达到挥发（衰减）的目的。使用调整函数调整信息素取值。调整方式为：如果出现了信息素负值则每一只蚂蚁的信息素+最小值的相反数；否则什么也不用做。

def adjust(self, phero_val):# 调整所有值非负， 为了保证信息素正常衰减min_val = min(phero_val)if min_val < 0:min_val = -min_valfor i in range(self.n):phero_val[i] += min_val

蚁群算法代码

Python版本：

import random
from copy import deepcopy
import mathdef func(x):# 一元函数测试return abs(x[0] * math.sin(x[0]) * math.cos(2 * x[0]) - 2 * x[0] * math.sin(3 * x[0]) + 3 * x[0] * math.sin(4 * x[0]))# # 二元函数测试# return -(x[0]**2 + x[1]**2 - x[0]*x[1] - 10 * x[0] - 4 * x[1] + 60)class ACO:def __init__(self, func, n = 300, var = 1, iter = 50, lb = None, ub = None):""" 默认寻找最大值，以及对应自变量取值。 若需要寻找最大值，对目标函数乘-1，并对最终结果乘-1即可:param func: type：函数， des：所要求解的目标函数:param n: type: int， des: 蚁群蚂蚁的个数:param var: type: int， des: 函数中自变量的个数，即：几元函数:param iter: type: int， des: 迭代次数:param lb: type: list(double)， des: 每一种自变量的下界，注意应和自变量一一对应:param ub: type: list(double)， des: 每一种自变量的上界，注意应和自变量一一对应"""if lb is None:lb = []if ub is None:ub = []# 目标函数self.func = func# 初始化蚂蚁数量self.n = n# 初始化自变量个数self.var = var# 初始化迭代次数self.iter = iter# 初始化自变量范围 len(lb) = len(ub) = varself.lb = lbself.ub = ub# 初始化信息素挥发系数self.Rou = 0.9# 初始化转移概率常数self.P0 = 0.8# 为每只蚂蚁的适应度申请空间## 每只蚂蚁的信息素浓度。 取值与适应度（一般为函数值）有关self.phero = [0] * n# 为每只蚂蚁的坐标申请空间。 注意：多元函数需要var个自变量来描述self.ant = [[0] * var for _ in range(n)]## 初始化每只蚂蚁的坐标for i in range(n): # n只蚂蚁for j in range(var):# 使个自变量随机分布于可行域中self.ant[i][j] = lb[j] + random.random() * (ub[j] - lb[j])# 计算一组初始解self.phero[i] = self.func(self.ant[i])# 最优解位置self.x = deepcopy(self.ant[0])# 初始化最优解位置for i in range(1, n):# 基于最大值选择最优值if self.phero[i] > self.func(self.x):self.x = deepcopy(self.ant[i])def adjust(self, phero_val):# 调整所有值非负， 为了保证信息素正常衰减min_val = min(phero_val)if min_val < 0:min_val = -min_valfor i in range(self.n):phero_val[i] += min_valdef run(self):# 预处理适应度（信息素）非负self.adjust(self.phero)for k in range(1, self.iter + 1):# 局部搜索步长## 随迭代次数增加步长逐渐减小step = 1 / k# 每只蚂蚁的转移概率p = [0] * self.n## 信息素越多， 转移概率越大for i in range(self.n):p[i] = self.phero[i] / max(self.phero)new_phero= [0] * self.nfor i in range(self.n):for j in range(self.var):if p[i] >= self.P0: # 局部搜索# rand - 0.5 为了均匀产生正负位移self.ant[i][j] += (random.random() - 0.5) * stepelse: # 全局搜索# rand - 0.5 为了均匀产生正负位移self.ant[i][j] += (random.random() - 0.5) * (self.ub[j] - self.lb[j])# 调整自变量值避免越界if self.ant[i][j] < self.lb[j]:self.ant[i][j] = self.lb[j]if self.ant[i][j] > self.ub[j]:self.ant[i][j] = self.ub[j]# 更新最优值位置if self.func(self.ant[i]) > self.func(self.x):self.x = deepcopy(self.ant[i])new_phero[i] = self.func(self.ant[i])self.adjust(new_phero)for i in range(self.n):self.phero[i] = (1 - self.Rou) * self.phero[i] + new_phero[i]print(f'最优解为：{self.func(self.x)}')print(f'最优解对应自变量取值为：{self.x}')"""一元函数测试"""
aco = ACO(func, 50, 1, 100, [0], [50])"""二元函数测试"""
# aco = ACO(func, 50, 2, 100, [-15, -15], [15, 15])aco.run()

以一元函数测试为例，对应输出为：

最优解为：219.52583163372353
最优解对应自变量取值为：[47.554148304588374]