精华内容
下载资源
问答
  • 简单蚁群算法C++代码

    2017-04-19 11:56:07
    简单蚁群算法C++代码
  • 蚁群算法C++程序

    2017-08-14 10:38:35
    蚁群算法C++实现
  • 蚁群算法c++源程序,修改部分数值可以直接使用
  • 蚁群算法 c++程序

    2018-06-06 10:11:08
    蚁群算法c++语言程序,求解TSP旅行商问题,可对任意数据求解
  • 蚁群算法C++

    2017-10-16 12:12:19
    该程序是以蚁群系统为模型写的蚁群算法程序(强调:非蚂蚁周模型),以三个著名的TSP问题为测试对象 //通过微调参数,都可以获得较好的解 有详细的注释文档
  • 蚁群算法C++实现

    2015-05-11 22:39:01
    蚁群算法的MFC程序,可以导入excel文件形式的地图信息
  • 资源完整的包含了在vs上运行的所有文件,下载后用vs打开即可运行。
  • 蚁群算法C++ vs2013

    2018-06-08 09:12:31
    上传了几个代码资源,都是课程作业。 对算法不理解的话就去看博客吧。
  • 资源包括详细的代码和注释,代码由VS2005 编写,附有可执行文件和源代码。附有说明文档可供参考。
  • 这是我做课题的一个初步的试验程序,代码质量不是很高,但能正确运行。这是将并行程序在串行运行
  • 蚁群算法状态维数5维,动作维数5维,可以使用网络调试助手连接调试,具体内容见代码 推荐资源 ...
  • 蚁群算法原理及c++实现

    千次阅读 多人点赞 2021-01-11 13:31:47
    一、原理 1. 蚂蚁觅食行为 蚁群在寻找食物时,总能找到一条蚁穴到食物的最短路径,并且能随着...2.蚁群算法 又称蚂蚁算法,是一种基于群体智能的算法,用来在图中寻找优化路径的概率型。它由Marco Dorigo于1992年在他的

    参考博客
    https://blog.csdn.net/Oudasheng/article/details/84994336
    https://blog.csdn.net/wayjj/article/details/72809344#commentsedit
    https://blog.csdn.net/Oudasheng/article/details/84994336
    https://www.cnblogs.com/mahaitao/p/5572095.html
    https://www.cnblogs.com/Horizon-asd/p/12723886.html
    https://blog.csdn.net/chen10217/article/details/100762552

    一、原理

    1. 蚂蚁觅食行为

    蚁群在寻找食物时,总能找到一条蚁穴到食物的最短路径,并且能随着环境的变化而更新最优路径。究其原因,是因为蚂蚁在运动过程中,会在所经过路径上留下一种称为信息素(pheromone)的物质,其他蚂蚁在运动中可以感知到这种物质,并以此来指导自己的运动方向。
    蚁群的这种行为表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率越大。

    2.蚁群算法

    又称蚂蚁算法,是一种基于群体智能的算法,用来在图中寻找优化路径的概率型。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在解决实际问题时,人工蚁群相较于自然蚁群有一定的记忆能力,可记住已访问过的节点,其次人工蚁群在选择路径时依照一定规律,并不是盲目的。蚁群算法常用来解决路径规划等离散优化问题,如旅行商问题(TSP)、指派问题、调度问题。

    2,1 特点

    1. 正反馈:可较快发现较优解。
    2. 分布式:基于种群的进化算法,本质具有并行性,易于并行实现。
    3. 启发式搜索:反映搜索中的的先验性和确定性因素(如距离)强度。
    4. 鲁棒性强:不易受某个个体影响。

    2.2 算法流程(以TSP问题为例)

    TSP问题:一商人去n个城市销货,所有城市走一遍再回到起点,使所走路程最短。

    1. 初始化相关参数:蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数和最大迭代次数等。将城市信息读入程序并进行预处理,即将城市间信息转化为矩阵。
    2. 随机将蚂蚁放入不同出发点,计算每个蚂蚁的下一步要访问的城市,直到有蚂蚁访问完所有城市。
    3. 计算每个蚂蚁经过的路径长度Lk,记录当前迭代次数下的最优解(访问完所有城市且路径长度最短),更新各条路径上的信息素浓度。
    4. 断是否达到最大迭代次数,若否则返回步骤2,若是则顺序执行。
    5. 输出最优路径和相关指标,如运行时间和迭代次数。

    2.3 相关公式

    在这里插入图片描述
    在这里插入图片描述

    2.4 流程图

    在这里插入图片描述

    三、例子

    试设计一个并行算法,求下图中一个源点到其他定点的最短路径。(VS2019+Eigen)
    在这里插入图片描述

    3.1 关键代码

    数据结构:

    将蚂蚁设置为一个结构体,包含所在位置、禁忌表、所走路径和是否到达终点标志四项内容。为了便于计算,将信息素、启发信息与距离信息分别在8*8的矩阵中存放,这样可以调用Eigen库直接进行矩阵计算,达到更新信息素的目的。
    城市也设为一个结构体,包含城市编号和选择概率两项内容。这里将城市设置为结构体,主要是考虑到在选择下一步行进城市时,要先计算选择概率再通过轮盘赌来确定下一步城市,轮盘赌时需要将城市编号与其选择概率一一对应。
    具体代码部分如下:

    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];     //线性化 可到达城市的选择概率
    

    城市选择方式

    当蚂蚁k选择下一步要去的城市时,有以下几个步骤:

    1. 对照蚂蚁k的禁忌表,求出下一步所有可去的城市各自的选择概率(概率计算见公式(1));
    2. 线性化所有可去城市的概率,生成介于0~1之间的随机数(线性化概率的目的是实现轮盘赌);
    3. 使用轮盘赌方法选择下一步要去的城市。
      概率计算与轮盘赌选择对应代码片如下:
    //轮盘赌选择下一步行进城市
    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;
    		}
    
    	}
    }
    

    信息素更新

    因为将信息素存入矩阵,所以在计算时较为简单,具体分为如下几步:

    1. 计算信息素增量矩阵:
      for k = 1 to m do (遍历蚁群)
      for j = 1 to n do (遍历蚂蚁k的行走路径)
         计算蚂蚁k在路径(i, j)对应的信息素增量(见公式(3));
      更新路径(i, j)在上一轮的信息素增量;
        end for
      end for
    2. 计算更新后的信息素矩阵:
      信息素挥发系数*信息素矩阵+信息素增量矩阵(见公式(2))。
      对应代码片如下:
     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;
    }
    

    3.2 运行结果

    参数设置

    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
    

    运行结果

    在这里插入图片描述

    问题

    1. 各项参数初始值虽然知道设置范围,但因为不够理解参数如何影响迭代的结果,参数设定主要依靠猜测。
    2. 代码运行后,发现回归太早,不符合蚁群算法回归较慢(200~500)的特点,后经过检查,发现是计算蚂蚁k在路径(i,j)上的信息素增量时,将除数Lk理解成了路径(i,j) 的距离,但实际上应该为蚂蚁k本次迭代中做走过路径距离之和。经修改后,可以符合蚁群算法回归较慢的特点。
    3. 只计算源点到某一个定点时,代码没有问题,循环结算到每个顶点最短路径时,有时运行会报如下错误,有时不会,不太明白。
      在这里插入图片描述

    源码

    #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;
    	}
    
    }
    
    展开全文
  • 用MATLAB 实现,基于栅格地图的蚁群算法路径规划,含蚁群相关文档。
  • C++蚁群算法

    2021-04-17 16:33:17
    C++基本蚁群算法,实现定点到任意位置的最短距离(含距离txt) ** 1.参考博客:https://blog.csdn.net/weixin_43686942/article/details/112462825 主要在此博客上做了修改,修改了原博客BUG的产生(主要原因是内存...

    **

    C++基本蚁群算法,实现定点到任意位置的最短距离(含距离txt)

    **

    1.参考博客:https://blog.csdn.net/weixin_43686942/article/details/112462825
    主要在此博客上做了修改,修改了原博客BUG的产生(主要原因是内存不足和数组越界)。

    2.关于蚁群算法的知识可参考以下资料:
    链接:https://pan.baidu.com/s/1GITbyt_ygnN3mIMINHgAfQ
    提取码:RBLG

    3.data.txt数据如下:

    **-1 10 6 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    10 -1 -1 -1 -1 10 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    6 -1 -1 8 20 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    8 -1 8 -1 -1 -1 10 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    -1 -1 20 -1 -1 7 -1 -1 -1 18 30 -1 -1 -1 -1 -1 -1 -1 -1
    -1 10 10 -1 7 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1
    -1 20 -1 10 -1 -1 -1 -1 -1 10 10 -1 -1 -1 -1 -1 -1 -1 -1
    -1 -1 -1 12 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 25 -1 -1 -1 -1
    -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 15 -1 20 -1 -1 -1 -1 -1
    -1 -1 -1 -1 18 10 10 -1 7 -1 7 -1 -1 15 -1 -1 -1 -1 -1
    -1 -1 -1 -1 30 -1 10 12 -1 7 -1 -1 20 -1 15 -1 -1 -1 -1
    -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 8 -1 -1 8 16 -1 -1
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 20 8 -1 -1 -1 8 -1 17 -1
    -1 -1 -1 -1 -1 -1 -1 -1 20 15 -1 -1 -1 -1 12 -1 8 -1 -1
    -1 -1 -1 -1 -1 -1 -1 25 -1 -1 15 -1 -1 12 -1 -1 -1 10 -1
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 8 -1 -1 -1 -1 -1 12
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 16 -1 8 -1 -1 -1 7 7
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 17 -1 10 -1 7 -1 11
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 7 11 -1 **
    在这里插入图片描述

    4.具体代码和运行结果如下:

    运行结果:

    在这里插入图片描述按下Q或q键可停止迭代

    #include<iostream>
    #include<string>
    #include<math.h>
    #include<fstream>
    #include<vector>
    #include<map>
    #include<unordered_map>
    #include<algorithm>
    #include<conio.h>
    
    using namespace std;
    
    #pragma region 变量与常量的定义
    
    //数据文件存放的路径
    constexpr auto FILE_PATH = "D:\\data.txt";
    //城市数量
    const int CITY_NUMBER = 19;
    //蚂蚁数量(一般为城市数量的1.5倍)
    const int ANT_NUMBER = 50;
    //最大迭代次数
    const int  MAX_ITERATIONS_NUMBER = 150;
    //路径数量
    const int  PATH_NUMBER = 74;
    //启发因子,信息素浓度重要性
    const double ALPHA = 1.0;
    //启发式重要性
    const double BETA = 2.0;
    //蚂蚁所携带总的信息素
    const double Q = 100.0;
    //信息素蒸发系数
    const double ROU = 0.5;
    
    //两两城市之间的信息素矩阵
    vector<vector<double>> pheromoneMatrix;
    //两两城市之间的距离
    vector<vector<double>> cityDistance;
    //下一代的信息素矩阵
    vector<vector<double>> nextPheromoneMatrix;
    //启发信息矩阵=1/cityDistance[i][j]
    vector<vector<double>> inspMartix;
    
    //关键字:string类型,值:int类型。分别对应保存每次迭代的最优路径和对应的路径距离。
    map<string, int>routResult;
    //含有充电设施的站点编号
    vector<int>rechargeNumber = { 3,4,7,8,12,14,16 };
    
    #pragma endregion
    
    #pragma region 蚂蚁
    class Ant {
    public:
    	//蚂蚁的当前位置
    	int antLoc;
    	//蚂蚁的禁忌表,存放已访问过的点
    	int taBu[CITY_NUMBER];
    	//蚂蚁走过路径的点的集合
    	int antPath[PATH_NUMBER];
    	//判断蚂蚁是否已经到达终点。True:表示到达,FALSE:表示未到达。
    	bool flag;
    };
    //初始化蚁群,大小为ANT_NUMBER
    Ant antColony[ANT_NUMBER];
    #pragma endregion
    
    #pragma region 城市 
    class City {
    public:
    	//城市编号
    	int cityNum;
    	//选择每个点的概率
    	double cityProb;
    };
    //初始化城市
    City cityArray[CITY_NUMBER];
    //线性化选择概率,用于轮盘赌算法
    double lineCityProb[CITY_NUMBER];
    #pragma endregion 
    
    #pragma region 矩阵初始化功能函数
    //res:表示待初始化的矩阵
    //temp:表示矩阵初始化的值
    void initMatrix(vector<vector<double>> &res, int temp) {
    	//定义中间变量v
    	vector<double>v;
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		//清空v
    		vector<double>().swap(v);
    		for (int j = 0; j < CITY_NUMBER; ++j) {
    			v.push_back(temp);
    		}
    		res.push_back(v);
    	}
    }
    #pragma endregion
    
    #pragma region 返回指定范围内的随机数
    ///		返回指定范围内的随机浮点数
    ///     @param dbLow		范围起始数    
    ///     @param dbUpper  范围终止数
    ///     @return					返回的此范围内的随机数 
    double randomNumber(double dbLow, double dbUpper)
    {
    	double dbTemp = rand() / ((double)RAND_MAX + 1.0);
    	return dbLow + dbTemp * (dbUpper - dbLow);
    }
    #pragma endregion
    
    #pragma region 蚁群初始化
    void initAntsColony() {
    	//初始化禁忌表和行走路线
    	for (int i = 0; i < ANT_NUMBER; ++i) {
    		for (int j = 0; j < CITY_NUMBER; ++j) {
    			//初始化蚁群的禁忌表,设置每只蚂蚁的禁忌表初始化为-1,代表从未访问任何点
    			antColony[i].taBu[j] = -1;
    		}
    		for (int j = 0; j < PATH_NUMBER; ++j) {
    			//初始化蚁群的行走路径,设置每只蚂蚁的路径初始化为-1,代表还未经过任何点
    			antColony[i].antPath[j] = -1;
    		}
    	}
    
    	//将蚂蚁放入初始位置,此处设置每只蚂蚁的出发点为0,代表从源点出发
    	for (int i = 0; i < ANT_NUMBER; ++i) {
    		//设置蚂蚁的当前位置为出发位置0
    		antColony[i].antLoc = 0;
    		//将当前位置更新到每只蚂蚁的禁忌表中,代表已经访问过此点
    		antColony[i].taBu[0] = 0;
    		//将当前位置更新到每只蚂蚁的行走路径中,代表路径中已有此点
    		antColony[i].antPath[0] = 0;
    		//将每只蚂蚁的flag设置为0,代表每只蚂蚁都还未到达终点
    		antColony[i].flag = 0;
    	}
    }
    #pragma endregion
    
    #pragma region 初始化城市
    void initCity() {
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		//初始化城市结构体
    		//初始化每个城市的编号为-1
    		cityArray[i].cityNum = -1;
    		//初始化每个城市的选择概率为0
    		cityArray[i].cityProb = 0;
    		//初始化线性选择概率为0
    		lineCityProb[i] = 0;
    	}
    }
    #pragma endregion
    
    #pragma region 初始化所需的各种矩阵,并读取文件距离数据
    void initVariousMatrix() {
    	//初始化城市距离矩阵为-1
    	initMatrix(cityDistance, -1);
    
    	/*             数据文件的读取                */
    
    
    	//创建文件流对象
    	ifstream CityFile;
    	//打开文件
    	CityFile.open(FILE_PATH, ios::in);
    	//如果文件打开失败,则退出
    	if (!CityFile.is_open()) {
    		cout << "Open file failure" << endl;
    		exit(0);
    	}
    	//从文件中读取数据到城市距离矩阵之中
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		for (int j = 0; j < CITY_NUMBER; ++j) {
    			CityFile >> cityDistance[i][j];
    		}
    	}
    	//关闭文件
    	CityFile.close();
    
    	//初始化信息素矩阵为0
    	 initMatrix(pheromoneMatrix, 0);
    	//初始化下一代信息素矩阵为0
    	initMatrix(nextPheromoneMatrix, 0);
    	//初始化启发信息矩阵为0
    	 initMatrix(inspMartix, 0);
    
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		for (int j = 0; j < CITY_NUMBER; ++j) {
    			if (cityDistance[i][j] != -1) {                 //如果两个城市之间有距离
    				inspMartix[i][j] = 1 / cityDistance[i][j];//启发信息为两两城市距离的倒数
    				pheromoneMatrix[i][j] = 1;                //路径上信息素浓度初始值为1
    			}
    		}
    	}
    }
    #pragma endregion
    
    #pragma region 判断城市j是否在蚂蚁k的禁忌表中
    bool ifCityInTabu(int k, int j) {
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		//如果城市j,已经在蚂蚁k的禁忌表中,则返回1
    		if (j == antColony[k].taBu[i]) {
    			return 1;
    		}
    	}
    	//如果不在蚂蚁k的禁忌表中,则返回0
    	return 0;
    }
    #pragma endregion
    
    #pragma region 蚂蚁k从当前城市i选择下一步行进的城市j的概率
    double nextCitySelProb(int k, int j) {
    	//初始化选择概率公式的分子
    	double p = 0;
    	//初始化选择概率公式的分母
    	double sum = 0;
    	//i保存蚂蚁k的当前位置
    	int i = antColony[k].antLoc;
    	//计算P
    	p = pow(pheromoneMatrix[i][j], ALPHA) + pow(inspMartix[i][j], BETA);
    	//计算sum
    	for (int m = 0; m < CITY_NUMBER; ++m) {
    		if (cityDistance[i][j] != -1 && !ifCityInTabu(k, m)) {
    			sum += pow(pheromoneMatrix[i][m], ALPHA) + pow(inspMartix[i][m], BETA);
    		}
    	}
    	//返回从i--j的选择概率
    	return (p / sum);
    }
    #pragma endregion
    
    #pragma region 更新蚂蚁k的禁忌表信息
    void updateAntTabu(int k, int j) {
    	//蚂蚁k的当前位置赋值为j
    	antColony[k].antLoc = j;
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		//如果蚂蚁k还未访问过j,则将蚂蚁k的禁忌表信息添加j
    		if (antColony[k].taBu[i] == -1) {
    			antColony[k].taBu[i] = j;
    			break;
    		}
    	}
    	//同理,将蚂蚁k的行走路径中更新一个j
    	for (int i = 0; i < PATH_NUMBER; ++i) {
    		if (antColony[k].antPath[i] == -1) {
    			antColony[k].antPath[i] = j;
    			break;
    		}
    	}
    }
    #pragma endregion
    
    #pragma region 轮盘赌选择下一步行进的城市
    //蚂蚁k,选择前进的地点j的概率
    int nextCitySelect(int k, int f) {
    
    	//记录蚂蚁可行进的城市个数,用于后面的计算
    	int c = 0;
    
    	//step 1:计算可行进的各城市的选择概率
    	for (int m = 0; m < CITY_NUMBER; ++m) {
    		//若城市(i,j)之间有路且j不在蚂蚁k的禁忌表中,则计算概率
    		if (cityDistance[antColony[k].antLoc][m] != -1 && !ifCityInTabu(k, m)) {
    			//对应的城市编号存入数组中
    			cityArray[c].cityNum = m;
    			//选择概率存入数组中
    			cityArray[c].cityProb = nextCitySelProb(k, m);
    			++c;
    		}
    	}
    
    	//step 2:线性化选择概率
    	for (int m = 0; m < c; ++m) {
    		for (int n = m; n >= 0; n--) {
    			//用于轮盘赌算法,将选择概率线性化累加
    			lineCityProb[m] += cityArray[n].cityProb;
    		}
    	}
    
    	//step 3 产生随机数选择城市
    	//产生随机浮点数,范围0-1
    	double r = randomNumber(0, 1);
    	//选取的目标城市
    	int j = 0;
    	for (int m = 0; m < CITY_NUMBER; ++m) {
    		if (r <= lineCityProb[m]) {
    			//将当前选择前进的城市编号赋值给j
    			j = cityArray[m].cityNum;
    			//将地点j更新至蚂蚁k的禁忌表中,代表已经访问过此点
    			updateAntTabu(k, j);
    			if (j == f) {
    				//若蚂蚁k下一步城市为目的地城市,则修改标志为1
    				antColony[k].flag = 1;
    			}
    			//return j;
    			return 0;
    		}
    	}
    	//return f;
    	return 0;
    
    }
    #pragma endregion
    
    #pragma region 计算路径长度
    int getAntLen(Ant ant) {
    	//定义路径长度为0
    	int len = 0;
    	for (int i = 0; i < PATH_NUMBER - 1; ++i) {
    		//如果蚂蚁行走的路径中有-1,表示未走过此点,则退出循环
    		if (ant.antPath[i] == -1 || ant.antPath[i + 1] == -1)
    			break;
    		//若走过有路径,则不断累加距离结果
    		else
    			len += cityDistance[ant.antPath[i]][ant.antPath[i + 1]];
    	}
    	//返回路径长度
    	return len;
    }
    #pragma endregion
    
    #pragma region 计算最优路径对应的蚂蚁编号
    int getBestPathAntNumber() {
    	//初始化数组d为-1,保存所有蚂蚁的行走路径
    	vector<int>d(ANT_NUMBER, -1);
    	//假设定义蚂蚁k的路线到达目的地节点最短,即走过的路径为最短路径
    	int k = 0;
    	//将所有路径距离存入d中
    	for (int i = 0; i < ANT_NUMBER; i++)
    	{
    		d.push_back(getAntLen(antColony[i]));
    	}
    	//定义指向最小路径的迭代器
    	auto min = min_element(d.begin(), d.end());
    	//计算此最短路径所对应的下标,此为蚂蚁的编号k
    	k = distance(d.begin(), min);
    	vector<int>(d).swap(d);
    	//返回蚂蚁k
    	return k;
    }
    #pragma endregion
    
    #pragma region 打印最优路径所对应的蚂蚁K的路径和距离
    void printBestPath(int k, int f) {
    	//初始化变量res,存放路线
    	string res = "";
    	cout << " 最短路径为:";
    
    	for (int i = 0; i < PATH_NUMBER - 1; ++i) {
    		//如果蚂蚁k的第i条路径为-1,表示没有走过此点,退出循环
    		if (antColony[k].antPath[i] == -1)
    			break;
    		//打印蚂蚁k的第i条路径
    		cout << antColony[k].antPath[i];
    
    
    		//将路径转化为字符串形式存入res中,方便打印输出
    		res += to_string(antColony[k].antPath[i]);
    
    		//若蚂蚁k的i+1条路径不为-1,代表访问过此点。即i--->i+1有路线。
    		if (antColony[k].antPath[i + 1] != -1) {
    			//打印"->"
    			cout << "->";
    
    
    			// 若此点含有充电设施
    			if (find(rechargeNumber.begin(), rechargeNumber.end(), antColony[k].antPath[i + 1]) != rechargeNumber.end()) {
    				res += "->(可充电站点)";
    			}
    			else {
    				res += "->";
    			}
    
    		}
    
    	}
    	cout << endl;
    	cout << " 对应距离为:" << getAntLen(antColony[k]) << endl;
    
    	//把每次距离结果保存到map中:关键字:路线,值:对应的路径长度
    	routResult[res] = getAntLen(antColony[k]);
    	res.swap(res);
    	//return routResult;
    }
    #pragma endregion
    
    #pragma region 更新信息素矩阵
    void updatePherMartix() {
    	for (int i = 0; i < ANT_NUMBER; ++i) {
    		//全局更新信息素矩阵
    		if (antColony[i].flag == 1) {
    			for (int j = 0; j < PATH_NUMBER - 1; ++j) {
    				if (antColony[i].antPath[j] == -1 || antColony[i].antPath[j + 1] == -1)
    					break;
    				else
    					nextPheromoneMatrix[antColony[i].antPath[j]][antColony[i].antPath[j + 1]]
    					+= Q / getAntLen(antColony[i]);
    			}
    		}
    	}
    	//更新下一代信息素矩阵
    	for (int i = 0; i < CITY_NUMBER; ++i) {
    		for (int j = 0; j < CITY_NUMBER; ++j) {
    			nextPheromoneMatrix[i][j] =
    				(1 - ROU) * pheromoneMatrix[i][j] + nextPheromoneMatrix[i][j];
    		}
    	}
    
    }
    #pragma endregion
    
    #pragma region 迭代过程
    void evolution(int city) {
    
    
    	cout << "开始进行迭代........." << endl;
    
    	//初始化参数
    	initAntsColony();
    	initCity();
    	initVariousMatrix();
    
    
    	int gen = 0;
    	while (gen < MAX_ITERATIONS_NUMBER) {
    		int p = 0;
    		while (p <11) {
    			for (int i = 0; i < ANT_NUMBER; ++i) {
    				if (antColony[i].flag == 1)
    					continue;
    				nextCitySelect(i, city);
    				initCity();
    			}
    			++p;
    		}
    
    		
    
    		if (gen == MAX_ITERATIONS_NUMBER - 1) {
    			cout << " 迭代完成,输出结果" << endl;
    			printBestPath(getBestPathAntNumber(), city);
    
    		}
    		
    		
    		//更新信息素矩阵
    		updatePherMartix();
    		//蚁群初始化
    		initAntsColony();
    		pheromoneMatrix = nextPheromoneMatrix;
    	    initMatrix(nextPheromoneMatrix, 0);
    		++gen;
    	}
    
    }
    #pragma endregion
    
    #pragma region 释放vector内存空间,避免内存无限增加而崩溃
    void deleArrary() {
    	vector<vector<double>>().swap(cityDistance);
    	vector<vector<double>>().swap(pheromoneMatrix);
    	vector<vector<double>>().swap(nextPheromoneMatrix);
    	vector<vector<double>>().swap(inspMartix);
    	//map<string, int>().swap(routResult);
    }
    #pragma endregion
    
    #pragma region 按从小到大的顺序将vec内部value值进行排序,并打印出结果
    void sortMap(map<string, int>t) {
    	//routeResult存入vec中,方便将结果进行排序
    	vector<pair<string, int>>vec;
    	for (const auto& n : t) {
    		vec.push_back(make_pair(n.first, n.second));
    	}
    	//将结果按照路径,从小到达进行排序
    	sort(vec.begin(), vec.end(), [](const pair<string, int>& x, const pair<string, int>& y)
    		-> int {
    			return x.second < y.second;
    		});
    
    	//输出排序好的所有结果
    	cout << "可供选择的路径中,从小到大为:" << endl;
    	int i = 1;
    	for (auto v : vec) {
    		cout << "第" << i << "条路径为:         ";
    		cout << v.first << " " << "距离为:"
    			<< v.second << endl;
    		++i;
    	}
    
    
    	cout << endl;
    	cout << "建议采纳的最佳路线为:" << vec[0].first << " "
    		<< "此路线距离最短,耗时最小为:"
    		<< vec[0].second << endl;
    
    
    	for (auto v : vec)
    	{
    		if (vec[0].first.find("可充电站点") != -1) {
    			break;
    		}
    		else if (v.first.find("可充电站点") != -1) {
    			cout << "若需要中途停靠充电,建议采纳的最佳路线为:"
    				<< v.first
    				<< "    此路线含有充电设施,总的路径为:"
    				<< v.second
    				<< endl;
    			break;
    		}
    	}
    
    	t.swap(t);
    	vector<pair<string, int>>().swap(vec);
    }
    #pragma endregion
    
    #pragma region 程序入口
    
    	int main() {
    	cout << " 请输入你要去往的城市:" << endl;
    	int city;
    	cin >> city;
    
    	//不断循环迭代,将每次循环的最优结果保存到routResult中
    	while (1) {
    		//随机化种子,用于生成随机数
    		srand((unsigned)time(NULL));
    		//开始进入迭代过程
    		evolution(city);
    		//每次迭代完成后,清空数组数据
    		deleArrary();
    		//判断键盘响应
    		if (_kbhit()) {
    			//如果读取到键盘按下'q'或'Q'键,则退出循环,结束整个过程
    			if (tolower(_getch()) == 'q') {
    				break;
    			}
    		}
    	}
    
    
    	//int x = 20;
    	//while (x) {
    	//	//随机化种子,用于生成随机数
    	//	srand((unsigned)time(NULL));
    	//	//开始进入迭代过程
    	//	evolution(city);
    	//	//每次迭代完成后,清空数组数据
    	//	deleArrary();
    	//	--x;
    	//}
    
    	//将所有保存的结果按照从小到大进行排序输出,并打印出最佳结果
    	sortMap(routResult);
    	return 0;
    }
    #pragma endregion
    
    
    
    
    展开全文
  • C++蚁群算法,带图,超详细

    千次阅读 2020-06-19 23:49:45
    使用C++编写蚁群算法+2-opt局部搜索算法的结合版,并调用python的matplotlib库显示结果。TSPlib中ch150的数据仅相差3.1% ch150.txt的格式为:第一行是已知最优路径,第二行开始每行都是城市编号与坐标,城市编号顺序...

    使用C++编写蚁群算法+2-opt局部搜索算法的结合版,并调用python的matplotlib库显示结果。TSPlib中ch150的数据仅相差3.1%。(150城)
    ch150.txt的格式为:第一行是已知最优路径,第二行开始每行都是城市编号与坐标,城市编号顺序递增。

    如果有误,请多指教。
    分为两个文件"main.cpp"存放main函数,"Head.h"存放其他一切。

    //main.cpp
    #include"Head.h"
    
    int main() {
    	//更新随机种子
    	srand((unsigned)time(NULL));
    
    	Graph* graph = new Graph;
    
    	graph->readCity();//启用文件读取,注销掉则为随机构造城市
    
    	graph->innitial_Graph();
    	AntColony* ant_colony = new AntColony;
    	ant_colony->innitial_AntColony();
    
    	for (int NC_now = 0; NC_now < NC_MAX; ++NC_now) {
    		for (int i = 1; i < N; ++i) {
    			ant_colony->ChooseNextCity(graph, i);
    		}
    		ant_colony->Update(graph,NC_now);
    		ant_colony->innitial_AntColony();
    	}
    	
    	cout << "The BestLength=" << BestLength << endl;
    
    	ShowByPython(graph);
    
    	int last, next;
    	double sum = 0;
    	for (int i = 1; i < N; ++i) {
    		last = BestPath[i-1];
    		next = BestPath[i];
    		cout << "Travel " << i << " : " << last << "   \t-> " << next << " \tdistante: " << graph->Length[last][next] << endl;
    		sum += graph->Length[last][next];
    	}
    	last = BestPath[N - 1];
    	next = BestPath[0];
    	cout << "Travel " << N << " : " << last << "   \t-> " << next << " \tdistante: " << graph->Length[last][next] << endl;
    	sum += graph->Length[last][next];
    	cout << "最优解路程和 = " << sum << endl;
    	cout << "TSPlib上的已知最优解 :" << graph->KnowBest << endl;
    	cout << "与已知最优解的偏差为 :" << ((sum - graph->KnowBest) / graph->KnowBest) * 100 << "%" << endl;//最后两句必须启用文件读取才有效
    
    	delete graph;
    	delete ant_colony;
    	return 0;
    }
    
    //Head.h
    #include<iostream>
    #include<cstdlib>
    #include<string>
    #include<cmath>
    #include<fstream>
    #include<Python.h>
    using namespace std;
    #define PATH "E:\\TSPlib\\ch150.txt"//TSPlib数据文件的路径
    
    #define N 150		//城市数量
    #define M 100		//蚂蚁数量
    #define NC_MAX 1200	//迭代次数
    #define α 1		//信息素浓度重要性
    #define β 1		//启发式重要性
    #define Q 100		//蚂蚁所携带信息素
    #define ρ 0.2		//蒸发系数
    
    //注意:如果从文件中读取City,目前需要手动调整城市数量N,要与文件中保持一致
    //并且修改 PATH 路径与启用main函数中的readCity函数
    
    //以下数据结构用于最后分析
    int BestPath_PerRound[NC_MAX][N] = { 0 };//记录每轮的最优路径
    double BestLength_PerRound[NC_MAX] = { 0 };//记录每轮最优路径的长度
    int BestPath[N] = { 0 };//全局最短路径(后一轮迭代未必一定比前一轮更优,只是总体是这样,不绝对),不保存每轮的信息
    double BestLength = 1000000;//全局最短路径长度
    double AverageLength_PerRound[NC_MAX] = { 0 };//记录每轮所有蚂蚁所走路径的平均长度
    
    class City {
    public:
    	//无参构造函数,创建城市时默认在[0,999]内随机获得x,y坐标
    	City() {
    		x = rand() % 1000;
    		y = rand() % 1000;
    	}
    	double x;
    	double y;
    };
    class Graph {
    public:
    	City citys[N];//无参构造函数创建N个城市
    	double Length[N][N] = { 0 };//路径长度表
    	double tao[N][N] = { 0 };//信息素浓度表
    	double Heuristic[N][N] = { 0 };//启发式表,将城市之间距离的倒数作为启发函数
    public:
    	//使用fstream读取文件中的城市坐标,并创建城市
    	int KnowBest;//读取文件时存放已知最优解
    	void readCity() {
    		ifstream CityFile;
    		CityFile.open(PATH, ios::in);
    		if (!CityFile.is_open()) {
    			cout << "Open file failure" << endl;
    			exit(0);
    		}
    		CityFile >> KnowBest;
    		cout << "The known best result is :" << KnowBest << endl;
    		int a;double b[2];
    		while (!CityFile.eof()) {
    			CityFile >> a >> b[0] >> b[1];
    			citys[a - 1].x = b[0];
    			citys[a - 1].y = b[1];
    		}
    		CityFile.close();
    	}
    	//初始化城市图,并计算各城市之间的距离
    	void innitial_Graph() {
    		double x = 0, y = 0;
    		for (int i = 0; i < N; ++i) {
    			for (int j = 0; j < N; ++j) {
    				x = citys[i].x - citys[j].x;
    				y = citys[i].y - citys[j].y;
    				Length[i][j] = sqrt(pow(x, 2) + pow(y, 2));//就是两点间距离公式
    				if (i == j) {
    					Length[i][j] = 10000;//默认城市到自己的距离为10000,防止启发式表出现无穷大,并不会计算城市自己到自己的概率
    				}
    				else {
    					if (x == 0 && y == 0) {
    						//这种情况是城市坐标完全重合,如果遇到这种情况则不能继续计算了,否则i与j之间的距离为0,启发式就会为无穷大
    						//随之p的分子和分母都会变成无穷大,无穷大除无穷大...
    						cout << "innitial_Graph ERROR!!! City overlapping, please retry." << endl;
    						cout << "City :" << i << " and City :" << j << endl;
    						exit(0);
    					}
    				}
    				Heuristic[i][j] = 1 / Length[i][j];//将距离的倒数作为启发式
    				tao[i][j] = 1;//信息素tao不能初始化为0
    			}
    		}
    	}
    };
    class AntColony {
    public:
    	int tabu[M][N] = { 0 };//禁忌列表,同时记录了蚂蚁的路径,每个元素取值为[0,N-1]
    	int allow[M][N] = { 0 };//允许列表,完全依赖于禁忌列表,只是为了算法方便一些而设置,无法记录路径,每个元素取值为[0,1]
    	double probability[M][N] = { 0 };//概率表,存放各蚂蚁选择下一作城市的概率
    	double cumulative_probability[M][N] = { 0 };//累积概率表,用于轮盘赌算法随机选择城市
    public:
    
    	//每轮迭代前都应该被调用一次
    	void innitial_AntColony() {
    		//初始化各列表
    		for (int i = 0; i < M; ++i) {
    			for (int j = 0; j < N; ++j) {
    				tabu[i][j] = -1;
    				allow[i][j] = 1;
    				probability[i][j] = 0;
    				cumulative_probability[i][j] = 0;
    			}
    		}
    		//为每一只蚂蚁随机一个初始城市,并将其加入禁忌列表
    		for (int i = 0; i < M; i++) {
    			tabu[i][0] = rand() % N;
    			allow[i][tabu[i][0]] = 0;
    		}
    	}
    
    	//求取概率表和累积概率表,然后根据轮盘赌算法选择下一个城市,每轮迭代应该被调用N-1次(初始化时已经有一个城市了)
    	void ChooseNextCity(Graph* graph, int times) {//times表示此轮迭代已经是第几次调用这个函数了,times应该从1开始,到N-1次结束
    
    		//求概率表
    		double sum = 0;
    		int city_now = -1;
    		for (int i = 0; i < M; ++i) {
    			sum = 0;
    			city_now = tabu[i][times - 1];//蚂蚁i目前在城市city_now
    			for (int j = 0; j < N; ++j) {
    				if (allow[i][j] == 1) {
    					probability[i][j] = pow(graph->tao[city_now][j], α) * pow(graph->Heuristic[city_now][j], β);
    					sum += probability[i][j];
    				}
    				else {
    					probability[i][j] = 0;
    					sum += 0;
    				}
    			}
    			//上面求出的probability表并不是真正的概率表,而只是概率的分子,下面求出真正的概率表
    			for (int j = 0; j < N; ++j) {
    				probability[i][j] = probability[i][j] / sum;
    			}
    		}
    
    		//用概率表求累积概率表
    		for (int i = 0; i < M; ++i) {
    			cumulative_probability[i][0] = probability[i][0];
    			for (int j = 1; j < N; ++j) {
    				cumulative_probability[i][j] = cumulative_probability[i][j - 1] + probability[i][j];
    			}
    		}
    
    		//依据累积概率表,用轮盘赌算法为每只蚂蚁选择下一个城市
    		double p = 0;
    		for (int i = 0; i < M; ++i) {
    			p = rand() % 1000;
    			p /= 1000;
    			for (int j = 0; j < N; ++j) {
    				if (p <= cumulative_probability[i][j]) {
    					//如果满足此式,则让蚂蚁i前往城市j(下面更新tabu表的操作就是从逻辑上把蚂蚁移动到城市j)
    					tabu[i][times] = j;
    					allow[i][j] = 0;
    					break;
    				}
    			}
    		}
    	}
    
    	//更新函数每次迭代后都应该被调用一次,用于更新信息素表graph->tabu,并记录本轮迭代的相关信息(最优路径,最优路径的长度,所有蚂蚁所走路径的平均长度)
    	//NC_now表示目前的迭代次数,应该从0开始,到NC_MAX-1结束,依次调用此函数
    	void Update(Graph* graph, int NC_now) {
    		double delta_ktao = 0;	//用于保存当前蚂蚁留在所经边的信息素
    		double delta_tao[N][N] = { 0 };	//此轮迭代的信息素增量表,表示本轮信息素的增量,配合蒸发系数更新信息素表
    		double sum_Length[M] = { 0 };	//保存此轮每只蚂蚁所经过的路径长度
    
    		int last_city, next_city;
    		//遍历tabu表,计算每只蚂蚁的路径长度,存放在sum_Length[]中
    		for (int i = 0; i < M; ++i) {
    			for (int j = 1; j < N; ++j) {
    				last_city = tabu[i][j - 1];
    				next_city = tabu[i][j];
    				sum_Length[i] += graph->Length[last_city][next_city];
    			}
    			//还要再加上终点到起点的距离
    			last_city = tabu[i][N - 1];
    			next_city = tabu[i][0];
    			sum_Length[i] += graph->Length[last_city][next_city];
    		}
    		//遍历tabu表,计算信息素增量表delta_tao[][]
    		for (int i = 0; i < M; ++i) {
    			delta_ktao = Q / sum_Length[i];
    			for (int j = 1; j < N; ++j) {
    				last_city = tabu[i][j - 1];
    				next_city = tabu[i][j];
    				delta_tao[last_city][next_city] += delta_ktao;
    			}
    		}
    		//利用信息素增量表和蒸发系数更新信息素表tao[][]
    		for (int i = 0; i < N; ++i) {
    			for (int j = 0; j < N; ++j) {
    				graph->tao[i][j] = graph->tao[i][j] * (1 - ρ) + delta_tao[i][j];
    			}
    		}
    
    		//计算本轮最优路径,最优路径的长度,所有蚂蚁所走路径的平均长度
    		int flag = 0;
    		double min = 1000000, sum = 0;	//min的初始值必须是一个足够大的值
    		for (int i = 0; i < M; ++i) {
    			sum += sum_Length[i];
    			if (min > sum_Length[i]) {
    				min = sum_Length[i];
    				flag = i;//标记最好的蚂蚁
    			}
    		}
    		//记录本轮信息至全局变量中
    		for (int i = 0; i < N; ++i) {
    			BestPath_PerRound[NC_now][i] = tabu[flag][i];
    		}
    		BestLength_PerRound[NC_now] = min;
    		AverageLength_PerRound[NC_now] = sum / M;
    
    
    		//更新全局最优路径和其长度
    		if (BestLength > min) {
    			for (int i = 0; i < N; ++i) {
    				BestPath[i] = BestPath_PerRound[NC_now][i];
    			}
    			BestLength = min;
    		}
    
    		//用2-opt局部搜索优化本轮最优路径并用信息素强化
    		{
    			int TempPath[N];
    			int flag = false;
    			int t;
    			for (int i = 0; i < N; ++i) {
    				TempPath[i] = BestPath_PerRound[NC_now][i];
    			}
    			for (int a = 0; a < N-1; ++a) {
    				//如果路径被优化为新路径,则再对新路径从头来一次局部搜索
    				if (flag == true) {
    					a = 0;
    					flag = false;
    				}
    				for (int b = a + 1; b < N; ++b) {
    					//逆序a~b的路径
    					for (int i = a, j = b; i < j; ++i, --j) {
    						t = TempPath[i];
    						TempPath[i] = TempPath[j];
    						TempPath[j] = t;
    					}
    					//重新求优化后的路径长度,加上终点到起点的距离
    					sum = 0;
    					for (int i = 1; i < N; ++i) {
    						last_city = TempPath[i - 1];
    						next_city = TempPath[i];
    						sum += graph->Length[last_city][next_city];
    					}
    					last_city = TempPath[N - 1];
    					next_city = TempPath[0];
    					sum += graph->Length[last_city][next_city];
    					//如果此解更优则更新本轮最优解
    					if (sum < BestLength_PerRound[NC_now]) {
    						flag = true;//如果路径被更新,则局部搜索从0开始
    						//先更新平均路径再更新最优路径
    						AverageLength_PerRound[NC_now] = (AverageLength_PerRound[NC_now] * M - BestLength_PerRound[NC_now] + sum) / M;
    						BestLength_PerRound[NC_now] = sum;
    						for (int i = 0; i < N; ++i) {
    							BestPath_PerRound[NC_now][i] = TempPath[i];
    						}
    						//如果比全局最优解还优,则更新全局最优解
    						if (sum < BestLength) {
    							for (int i = 0; i < N; ++i) {
    								BestPath[i] = TempPath[i];
    							}
    							BestLength = sum;
    						}
    					}
    				}
    			}
    			//使用2opt局部搜索获得更强的解之后,给最优路径追加信息素奖励
    			double reward = Q / sum;
    			for (int i = 1; i < N; ++i) {
    				last_city = BestPath[i-1];
    				next_city = BestPath[i];
    				graph->tao[last_city][next_city] += reward;
    			}
    		}
    	}
    };
    
    //此函数的目的是为了用图展示出蚁群算法的结果,用C++调用python的matplotlib库
    bool ShowByPython(Graph* graph) {
    
    	//C++中初始化python环境
    	Py_Initialize();
    	if (!Py_IsInitialized()) {
    		std::cout << "Py_Initialize Error!" << std::endl;
    		return false;
    	}
    
    	try {
    		//执行python语句
    		PyRun_SimpleString("import sys");
    		PyRun_SimpleString("import matplotlib.pyplot as plt");
    		string importPy = "sys.argv = ['suibiantian']";
    		PyRun_SimpleString(importPy.c_str());
    
    		double x, y;
    		PyRun_SimpleString("plt.figure(num=1)");
    		PyRun_SimpleString("plt.title('Ant Colony algorithm for solving TSP')");//蚁群算法解决TSP问题
    		PyRun_SimpleString("plt.xlabel('x')");
    		PyRun_SimpleString("plt.ylabel('y')");
    		importPy= "plt.xlabel('Shortest=" + to_string(BestLength) + "')";
    		PyRun_SimpleString(importPy.c_str());
    		for (int i = 0; i < N; ++i) {
    			x = graph->citys[i].x;//Graph[i].get_x();
    			y = graph->citys[i].y;
    			importPy = "plt.scatter(" + to_string(x) + "," + to_string(y) + ")";
    			PyRun_SimpleString(importPy.c_str());
    		}
    
    		int last_city, next_city;
    		double X1, X2, Y1, Y2;
    		string str;
    		//把全局最优路径按顺序画出来,画在第一副图上
    		PyRun_SimpleString("plt.figure(num=1)");
    		for (int i = 1; i < N; ++i) {
    			last_city = BestPath[i - 1];
    			next_city = BestPath[i];
    			X1 = graph->citys[last_city].x;
    			Y1 = graph->citys[last_city].y;
    			X2 = graph->citys[next_city].x;
    			Y2 = graph->citys[next_city].y;
    			str = "plt.plot([" + to_string(X1) + "," + to_string(X2) + "],[" + to_string(Y1) + "," + to_string(Y2) + "])";
    			PyRun_SimpleString(str.c_str());
    		}
    		//把终点到起点的线也画上
    		last_city = BestPath[N - 1];
    		next_city = BestPath[0];
    		X1 = graph->citys[last_city].x;
    		Y1 = graph->citys[last_city].y;
    		X2 = graph->citys[next_city].x;
    		Y2 = graph->citys[next_city].y;
    		str = "plt.plot([" + to_string(X1) + "," + to_string(X2) + "],[" + to_string(Y1) + "," + to_string(Y2) + "])";
    		PyRun_SimpleString(str.c_str());
    
    		//下面展示随着迭代进行,每轮最优路径长度的变化,这是第二幅图
    		double last = 0, next = 0;
    		//string str;
    		PyRun_SimpleString("plt.figure(num=2)");
    		PyRun_SimpleString("plt.title('ShortestLength Convergence graph')");//最优路径收敛图
    		PyRun_SimpleString("plt.xlabel('times of iterations')");
    		PyRun_SimpleString("plt.ylabel('BestLength')");
    		for (int i = 1; i < NC_MAX; ++i) {
    			last = BestLength_PerRound[i - 1];
    			next = BestLength_PerRound[i];
    			str = "plt.plot([" + to_string(i - 1) + "," + to_string(i) + "],[" + to_string(last) + "," + to_string(next) + "])";
    			PyRun_SimpleString(str.c_str());
    		}
    
    		//下面展示随着迭代进行,每轮平均路径长度的变化,这是第三幅图
    		PyRun_SimpleString("plt.figure(num=3)");
    		PyRun_SimpleString("plt.title('AverageLength Convergence graph')");//平均路径收敛图
    		PyRun_SimpleString("plt.xlabel('times of iterations')");
    		PyRun_SimpleString("plt.ylabel('AverageLength')");
    		for (int i = 1; i < NC_MAX; ++i) {
    			last = AverageLength_PerRound[i - 1];
    			next = AverageLength_PerRound[i];
    			str = "plt.plot([" + to_string(i - 1) + "," + to_string(i) + "],[" + to_string(last) + "," + to_string(next) + "])";
    			PyRun_SimpleString(str.c_str());
    		}
    
    		//展示上面描绘的三幅图
    		PyRun_SimpleString("plt.show()");
    	}
    	catch (...) {
    		PyErr_Print();
    		PyErr_Clear();
    		Py_Finalize();
    		return false;
    	}
    	Py_Finalize();
    	return true;
    }
    

    下面是搜索出的最优路径
    在这里插入图片描述
    下面是每轮最短路径的收敛图
    在这里插入图片描述
    每轮平均路径的收敛图
    在这里插入图片描述
    详细路径信息,格式为:Travel 路径编号:起点->中点 distante: 路径距离
    在这里插入图片描述
    贴在下面了,欢迎核验,如有错误请务必指出。
    Travel 1 : 117 -> 126 distante: 55.1443
    Travel 2 : 126 -> 68 distante: 23.8115
    Travel 3 : 68 -> 35 distante: 29.2264
    Travel 4 : 35 -> 60 distante: 9.72314
    Travel 5 : 60 -> 10 distante: 51.2535
    Travel 6 : 10 -> 147 distante: 46.2648
    Travel 7 : 147 -> 129 distante: 55.4831
    Travel 8 : 129 -> 59 distante: 65.0094
    Travel 9 : 59 -> 65 distante: 30.1797
    Travel 10 : 65 -> 16 distante: 27.3557
    Travel 11 : 16 -> 139 distante: 110.504
    Travel 12 : 139 -> 116 distante: 86.7004
    Travel 13 : 116 -> 56 distante: 78.7559
    Travel 14 : 56 -> 38 distante: 29.3313
    Travel 15 : 38 -> 40 distante: 54.1271
    Travel 16 : 40 -> 100 distante: 50.9215
    Travel 17 : 100 -> 115 distante: 34.8224
    Travel 18 : 115 -> 11 distante: 61.9085
    Travel 19 : 11 -> 23 distante: 29.6934
    Travel 20 : 23 -> 52 distante: 40.9306
    Travel 21 : 52 -> 39 distante: 42.3001
    Travel 22 : 39 -> 138 distante: 40.6155
    Travel 23 : 138 -> 119 distante: 44.4553
    Travel 24 : 119 -> 41 distante: 36.8047
    Travel 25 : 41 -> 8 distante: 33.4683
    Travel 26 : 8 -> 27 distante: 17.6044
    Travel 27 : 27 -> 5 distante: 39.5344
    Travel 28 : 5 -> 36 distante: 50.9311
    Travel 29 : 36 -> 1 distante: 38.1426
    Travel 30 : 1 -> 18 distante: 45.8299
    Travel 31 : 18 -> 98 distante: 32.8616
    Travel 32 : 98 -> 113 distante: 25.9416
    Travel 33 : 113 -> 101 distante: 37.9277
    Travel 34 : 101 -> 136 distante: 91.5024
    Travel 35 : 136 -> 131 distante: 78.4181
    Travel 36 : 131 -> 64 distante: 70.9377
    Travel 37 : 64 -> 84 distante: 79.0921
    Travel 38 : 84 -> 141 distante: 43.3364
    Travel 39 : 141 -> 17 distante: 18.7001
    Travel 40 : 17 -> 74 distante: 68.229
    Travel 41 : 74 -> 25 distante: 52.9664
    Travel 42 : 25 -> 145 distante: 30.1759
    Travel 43 : 145 -> 55 distante: 48.4976
    Travel 44 : 55 -> 82 distante: 60.9404
    Travel 45 : 82 -> 89 distante: 78.7118
    Travel 46 : 89 -> 45 distante: 37.2769
    Travel 47 : 45 -> 137 distante: 32.2974
    Travel 48 : 137 -> 133 distante: 36.4663
    Travel 49 : 133 -> 53 distante: 49.6458
    Travel 50 : 53 -> 91 distante: 18.2787
    Travel 51 : 91 -> 32 distante: 68.4011
    Travel 52 : 32 -> 125 distante: 34.6496
    Travel 53 : 125 -> 92 distante: 42.6625
    Travel 54 : 92 -> 123 distante: 49.6092
    Travel 55 : 123 -> 96 distante: 83.7926
    Travel 56 : 96 -> 99 distante: 64.4461
    Travel 57 : 99 -> 142 distante: 27.2312
    Travel 58 : 142 -> 4 distante: 63.2943
    Travel 59 : 4 -> 106 distante: 41.3304
    Travel 60 : 106 -> 94 distante: 31.1275
    Travel 61 : 94 -> 81 distante: 31.9049
    Travel 62 : 81 -> 102 distante: 106.139
    Travel 63 : 102 -> 97 distante: 14.1672
    Travel 64 : 97 -> 0 distante: 12.4814
    Travel 65 : 0 -> 86 distante: 21.0398
    Travel 66 : 86 -> 75 distante: 39.3925
    Travel 67 : 75 -> 72 distante: 35.7439
    Travel 68 : 72 -> 47 distante: 36.0159
    Travel 69 : 47 -> 62 distante: 26.0187
    Travel 70 : 62 -> 33 distante: 64.609
    Travel 71 : 33 -> 29 distante: 51.9375
    Travel 72 : 29 -> 83 distante: 29.438
    Travel 73 : 83 -> 6 distante: 21.5333
    Travel 74 : 6 -> 7 distante: 37.8298
    Travel 75 : 7 -> 88 distante: 19.5707
    Travel 76 : 88 -> 95 distante: 28.0031
    Travel 77 : 95 -> 34 distante: 45.2472
    Travel 78 : 34 -> 51 distante: 63.4108
    Travel 79 : 51 -> 110 distante: 59.0715
    Travel 80 : 110 -> 104 distante: 16.3226
    Travel 81 : 104 -> 15 distante: 64.9284
    Travel 82 : 15 -> 58 distante: 24.72
    Travel 83 : 58 -> 78 distante: 32.2454
    Travel 84 : 78 -> 120 distante: 36.1277
    Travel 85 : 120 -> 87 distante: 41.0983
    Travel 86 : 87 -> 93 distante: 25.7435
    Travel 87 : 93 -> 9 distante: 46.3794
    Travel 88 : 9 -> 112 distante: 10.3364
    Travel 89 : 112 -> 2 distante: 59.0653
    Travel 90 : 2 -> 61 distante: 47.9991
    Travel 91 : 61 -> 148 distante: 34.7824
    Travel 92 : 148 -> 124 distante: 29.0095
    Travel 93 : 124 -> 21 distante: 38.7598
    Travel 94 : 21 -> 103 distante: 97.2203
    Travel 95 : 103 -> 3 distante: 39.9367
    Travel 96 : 3 -> 44 distante: 43.7677
    Travel 97 : 44 -> 127 distante: 38.5289
    Travel 98 : 127 -> 67 distante: 39.3229
    Travel 99 : 67 -> 118 distante: 17.3873
    Travel 100 : 118 -> 90 distante: 21.9871
    Travel 101 : 90 -> 105 distante: 62.0361
    Travel 102 : 105 -> 12 distante: 49.6411
    Travel 103 : 12 -> 73 distante: 68.0154
    Travel 104 : 73 -> 122 distante: 45.3449
    Travel 105 : 122 -> 135 distante: 78.0568
    Travel 106 : 135 -> 111 distante: 27.5365
    Travel 107 : 111 -> 63 distante: 40.7227
    Travel 108 : 63 -> 43 distante: 72.4602
    Travel 109 : 43 -> 70 distante: 31.6304
    Travel 110 : 70 -> 114 distante: 48.8181
    Travel 111 : 114 -> 149 distante: 10.7822
    Travel 112 : 149 -> 20 distante: 79.5582
    Travel 113 : 20 -> 77 distante: 89.5726
    Travel 114 : 77 -> 14 distante: 23.1417
    Travel 115 : 14 -> 132 distante: 42.269
    Travel 116 : 132 -> 76 distante: 45.1619
    Travel 117 : 76 -> 121 distante: 26.6059
    Travel 118 : 121 -> 13 distante: 27.6407
    Travel 119 : 13 -> 79 distante: 12.1495
    Travel 120 : 79 -> 71 distante: 64.5719
    Travel 121 : 71 -> 48 distante: 38.6427
    Travel 122 : 48 -> 146 distante: 1.64922
    Travel 123 : 146 -> 143 distante: 21.5679
    Travel 124 : 143 -> 128 distante: 50.3949
    Travel 125 : 128 -> 26 distante: 44.8038
    Travel 126 : 26 -> 30 distante: 41.4632
    Travel 127 : 30 -> 144 distante: 67.7661
    Travel 128 : 144 -> 22 distante: 146.406
    Travel 129 : 22 -> 37 distante: 17.5752
    Travel 130 : 37 -> 31 distante: 25.0768
    Travel 131 : 31 -> 130 distante: 28.8611
    Travel 132 : 130 -> 66 distante: 59.137
    Travel 133 : 66 -> 42 distante: 46.6341
    Travel 134 : 42 -> 108 distante: 38.3764
    Travel 135 : 108 -> 50 distante: 40.2562
    Travel 136 : 50 -> 19 distante: 53.2103
    Travel 137 : 19 -> 24 distante: 33.4419
    Travel 138 : 24 -> 140 distante: 63.6564
    Travel 139 : 140 -> 57 distante: 59.038
    Travel 140 : 57 -> 54 distante: 20.8724
    Travel 141 : 54 -> 49 distante: 48.5817
    Travel 142 : 49 -> 134 distante: 31.587
    Travel 143 : 134 -> 69 distante: 22.4594
    Travel 144 : 69 -> 107 distante: 22.2829
    Travel 145 : 107 -> 85 distante: 35.2128
    Travel 146 : 85 -> 28 distante: 32.9668
    Travel 147 : 28 -> 80 distante: 48.2219
    Travel 148 : 80 -> 109 distante: 32.195
    Travel 149 : 109 -> 46 distante: 51.5045
    Travel 150 : 46 -> 117 distante: 156.05

    展开全文
  • C++实现蚁群算法(TSP问题)

    千次阅读 2020-04-02 23:03:38
    代码使用了C++矩阵运算库armadillo,这个库语法和MATLAB相似且功能强大。 头文件 #pragma once #include <armadillo> #include<iostream> using namespace arma; using namespace std; extern const ...

    注意

    代码使用了C++矩阵运算库armadillo,这个库语法和MATLAB相似且功能强大。
    armadillo在Visual Studio中的配置

    头文件

    头文件的变量记得extern,armadillo中整数矩阵声明为imat。

    #pragma once
    #include <armadillo>
    #include<iostream>
    using namespace arma;
    using namespace std;
    
    extern const int city_size;
    extern int m;
    extern float alpha;
    extern float beta;
    extern float rho;
    extern float Q;
    extern int iter ;
    extern int iter_max;
    extern int temp[100];
    extern mat Tau;
    extern imat Table;
    extern imat Route_best;
    extern mat Length_best;
    extern mat Length_ave;
    extern mat D;
    extern imat citys;
    extern mat Eta;
    extern imat start;                   /*各个蚂蚁的起点城市*/
    extern imat citys_index;
    extern mat Length;
    extern mat Delta_Tau;
    
    void shuffle(int r[]);
    void Init();
    double mean(mat);
    int find_index(mat, double s);
    

    实现文件cpp

    实现中的shuffle函数实际上是编写了一个matlab中的低配randperm函数,打乱顺序自然数。Init是算法的一些初始化工作。mean是一个求均值函数,find_index是一个找到最小值索引的函数。

    #include <iostream>
    #include "Ant.h"
    #include<vector>
    #include <ctime>
    #include <math.h>
    using namespace std;
    
    const int city_size = 100;
    int m = 50;
    float alpha = 1;
    float beta = 5;
    float rho = 0.1;
    float Q = 1;
    int iter = 1;
    int iter_max = 150;
    int temp[100];
    mat Tau = ones(city_size, city_size);
    imat Table(m, city_size);
    imat Route_best(iter_max, city_size);
    mat Length_best = zeros(iter_max, 1);
    mat Length_ave = zeros(iter_max, 1);
    mat D = zeros(city_size, city_size);
    imat citys(city_size, 2);
    mat Eta = zeros(city_size, city_size);
    mat Length = zeros(m, 1);
    mat Delta_Tau = zeros(city_size, city_size);
    imat citys_index(1, city_size);
    imat start(m, 1);
    
    
    
    void shuffle(int r[]) 
    {
    	vector<int>a(100);
    	for (int i = 0; i < 100; i++)
    	{
    		a[i] = i;
    	}
    	for (int i = 99; i >= 0; i--)
    	{
    		int uu = int(rand() * RAND_MAX) % (i+1);
    		r[99 - i] = a[uu];
    		a.erase(a.begin() + uu);
    	}
    }
    
    void Init()
    {
    	for (int i = 0; i < 100; i++)
    	{
    		for (char j = 0; j < 2; j++)
    		{
    			citys(i, j) = int(rand()*RAND_MAX) % 100;
    		}
    	}
    	citys.save("citys.txt", raw_ascii);
    	for (int i = 0; i < city_size; i++)
    	{
    		for (int j = 0; j < city_size; j++)
    		{
    			D(i, j) = sqrt(pow((citys(i, 0) - citys(j, 0)), 2) + pow((citys(i, 1) - citys(j, 1)), 2));
    		}
    	}
    	for (int i = 0; i < city_size; i++)
    	{
    		for (int j = 0; j < city_size; j++)
    		{
    			Eta(i, j) = 1/D(i,j);
    		}
    	}
    
    	start.fill(0);
    	Table.fill(0);
    }
    
    double mean(mat a)
    {
    	double s = 0;
    	for (int i = 0; i < m; i++)
    	{
    		s += a(i);
    	}
    	return s / m;
    }
    
    int find_index(mat a, double s)
    {
    	int key = 0;
    	for (int i = 0; i < m; i++)
    	{
    		if (a(i) == s)
    		{
    			key = i;
    			break;
    		}
    	}
    	return key;
    }
    

    main函数

    C++的vector实际上就是一个加强版数组,支持动态赋值,有点类似Python中的数组的操作方式和方法。值得提醒的是vector在迭代过程中用完记得clear。

    #include <iostream>
    #include <armadillo>
    #include<vector>
    #include <ctime>
    #include "Ant.h"
    #include <math.h>
    
    
    using namespace std;
    using namespace arma;
    vector<int>tabu;                   //记得clear
    vector<int>allow;
    vector<double>P;
    vector<double>Pc;
    char key;
    double s;
    int target_index;
    int target;
    int min_index;
    double min_Length;
    
    
    
    
    int main(int argc, char** argv)
    {	
    	srand((int)time(0));
    	Init();
    
    	for (int iter = 0; iter < iter_max; iter++)
    	{
    		for (int i = 0; i < m; i++)
    		{
    			int ran = int(rand()*RAND_MAX)%100;
    			start(i) = ran;
    		}
    		Table.col(0) = start;
    		for (int k = 0; k < city_size; k++)
    		{
    			citys_index(k) = k;
    		}
    
    		for (int i = 0; i < m; i++)
    		{
    			for (int j = 1; j < city_size; j++)
    			{
    				//找到已经走了的城市索引
    				for (int k = 0; k < j; k++)
    				{
    					tabu.push_back(Table(i, k));
    				}
    				//end
    				
    				// 找到还没走的城市索引
    				for (int k = 0; k < city_size; k++)
    				{
    					key = 0;
    					for (int y = 0; y < tabu.size(); y++)
    					{
    						if (citys_index(k) == tabu[y])
    						{
    							key = 1;
    							break;
    						}
    					}
    					if (key == 0)allow.push_back(citys_index[k]);
    				}
    				//  end
                    
    				// 计算城市间转移概率
    				s = 0;
    				for (int k = 0; k < allow.size(); k++)
    				{
    					P.push_back( pow(Tau(tabu[tabu.size()-1], allow[k]), alpha) * pow(Eta(tabu[tabu.size() - 1], allow[k]), beta));
    					s += P[P.size() - 1];
    				}
    				for (int k = 0; k < allow.size(); k++)
    				{
    					P[k] /= s;
    				}
    				//end
    
    				//轮盘赌算法选择下一个城市
    				for (int k = 0; k < P.size(); k++)
    				{
    					s = 0;
    					for (int i = 0; i <= k; i++)
    					{
    						s += P[i];
    					}
    					Pc.push_back(s);
    				}
    				s = double(rand()) / RAND_MAX;
    				for (int k = 0; k < Pc.size(); k++)
    				{
    					if (Pc[k] >= s)
    					{
    						target_index = k;
    						break;
    					}
    				}
    				target = allow[target_index];
    				Table(i, j) = target;
    				//end
    
    				tabu.clear();
    				allow.clear();
    				P.clear();
    				Pc.clear();
    			}
    		}
    		// 计算各个蚂蚁的路径距离
    		for (int k = 0; k < m; k++)
    		{
    			for (int n = 0; n < city_size - 1; n++)
    			{
    				Length(k) += D(Table(k, n), Table(k, n + 1));
    			}
    			Length(k) += D(Table(k, city_size-1), Table(k, 0));
    		}
    		//end
    		//计算最短路径距离及平均距离
    		if (iter == 0)
    		{
    			mat temp;
    			temp = min(Length);
    			Length_best(iter) = temp(0);
    			key = find_index(Length, temp(0));
    			Route_best.row(iter) = Table.row(key);
    			Length_ave(iter) = mean(Length);
    		}
    		else
    		{
    			mat temp;
    			temp = min(Length);
    			Length_ave(iter) = mean(Length);
    			key = find_index(Length, temp(0));
    			if (temp(0) <= Length_best(iter - 1))
    			{
    				Length_best(iter) = temp(0);
    				Route_best.row(iter) = Table.row(key);
    			}
    			else
    			{
    				Length_best(iter) = Length_best(iter - 1);
    				Route_best.row(iter) = Route_best.row(iter-1);
    			}	
    		}
    		//end
    
    		//更新信息素
    		Delta_Tau.fill(0);
    		for (int k = 0; k < m; k++)
    		{
    			for (int y = 0; y < city_size - 1;y++)
    			{
    				Delta_Tau(Table(k, y), Table(k, y + 1)) += Q / Length(k);
    			}
    			Delta_Tau(Table(k,city_size-1),Table(k,0)) += Q / Length(k);
    		}
    		Tau = (1 - rho) * Tau + Delta_Tau;
    		//end
    
    		Table.fill(0);
    		cout << iter << endl;
    	}
    
    	cout << Length_best(iter_max - 1) << endl;
    	Route_best.save("Route_best.txt", raw_ascii);
    	return 0;
    }
    

    MATLAB绘制结果

    由于C++可视化这方面不如matlab,我们用matlab绘制结果。
    在这里插入图片描述
    可以适当增加iter_max从而使结果更好。

    MATLAB对应代码

    这次C++的实现实际上是我对着MATLAB的实现写的,下面贴上MATLAB代码。citys是城市坐标,可以自己随机生成。

    close all;clear;clc;
    citys = [12,26;55,28;76,81;82,13;42,64;58,35;84,92;17,51;87,34;92,83;67,63;77,88;24,24;59,68;43,10;64,21;19,17;41,98;91,44;98,67;25,29;99,50;23,94;4,61;20,32;66,77;13,57;97,37;57,33;62,9;22,85;38,70;37,96;44,100;35,11;18,86;33,58;27,47;83,27;79,5;80,65;88,20;49,56;30,41;89,16;15,46;14,74;53,71;93,38;74,55;60,97;51,12;40,49;86,6;72,66;11,80;5,54;81,52;31,73;8,89;95,91;90,42;34,79;28,4;47,43;69,40;85,53;50,69;3,76;21,95;94,31;65,72;78,93;46,19;63,1;9,30;100,48;26,3;52,18;1,36;10,59;48,75;68,62;54,87;16,22;36,45;61,78;75,82;7,84;96,14;73,2;39,23;2,15;29,99;6,90;70,25;45,39;32,8;71,7;56,60];
    %计算城市间的相互距离
    n=size(citys,1);
    D=zeros(n,n);
    for i=1:n
        for j=1:n
            if i~=j
                D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));
            else
                D(i,j)=1e-4;
            end
        end
    end
    
    
    %初始化参数
    m=50;                 %蚂蚁数量
    alpha=1;             %信息素重要程度因子
    beta=5;              %启发函数重要程度因子
    rho=0.1;             %信息素挥发因子
    Q=1;                 %常系数
    Eta=1./D;            %启发函数
    Tau=ones(n,n);       %信息素矩阵
    Table=zeros(m,n);    %路径记录表 m个蚂蚁走过的路径
    iter=1;              %迭代次数的初值
    iter_max=200;        %最大迭代次数
    Route_best=zeros(iter_max,n);  %到该代为止最优的路线
    Length_best=zeros(iter_max,1); %到该代为止最小的路径距离
    Length_ave=zeros(iter_max,1);  %各代路径的平均长度
    
    %迭代巡展最佳路径
    while iter<=iter_max
        %随机产生各个蚂蚁的起点城市
        start=zeros(m,1);
        for i=1:m
            temp=randperm(n);
            start(i)=temp(1);
        end
        Table(:,1)=start;  %蚂蚁初始城市位置
        citys_index=1:n;   %城市索引,从1到n
        %逐个蚂蚁的路径选择
        for i=1:m
            %对于一个蚂蚁的逐个城市的选择
            for j=2:n
                tabu=Table(i,1:(j-1));   %已经访问过的城市集合
                allow_index=~ismember(citys_index,tabu); %没有访问过的城市置1
                allow=citys_index(allow_index);   %待访问的城市集合
                P=allow;
                %计算城市间转移概率
                for k=1:length(allow)
                    P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;
                end
                P=P/sum(P);
                %轮盘赌选择下一个访问城市
                Pc=cumsum(P);
                target_index=find(Pc>=rand);
                target=allow(target_index(1));
                Table(i,j)=target;              %记录下来,加入Table,成为下一个访问的城市
            end
        end
        %计算各个蚂蚁的路径距离
        Length=zeros(m,1);
        for i=1:m
            Route=Table(i,:); %每个蚂蚁的路径
            for j=1:(n-1)
                Length(i)=Length(i)+D(Route(j),Route(j+1));
            end
            Length(i)=Length(i)+D(Route(n),Route(1));
        end
        %计算最短路径距离及平均距离
        if iter==1
            [min_Length,min_index]=min(Length);
            Length_best(iter)=min_Length;
            Length_ave(iter)=mean(Length);
            Route_best(iter,:)=Table(min_index,:);
        else
            [min_Length,min_index]=min(Length);
            Length_best(iter)=min(Length_best(iter-1),min_Length);
            Length_ave(iter)=mean(Length);
            if Length_best(iter)==min_Length
                Route_best(iter,:)=Table(min_index,:);
            else
                Route_best(iter,:)=Route_best((iter-1),:);
            end
        end
        %更新信息素
        Delta_Tau=zeros(n,n);
        %逐个蚂蚁计算
        for i=1:m
            %逐个城市计算
            for j=1:(n-1)
                Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i);
            end
            Delta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,n),Table(i,1))+Q/Length(i);
        end
        Tau=(1-rho)*Tau+Delta_Tau;
        %迭代次数加1,清空路径记录表
        iter=iter+1;
        Table=zeros(m,n);
    end
    %结果显示
    [Shortest_Length,index]=min(Length_best);
    Shortest_Route=Route_best(index,:);
    disp(['最短距离:',num2str(Shortest_Length)]);
    disp(['最短路径:',num2str([Shortest_Route Shortest_Route(1)])]);
    %绘图
    figure(1)
    plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-')
    xlabel('x'),ylabel('y'),title('the best route');
    figure(2)
    plot(1:iter_max,Length_best,'b')
    xlabel('The iteration number'),ylabel('the shortest length'),title('The best length in every iteration');
    figure(3)
    plot(1:iter_max,Length_ave,'r'),xlabel('The iteration number'),ylabel('the average length'),title('The average length in every iteration');                                        
    
    展开全文
  • 蚁群算法

    2018-01-14 15:39:46
    此类算法适合蚁群算法,希望对大家有所帮助。如有改进请指教
  • 蚁群算法c++实现!,很好,希望对你有帮助!
  • 蚁群算法原理解决多任务多车间车间调度问题
  • 蚁群算法解决TSP问题

    2016-12-05 14:08:05
    根据10个城市和30个城市的数据,用蚁群算法选择出来最短的路径
  • 蚁群算法求解TSP问题 C++

    千次阅读 2018-09-20 22:19:56
    #include &amp;amp;amp;amp;amp;lt;iostream&amp;amp;amp;amp;amp;gt; #include &amp;amp;amp;amp;amp;lt;math.h&amp;amp;amp;amp;amp;gt; #include &...//该程序是以蚁群系统为模型写的
  • //该程序是以蚁群系统为模型写的蚁群算法程序(强调:非蚂蚁周模型),以三个著名的TSP问题为测试对象 //通过微调参数,都可以获得较好的解 //----------(1)问题一:Oliver 30 城市 TSP 问题 best_length = ...
  • 是关于蚁群算法中在tsp问题中的应用。代码可运行,可读性很好,欢迎大家下载!
  • 基于蚁群算法的机器人路径规划源码,做毕设或者课时作业,通过常规修改该源码即可实现
  • 该程序为本人所写 希望对大家有用,研究生毕业那年研究蚁群算法,写了好长时间 ,效率还可以
  • C++蚁群优化算法

    2018-02-06 10:06:53
    这个类似与TSP问题,代码中解决的问题是:用最短的距离走完所有的城市并且不重复走。
  • C++利用蚁群算法,求解TSP问题。含代码,可用VC2010打开。
  • 本系统采用C++实现了蚁群算法,同时有图形实时显示,非常适合解决旅商算法Tsp学习
  • 蚁群算法解决vrp问题

    2018-08-24 09:54:05
    内含蚁群算法解决vrp问题的代码和数据,可以直接运行。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,956
精华内容 782
关键字:

蚁群算法c++

c++ 订阅