www.pudn.com > 遗传算法解决TSP问题.rar > TSP_Demo.cpp
/*
用遗传算法(GA)解决TSP（旅行商）问题
完成时间:2005.8.2
编译环境:VC7.1 (用VC6的话需要修改几处，要把hash_map改为map)
作者:西南科技大学 唐坤(sf.tk)
QQ: 226152161
Blog: blog.gameres.com/show.asp?BlogID=1450&column=0
E-mail: starsftk@yahoo.com.cn
ps:初学遗传算法，很多都不懂，程序还有很多不足，若你改进了别忘了告诉我
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
float pcross = 0.85; //交叉率
float pmutation = 0.1; //变异率
int popsize = 300; //种群大小
const int lchrom = 20; //染色体长度
int gen; //当前世代
int maxgen = 100; //最大世代数
int run; //当前运行次数
int maxruns =10; //总运行次数
float max_var = 9 ; //路径最大连接开销!!
//基因定义(一个城市)
struct Gene
{
string name;
hash_map linkCost; //该城市到其它城市的路程开销
};
//染色体定义(到各城市顺序的一种组合)
struct Chrom
{
vector chrom_gene; //染色体（到各城市去的顺序）
float varible; //路程总开销
float fitness; //个体适应度
};
//种群定义
struct Pop
{
vector pop_chrom; //种群里的染色体组
float sumfitness; //种群中个体适应度累计
};
Pop oldpop; //当前代种群
Pop newpop; //新一代种群
vector genes(lchrom); //保存全部基因
//产生一个随机整数(在low和high之间)
inline int randomInt(int low,int high)
{
if(low==high)
return low;
return low+rand()%(high-low+1);
}
//计算一条染色体的个体适应度
inline void chromCost(Chrom& chr)
{
float sum=0;
for(int i=0;ilinkCost[chr.chrom_gene[i+1]];
}
sum += (chr.chrom_gene.front())->linkCost[chr.chrom_gene.back()];
chr.varible=sum;
chr.fitness=max_var*(lchrom) - chr.varible;
}
//计算一个种群的个体适应度之和
inline void popCost(Pop &pop)
{
float sum=0;
for(int i=0;i tmp(lchrom);
for(int i=0;i1)
{
choose=randomInt(0,tmp.size()-1);
chr.chrom_gene.push_back(&genes[tmp[choose]]);
tmp.erase(tmp.begin()+choose);
}
chr.chrom_gene.push_back(&genes[tmp[0]]);
chromCost(chr);
}
//随机初始化种群
inline void initpop(Pop& pop)
{
pop.pop_chrom.reserve(popsize);
Chrom tmp;
tmp.chrom_gene.reserve(lchrom);
for(int i=0;i pick) || i==pop.pop_chrom.size()-1)
return i-1; //??为什么返回29就会出错？？？
}
}
else
return randomInt(0,pop.pop_chrom.size()-2);
}
//精英策略，返回最优秀的一条染色体
inline int chooseBest(const Pop& pop)
{
int choose = 0;
float best = 0;
for(int i = 0;i< pop.pop_chrom.size();i++)
{
if(pop.pop_chrom[i].fitness > best)
{
best = pop.pop_chrom[i].fitness;
choose = i;
}
}
return choose;
}
//染色体交叉操作,由两个父代产生两个子代( 顺序交叉 OX )
inline void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)
{
child1.chrom_gene.resize(lchrom);
child2.chrom_gene.resize(lchrom);
vector::iterator v_iter,p1_beg,p2_beg,c1_beg,c2_beg,p1_end,p2_end,c1_end,c2_end;
p1_beg = parent1.chrom_gene.begin();
p2_beg = parent2.chrom_gene.begin();
c1_beg = child1.chrom_gene.begin();
c2_beg = child2.chrom_gene.begin();
p1_end = parent1.chrom_gene.end();
p2_end = parent2.chrom_gene.end();
c1_end = child1.chrom_gene.end();
c2_end = child2.chrom_gene.end();
vector v1(parent2.chrom_gene), v2(parent1.chrom_gene); //用于交叉的临时表
//随机选择两个交叉点
int pick1 = randomInt(1,lchrom-3);
int pick2 = randomInt(pick1+1,lchrom-2);
int dist = lchrom-1-pick2; //第二交叉点到尾部的距离
//子代保持两交叉点间的基因不变
copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1);
copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1);
//循环移动表中元素
rotate(v1.begin(), v1.begin()+pick2+1,v1.end());
rotate(v2.begin(), v2.begin()+pick2+1,v2.end());
//从表中除去父代已有的元素
for(v_iter = p1_beg+pick1; v_iter!=p1_beg+pick2+1; ++v_iter)
remove(v1.begin(),v1.end(),*v_iter);
for(v_iter = p2_beg+pick1; v_iter!=p2_beg+pick2+1; ++v_iter)
remove(v2.begin(),v2.end(),*v_iter);
//把表中元素复制到子代中
copy(v1.begin(), v1.begin()+dist, c1_beg+pick2+1);
copy(v1.begin()+dist, v1.begin()+dist+pick1, c1_beg);
copy(v2.begin(), v2.begin()+dist, c2_beg+pick2+1);
copy(v2.begin()+dist, v2.begin()+dist+pick1, c2_beg);
}
//染色体变异操作,随机交换两个基因
inline void mutation(Chrom& chr)
{
vector::iterator beg = chr.chrom_gene.begin();
int pick1,pick2;
pick1 = randomInt(0,lchrom-1);
do{
pick2 =randomInt(0,lchrom-1);
}while(pick1==pick2);
iter_swap(beg+pick1, beg+pick2);
}
//世代进化(由当前种群产生新种群)
void generation(Pop& oldpop,Pop& newpop)
{
newpop.pop_chrom.resize(popsize);
int mate1,mate2,j;
float pick;
float tmp;
Chrom gene1,gene2,tmp1,tmp2;
gene1.chrom_gene.resize(lchrom);
gene2.chrom_gene.resize(lchrom);
tmp1.chrom_gene.resize(lchrom);
tmp2.chrom_gene.resize(lchrom);
//将最佳染色体放入下一代
mate1 = chooseBest(oldpop);
newpop.pop_chrom[0] = oldpop.pop_chrom[mate1];
j = 1;
//产生两条新染色体
do{
int count = 0;
mate1 = selectChrom(oldpop);
mate2 = selectChrom(oldpop);
pick = float(randomInt(0,1000))/1000;
gene1= oldpop.pop_chrom[mate1];
gene2= oldpop.pop_chrom[mate1];
if(pick < pcross) //交叉操作
{
int count = 0;
bool flag1 = false;
bool flag2 = false;
while(1)
{
crossover(oldpop.pop_chrom[mate1],oldpop.pop_chrom[mate2],tmp1,tmp2);
chromCost(tmp1); //计算适应度
chromCost(tmp2);
if(tmp1.fitness > gene1.fitness)
{
gene1 = tmp1;
flag1 = true;
}
if(tmp2.fitness > gene2.fitness)
{
gene2 = tmp2;
flag2 = true;
}
if((flag1==true && flag2==true) || count> 50)
{
newpop.pop_chrom[j] = gene1;
newpop.pop_chrom[j+1] = gene2;
break;
}
count++;
}
}
else
{
newpop.pop_chrom[j].chrom_gene = oldpop.pop_chrom[mate1].chrom_gene;
newpop.pop_chrom[j+1].chrom_gene = oldpop.pop_chrom[mate2].chrom_gene;
chromCost(newpop.pop_chrom[j]);
chromCost(newpop.pop_chrom[j+1]);
}
pick = float(randomInt(0,1000))/1000;
if(pick < pmutation) //变异操作
{
int count = 0;
do{
tmp = newpop.pop_chrom[j].fitness;
mutation(newpop.pop_chrom[j]);
chromCost(newpop.pop_chrom[j]); //计算适应度
count++;
}while(tmp > newpop.pop_chrom[j].fitness && count < 50);
}
pick = float(randomInt(0,1000))/1000;
if(pick < pmutation) //变异操作
{
int count = 0;
do{
tmp = newpop.pop_chrom[j+1].fitness;
mutation(newpop.pop_chrom[j+1]);
chromCost(newpop.pop_chrom[j+1]); //计算适应度
count++;
}while(tmp > newpop.pop_chrom[j+1].fitness && count < 50);
}
//chromCost(newpop.pop_chrom[j]); //计算适应度
//chromCost(newpop.pop_chrom[j+1]);
j += 2;
}while(j < popsize-1);
popCost(newpop); //计算新种群的适应度之和
}
//输出一条染色体信息
inline void outChrom(Chrom& chr)
{
cout<name;
}
cout< bestChrom.fitness)
bestChrom = oldpop.pop_chrom[best];
sumVarible += oldpop.pop_chrom[best].varible;
sumFitness += oldpop.pop_chrom[best].fitness;
cout<