*遗传算法解决TSP问题
/***********************************************************************/
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)
{
评论0