genetic.cpp

使用遗传算法求解旅行商问题

/*遗传算法中：
  个体编码方案：整数编码
  交配方法：常规交配法
  变异方法：打乱变异（逆序交换）
  新种群构成方法：交配及变异后产生的所有子代
  算法结束条件：繁衍2000代
*/

#include<iostream>
#include<fstream>
#include<string>
#include<math.h>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;


struct City{																//城市结构
	string name;															//城市名
	int id;																	//城市对应的编码值
	double x;																//城市x坐标值
	double y;																//城市y坐标值
	bool accept;															//标记，在生成初始状态时判断该城市是否已经加入到状态中
};
City start[200][200];														//父代状态数组
City next[200][200];														//下一代状态数组
City last[200];																//最终状态数组
double f_val[200];															//适应值函数值数组
double f_last[200];															//每一代最终的所有种群的f函数值
double p[200];																//每个种群被选中的概率
int num;																	//城市数
double pm=0.1;																//突变概率
int select[200];															//每一代被选中进行繁衍的所有状态
double final=0.0;															//记录每代的最优解f值
bool ismated[200];															//判断当前状态是否交配过的标记


double calculate_f(City c[]){												//计算某一状态的f值
	int size=num;
	double distance=0.0;
	for(int i=0;i<size-1;i++){												//循环求得相邻城市之间的距离，并加到最终距离上
		double delta_x=c[i].x-c[i+1].x;
		double delta_y=c[i].y-c[i+1].y;
		distance=distance+sqrt(pow(delta_x,2.0)+pow(delta_y,2.0));
	}
	double delta_x=c[size-1].x-c[0].x;										//将最后一城市与第一个城市的距离加到最终距离上
	double delta_y=c[size-1].y-c[0].y;
	distance=distance+sqrt(pow(delta_x,2.0)+pow(delta_y,2.0));
	return distance;														//返回最终距离值
}

void mating(int i, int o){													//交配函数，将第i个被选中的状态和第o个被选中的状态进行交配，用的是常规交配法
	City temp[100];
	City temp2[100];
	for(int j=0;j<num;j++){
		temp[j]=next[i][j];
		temp2[j]=next[o][j];
	}
	int a=rand()%num;														//产生交配位
	int l=a;
	int change_num=9-a;
	int id_num[10];
	for(int j=0;j<change_num;j++){
		id_num[j]=temp[l].id;
		l++;
	}
	l=a;
	for(int j=0;j<num;j++){
		for(int k=0;k<change_num;k++){
			if(temp2[j].id==id_num[k]){
				next[i][l]=temp2[j];
				l++;
				break;
			}
		}
	}
	l=a;
	for(int j=0;j<change_num;j++){
		id_num[j]=next[o][l].id;
		l++;
	}
	l=a;
	for(int j=0;j<num;j++){
		for(int k=0;k<change_num;k++){
			if(temp[j].id==id_num[k]){
				next[o][l]=temp[j];
				l++;
				break;
			}
		}
	}
}

