tsp.h

ga算法解tsp问题.动态TSP就是城市坐标在随着时间变化,我们的目标则要在最短的时间窗内寻找出最优的城市遍历路径,这是个双最优问题. 这是我对动态TSP算法的理解,使用改进的反序-杂交算法

#include <cstdio>
#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);}
                 fnGeneAberranceOne(i, j);
             }//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));

     typename T::iterator pos;

     //找到变异位与另外一位交换
     pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);

     printf("%d\n", m_GenerationGene[i].end());
	 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 );
     
     typename 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; 
     }
     #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;                     //父亲与母亲杂交出的子女的基因
     typename T::iterator tempIter;
     int LowBoundary;
     int HighBoundary;
     //int iChild1Probability,iChild2Probability;
     T fatherBk,motherBk;
     typename T::iterator V_iter;
     typename 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];
         }
         
     }//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最小路程为:"; 
#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;
}