C++程序遗传算法TSP.docx

C++程序遗传算法TSP.docx

《C++程序遗传算法TSP.docx》由会员分享，可在线阅读，更多相关《C++程序遗传算法TSP.docx（10页珍藏版）》请在冰点文库上搜索。

C++程序遗传算法TSP

#include

#include

#include

#include

#include

#include

#include

usingnamespacestd;

#definePOPULATION1000

#defineMUTATION_RATE0.5

#defineCROSSOVER_RATE0.7

#defineMAXCITYNUM100

#defineELITISMNUMBER20

intDistanceData[MAXCITYNUM][MAXCITYNUM];//最多计算100城市

intCityNum;//实际计算的城市数

intLongest;//当代的最长路径

intShortest;//当代的最短路径

intRandInt（intx,inty）

{

returnrand（）%（y-x+1）+x;

}

voidreadData（char*filename）{//读入城市距离矩阵

FILE*p;

p=fopen（filename,"r"）;

fscanf（p,"%d",&CityNum）;

for（inti=1;i<=CityNum;i++）{

for（intj=1;j<=CityNum;j++）{

fscanf（p,"%d",&DistanceData[i][j]）;

}

}

}

classroute{//一个个体

public:

intRouterNode[MAXCITYNUM];

intTotalDistance;

intFitNess;

booloperator==（constroute&lhs）

{

for（inti=0;i

if（RouterNode[i]!

=lhs.RouterNode[i]）returnfalse;

}

returntrue;

}

};

routeOneGeneration[POPULATION];//一代

routeTmpGeneration[POPULATION];//中间一代

voidCountRouteDistance（route&r）{//计算每个个体的路径长度

r.TotalDistance=0;

for（inti=0;i

r.TotalDistance+=DistanceData[r.RouterNode[i]][r.RouterNode[i+1]];

}

r.TotalDistance+=DistanceData[r.RouterNode[CityNum-1]][r.RouterNode[0]];

}

voidmySwap（int&t1,int&t2）{

inttmp;

tmp=t1;

t1=t2;

t2=tmp;

}

voidgrabPermutation（route&r）{//产生一个随机排列

inti=0;

for（i=0;i

r.RouterNode[i]=i+1;

}

for（i=0;i

inttmp=RandInt（i,CityNum-1）;

mySwap（r.RouterNode[i],r.RouterNode[tmp]）;

}

}

voidinitializeFirstGun（）{//初始化第一代

inti;

for（i=0;i

grabPermutation（OneGeneration[i]）;

}

}

voidcalculateFitness（）{//计算一代的适应性

inti;

for（i=0;i

CountRouteDistance（OneGeneration[i]）;

if（OneGeneration[i].TotalDistance>Longest）Longest=OneGeneration[i].TotalDistance;

if（OneGeneration[i].TotalDistance

}

for（i=0;i

OneGeneration[i].FitNess=Longest-OneGeneration[i].TotalDistance;

}

}

voidelitism（intDangQianDaiShu）{//每一代最优秀的前几个保留

//冒泡排序

inti,j;

routetmp;

for（i=1;i

for（j=0;j<=POPULATION-1-i;j++）{

if（OneGeneration[j].FitNess

tmp=OneGeneration[j];

OneGeneration[j]=OneGeneration[j+1];

OneGeneration[j+1]=tmp;

}

}

}

for（i=0;i

TmpGeneration[i]=OneGeneration[i];

}

printf（"第%d代;路径长度%d;路径:

",DangQianDaiShu,OneGeneration[0].TotalDistance）;

for（i=0;i

printf（"%d",OneGeneration[0].RouterNode[i]）;

}

printf（"\n"）;

}

routeselection（）{

intBestFitness=0;

intPosition;

intRandShu;

inti;

for（i=0;i

RandShu=RandInt（0,POPULATION-1）;

if（OneGeneration[RandShu].FitNess>BestFitness）{

Position=RandShu;

BestFitness=OneGeneration[RandShu].FitNess;

}

}

returnOneGeneration[Position];

}

floatRandFloat（）

{return（rand（））/（RAND_MAX+1.0）;}

voidcrossover（routemather,routefather,route&baby1,route&baby2）{

baby1=mather;

baby2=father;

if（（RandFloat（）>CROSSOVER_RATE）||（mather==father））

{

return;

}

//firstwechooseasectionofthechromosome

intbeg=RandInt（0,CityNum-2）;

intend=beg;

//findanend

while（end<=beg）

{

end=RandInt（0,CityNum-1）;

}

for（intpos=beg;pos

//thesearethegeneswewanttoswap

intgene1=mather.RouterNode[pos];

intgene2=father.RouterNode[pos];

//findandswaptheminbaby1

inttmp1;

inttmp2;

inti;

for（i=0;i

for（i=0;i

mySwap（baby1.RouterNode[tmp1],baby1.RouterNode[tmp2]）;

//findandswaptheminbaby2

for（i=0;i

for（i=0;i

mySwap（baby2.RouterNode[tmp1],baby2.RouterNode[tmp2]）;

}

}

voidmutate（route&baby）{

routetemp;

if（RandFloat（）>MUTATION_RATE）return;

if（RandFloat（）>0.5）{

inttmp1;

inttmp2;

//for（inti=1;i<=10;i++）{

temp=baby;

tmp1=RandInt（0,CityNum-1）;

tmp2=RandInt（0,CityNum-1）;

if（tmp1>tmp2）mySwap（tmp1,tmp2）;

inti;

for（i=tmp1;i<=tmp2;i++）{

baby.RouterNode[i]=temp.RouterNode[tmp1+tmp2-i];

}

//mySwap（baby.RouterNode[tmp1],baby.RouterNode[tmp2]）;

//}

}

else{

for（inti=0;i

inttmp=RandInt（i,CityNum-1）;

mySwap（baby.RouterNode[i],baby.RouterNode[tmp]）;

}

}

}

voidmain（intargc,char*argv[]）{

srand（（unsigned）time（NULL））;

//初始化城市距离矩阵

readData（argv[1]）;

//初始化第一代

initializeFirstGun（）;

Longest=0;

Shortest=99999999;

intDijidai=1;

while

（1）{

Longest=0;

Shortest=99999999;

calculateFitness（）;

elitism（Dijidai）;

if（Dijidai>2000）break;

Dijidai++;

//选择&&杂交&&变异

intNowGunNum=ELITISMNUMBER;

while

（1）

{

routemather=selection（）;

routefather=selection（）;

routebaby1;

routebaby2;

crossover（mather,father,baby1,baby2）;

mutate（baby1）;

mutate（baby2）;

if（NowGunNum

TmpGeneration[NowGunNum]=baby1;

TmpGeneration[NowGunNum+1]=baby2;

NowGunNum++;

NowGunNum++;

}

else{

printf（"NowGunNum=%d\n",NowGunNum）;

break;

}

}

for（inti=0;i

OneGeneration[i]=TmpGeneration[i];

}

}

}