蚁群算法原理及c++实现

admin · 发表于 2024-7-16 23:10:58

//轮盘赌选择下一步行进城市
int citySelect(int k, int f)
{
int c = 0;//记录蚂蚁可行进的城市个数
//1、计算可行进的各城市选择概率
for (int m = 0; m < cityNum; m++)
{
//若城市（i,j）之间有路且j不在蚂蚁k的禁忌表中，则计算概率
if (dist(ants[k].loc, m) != -1 && !ifCityInTabu(m, k))
{
cityProb[c].num = m;
cityProb[c].prob = citySelProb(k, m);
c++;
}
}
//2、线性化选择概率
for (int m = 0; m < c; m++)
{
for (int n = m; n >= 0; n--)
{
lineCityProb[m] += cityProb[n].prob;
}
}
//3、产生随机数选择城市
double r = rand() / double(RAND_MAX);
int j = 0; //选取的目标城市
for (int m = 0; m < cityNum; m++)
{
if (r <= lineCityProb[m])
{
j = cityProb[m].num;
updateAnt(k, j);
if (j == f)
ants[k].flag = 1; //若蚂蚁k下一步城市为目的地城市，则修改标志
return j;
}
}
}
void updatePher()
{
for (int i = 0; i < antNum; i++)
{
if(ants[i].flag == 1) //只对到达目的点的蚂蚁所走过路径更新信息素
for (int j = 0; j < pathNum; j++)
{
if (ants[i].antPath[j] == -1 || ants[i].antPath[j + 1] == -1)
break;
else
nextPher(ants[i].antPath[j], ants[i].antPath[j + 1])
+= pQ / getAntLen(ants[i]);
}
}
nextPher = pVol * pher + nextPher;
}
const int cityNum = 8; //城市数量
const int pathNum = 16; //路径数量
const int antNum = 12; //蚂蚁数量（1.5倍城市数量）
const double pVol = 0.3; //信息素挥发系数 0.2~0.5
const int pQ = 10; //信息素强度 10~1000
const double pImp = 3; //信息素相对重要性 1~4
const double qImp = 4; //启发信息相对重要性 3~4.5
const int gen = 100; //迭代次数 100~500

复制代码

