一、原理

1. 螞蟻覓食行為

蟻群在尋找食物時，總能找到一條蟻穴到食物的最短路徑，并且能随着環境的變化而更新最優路徑。究其原因，是因為螞蟻在運動過程中，會在所經過路徑上留下一種稱為資訊素（pheromone）的物質，其他螞蟻在運動中可以感覺到這種物質，并以此來指導自己的運動方向。

蟻群的這種行為表現出一種資訊正回報現象：某一路徑上走過的螞蟻越多，則後來者選擇該路徑的機率越大。

2.蟻群算法

又稱螞蟻算法，是一種基于群體智能的算法，用來在圖中尋找優化路徑的機率型。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。在解決實際問題時，人工蟻群相較于自然蟻群有一定的記憶能力，可記住已通路過的節點，其次人工蟻群在選擇路徑時依照一定規律，并不是盲目的。蟻群算法常用來解決路徑規劃等離散優化問題，如旅行商問題（TSP）、指派問題、排程問題。

2,1 特點

正回報：可較快發現較優解。
分布式：基于種群的進化算法，本質具有并行性，易于并行實作。
啟發式搜尋：反映搜尋中的的先驗性和确定性因素（如距離）強度。
魯棒性強：不易受某個個體影響。

2.2 算法流程（以TSP問題為例）

TSP問題：一商人去n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。

初始化相關參數：蟻群規模、資訊素因子、啟發函數因子、資訊素揮發因子、資訊素常數和最大疊代次數等。将城市資訊讀入程式并進行預處理，即将城市間資訊轉化為矩陣。
随機将螞蟻放入不同出發點，計算每個螞蟻的下一步要通路的城市，直到有螞蟻通路完所有城市。
計算每個螞蟻經過的路徑長度Lk，記錄目前疊代次數下的最優解（通路完所有城市且路徑長度最短），更新各條路徑上的資訊素濃度。
斷是否達到最大疊代次數，若否則傳回步驟2，若是則順序執行。
輸出最優路徑和相關名額，如運作時間和疊代次數。

2.3 相關公式

蟻群算法原理及c++實作一、原理三、例子

2.4 流程圖

蟻群算法原理及c++實作一、原理三、例子

三、例子

試設計一個并行算法，求下圖中一個源點到其他定點的最短路徑。（VS2019+Eigen）

蟻群算法原理及c++實作一、原理三、例子

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選擇下一步要去的城市時，有以下幾個步驟：

對照螞蟻k的禁忌表，求出下一步所有可去的城市各自的選擇機率(機率計算見公式(1)）；
線性化所有可去城市的機率，生成介于0~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;
		}

	}
}

資訊素更新

因為将資訊素存入矩陣，是以在計算時較為簡單，具體分為如下幾步：

計算資訊素增量矩陣：

for k = 1 to m do (周遊蟻群)

for j = 1 to n do (周遊螞蟻k的行走路徑)

　　計算螞蟻k在路徑(i, j)對應的資訊素增量（見公式（3））;

更新路徑(i, j)在上一輪的資訊素增量；

　 end for

end for
計算更新後的資訊素矩陣：

資訊素揮發系數*資訊素矩陣+資訊素增量矩陣（見公式（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

運作結果

蟻群算法原理及c++實作一、原理三、例子

問題

各項參數初始值雖然知道設定範圍，但因為不夠了解參數如何影響疊代的結果，參數設定主要依靠猜測。
代碼運作後，發現回歸太早，不符合蟻群算法回歸較慢（200~500）的特點，後經過檢查，發現是計算螞蟻k在路徑(i,j)上的資訊素增量時，将除數Lk了解成了路徑(i，j) 的距離，但實際上應該為螞蟻k本次疊代中做走過路徑距離之和。經修改後，可以符合蟻群算法回歸較慢的特點。
隻計算源點到某一個定點時，代碼沒有問題，循環結算到每個頂點最短路徑時，有時運作會報如下錯誤，有時不會，不太明白。

蟻群算法原理及c++實作一、原理三、例子

源碼

#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;
	}

}

蟻群算法原理及c++實作一、原理三、例子

一、原理

1. 螞蟻覓食行為

2.蟻群算法

2,1 特點

2.2 算法流程（以TSP問題為例）

2.3 相關公式

2.4 流程圖

三、例子

3.1 關鍵代碼

資料結構：

城市選擇方式

資訊素更新

3.2 運作結果

問題

源碼

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希