ac.cpp

经典的蚁群算法蚁周模型的实现

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cmath>
using namespace std;
const int g_max_n = 532;						// 最大城市个数
const int g_max_m = g_max_n;					// 最大蚂蚁个数
const int g_inf = 9999999;						// 最大距离
const int g_max_generation = 1500;				// 迭代次数
const double g_alpha = 1.0;
const double g_belta = 2.0;
const double g_rho = 0.7;
const int g_q = 100;
const double g_r0 = 1e-5;

struct Ant
{
	int path[g_max_n];
	bool tabu_list[g_max_n];
	int allowed_id[g_max_n];
	int allowed_no;
	int length;
}ant[g_max_m];

int g_n;										// 城市个数
int g_m;										// 蚂蚁的个数
int g_generation;								// 当前迭代次数
Ant best_ant;									// 最好的个体
int dis[g_max_n][g_max_n];						// 城市间的距离
double probability[g_max_n];					// 从一个城市转移到另一城市的概率
double cProbability[g_max_n];					// 转移城市概率的累积
double tau[g_max_n][g_max_n];					// 路径上的信息量
double delta_tau[g_max_n][g_max_n];				// 路径上的信息量的增量
double eta[g_max_n][g_max_n];					// 路径上的期望

ofstream fgalog;
ifstream fdata;
string strGalog("out.txt");
string strData("ry48p.txt");

int initialize();								// 初始化
int uninitialize();								// 反初始化
int iterative();								// 迭代过程
int report();									// 报告

template<typename T>
int display(T v)
{
	cout<<v<<' ';
	return 0;
}

int showAnt(const Ant& a)
{
	int i;
	cout<<"path: "<<endl;
	for (i = 0; i < g_n; i++)
	{
		cout<<"{"<<i<<", "<<a.path[i]<<"},"<<endl;
	}
	cout<<"length "<<a.length<<endl;
}

//返回 [low, high]
double randrange(double low, double high)
{
	return (double)rand() / double(RAND_MAX - 1) * (high - low) + low;
}

int initialize()
{
	int i, j;
	srand(time(0));
	streambuf* pStream = cin.rdbuf(fdata.rdbuf());
	memset(tau, 0, sizeof(tau));
	cin>>g_n;
	g_m = g_n;
	for (i = 0; i < g_n; i++)
	{
		for (j = 0; j < g_n; j++)
		{
			cin>>dis[i][j];
		}
	}
	cin.rdbuf(pStream);

	// 计算从城市i转移到城市j的期望
	for (i = 0; i < g_n; i++)
	{
		for (j = 0; j < g_n; j++)
		{
			eta[i][j] = 1.0 / dis[i][j];
		}
	}

	for (i = 0; i < g_n; i++)
	{
		for (j = 0; j < g_n; j++)
		{
			if (i != j)
			{
				tau[i][j] = g_r0;
			}
		}
	}
	
	// 初始化蚂蚁的位置
	for (i = 0; i < g_m; i++)
	{
		ant[i].path[0] = rand() % g_n;
	}
	
	best_ant.length = g_inf;
	return 0;
}

int uninitialize()
{
	fgalog.close();
	fdata.close();
	return 0;
}

int computeProbability(int k, int i)
{
	int j;
	memset(probability, 0, sizeof(probability));
	double denominator = 0.0;
	int num = ant[k].allowed_no;
	for (j = 0; j < num; j++)
	{
		int city = ant[k].allowed_id[j];
		denominator += pow(tau[i][city], g_alpha) * pow(eta[i][city], g_belta);
	}

	// 可行的所有路径信息量都非常小则取相同概率
	if (denominator == 0)
	{
		for (j = 0; j < num; j++)
		{
			int city = ant[k].allowed_id[j];
			probability[city] = 1.0 / num;
		}
		return 0;			
	}

	for (j = 0; j < num; j++)
	{
		int city = ant[k].allowed_id[j];
		double numerator = pow(tau[i][city], g_alpha) * pow(eta[i][city], g_belta);
		probability[city] = numerator / denominator;
	}
	return 0;
}

int iterative()
{
	int i, j, k, h;

	// 初始化蚂蚁位置和禁忌表
	memset(ant, 0, sizeof(ant));
	for (k = 0; k < g_m; k++)
	{
		int rnd = rand() % g_n;
		ant[k].path[0] = rnd;
		ant[k].tabu_list[rnd] = true;
	}

	for (h = 1; h < g_n; h++)
	{
		for (k = 0; k < g_m; k++)
		{
			int city = ant[k].path[h-1];
			ant[k].allowed_no = 0;
			for (j = 0; j < g_n; j++)
			{
				if (!ant[k].tabu_list[j])
				{
					ant[k].allowed_id[ant[k].allowed_no++] = j;
				}
			}
			computeProbability(k, city);
			for (j = 0; j < g_n; j++)
			{
				if (j == 0)
				{
					cProbability[j] = probability[j];
				}
				else
				{
					cProbability[j] = cProbability[j-1] + probability[j];
				}
			}
			
			// 按概率选择下一个城市
			double rnd = randrange(0.0, 1.0);
			double* p = lower_bound(cProbability, cProbability + g_n, rnd);
			int select_id = p - cProbability;

			ant[k].path[h] = select_id;
			ant[k].length += dis[city][select_id];
			ant[k].tabu_list[select_id] = true;

			int city2 = ant[k].path[h];
			delta_tau[city][city2] += (double)g_q / ant[k].length;
		}

		// 更新信息量
		for (i = 0; i < g_n; i++)
		{
			for (j = 0; j < g_n; j++)
			{
				tau[i][j] = g_rho * tau[i][j] + delta_tau[i][j];
				delta_tau[i][j] = 0.0;
			}
		}
	}
	
	for (k = 0; k < g_m; k++)
	{
		ant[k].length += dis[ant[k].path[g_n-1]][ant[k].path[0]];
		if (ant[k].length < best_ant.length)
		{
			best_ant = ant[k];
		}
	}
	return 0;
}

int report()
{
	fgalog.width(18);
	fgalog.setf(ios::left);
	fgalog<<g_generation<<' '<<best_ant.length<<endl;
	return 0;
}

int main()
{
	
	int i, j;
	srand(time(0));
	fgalog.open(strGalog.c_str());
	if (!fgalog.is_open())
	{
		cout<<"open galog file failed!"<<endl;
		exit(1);
	}

	fdata.open(strData.c_str());
	if (!fdata.is_open())
	{
		cout<<"open data file failed!"<<endl;
		exit(1);
	}
	fgalog<<"generation         best value"<<endl;

	initialize();
	long start = clock();
	for (g_generation = 1; g_generation <= g_max_generation; g_generation++)
	{
		iterative();
		report();
	}

	fgalog<<"best ant: "<<endl;
	streambuf* pStream = cout.rdbuf(fgalog.rdbuf());
	showAnt(best_ant);
	cout.rdbuf(pStream);
	uninitialize();

	return 0;
}