#include<iostream>
#include<Eigen\Dense>
#include<stdlib.h>
#include<time.h>
#include<math.h>
using namespace Eigen;
using namespace std;
/*
功能：此代码使用蚁群算法计算源点0 ~ 其他定点的最短路径
author：yuzewei
date：2020/12/19
*/
#define CLOCK_PER_SEC ((clock_t)1000)
const int cityNum = 8; //城市数量
const int pathNum = 16; //路径数量
const int antNum = 12; //蚂蚁数量（1.5倍城市数量）
const double pVol = 0.3; //信息素挥发系数 0.2~0.5
const int pQ = 10; //信息素强度 10~1000
const double pImp = 3; //信息素相对重要性 1~4
const double qImp = 4; //启发信息相对重要性 3~4.5
const int gen = 100; //迭代次数 100~500
struct ant //蚂蚁结构体
{
int loc; //位置
int tabu[cityNum]; //禁忌表
int antPath[pathNum]; //走过的路
bool flag; //是否到达终点7
};
struct ant ants[antNum]; //蚁群
typedef Matrix<double, 8, 8> Matrix8d;
Matrix8d dist; //距离矩阵
Matrix8d pher; //信息素矩阵
Matrix8d nextPher; //下一代信息素矩阵
Matrix8d insp; //启发信息矩阵
struct city //城市结构体
{
int num; //编号
double prob; //选择概率
};
struct city cityProb[cityNum]; //可到达城市组
double lineCityProb[cityNum]; //线性化可到达城市的选择概率
clock_t start, finish;
double duration;
void initAnts();
void initCityProb();
void initMarix();
bool ifCityInTabu(int, int);
int citySelect(int, int);
void updateAnt(int, int);
double citySelProb(int, int);
int getAntLen(ant);
int getBestPath();
void printBestPath(int, int);
void updatePher();
void evolution();
int main()
{
srand((unsigned)time(NULL));
evolution();
}
//蚁群初始化
void initAnts()
{
//初始化禁忌表与行走路线
for (int i = 0; i < antNum; i++)
{
for (int j = 0; j < cityNum; j++)
{
ants[i].tabu[j] = -1;
}
for (int j = 0; j < pathNum; j++)
{
ants[i].antPath[j] = -1;
}
}
//将蚂蚁放入城市
for (int i = 0; i < antNum; i++)
{
//ants[i].loc = rand() % 8;
ants[i].loc = 0;//出发点都在起点
ants[i].tabu[0] = ants[i].loc;
ants[i].antPath[0] = ants[i].loc;
ants[i].flag = 0;
}
}
//初始化城市选择概率数组
void initCityProb()
{
for (int i = 0; i < cityNum; i++)
{
cityProb[i].num = -1;
cityProb[i].prob = 0;
lineCityProb[i] = 0;
}
}
//初始化距离、信息素、启发信息矩阵
void initMarix()
{
dist = Matrix8d::Constant(8, 8, -1);
dist(0, 2) = 47;
dist(0, 4) = 70;
dist(0, 5) = 24;
dist(1, 3) = 31;
dist(1, 6) = 74;
dist(1, 7) = 79;
dist(2, 1) = 55;
dist(2, 3) = 88;
dist(2, 4) = 23;
dist(2, 6) = 66;
dist(3, 7) = 29;
dist(4, 1) = 31;
dist(4, 6) = 42;
dist(5, 2) = 25;
dist(5, 3) = 120;
dist(6, 7) = 66;
pher = Matrix8d::Zero();
nextPher = Matrix8d::Zero();
insp = Matrix8d::Zero();
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (dist(i, j) != -1)
{
insp(i, j) = 1 / dist(i, j);//启发信息为距离的倒数
pher(i, j) = 1; //信息素浓度初始值为1
}
}
}
}
//轮盘赌选择下一步行进城市
int citySelect(int k, int f)
{
int c = 0;//记录蚂蚁可行进的城市个数
//1、计算可行进的各城市选择概率
for (int m = 0; m < cityNum; m++)
{
//若城市（i,j）之间有路且j不在蚂蚁k的禁忌表中，则计算概率
if (dist(ants[k].loc, m) != -1 && !ifCityInTabu(m, k))
{
cityProb[c].num = m;
cityProb[c].prob = citySelProb(k, m);
c++;
}
}
//2、线性化选择概率
for (int m = 0; m < c; m++)
{
for (int n = m; n >= 0; n--)
{
lineCityProb[m] += cityProb[n].prob;
}
}
//3、产生随机数选择城市
double r = rand() / double(RAND_MAX);
int j = 0; //选取的目标城市
for (int m = 0; m < cityNum; m++)
{
if (r <= lineCityProb[m])
{
j = cityProb[m].num;
updateAnt(k, j);
if (j == f)
ants[k].flag = 1; //若蚂蚁k下一步城市为目的地城市，则修改标志
return j;
}
}
}
//更新蚂蚁信息
void updateAnt(int k, int l)
{
ants[k].loc = l;
for (int i = 0; i < cityNum; i++)
if (ants[k].tabu[i] == -1)
{
ants[k].tabu[i] = l;
break;
}
for (int i = 0; i < pathNum; i++)
if (ants[k].antPath[i] == -1)
{
ants[k].antPath[i] = l;
break;
}
}
//蚂蚁k从当前城市i选择下一步行进城市为j市的概率
double citySelProb(int k, int j)
{
double a, b, c, prob;
a = b = c = prob = 0;
int i = ants[k].loc;
a = pow(pher(i, j), pImp) + pow(insp(i, j), qImp);
for (int m = 0; m < cityNum; m++)
{
if (dist(i, m) != -1 && !ifCityInTabu(m, k))
{
b = pow(pher(i, m), pImp) + pow(insp(i, m), qImp);
c += b;
}
}
prob = a / c;
return prob;
}
//判断城市j是否在蚂蚁k的禁忌表中
bool ifCityInTabu(int j, int k)
{
for (int i = 0; i < cityNum; i++)
{
if (j == ants[k].tabu[i])
{
return 1;
//break;
}
}
return 0;
}
//计算路径长度
int getAntLen(struct ant a)
{
int len = 0;
for (int j = 0; j < pathNum; j++)
{
if (a.antPath[j] == -1 || a.antPath[j + 1] == -1)
break;
else
len += dist(a.antPath[j], a.antPath[j + 1]);
}
return len;
}
//计算最优路径对应的蚂蚁编号
int getBestPath()
{
int d[antNum];
int min;
int k; //蚂蚁k的路线到达目的地节点最短
for (int i = 0; i < antNum; i++)
{
d[i] = -1;
}
for (int i = 0; i < antNum; i++)
{
d[i] = getAntLen(ants[i]);
}
min = d[0];
k = 0;
for (int i = 1; i < antNum; i++)
{
if (d[i] < min && ants[i].flag == 1) // 最优路径只从到达目标点的蚂蚁中筛选
{
min = d[i];
k = i;
}
}
return k;
}
//打印最优路径、最短距离
void printBestPath(int k, int f)
{
cout << " 最短路径为：";
for (int i = 0; i < pathNum; i++)
{
if (ants[k].antPath[i] == -1)
break;
cout << ants[k].antPath[i];
if (ants[k].antPath[i+1] != -1)
cout << "->";
}
cout << endl;
cout << " 对应距离为：" << getAntLen(ants[k]) << endl;
}
//更新信息素矩阵
void updatePher()
{
for (int i = 0; i < antNum; i++)
{
if(ants[i].flag == 1) //只对到达目的点的蚂蚁所走过路径更新信息素
for (int j = 0; j < pathNum; j++)
{
if (ants[i].antPath[j] == -1 || ants[i].antPath[j + 1] == -1)
break;
else
nextPher(ants[i].antPath[j], ants[i].antPath[j + 1])
+= pQ / getAntLen(ants[i]);
}
}
nextPher = pVol * pher + nextPher;
}
//迭代
void evolution()
{
for (int f = 1; f < cityNum; f++)
{
cout << "【从源点0到定点" << f << "】" << endl;
cout << "开始迭代........." << endl;
//初始化参数
initAnts();
initMarix();
int g = 0; //当前代数
start = clock();
while (g < gen)
{
//1、蚁群内所有蚂蚁都到达目的地
int p = 0; //蚁群前进步数
while (p < pathNum)
{
for (int i = 0; i < antNum; i++)
{
if (ants[i].flag == 1)//到达目的地
continue;
citySelect(i, f);
initCityProb();
}
p++;
}
if (g == gen - 1)
{
cout << "达到最高迭代次数!" << endl;
printBestPath(getBestPath(), f);
}
//3、更新信息素矩阵
updatePher();
//4、初始化蚁群；更新信息素矩阵
initAnts();
pher = nextPher;
nextPher = Matrix8d::Zero();
g++;
}
finish = clock();
duration = ((double)finish - start) / CLOCK_PER_SEC;
cout << " 耗时：" << duration << "秒" << endl;
}
}

复制代码

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