ga.cpp

遗传算法解旅行商问题 （工程须运行在VS2008下）

/**************************
遗传算法解TSP问题
06373055 陈宗泽
**************************/

/*
算法中相关参数的设置方法：

个体的编码方案：
	采用整数编码的方法，由于采用大写字母组成的字符串表示一个路径，即用这样的路径表示一个个体

适应函数：
	采用课件中介绍的非线性加速适应函数的方法，并且做了适当的调整，具体见源代码中的F()函数

交配方法：
	采用课件中基于位置的交配法，从两个双亲中可以产生两个后代

变异方法：
	采用课件中介绍的基于次序的变异方法，交换随机产生的两个变异位

新种群构成的方法：
	随机生成一个解的集合，按照确定性法，获得一个数量为MEMBER_NUMBER为初始种群。
	依据交配概率pc从种群中选择染色体进行交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中；
	依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体；
	用新群体代替旧群体

算法结束的条件：
	进化代数超过给定值t后结束，输出当前的最优解作为最优解。
*/


#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

struct dis        //城市的结构体
{
	double x,y;
};

const int MEMBER_NUMBER = 1000;		//种群众个体的数量
const int MAX_LOOP_NUMBER = 100;	//最多产生代数
const int ACCEPT_NUMBER	= 4;		//多于一定次数最优解不变则停止
const double MAX_LENGTH = 1000000.0;
const double pc = 0.6;				//交配概率
const double pm = 0.1;				//变异概率
const double epsln = 0.000001;

dis citys[20];				//城市的坐标,用数组记录
int n;						//城市数目
double bestLength;			//最优解
double preLength;			//前一次的解，用来判断结束条件
double currentLength;		//当前解
string bestPath;			//城市路径，根据两个输入数据都顺序用一位字符表示城市名的情况，可以用字符串记录路径。
string currentPath;			//每次得到的当前城市路径
vector<string> group;		//种群

double distance(char a, char b) //两城市之间距离
{
	double dis = sqrt((citys[a - 'A'].x - citys[b - 'A'].x) * (citys[a - 'A'].x - citys[b - 'A'].x) 
		+ (citys[a - 'A'].y - citys[b - 'A'].y) * (citys[a - 'A'].y - citys[b - 'A'].y));
	return dis;
}

double pathLength(string p)     //当前路径长度
{
	double length = 0;
	for(int i = 0; i < n - 1; i ++) 
		length += distance(p[i], p[i + 1]);
	length += distance(p[n - 1], p[0]);
	return length;
}

void readData()                 //读入数据
{

	while (1)
	{
    cout<<"******************遗传解决旅行商问题*********************"<<endl;
    cout<<"请输入文件名：";
    string filename;
    cin>>filename;
	ifstream fin(filename.c_str());
	if(!fin.is_open()) {
		cout<<"文件不存在!"<<endl;
		cout<<endl;
		continue;
	}
	fin>>n;
	

	for (int i = 0; i < n; i++)
	{
		citys[i].x = 0;
		citys[i].y = 0;
	}
	for (int i = 0; i < n; i++)
	{
		char city;
		double x,y;
		fin >> city >> x >> y;
		citys[(int)(city - 'A')].x = x;
		citys[(int)(city - 'A')].y = y;
	}
	fin.close();
	return ;
}
}

string getRands(vector<char> v)  //随机化
{
	string s = "";
	random_shuffle(v.begin(), v.end());					//将v中的字符随机打乱顺序
	for (vector<char>::iterator it = v.begin(); it != v.end(); it++)
	{
		s = s + *it;
	}
	return s;
}

void getGroup()                  //得到初始种群
{
	srand((unsigned int)time(NULL)); 
	vector<char> v;
	v.clear();
	for (char c = 'A'; c < 'A' + n; c++)
		v.push_back(c);

	//随机选取MAX_LENGTH个，得到初始的种群
	bestLength = MAX_LENGTH;
	string s;
	group.clear();
	for (int i = 0; i < MEMBER_NUMBER; i++)
	{
		s = getRands(v);
		group.push_back(s);
	}
}

void init()
{
	readData();
	getGroup();
}