void search(){																	//遗传算法搜索最优解
	double count=2000;															//繁衍的代数
	int count2=0;																//计数，每次选择的状态数
	srand((unsigned int) time(NULL));											//设置种子
	while(count>0){
		count2=0;
		final=0.0;
		double f=0.0;
		for(int i=0;i<200;i++){
			f_val[i]=calculate_f(start[i]);
			f_val[i]=exp(-f_val[i]);											//适应值函数——e^(-f)，其中f为路径长度
		}
		for(int i=0;i<200;i++){
			f=f+f_val[i];														//适应值函数总和
		}
		for(int i=0;i<200;i++){
			p[i]=f_val[i]/f;													//状态被选中的概率
		}
		double p_select=0.0;
		while(count2<200){														//轮盘赌法选择
			double random=(double)rand()/RAND_MAX;
			p_select=0.0;
			for(int i=0;i<200;i++){
				p_select=p_select+p[i];
				if(p_select>=random){
					select[count2]=i;											//记录被选中状态的序号
					break;
				}
			}
			count2++;
		}
		for(int i=0;i<200;i++){
			for(int j=0;j<num;j++){
				next[i][j]=start[select[i]][j];									//取出被选中的状态
			}
		}
		int mate=100;															//两两交配，共进行100次
		for(int i=0;i<200;i++){
			ismated[i]=false;													//将每个状态是否交配过的标记设为false
		}
		while(mate>0){
			int a=rand()%200;													//产生两个未交配的不同的状态序号
			int b=0;
			while(ismated[a]==true){
				a=rand()%200;
			}
			b=rand()%200;
			while(a==b||ismated[b]==true){
				b=rand()%200;
			}
			mating(a,b);														//交配
			ismated[a]=true;													//将两者交配否的标记设为true
			ismated[b]=true;
			mate--;
		}
		double chance=(double)rand()/RAND_MAX;									//产生0——1的随机数
		if(chance<pm){															//若突变概率大于该随机数，则发生突变
			int w=rand()%200;													//产生随机数，代表突变的种群个数
			while(w>0){															
				int a=rand()%200;												//随机产生一个状态序号
				int pos1=rand()%num;											//产生两个突变位，逆序交换进行突变
				int pos2=rand()%num;
				while(pos2==pos1){
					pos2=rand()%num;
				}
				City temp[200];
				for(int i=0;i<pos1;i++){
					temp[i]=next[a][i];
				}
				int j=pos1;
				for(int i=pos2;i>=pos1;i--){
					temp[j]=next[a][i];
					j++;
				}
				for(int i=pos2+1;i<num;i++){
					temp[i]=next[a][i];
				}
				double f1=calculate_f(temp);
				double f2=calculate_f(next[a]);
				if(f1<f2){														//若突变出来的个体比原来好，则接收这次突变，否则淘汰突变出的新个体
					for(int i=0;i<num;i++){
						next[a][i]=temp[i];
					}
				}
				w--;
			}
		}
		for(int i=0;i<200;i++){													//将下一代种群赋给原来的父代，父代死亡
			for(int j=0;j<num;j++){
				start[i][j]=next[i][j];
			}
		}
		for(int i=0;i<200;i++){
			f_last[i]=calculate_f(start[i]);									//计算f值
		}
		int n=0;
		for(int i=0;i<200;i++){													//寻找最优解及对应的f值
			if(i==0){
				final=f_last[i];
			}
			else{
				if(final>f_last[i]){
					final=f_last[i];
					n=i;
				}
			}
		}
		for(int i=0;i<num;i++){													//输出最优解及f值
			cout<<start[n][i].name<<" ";
		}
		cout<<final<<endl;
		count--;
	}
}

int main(int argv, char *args[]){
	num=0;
	vector<City> cv;
	ifstream in(args[1]);													//从命令行读入文件名
	if(!in){
		cout<<"fail"<<endl;
		return -1;
	}
	in>>num;																//第一行为城市数
	for(int i=1;i<=num;i++){												//之后每一行均为城市名，x坐标和y坐标
		City c;
		in>>c.name;															
		in>>c.x;
		in>>c.y;
		c.id=i;
		c.accept=false;
		cv.push_back(c);
	}
	srand((unsigned int) time(NULL));										//设置种子
	for(int k=0;k<200;k++){													//产生初始的两百个种群
		for(int i=0;i<num;i++){							
			int j=rand()%num;												//生成0——n-1的随机数（n为城市数）
			if(cv[j].accept==false){										//若该城市未被加入到初始状态中，则加入之
				start[k][i]=cv[j];
				cv[j].accept=true;											//将已加入的标记设为true
			}
			else{															//否则重新生成随机数
				i--;
				continue;
			}
		}
		for(int c=0;c<num;c++){												//生成完一个个体后，将所有城市是否加入到状态中的标记设为false
			cv[c].accept=false;
		}
	}
	search();																//遗传算法搜索最优路径
	return 0;
}