蚁群算法
henl9l
·
·
算法·理论
四大优化算法之蚁群算法
一、基本信息
蚁群算法（\texttt{Ant} \texttt{Colony} \texttt{Optimization}），简称 \texttt{ACO}，该算法主要用于解决旅行商问题等组合优化问题。
蚁群算法是根据蚂蚁觅食设计的一种随机搜索算法。蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。
二、基本原理
蚂蚁在寻找食物时会在路径上留下信息素。通常情况下，蚂蚁有较大的概率选择信息素浓度较高的路径，并释放信息素增强该条路径上的信息素浓度。
三、基本定义
一、蚂蚁
在蚁群算法中，蚂蚁是最基本的个体，代表着搜索过程中的一个解。每只蚂蚁在做每一步决策时，都会根据信息素浓度和启发式信息来选择下一步的路径。蚂蚁的数量、运动方式以及选择路径的规则是蚁群算法的核心。
二、信息素
信息素是蚂蚁在路上留下的化学物质，用于传递信息和标记路径。
1、信息素更新（\texttt{Deposit}）： 蚂蚁在路径上留下信息素，路径质量越好，信息素浓度就会增加越多。
2、信息素挥发（\texttt{Evaporation}）： 随着时间推移，信息素会自然挥发，避免过度依赖某条路径并促进新的搜索，通常在 0 到 1 之间。
三、启发式信息
启发式信息是指在决策过程中，可以帮助蚂蚁做出选择的额外信息。启发式信息与信息素一起决定了蚂蚁选择路径的概率。
四、路径选择概率
蚂蚁选择路径的概率是根据信息素浓度和启发式信息综合计算的。公式如下：
P_{i,j}=\displaystyle\frac{τ_{i,j}^{α}
η_{i,j}^{β}}{\sum_{k\in allowed}τ_{i,k}^{α}
η_{i,k}^{β}}
其中：
1、P_{i,j} 是蚂蚁选择路径 i\to j 的概率。
2、τ_{i,j} 是路径 i\to j 上的信息素浓度。以下为计算新增加的信息素的公式：
Δτ_{i,j}=\sum_{k=1}^{n}Δτ_{i,j}^k
其中 ρ 代表信息素的挥发率，Δ\tau_{ij} 表示新增加的信息素。
3、η_{i,j} 是启发式信息。
4、α 和 β 是控制信息素与启发式信息影响权重的参数。
5 allowed 是当前可选路径的集合，蚂蚁只能在这些路径中选择。
算法步骤
1、设定参数：
$m$：蚂蚁所在的节点的数量。
$α$：信息素的重要程度（通常为常数）。
$β$：启发函数的重要程度（通常为常数）。
$ρ$：信息素挥发因子。
$Q$：每次蚂蚁通过边时增加的信息素量。
最大迭代次数（或满足精度的停止条件）
初始化信息素矩阵：通常设置为一个常数，表示路径初始时的吸引力。
初始化启发函数：根据具体问题设定启发函数。
### 2、寻路
在每一轮迭代中，所有蚂蚁根据当前的路径选择规则进行路径选择：
对于每一只蚂蚁，选择当前城市到下一城市的路径。通常靠概率选择：
$$
P_{i,j}=\displaystyle\frac{τ_{i,j}^{α}
η_{i,j}^{β}}{\sum_{k\in allowed}τ_{i,k}^{α}
η_{i,k}^{β}}
$$
### 3、更新信息素
**局部更新：** 在蚂蚁移动时，沿途的路径信息素会按照一定比例减少，以模拟信息素的挥发。更新公式为：
$$
τ_{i,j}(t+1)=(1−ρ)τ_{i,j}(t)+Δτ_{i,j}
$$
**全局更新：** 在所有蚂蚁完成路径选择之后，根据最优解对路径上的信息素进行全局更新。更新公式为：
$$
τ_{i,j}(t+1)=(1−ρ)τ_{i,j}(t)+\frac{Q}{L}
$$
其中，$L$ 是当前最优路径的长度。
### 4、迭代
根据设定的终止条件，并判断是否停止算法。如果满足停止条件，输出最优解；如果未满足，则返回步骤二进行下一轮迭代。
## 五、整体代码
**代码如下：**
```cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MAXN 110
double INF = 10e9;
const int num_ant=30;//蚂蚁的数量
int num_city;//城市数量
const int MAX_GEN=1000;//最大迭代次数
int ALPHA=1;//信息素的权重
int BETA=4;//启发式因子重要程度权重
int remain=100;//信息素残留参数
double dis[MAXN][MAXN];//各个城市的距离
int city[MAXN][2];//各个城市的位置
int vis[MAXN][MAXN];//禁忌表
double info[MAXN][MAXN];//信息素矩阵
const int Q=100;//信息素残留系数
double ROU=0.5;//信息素残留度
unsigned seed=(unsigned)time(0);
int random (int l,int h){
return l+(h-l)*rand()/(RAND_MAX+1);
}
double random(double l,double h){
return l+(h-l)*rand()/(RAND_MAX+1.0);
}
double Random (double ans){
return (double)((int)(ans+0.5));
}
double power(double x, int y){//快速幂
double ans=1;
while(y){
if(y&1)ans*=x;
x*=x;
y>>=1;
}
return ans;
}
struct Ant{
int Path[MAXN];
double length;//当前已走的长度；
int vis[MAXN];//已走的城市
int cur_city;//现在所在的城市
int num_move;//已经走的城市数
void Init(){
memset(vis,0,sizeof(vis));
length=0.0;
cur_city=random(0,num_city);
Path[0]=cur_city;
vis[cur_city]=1;
num_move=1;
}
int choose(){
int select_city=-1;//选择的城市
double sum=0.0;
double possible_city[MAXN];//各个城市被选中的概率
for(int i=0;i<num_city;i++){
if(!vis[i]){
possible_city[i]=power(info[cur_city][i],ALPHA)*power(1.0/dis[cur_city][i],BETA);
sum+=possible_city[i];//计算概率
}
else possible_city[i]=0;
}
//概率选择
double possible_du=0.0;
if(sum>0.0){
possible_du=random(0.0,sum);
for(int i=0;i<num_city;i++)
if(!vis[i]){
possible_du-=possible_city[i];
if(possible_du<0.0){
select_city=i;
break;
}
}
}
if(select_city==-1)
for(int i=0;i<num_city;i++)
if(!vis[i]){
select_city=i;
break;
}
return select_city;
}
void move_ant(){
int next_city=choose();//选择的城市
Path[num_move]=next_city;
vis[next_city]=1;
cur_city=next_city;//更新当前位置
length+=dis[Path[num_move-1]][Path[num_move]];
num_move++;
}
void find_(){
Init();
while(num_move<num_city) move_ant();
length+=dis[Path[num_city-1]][Path[0]];//更新长度
}
};
struct TSP{
Ant ants[num_ant];
Ant ant_best;
void Init(){
ant_best.length=double(INF);//初始化最优的蚂蚁，设为最大
for(int i=0;i<num_city;i++)
for(int j=0;j<num_city;j++){
double tmp1=city[j][0]-city[i][0];
double tmp2=city[j][1]-city[i][1];
dis[i][j]=sqrt(tmp1*tmp1+tmp2*tmp2);//计算每个城市间的距离
}
for(int i=0;i<num_city;i++)
for(int j=0;j<num_city;j++) info[i][j]=1.0;//初始化信息素
}
void Update(){
double tmpinfo[MAXN][MAXN];//临时矩阵储存新增的信息素
memset(tmpinfo,0,sizeof(tmpinfo));
int n=0;
int m=0;
//蚁量算法更新信息素
for(int i=0;i<num_ant;i++){
for(int j=1;j<num_city;j++){
n=ants[i].Path[j-1];
m=ants[i].Path[j];
tmpinfo[n][m]+=Q/ants[i].length;
tmpinfo[m][n]=tmpinfo[n][m];
}
n=ants[i].Path[0];
tmpinfo[n][m]+=Q/ants[i].length;
tmpinfo[m][n]=tmpinfo[n][m];
}
//更新环境的信息素
for(int i=0;i<num_city;i++)
for(int j=0;j<num_city;j++)info[i][j]=info[i][j]*ROU+tmpinfo[i][j];
}
void find_(){
for(int i=0;i<MAX_GEN;i++){
for(int j=0;j<num_ant;j++) ants[j].find_();
for(int j=0;j<num_ant;j++)
if(ant_best.length>ants[j].length) ant_best=ants[j];//更新最优解
Update();
}
}
};
int main(){
srand(seed);
TSP tsp;
printf("Input num_city:");
scanf("%d",&num_city);
printf("Please enter %d cities position\n",num_city);
for(int i=0;i<num_city;i++) scanf("%d%d",&city[i][0],&city[i][1]);//输入城市位置
tsp.Init();
tsp.find_();
printf("The minimum path is \n");
for(int i=0;i<num_city;i++) printf("%d ",tsp.ant_best.Path[i]);//打印出路径
return 0;
}
```
材料来源：
<https://blog.csdn.net/u012121721/article/details/144981942>
<https://www.cnblogs.com/kayiko/p/12049296.html>