void mating()                    //交配
{
	vector<string> temp;
	temp.clear();
	srand((unsigned int)time(NULL));
	for (vector<string>::iterator it  = group.begin(); it != group.end(); it++)
	{
		double p = (double)rand() / (double)(RAND_MAX);
		//如果满足进行交配的概率，则随机找另一个双亲，交配
		if (p < pc)
		{
			//另一个双亲
			int jt = rand() % (int)group.size();
			int count = 0;
			while (*it == group.at(jt) && count < 10)
			{
				jt = rand() % (int)group.size();
				count++;
			}
			//交配中交换一半的位置
			set<char> chars1;
			set<char> chars2;
			chars1.clear();
			chars2.clear();
			string string1 = *it;
			string string2 = group.at(jt);
					
			for (int i = 0; i < n / 2; i++)
			{
				int pos = rand() % n;				//随机选取交配的位点
				int count = 0;
				while (string1[pos] == string2[pos] && count < 10)//尽可能让交配位置上的基因不一样
				{
					pos = rand() % n;
					count++;
				}
				if (string1[pos] != string2[pos])
				{
					chars1.insert(string1[pos]);			//记下父亲1中这些位点上的基因
					chars2.insert(string2[pos]);			//记下父亲2中这些位点上的基因
				}
			}

			set<char>::iterator it = chars2.begin();
			for (int i = 0; i < n; i++)				//在父亲1中，去除父亲2上取出位点上的基因，并用取出的基因依次替代
			{
				if (chars2.count(string1[i]))
				{
					string1[i] = *it;
					it++;
				}
			}
			
			it = chars1.begin();
			for (int i = 0; i < n; i++)				//在父亲2中，去除父亲1上取出位点上的基因，并用取出的基因依次替代
			{
				if (chars1.count(string2[i]))
				{
					string2[i] = *it;
					it++;
				}
			}

			//把两个儿子加入种群
			temp.push_back(string1);
			//temp.push_back(string2);
		}
		else
		{
			//不交配则直接加入种群
			temp.push_back(*it);
		}
	}
	group.clear();
	group = temp;
}

void variation()          //变异
{
	for (vector<string>::iterator it  = group.begin(); it != group.end(); it++)
	{
		double p = (double)rand() / (double)(RAND_MAX);
		if (p < pm)
		{
			//如果满足变异的概率，就随机选取两个位置交换
			int posA = rand() % n;
			int posB = rand() % n;
			int count = 0;
			while ((*it)[posB] == (*it)[posA] && count <= 10)
			{
				int posB = rand() % n;
				count++;
			}
			char c = (*it)[posA];
			(*it)[posA] = (*it)[posB];
			(*it)[posB] = c;
		}
	}
}


double F(double currentlength)    //计算适应函数
{
	double pt;
	if (currentlength < preLength)
		pt = 200;
	else 
	{
		pt = 1/ fabs(preLength - currentlength);
		if (pt > 100)
			pt = 100;
	}
	return pt;
}

void inherit()                   //主要函数
{
	int count = 0;
	preLength = MAX_LENGTH;
	int g = 0;				//记录繁殖的代数
	while (true && g < 10000)
	{
		//计算当前最优解
		bestLength = MAX_LENGTH;
		for (vector<string>::iterator it = group.begin(); it != group.end(); it++)
			if (pathLength(*it) < bestLength)
			{
				bestLength = pathLength(*it);
				bestPath = *it;
			}
		cout << "\n当前代数：" << g << "\n路线：" << bestPath << "\t路程：" << bestLength << endl;

		//判断是否满足结束条件
		if(fabs(preLength - bestLength) < epsln) 
		{
			count++;
			//满足结束条件，输出终结状态，MAX_COUNT标记结束时要求的结果不变的次数
			if(count > ACCEPT_NUMBER) 
			{
				cout << "\n终结状态: ";
				cout << "\n路线：" << bestPath << "\t路程：" << bestLength << endl;
				return;
			}
		} 
		else 
		{
			if (preLength == MAX_LENGTH)
				preLength = preLength;
			preLength = bestLength;
			count = 0;
		}

		//计算总的指标函数值
		double totalF = 0.0;	
		for (vector<string>::iterator it = group.begin(); it != group.end(); it++)
			totalF += F(pathLength(*it));

		//用确定值法获得当代的种群
		vector<string> temp = group;
		group.clear();
		for (vector<string>::iterator it = temp.begin(); it != temp.end(); it++)
		{
			double p = F(pathLength(*it)) / totalF; //选择的概率

			for (int i = 0; i < floor(p * MEMBER_NUMBER + 0.5); i++)
				group.push_back(*it);
		}
		//cout << (int)group.size();

		//交配
		mating();

		//变异
		variation();

		g++;
	}
}

int main()
{
	init();
	inherit();
	system("pause");
	return 0;
}