王朝网络
分享
 
 
 

遗传算法解决TSP问题

王朝other·作者佚名  2006-01-10
宽屏版  字体: |||超大  

/***********************************************************************

*遗传算法解决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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
>>返回首页<<
推荐阅读
 
 
频道精选
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有