tsp.cpp

利用遗传算法求解TSP问题。TSP问题描述如下：给定一组n个城市和他们两两之间地直达距离

/***********************************************************************
*遗传算法解决TSP问题 *
*code by 小白 at July.30 *
***********************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include "def.h"
#include "TSP.h"
void 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城市的距离
 
  
 Csga<_CONTAINER, _CONTAINER_P> CUnit((DISTANCE *)distance); //初始化
 
 //开始遗传算法
 if(!CUnit.fnCreateRandomGene()) //产生随机的基因
 {
	 printf("cuint fncreate err e\n");
 exit(0);
 }
  //循环基因编译,杂交,淘汰过程
 CUnit.fnEvalAll();

 //printf("cuint  here 3333 \n");
 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();
 }
 }
 CUnit.fnDispHistoryMin();
}