bagcopy.cpp

采用遗传算法解决０-１背包问题 并采用了二重编码形式

#include <cmath>
#include <ctime>
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

float pcross = 0.85; //交叉率
float pmutation = 0.1; //变异率
int popsize = 30; //种群大小
const int lchrom = 5; //染色体长度
const int maxweight=200;
int gen; //当前世代
int maxgen = 100; //最大世代数
int run; //当前运行次数
int maxruns =10; //总运行次数

//基因定义(一件物品)
/*struct Gene
{ 
string name;
map<Gene*,char> ch;
map<Gene*,float> weight; 
map<Gene*,float> profit;
};*/
struct Gene
{ 
string name;
char ch;
float weight; 
float profit;
//float midu;
//map<Gene*,float> midu;
};



//染色体定义()
struct Chrom
{
vector<Gene*> chrom_gene; //染色体
float sumweight; //
float fitness; //个体适应度 
};

//种群定义
struct Pop
{
vector<Chrom> pop_chrom; //种群里的染色体组
float sumfitness; //种群中个体适应度累计 
};


Pop oldpop; //当前代种群
Pop newpop; //新一代种群
vector<Gene> genes(lchrom); //保存全部基因  const int lchrom = 20; //染色体长度

bool myfunction (const Gene &i, const Gene &j) 
{ return (i.profit/i.weight) > (j.profit/j.weight); }
      
 
//计算一条染色体的个体适应度
inline void chromCost(Chrom &chr)
{
float sumw=0,sump=0;
/*struct Gene 
{  
    string name; 
    char ch; 
    float weight;  
    float profit; 
}; */

//vector<Gene> myvector;
//sort (chr.chrom_gene.begin(), chr.chrom_gene.end(), myfunction); //对该染色体中的基因进行排序

for(int i=0;i<chr.chrom_gene.size()-1;i++)  //chr.chrom_gene.size()一个染色体中基因的个数 size() Returns the number of components in this vector.
{
        if((sumw>maxweight)&&(chr.chrom_gene[i]->ch=='1'))
chr.chrom_gene[i]->ch='0';
else
{sumw += (chr.chrom_gene[i]->ch-'0')*chr.chrom_gene[i]->weight;
sump += (chr.chrom_gene[i]->ch-'0')*chr.chrom_gene[i]->profit;
}
chr.sumweight=sumw;
chr.fitness=sump;
}
}

//计算一个种群的个体适应度之和
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);
//my_compare(float )
//随机初始化一条染色体(编码)
inline void initChrom(Chrom &chr)
{ 
//vector<int> tmp(lchrom);
double sumw=0;
//for(int i=0;i<lchrom;i++)
//tmp[i]=i;
srand( (unsigned)time( NULL ) );
int choose;

for(int i=0;i<lchrom;i++)//
{genes[i].ch=(rand()%10<5)?'0':'1';
//cout<<genes[i].ch;
}

for(int i=0;i<lchrom;i++)
 {       //choose=rand()%tmp.size();//随机选择一个基因的下标
 choose=rand()%lchrom;
chr.chrom_gene.push_back(&genes[choose]);
//cout<<chr.chrom_gene[i]->ch;
}
cout<<endl;

for(int i=0;i<lchrom;i++)
{if((sumw>maxweight)&&(chr.chrom_gene[i]->ch=='1'))
chr.chrom_gene[i]->ch='0';
else
sumw += (chr.chrom_gene[i]->ch-'0')*((chr.chrom_gene[i])->weight);
}
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;
srand( (unsigned)time( NULL ) );
float pick = (rand()%((int)pop.sumfitness)+1)/10000.0;
int i = 0;
if(pop.sumfitness!=0)
{
while(1)
{
sum += pop.pop_chrom[i].fitness;
i++;
if( (sum > pick) || i==pop.pop_chrom.size())
return i-1; //
} 
}
else
return rand()%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;
}
//染色体交叉操作,由两个父代产生两个子代
inline void crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)
{


//随机选择两个交叉点
srand( (unsigned)time( NULL ) );
int pick1 = rand()%(lchrom-1);
int pick2 = pick1+1+rand()%lchrom;

char tempch;
string tempname;
int i,j,choose1,choose2;
for(i=pick1+1;i<=pick2;i++)
{tempname=parent2.chrom_gene[i]->name;
for(j=0;j<lchrom;j++)
{
if(parent1.chrom_gene[j]->name==tempname)
   {choose1=j;
      break;}
}
tempname=parent1.chrom_gene[i]->name;
for(j=0;j<lchrom;j++)
{
if(parent2.chrom_gene[j]->name==tempname)
   {choose2=j;
      break;}
}
tempch=parent1.chrom_gene[choose1]->ch;
parent1.chrom_gene[choose1]->ch=parent1.chrom_gene[pick1]->ch;
parent1.chrom_gene[pick1]->ch=tempch;
tempch=parent2.chrom_gene[choose2]->ch;
parent2.chrom_gene[choose2]->ch=parent2.chrom_gene[pick1]->ch;
tempch=parent2.chrom_gene[choose2]->ch;
}
child1.chrom_gene.swap(parent1.chrom_gene);
child2.chrom_gene.swap(parent2.chrom_gene);
}


