tsp.h

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

#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);
 
 } 
 }
 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)) {
	 printf("eerr基因进行变异 :\n");
//	 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;
 //找到变异位与另外一位交换
 temp = rand()%_CITY_AMOUNT;
 
 pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);
// printf("temp is %d  pos %d",temp,*pos);
 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()
{
 srand(time(0));
 std::vector<int> temp; //选择池
 P vProbabilityBk; //临时保存适应度
 vProbabilityBk = m_vProbability;
 temp.reserve( ((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2 );
 
 P::iterator pos;
 int i;
  
 for ( i = _GENERATION_AMOUNT; i > 0; --i)
 {
 pos = std::min_element(vProbabilityBk.begin(), vProbabilityBk.end());
 temp.insert( temp.end(), i, (int)(pos-vProbabilityBk.begin()) );
 //printf("\nsss   %d ",*pos);;
 *pos = _INFINITE; 
 }
  #define _MIN_ELEMENT std::min_element(m_vProbability.begin(), m_vProbability.end())
 m_GenerationGeneBk[_GENERATION_AMOUNT-1] = m_GenerationGene[_MIN_ELEMENT - m_vProbability.begin()];
 
 int iFather; //父亲的代号
 int iMother; //母亲的代号
 T Child1, Child2; //父亲与母亲杂交出的子女的基因
 T::iterator tempIter;
 int LowBoundary;
 int HighBoundary;
 //int iChild1Probability,iChild2Probability;
 T fatherBk,motherBk;
 T::iterator V_iter;
 P::iterator P_iter;
 int iDistance;
 srand(time(0));
#ifndef _ITEMP
#define _ITEMP rand()%(((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2)
#endif
 for (i = 0; i < _P_GENE_MIX; ++i) //杂交_P_GENE_MIX/10次
 {
 iFather = temp[_ITEMP];
 do
 {
 iMother = temp[_ITEMP];
 }while(iMother == iFather);
 
 Child1.reserve(_CITY_AMOUNT); //初始化子女的碱基数
 Child2.reserve(_CITY_AMOUNT);
 Child1.clear();
 Child2.clear();
 
 LowBoundary = fnRndBoundary(0, _CITY_AMOUNT-2);
 HighBoundary= fnRndBoundary(LowBoundary+1, _CITY_AMOUNT-1);
  fatherBk = m_GenerationGene[iFather];
 motherBk = m_GenerationGene[iMother];
 std::copy (fatherBk.begin()+LowBoundary, fatherBk.begin()+HighBoundary+1, 
 std::back_inserter(Child1));
 
 std::copy (motherBk.begin()+LowBoundary, motherBk.begin()+HighBoundary+1,
 std::back_inserter(Child2));
  std::rotate (fatherBk.begin(), fatherBk.begin()+HighBoundary+1, fatherBk.end());
 std::rotate (motherBk.begin(), motherBk.begin()+HighBoundary+1, motherBk.end());
  for (V_iter = m_GenerationGene[iFather].begin()+LowBoundary;
 V_iter != m_GenerationGene[iFather].begin()+HighBoundary+1; ++V_iter)
 {
 motherBk.erase(std::remove(motherBk.begin(), motherBk.end(), *V_iter),
 motherBk.end());
 }
 
 for (V_iter = m_GenerationGene[iMother].begin()+LowBoundary;
 V_iter != m_GenerationGene[iMother].begin()+HighBoundary+1; ++V_iter)
 {
 
 fatherBk.erase(std::remove(fatherBk.begin(), fatherBk.end(), *V_iter),
 fatherBk.end());
 }
  iDistance = _CITY_AMOUNT -HighBoundary - 1;
 std::copy(motherBk.begin(), motherBk.begin()+iDistance, std::back_inserter(Child1));
 std::copy(motherBk.begin()+iDistance, motherBk.end(), std::inserter(Child1,Child1.begin()));
 std::copy(fatherBk.begin(), fatherBk.begin()+iDistance, std::back_inserter(Child2));
 std::copy(fatherBk.begin()+iDistance, fatherBk.end(), std::inserter(Child2,Child2.begin()));
 m_GenerationGeneBk[2*i] = Child1;
 m_GenerationGeneBk[2*i+1] = Child2;
 } 
 for (i = 0; i < _GENERATION_AMOUNT; ++i)
 {
 m_GenerationGene[i] = m_GenerationGeneBk[i];
 }
 
 
 return true;
}

//测试基因的适应度
template <typename T, typename P>
bool Csga<T, P>::fnEvalAll()
{
 int i, j;
 m_vProbability.assign( _GENERATION_AMOUNT, 0);
 //cout << "\t基因适应度\n";
 
 //测试每组基因的适应性
 for (i = 0; i < _GENERATION_AMOUNT; ++i)
 {
 for (j = 0; j < _CITY_AMOUNT-1; ++j)
 {
 m_vProbability[i] += _P(lpCityDistance, 
 m_GenerationGene[i][j], m_GenerationGene[i][j+1]);
 }//end for (j = 0; j < _CITY_AMOUNT; ++j); 
 m_vProbability[i] += _P(lpCityDistance, 
 m_GenerationGene[i][_CITY_AMOUNT-1], m_GenerationGene[i][0]);
 if (m_vProbability[i] < HistoryMin)
 {
 HistoryMin = m_vProbability[i];
 HistoryMinWay = m_GenerationGene[i];
 }
 
 }
 return true;
}



//测试某个基因的适应度并返回适应度
template <typename T, typename P>
int Csga<T, P>::fnEvalOne(T &Gene)
{
 int iResult = 0;
 
 for (int i = 0; i < _CITY_AMOUNT-1; ++i)
 {
 iResult += _P(lpCityDistance, Gene[i], Gene[i + 1]);
 }
 
 return iResult;
}








template <typename T, typename P>
void Csga<T, P>::fnDispProbability()
{
 cout << "\t最小开销为:"; 
#define _VECT_TEMP std::min_element(m_vProbability.begin(), m_vProbability.end())
 cout << *_VECT_TEMP << std::endl;//+_GENERATION_AMOUNT
 cout << std::endl;
 cout << "*******************************************************" << std::endl;
}




template <typename T, typename P>
void Csga<T, P>::fnDispHistoryMin()
{
 cout << "历史上最短开销为:"<< HistoryMin << " 路径为:" ;
 std::copy (HistoryMinWay.begin(), HistoryMinWay.end(), std::ostream_iterator<int>(cout, " ->"));
 cout << *HistoryMinWay.begin();
 cout <<std::endl;
}