蚁群算法原理及c++实现
//轮盘赌选择下一步行进城市int citySelect(int k, int f)
{
int c = 0;//记录蚂蚁可行进的城市个数
//1、计算可行进的各城市 选择概率
for (int m = 0; m < cityNum; m++)
{
//若城市（i,j）之间有路且j不在蚂蚁k的禁忌表中，则计算概率
if (dist(ants.loc, m) != -1 && !ifCityInTabu(m, k))
{
cityProb.num = m;
cityProb.prob = citySelProb(k, m);
c++;
}
}
//2、线性化选择概率
for (int m = 0; m < c; m++)
{
for (int n = m; n >= 0; n--)
{
lineCityProb += cityProb.prob;
}
}
//3、产生随机数选择城市
double r = rand() / double(RAND_MAX);
int j = 0; //选取的目标城市
for (int m = 0; m < cityNum; m++)
{
if (r <= lineCityProb)
{
j = cityProb.num;
updateAnt(k, j);
if (j == f)
ants.flag = 1;//若蚂蚁k下一步城市为目的地城市，则修改标志
return j;
}
}
}
void updatePher()
{
for (int i = 0; i < antNum; i++)
{
if(ants.flag == 1)//只对到达目的点的蚂蚁 所走过路径 更新信息素
for (int j = 0; j < pathNum; j++)
{
if (ants.antPath == -1 || ants.antPath == -1)
break;
else
nextPher(ants.antPath, ants.antPath)
+= pQ / getAntLen(ants);
}
}
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; //禁忌表
int antPath;//走过的路
bool flag; //是否到达终点7
};
struct ant ants; //蚁群
typedef Matrix<double, 8, 8> Matrix8d;
Matrix8d dist; //距离矩阵
Matrix8d pher; //信息素矩阵
Matrix8d nextPher; //下一代信息素矩阵
Matrix8d insp; //启发信息矩阵
struct city //城市结构体
{
int num; //编号
double prob; //选择概率
};
struct city cityProb; //可到达城市组
double lineCityProb; //线性化 可到达城市的选择概率
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.tabu = -1;
}
for (int j = 0; j < pathNum; j++)
{
ants.antPath = -1;
}
}
//将蚂蚁放入城市
for (int i = 0; i < antNum; i++)
{
//ants.loc = rand() % 8;
ants.loc = 0;//出发点都在起点
ants.tabu = ants.loc;
ants.antPath = ants.loc;
ants.flag = 0;
}
}
//初始化城市选择概率数组
void initCityProb()
{
for (int i = 0; i < cityNum; i++)
{
cityProb.num = -1;
cityProb.prob = 0;
lineCityProb = 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.loc, m) != -1 && !ifCityInTabu(m, k))
{
cityProb.num = m;
cityProb.prob = citySelProb(k, m);
c++;
}
}
//2、线性化选择概率
for (int m = 0; m < c; m++)
{
for (int n = m; n >= 0; n--)
{
lineCityProb += cityProb.prob;
}
}
//3、产生随机数选择城市
double r = rand() / double(RAND_MAX);
int j = 0; //选取的目标城市
for (int m = 0; m < cityNum; m++)
{
if (r <= lineCityProb)
{
j = cityProb.num;
updateAnt(k, j);
if (j == f)
ants.flag = 1;//若蚂蚁k下一步城市为目的地城市，则修改标志
return j;
}
}
}
//更新蚂蚁信息
void updateAnt(int k, int l)
{
ants.loc = l;
for (int i = 0; i < cityNum; i++)
if (ants.tabu == -1)
{
ants.tabu = l;
break;
}
for (int i = 0; i < pathNum; i++)
if (ants.antPath == -1)
{
ants.antPath = l;
break;
}
}
//蚂蚁k从当前城市i选择下一步行进城市为j市的概率
double citySelProb(int k, int j)
{
double a, b, c, prob;
a = b = c = prob = 0;
int i = ants.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.tabu)
{
return 1;
//break;
}
}
return 0;
}
//计算路径长度
int getAntLen(struct ant a)
{
int len = 0;
for (int j = 0; j < pathNum; j++)
{
if (a.antPath == -1 || a.antPath == -1)
break;
else
len += dist(a.antPath, a.antPath);
}
return len;
}
//计算最优路径对应的蚂蚁编号
int getBestPath()
{
int d;
int min;
int k;//蚂蚁k的路线到达目的地节点最短
for (int i = 0; i < antNum; i++)
{
d = -1;
}
for (int i = 0; i < antNum; i++)
{
d = getAntLen(ants);
}
min = d;
k = 0;
for (int i = 1; i < antNum; i++)
{
if (d < min && ants.flag == 1)// 最优路径只从到达目标点的蚂蚁中筛选
{
min = d;
k = i;
}
}
return k;
}
//打印最优路径、最短距离
void printBestPath(int k, int f)
{
cout << "最短路径为：";
for (int i = 0; i < pathNum; i++)
{
if (ants.antPath == -1)
break;
cout << ants.antPath;
if (ants.antPath != -1)
cout << "->";
}
cout << endl;
cout << "对应距离为：" << getAntLen(ants) << endl;
}
//更新信息素矩阵
void updatePher()
{
for (int i = 0; i < antNum; i++)
{
if(ants.flag == 1)//只对到达目的点的蚂蚁 所走过路径 更新信息素
for (int j = 0; j < pathNum; j++)
{
if (ants.antPath == -1 || ants.antPath == -1)
break;
else
nextPher(ants.antPath, ants.antPath)
+= pQ / getAntLen(ants);
}
}
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.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;
}
}
页:
[1]