tsp.cpp

本程序实现了多城市的tsp问题（即旅行商问题）的遗传算法

#include <fstream>
#include<iostream>
#include <vector>
#include <algorithm>
#include<math.h>
#include <time.h>
#include <stdlib.h>
#include "def.h"
#include "TSP.h"
void main()
{
   	ifstream input_file;
	ofstream output_file;
   time_t time1,time2;
    int _GENERATION_AMOUNT;
	int times;
	int _CITY_AMOUNT=-1;
	int ii,j,k;
	std::vector<double> x;
	std::vector<double> y;
	char readfile[50];
	const char* writefile="tsp.txt";
	double tempx[10000],tempy[10000];
	cout<<"打开城市坐标文件：";
	cin>>readfile;
	input_file.open(readfile);
	if(!input_file)
	{
		cout<<"打开错误！";
		return;
	}
   cout<<"读入城市坐标........"<<endl;
  while(1)
  {
	  if(!input_file.eof())
	  {
		  _CITY_AMOUNT++;
		  input_file>>tempx[_CITY_AMOUNT]>>tempy[_CITY_AMOUNT];
		  if(tempx[_CITY_AMOUNT]<0||tempy[_CITY_AMOUNT]<0)
		  {
			  cout<<"文件格式有误！";
			  return;
		  }
      }
	  else
		  break;
  }
  if( _CITY_AMOUNT==-1)
  {
			  cout<<"文件格式有误！";
			  return;
  }
    input_file.close();
  _CITY_AMOUNT=_CITY_AMOUNT+1;
  x.reserve(_CITY_AMOUNT);
  y.reserve(_CITY_AMOUNT);
  lpCityDistance.reserve(_CITY_AMOUNT*_CITY_AMOUNT);
  for(k=0;k<_CITY_AMOUNT;k++)
  {
	    x[k]=tempx[k];
		y[k]=tempy[k];
  }
   cout<<"已存入的城市信息为:"<<endl;
   for(ii=0;ii<_CITY_AMOUNT;ii++)
	   cout<<"第"<<ii+1<<"个城市"<<"("<<x[ii]<<","<<y[ii]<<")"<<endl;
   lpCityDistance.clear();
	for(k=0;k<_CITY_AMOUNT;k++)
	{
		lpCityDistance[k*_CITY_AMOUNT+k]=0;
		for(j=k+1;j<_CITY_AMOUNT;j++)
		{
		   lpCityDistance[k*_CITY_AMOUNT+j]=lpCityDistance[j*_CITY_AMOUNT+k]=sqrt((x[k]-x[j])*(x[k]-x[j])+(y[k]-y[j])*(y[k]-y[j]));
		}
	}
	 cout<<"输入进化代数:"<<endl;
	cin>>times;	
  cout<<"输入种群大小:(大于城市个数小于10000)"<<endl;
  cin>> _GENERATION_AMOUNT;
  while(_GENERATION_AMOUNT>=10000||_GENERATION_AMOUNT< _CITY_AMOUNT)
  {
	  cout<<"种群数输入错误!请重新输入(大于城市个数小于10000)"<<endl;
	  cin>> _GENERATION_AMOUNT;
  }
        Csga<_CONTAINER, _CONTAINER_P> CUnit(times,_GENERATION_AMOUNT,_CITY_AMOUNT);        //初始化
        time1=time(NULL);
        //开始遗传算法
      if(!CUnit.fnCreateRandomGene())  //产生随机基因                                                              //产生随机的基因
        {   
			exit(0);
        }
        
        //循环基因编译,杂交,淘汰过程
        CUnit.fnEvalAll();  //测试所有基因的适应度
        for ( int i = 0; i<times; ++i )
        {
                //CUnit.fnDispProbability();//显示每个个体的权值
                CUnit.fnGeneAberrance(); //基因变异                                                               //基因变异
                //CUnit.fnDispProbability();//显示每个个体的权值
               CUnit.fnGeneMix();//交叉产生新的个体测试并淘汰适应度低的个体                                                                               //基因杂交
                CUnit.fnEvalAll();   //测试所有基因的适应度                                                                             
  
               // 每隔_DISP_INTERVAL显示一次结果
               if ( (i+1)%_DISP_INTERVAL == 0 || i == 0)
                {
                        cout << "第" << i+1 << "代" <<endl;
                        CUnit.fnDispProbability();
                        CUnit.fnDispHistoryMin();
                }
        
        }

       CUnit.fnDispHistoryMin();
        time2=time(NULL);
		cout<<"\n\n计算用时为:"<<difftime(time2,time1)<<"s"<<endl;



}