?? 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 <cmath>
#include <ctime>
#include <vector>
#include <hash_map>
#include <string>
#include <iostream>
#include <algorithm>
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<Gene*,float> linkCost; //該城市到其它城市的路程開銷
};
//染色體定義(到各城市順序的一種組合)
struct Chrom
{
vector<Gene*> chrom_gene; //染色體（到各城市去的順序）
float varible; //路程總開銷
float fitness; //個體適應度
};
//種群定義
struct Pop
{
vector<Chrom> pop_chrom; //種群里的染色體組
float sumfitness; //種群中個體適應度累計
};
Pop oldpop; //當前代種群
Pop newpop; //新一代種群
vector<Gene> genes(lchrom); //保存全部基因
//產生一個隨機整數(在[low,high)區間上)
inline int randomInt(int low,int high)
{
if(low==high)
return low;
return low+rand()%(high-low);
}
//計算一條染色體的個體適應度
inline void chromCost(Chrom& chr)
{
float sum=0;
for(int i=0;i<chr.chrom_gene.size()-1;i++)
{
sum += (chr.chrom_gene[i])->linkCost[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<pop.pop_chrom.size();i++)
{
sum+=pop.pop_chrom[i].fitness;
}
pop.sumfitness = sum;
}
void outChrom(Chrom& chr);
//隨機初始化一條染色體
inline void initChrom(Chrom& chr)
{
vector<int> tmp(lchrom);
for(int i=0;i<lchrom;i++)
tmp[i]=i;
int choose;
while(tmp.size()>1)
{
choose=randomInt(0,tmp.size());
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<popsize;i++)
{
initChrom(tmp);
pop.pop_chrom.push_back(tmp);
tmp.chrom_gene.clear();
}
popCost(pop);
}
//輪盤賭選擇,返回種群中被選擇的個體編號
inline int selectChrom(const Pop& pop)
{
float sum = 0;
float pick = float(randomInt(0,1000))/1000;
int i = 0;
if(pop.sumfitness!=0)
{
while(1)
{
sum += pop.pop_chrom[i].fitness/pop.sumfitness;
i++;
if( (sum > pick) || i==pop.pop_chrom.size())
return i-1; //
}
}
else
return randomInt(0,pop.pop_chrom.size());
}
//精英策略，返回最優秀的一條染色體
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<Gene*>::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<Gene*> v1(parent2.chrom_gene), v2(parent1.chrom_gene); //用于交叉的臨時表
//隨機選擇兩個交叉點
int pick1 = randomInt(1,lchrom-2);
int pick2 = randomInt(pick1+1,lchrom-1);
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<Gene*>::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> 40)
{
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 < 30);
}
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 < 30);
}
//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<<endl<<"路徑:";
for(int i=0;i<lchrom;i++)
{
cout<<chr.chrom_gene[i]->name;
}
cout<<endl<<"回路總開銷:"<<chr.varible<<endl;
cout<<"適應度:"<<chr.fitness<<endl;
}
int main()
{
cout<<"*************用遺傳算法解決TSP(旅行商)問題******************"<<endl;
//string names[lchrom]={"A","B","C","D","E","F","G","H","I","J"}; //基因（城市）名稱
string names[lchrom]={"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"};
//用矩陣保存各城市間的路程開銷
//float dist[lchrom][lchrom] = {{0,8,5,4,1,2,3,1,5,6},{8,0,4,6,7,1,6,5,4,1},{5,4,0,3,1,2,9,8,1,5},{4,6,3,0,2,1,8,1,9,6},{1,7,1,2,0,5,6,1,3,4},
//{2,1,2,1,5,0,7,3,2,8},{3,6,9,8,6,7,0,1,3,1},{1,5,8,1,1,3,1,0,9,2},{5,4,1,9,3,2,3,9,0,8},{6,1,5,6,4,8,1,2,8,0}};
float dist[lchrom][lchrom] ={{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}};
//初始化基因(所有基因都保存在genes中)
int i,j;
for(i=0;i<lchrom;i++)
{
genes[i].name =names[i];
for(j=0;j<lchrom;j++)
{
genes[i].linkCost[&genes[j]] = dist[i][j];
}
}
//輸出配置信息
cout<<"\n染色體長度:"<<lchrom<<"\n種群大小:"<<popsize<<"\n交叉率:"<<pcross<<"\n變異率:"<<pmutation;
cout<<"\n最大世代數:"<<maxgen<<"\n總運行次數:"<<maxruns<<"\n路徑最大連接開銷:"<<max_var<<endl;
//輸出路徑信息
cout<<endl<<" ";
for(int i=0;i<lchrom;i++)
cout<<genes[i].name<<" ";
cout<<endl;
for(int i=0;i<lchrom;i++)
{
cout<<genes[i].name<<":";
for(j=0;j<lchrom;j++)
{
cout<<genes[i].linkCost[&genes[j]]<<" ";
}
cout<<endl;
}
cout<<endl;
int best;
Chrom bestChrom; //全部種群中最佳染色體
bestChrom.fitness = 0;
float sumVarible = 0;
float sumFitness = 0;
//運行maxrns次
for(run = 1;run<=maxruns;run++)
{
initpop(oldpop); //產生初始種群
//通過不斷進化，直到達到最大世代數
for(gen = 1;gen<=maxgen;gen++)
{
generation(oldpop,newpop); //從當前種群產生新種群
oldpop.pop_chrom.swap(newpop.pop_chrom);
oldpop.sumfitness = newpop.sumfitness;
newpop.pop_chrom.clear();
}
best = chooseBest(oldpop); //本次運行得出的最佳染色體
if(oldpop.pop_chrom[best].fitness > bestChrom.fitness)
bestChrom = oldpop.pop_chrom[best];
sumVarible += oldpop.pop_chrom[best].varible;
sumFitness += oldpop.pop_chrom[best].fitness;
cout<<run<<"次"<<"Best:";
outChrom(oldpop.pop_chrom[best]); //輸出本次運行得出的最佳染色體
cout<<endl;
oldpop.pop_chrom.clear();
}
cout<<endl<<"一條最佳染色體:";
outChrom(bestChrom); //輸出全部種群中最佳染色體
cout<<endl<<endl<<"最佳染色體平均開銷:"<<sumVarible/maxruns;
cout<<endl<<"最佳染色體平均適應度:"<<sumFitness/maxruns<<endl;
system("PAUSE");
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -