ga_tsp.cpp

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

/***********************************************************************
*遗传算法解决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
 #include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.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()
{
 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;
}