遗传算法解决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()
{
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;
}
