test_tsp.h

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

#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];
     
     
};

 int temp;


//构造函数
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)) {cout<<"Gene Aberramce does not happen"<<endl;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()
{
     srand(time(0));
     std::vector<int> temp;                 //选择池
     P vProbabilityBk;                     //临时保存适应度
     vProbabilityBk = m_vProbability;
     temp.reserve( ((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2 );
     
     P::iterator pos;
     
     for (int i = _GENERATION_AMOUNT; i > 0; --i)
     {
         pos  = std::min_element(vProbabilityBk.begin(), vProbabilityBk.end());
         temp.insert( temp.end(), i, (int)(pos-vProbabilityBk.begin()) );
         *pos = _INFINITE; 
     }
     
     /**************************************************************************
     fnDispProbability();
     cout << "\ttemp\n" << std::endl;                     //调试用

         copy( temp.begin(), temp.end(), std::ostream_iterator<int>(cout," ") );
         cout << std::endl;                                 //调试用


     **************************************************************************/
     #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);

         /**********************************************************************
         cout << "iMother:" << iMother << std::endl;
         cout << "iFather:" << iFather << std::endl;
         cout << "LowBoundary:"  << LowBoundary  << std::endl;
         cout << "HighBoundary:" << HighBoundary << std::endl;
         **********************************************************************/

         
         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));
         /**********************************************************************
         cout << "Child1:" ;
         for (tempIter=Child1.begin(); tempIter!=Child1.end(); ++tempIter)
             cout << *tempIter << " ";
         cout << std::endl;
         cout << "Child2:" ;
         for (tempIter=Child2.begin(); tempIter!=Child2.end(); ++tempIter)
             cout << *tempIter << " ";
         cout << std::endl;
         **********************************************************************/

         std::rotate (fatherBk.begin(), fatherBk.begin()+HighBoundary+1, fatherBk.end());
         std::rotate (motherBk.begin(), motherBk.begin()+HighBoundary+1, motherBk.end());
         /**********************************************************************
         cout << "fatherBk:" ;
         copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         cout << "motherBk:" ;
         copy (motherBk.begin(), motherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         **********************************************************************/
         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());
         }
         /**********************************************************************
         cout << "fatherBk:" ;
         copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         cout << "motherBk:" ;
         copy (motherBk.begin(), motherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         **********************************************************************/

         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()));

         

         /**********************************************************************
         cout << "Child1:";
         copy (Child1.begin(), Child1.end(), std::ostream_iterator<int>(cout, " "));
         
         cout << "iChild1Probability:" << iChild1Probability << std::endl;
         cout << "Child2:" ;
         copy (Child2.begin(), Child2.end(), std::ostream_iterator<int>(cout, " "));
         cout << "iChild2Probability:" << iChild2Probability << std::endl;
         **********************************************************************/
         /*iChild1Probability = fnEvalOne(Child1);
         //iChild2Probability = fnEvalOne(Child2);

         
         
         P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());

         if (iChild1Probability < *P_iter)
         {
             m_GenerationGene[P_iter-m_vProbability.begin()] = Child1;
             *P_iter = iChild1Probability;
         }

         P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());
         if (iChild2Probability < *P_iter)
         {
             m_GenerationGene[P_iter-m_vProbability.begin()] = Child2;
             *P_iter = iChild2Probability;
         }
         */
         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];
         }
         
     }//end for (int j, i = 0; i < _GENERATION_AMOUNT; ++i)
     //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout," "));
     //cout << std::endl;

     //m_vProbability[_GENERATION_AMOUNT-1] = fnEvalOne(m_GenerationGeneBk[_GENERATION_AMOUNT-1]);
     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个体基因序列" <<std::endl;                     //调试用
     for (int i = 0; i < _GENERATION_AMOUNT; ++i)
     {
         cout << " 个体" << i+1 << "的基因:";
         copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
                                         std::ostream_iterator<int>(cout," ") );
         if (i%2 == 1)
             cout << std::endl;
     }
     */
     cout << "\t最小开销为:"; 
#define _VECT_TEMP     std::min_element(m_vProbability.begin(), m_vProbability.end())
     
     
     cout << *_VECT_TEMP << std::endl;//+_GENERATION_AMOUNT
     
     //cout << "各个方案的路程分别为:" ;
     //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout, " "));
     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;
}