遗传算法求解CHN144城市的TSP问题

遗传算法求解CHN144城市的TSP 问题

#include    
#include    
#include    
#include “math.h“   
#include    
#include    
#include    
  
int randomi（int a int b）;   
double randomf（double a double b）;   
  
int randomi（int a int b）   
{   
    int c=rand（）%（b-a+1）+a;   
    return c;   
}   
  
double randomf（double a double b）   
{      
    double c = （double）（rand（）%（（int）b-（int）a）） + a + （double）（rand（）/（RAND_MAX + 1.0））;   
    return c;   
}   
  
  
class TSP_GA   
{   
public:   
    TSP_GA（）;   
    void generate（）;   
    void calculate（）;   
    bool accept（）;   
    void TSP_SA（）;   
    void onechain（）;   
    void twochain（）;   
    void threechain（）;   
    void firstgeneration（）;   
    void nextgeneration（）;   
    void crossone（）;   
    void crosstwo（）;   
    void TSP_GAA（）;   
    bool noIN（int aint b[]int iint c）;   
    void test（）;   
protected:   
private:   
    int r;   
    double d[144][144];   
    int point[144][2];   
    int p[144];   
    int c1;   
    int c2;   
    int c3;   
    double distance;   
    double df;   
    bool change;   
    int s;   
    int L;   
    int n;   
    double t;   
    double dt;   
    bool acc;   
  
    int pcurrent[100][144];   
    int pnext[200][144];   
    double distcurrent[100];   
    double distnext[200];   
    int nextnum;   
    int currentnum;   
};   
  
  
  
  
TSP_GA::TSP_GA（）   
{   
  
  int ij;   
	FILE * fp;
	if（（fp=fopen（“CHN144.TXT““r“））==NULL）
		return;
	fscanf（fp“%d“&n）;
	for （i=0;i<144;i++）
	{
		for （j=0;j<2;j++）
		{
			fscanf（fp“%d“&point[i][j]）;
		}
	}
	fclose（fp）;
	for （i=0;i<144;i++）
	{
		for （j=0;j<144;j++）
		{
			d[i][j]=sqrt（（point[i][0]-point[j][0]）*（point[i][0]-point[j][0]）+（point[i][1]-point[j][1]）*（point[i][1]-point[j][1]））;
			//	cout<		}
		//	cout<	}
	for （i=0;i	{
		p[i]=i;
	}
	distance=0;
	for （i=0;i	{
		j=i+1;
		distance+=d[i][j];
	}
	distance +=d[n-1][0];
	change=false;
	df=0;
	s=1;
	L=2000;
	t=500;
	dt=0.9;
	c1=0;
	c2=0;
	r=0;
	currentnum=50;   
  
}   
  
  
void TSP_GA::firstgeneration（）   
{   
    int ij;   
//	cout<    for （i=0;i    {   
        TSP_SA（）;  
//		cout<        distcurrent[i]=distance;   
        for （j=0;j        {   
            pcurrent[i][j]=p[j];   
        }   
    }   
	
}   
  
void TSP_GA::nextgeneration（）   
{   
    int i;   
    int jk;   
    nextnum=0;   
    crossone（）;   
//  crosstwo（）;   
    for （i=0;i    {   
        for （j=0;j        {   
            if （distnext[i]            {   
                distcurrent[j]=distnext[i];   
                for （k=0;k                {   
                    pcurrent[j][k]=pnext[i][k

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2184  2011-07-03 08:44  遗传算法求解TSP\CHN143.TXT

     文件       1710  2011-06-10 18:13  遗传算法求解TSP\CHN144.TXT

     文件       9608  2011-07-01 08:26  遗传算法求解TSP\GA.cpp

     文件      49664  2011-07-20 09:42  遗传算法求解TSP\报告.doc

     目录          0  2011-11-02 11:21  遗传算法求解TSP

----------- ---------  ---------- -----  ----

                63166                    5