tspga.txt

使用遗传算法解决TSP问题

　　/***********************************************************************
　　*遗传算法解决TSP问题 *
　　*code by 小白 at July.30 *
　　***********************************************************************/
　　def.h
　　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　　#ifndef _GENERATION_AMOUNT
　　#define _GENERATION_AMOUNT 201 //每一代的生存数
　　#define _CITY_AMOUNT 10 //城市数,等于基因数
　　//#define _XCHG_GENE_AMOUNT_WHEN_MIX 2 //每次杂交所交换的碱基数量 
　　#define _TIMES 50 //定义进化次数
　　#define _DISP_INTERVAL 5 //每隔多少次显示基因中的最高适应度
　　#define _CONTAINER std::vector<int> //定义个体基因容器类型
　　#define _CONTAINER_P std::vector<int> //定义适应度容器类型
　　#define _P(a,x,y) *(a+(x)+(y)*_CITY_AMOUNT) 
　　#define _P_GENE_ABERRANCE 10 //变异概率1%
　　#define _P_GENE_MIX (_GENERATION_AMOUNT-1)/2 //杂交次数
　　#define _INFINITE 100000
　　typedef int DISTANCE; //距离矩阵的数据存储类型
　　#endif
　　___________________________________________________________________________
　　TSP.cpp
　　____________________________________________________________________________
　　#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城市的距离
　　 /*
　　 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();
　　 }
　　 
　　 }
　　 CUnit.fnDispHistoryMin();
　　 
　　 
　　}
　　___________________________________________________________________________
　　tsp.h
　　___________________________________________________________________________
　　#include "def.h"
　　using namespace std;
　　template <typename T, typename P>
　　class Csga
　　{
　　 
　　public:
　　 Csga();
　　 Csga(DISTANCE *lpDistance); //构造函数
　　 ~Csga(); //析构函数 
　　 
　　 bool fnCreateRandomGene(); //产生随机基因
　　 bool fnGeneAberrance(); //基因变异
　　 bool fnGeneMix(); //基因交叉产生新的个体测试并淘汰适应度低的个体
　　 
　　 bool fnEvalAll(); //测试所有基因的适应度
　　 int fnEvalOne(T &Gene); //测试某一个基因的适应度
　　 void fnDispProbability(); //显示每个个体的权值
　　 void fnDispHistoryMin();
　　 
　　private:
　　 bool fnGeneAberranceOne(const int &i, const int &j);//变异某个基因
　　 T m_GenerationGene[_GENERATION_AMOUNT]; //定义每个群体的基因
　　 P m_vProbability; //定义每个群体的适应度
　　 DISTANCE *lpCityDistance;
　　 int HistoryMin;
　　 T HistoryMinWay;
　　 T m_GenerationGeneBk[_GENERATION_AMOUNT];
　　 
　　 
　　};
　　//构造函数
　　template <typename T, typename P>
　　Csga<T, P>::Csga()
　　{
　　}
　　template <typename T, typename P>
　　Csga<T, P>::Csga(DISTANCE *lpDistance)
　　{
　　 lpCityDistance = lpDistance;
　　 m_vProbability.reserve(_CITY_AMOUNT);
　　 HistoryMin = _INFINITE;
　　 
　　 //cout << _P(lpCityDistance, 3, 2); //调试用
　　}
　　//析构函数
　　template <typename T, typename P>
　　Csga<T, P>::~Csga()
　　{
　　}
　　//产生随机基因
　　template <typename T, typename P>
　　bool Csga<T, P>::fnCreateRandomGene()
　　{
　　 srand( time(0) ); //初始化随机数
　　 //cout << "\t基因序列" << std::endl; //调试用
　　 
　　 //生成随机基因
　　 for(int j, temp, i = 0; i < _GENERATION_AMOUNT; ++i)
　　 {
　　 m_GenerationGene[i].reserve(_CITY_AMOUNT);
　　 
　　 for (j = 0; j < _CITY_AMOUNT; ++j)
　　 {
　　 do
　　 {
　　 temp = rand()%_CITY_AMOUNT;
　　 }while (find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp)
　　 != m_GenerationGene[i].end());
　　 m_GenerationGene[i].push_back(temp);
　　 
　　 }//end for
　　 /*copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
　　 std::ostream_iterator<int>(cout," ") );
　　 cout << std::endl; */ //调试用
　　 }
　　 return true;
　　}
　　//基因变异
　　template <typename T, typename P>
　　bool Csga<T, P>::fnGeneAberrance()
　　{
　　 int i, j;
　　 int temp;
　　 srand(time(0));
　　 
　　 //抽选一代中的某个基因进行变异
　　 for (i = 0; i < _GENERATION_AMOUNT; ++i)
　　 {
　　 for (j = 0; j < _CITY_AMOUNT; ++j)
　　 {
　　 temp = rand()%10000;
　　 if ( temp > 0 && temp <= _P_GENE_ABERRANCE)
　　 {
　　 //随机抽选到的基因进行变异
　　 if(!fnGeneAberranceOne(i, j)) {exit(0);}
　　 }//end if
　　 }//end for j
　　 }//end for i 
　　 return true;
　　}
　　//变异第i个基因的第j位染色体
　　template <typename T, typename P>
　　bool Csga<T, P>::fnGeneAberranceOne(const int &i, const int &j)
　　{
　　 int temp; //基因变异结果
　　 srand(time(0));
　　 T::iterator pos;
　　 //找到变异位与另外一位交换
　　 pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);
　　 if (pos != m_GenerationGene[i].end())
　　 {
　　 *pos = m_GenerationGene[i][j];
　　 m_GenerationGene[i][j] = temp;
　　 return true;
　　 }
　　 return false;
　　}
　　inline int fnRndBoundary(int iBegin, int iEnd)
　　{ 
　　 
　　 return rand()%(iEnd-iBegin) + iBegin;
　　}
　　//基因交叉产生新的个体并淘汰适应度低的个体
　　template <typename T, typename P>
　　bool Csga<T, P>::fnGeneMix()