/*//染色体交叉操作,由两个父代产生两个子代( 顺序交叉 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); //用于交叉的临时表 

//随机选择两个交叉点
srand( (unsigned)time( NULL ) );
int pick1 = rand()%(lchrom-1);
int pick2 = pick1+1+rand()%lchrom;
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;
char temp;
pick1 = rand()%lchrom;
do{
pick2 =rand()%lchrom;
}while(pick1==pick2||chr.chrom_gene[pick1]->ch==chr.chrom_gene[pick2]->ch);//满足该条件，则继续do操作 
temp=chr.chrom_gene[pick1]->ch;
chr.chrom_gene[pick1]->ch=chr.chrom_gene[pick2]->ch;
chr.chrom_gene[pick2]->ch=temp;
}

//世代进化(由当前种群产生新种群)
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;//表示新种群中的染色体个数 ，从0开始计数 

//产生两条新染色体
do{
int count = 0;
mate1 = selectChrom(oldpop);//轮盘赌选择,返回种群中被选择的个体编号 
mate2 = selectChrom(oldpop);
pick = float(rand()%1000)/1000;
gene1= oldpop.pop_chrom[mate1];//将通过轮盘赌所选择的染色体赋给gene1,gene2 
gene2= oldpop.pop_chrom[mate1];

if(pick < pcross) //交叉操作 ，随机产生的数小于交叉率则进行该操作 float pcross = 0.85; //交叉率
{
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;//退出while循环 
}
count++;
} //while(1)的结束点 
}
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(rand()%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(rand()%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);
int i;
for(i=0;i<popsize;i++)
{for(j=0;j<lchrom;j++)
cout<<newpop.pop_chrom[i].chrom_gene[j]->ch;
cout<<"  ";
}
popCost(newpop); //计算新种群的适应度之和 
}

//输出一条染色体信息
inline void outChrom(Chrom& chr)
{
cout<<endl<<"选择情况:";
for(int i=0;i<lchrom;i++)
{
  if(chr.chrom_gene[i]->ch=='1')  
cout<<chr.chrom_gene[i]->name;
}
cout<<endl<<"装入背包的总重量:"<<chr.sumweight<<endl;
cout<<"适应度:"<<chr.fitness<<endl;
}

int main()
{
    time_t   start   =   clock(); 

cout<<"*************用遗传算法解决背包问题******************"<<endl;
//初始化基因(所有基因都保存在genes中) 
int i,j;

cout<<"请输入物件的名称:"<<endl;
for(i=0;i<lchrom;i++)
cin>>genes[i].name ;
cout<<endl;
cout<<"请输入物件的重量:"<<endl;
for(i=0;i<lchrom;i++)
cin>>genes[i].weight ;
cout<<endl;
cout<<"请输入物件的价值:"<<endl;
for(i=0;i<lchrom;i++)
cin>>genes[i].profit ;
cout<<endl;

                    
//输出配置信息
cout<<"\n染色体长度:"<<lchrom<<"\n种群大小:"<<popsize<<"\n交叉率:"<<pcross<<"\n变异率:"<<pmutation;
cout<<"\n最大世代数:"<<maxgen<<"\n总运行次数:"<<maxruns<<"\n背包的最大容量"<<maxweight<<endl;


/*输出路径信息

cout<<endl<<"   ";
for(i=0;i<lchrom;i++)
cout<<genes[i].name<<"  ";
cout<<endl; 

cout<<"weight:";
for(i=0;i<lchrom;i++)
cout<<genes[i].weight<<" ";
cout<<endl;

cout<<"profit:";
for(i=0;i<lchrom;i++)
cout<<genes[i].profit<<" ";
cout<<endl;*/

sort (genes.begin(), genes.end(), myfunction); //对该染色体中的基因进行排序

/*//输出排序后的信息

cout<<endl<<"   ";
for(i=0;i<lchrom;i++)
cout<<genes[i].name<<"  ";
cout<<endl; 

cout<<"weight:";
for(i=0;i<lchrom;i++)
cout<<genes[i].weight<<" ";
cout<<endl;

cout<<"profit:";
for(i=0;i<lchrom;i++)
cout<<genes[i].profit<<" ";
cout<<endl;*/

int best;
Chrom bestChrom; //全部种群中最佳染色体
bestChrom.fitness = 0;
//float sumWeight = 0;//整个种群的重量 
//float sumFitness = 0;//整个种群的价值 

//运行maxrns次,即随机产生 maxrns最优结果
for(run = 1;run<=maxruns;run++)
{
initpop(oldpop); //产生初始种群
/*for(i=0;i<popsize;i++)//输出初始种群 
{for(j=0;j<lchrom;j++)
cout<<oldpop.pop_chrom[i].chrom_gene[j]->ch;
cout<<endl;
}*/

//通过不断进化，直到达到最大世代数
for(gen = 1;gen<=maxgen;gen++)
{ 
generation(oldpop,newpop); //从当前种群产生新种群

oldpop.pop_chrom.swap(newpop.pop_chrom); //slist1.swap(slist2);如果slist1有10个元素，slist2有20个元素，那赋值后，slit1的前10个元素将被删除。它的容量是动态的，不必担心大小问题。
oldpop.sumfitness = newpop.sumfitness;
newpop.pop_chrom.clear(); 
}
best = chooseBest(oldpop); //本次运行得出的最佳染色体
if(oldpop.pop_chrom[best].fitness > bestChrom.fitness)
bestChrom = oldpop.pop_chrom[best];
//sumWeight += oldpop.pop_chrom[best].sumweight;
//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<<"最佳染色体平均开销:"<<sumWeight/maxruns;
//cout<<endl<<"最佳染色体平均适应度:"<<sumFitness/maxruns<<endl;
//system("PAUSE");
//return 0;
time_t   end   =   clock();   
  double   dur   =   static_cast<double>(end -start)/CLOCKS_PER_SEC   *   1000;   
  cout   <<   "\n您的程序执行所耗费的时间为:   "   <<   dur   <<   "   毫秒"   <<   endl;   
 
}