tsp.cpp

hws01:野人和传教士问题 hws02:用Romberg外推法求积分近似值 hws03:八数码问题 hws04:模拟退火算法 hws05:遗传算法解决旅行商问题

/*
（1）给定群体规模N，交配概率pc和变异概率pm，t＝0；
（2）随机生成N个染色体作为初始群体；
（3）对于群体中的每一个染色体xi分别计算其适应值F(xi)；
（4）如果算法满足停止准则，则转（10）；
（5）对群体中的每一个染色体xi计算概率；
（6）依据计算得到的概率值，从群体中随机的选取N个染色体，得到种群；
（7）依据交配概率pc从种群中选择染色体进行交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中；
（8）依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体；
（9）用新群体代替旧群体，t=t+1，转（3）；
（10）进化过程中适应值最大的染色体，经解码后作为最优解输出；
（11）结束。 
*/
#include "head.h"
int main()
{
	char   filename[20];           //文本文件的名称
	cin>>filename;
    ifstream fin(filename);
	if(!fin)
	{
		cout<<"Open file error!"<<endl;
		return 0;
	}
	BuildCity(fin);                //从文本中读入建立城市
	BuildMatrix();                 //建立城市的距离矩阵
	srand((unsigned int) time(NULL));
	for(int j=0;j<15;j++)
	{
		thebest.F=0.0;
     	thebest.Ex=0.0;
		thebest.road.clear();
		GenGroup(Group);           //生成新的种群
		for(int i=0;i<Generation;i++){//遗传算法的停止准则，通过代数来控制
			figure();
			newGroup(Group);       //根据所得概率选取N个染色体，得到种群
			Mating(Group);         //基于位置的交配法
			Variation(Group);      //基于次序的变异函数
		}
		for(int i=0;i<Num;i++)
			cout<<city[thebest.road[i]].name<<" ";
		cout<<length(thebest.road)<<endl;
    }
	return 0;
}