tsp_test.cpp

这是一篇关于遗传算法求解TSP问题的源码,用C++编写,带注释.

// tsp_test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>

#include "def.h"
#include "test_tsp.h"

/*
int main(t arginc, char* argv[])
{
	printf("Hello World!\n");
	return 0;
}
--*/




int  main( )
{
     
    const static DISTANCE distance[][_CITY_AMOUNT] 
                                 =     {
                                         0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
                                         1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
                                         4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
                                         6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
                                         8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
                                         1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
                                         3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
                                         7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
                                         2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
                                         9, 4, 2, 1, 6, 5, 9, 3, 1, 0
                                     };                             //城市间的距离矩阵
                                                                 //distance[i][j]代表i城市与j城市的距离

    
     /*  const static DISTANCE distance[][_CITY_AMOUNT]
                                                 ={
                                 0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8,
                                 1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1,
                                 4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8, 1, 8, 9, 4, 7, 4, 8, 4,
                                 6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2,
                                 8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7,
                                 1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1,
                                 3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1,
                                 7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7, 6, 3, 3, 8, 3, 5,
                                 2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7,
                                 9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5,
                                 7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3,
                                 3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3, 
                                 4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4, 8, 3, 5, 3,
                                 5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5,
                                 8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4, 
                                 9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4, 
                                 2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7,
                                 8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6,
                                 2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4, 
                                 8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3, 3, 5, 4, 4, 7, 6, 4, 0
                                                 };
*/

     Csga<_CONTAINER, _CONTAINER_P> CUnit((DISTANCE *)distance);     //初始化
     
     //开始遗传算法
     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 << "代" << std::endl;
             CUnit.fnDispProbability();
             CUnit.fnDispHistoryMin();
			 cout<<endl<<"_____________________________________________________"<<endl;
         }
     
     }
	 cout<<endl<<"最终结果："<<endl;
     CUnit.fnDispHistoryMin();
      return 0;
}