遗传算法求解背包问题.doc

开始

初始化

调用保证放入背包物品体积和不超过背包容量函数

达到算法终止条件？

结束
是

选择算子
否
达到种群大小？
将选择得到的两条染色体，进行杂交得到一条新的染色体，调用保证放入背包物品体积和不超过背包容量函数
杂交
从原种群中选择连续的几个染色体（随机），在选出来的染色体中选择适应度最大的一条染色体，如此进行两次得到两条父代染色体，调用保证放入背包物品体积和不超过背包容量函数

否

变异
变异
逐条考察染色体，判断是否要进行变异

是

得到新种群并赋值给旧种群
是

遗传算法的过程：
初始化：将计划装入背包的每个物品看成一个二进制串的一位，为1表示放入该物品，为0表示不放入该物品。
初始种群的产生：初始化前对放入背包物品数的一个预测（背包容积/物品最大体积），接下来只要在种群每条染色体中保证有（背包容积/物品最大体积）个为1的位初始化就完成了。
选择：选择进行杂交的父代染色体，被选中的父代染色体总是若干个染色体中最优（适应度最高）的，来保证向优化的方向发展。
详细的选择方法：
随机产生2个数：Chrom_Cross_From, Chrom_Cross_To,当然得采用一定的手段来保证前者比后者小。从Chrom_Cross_From到 Chrom_Cross_To这Chrom_Cross_To-Chrom_Cross_From+1条染色体中选择最优（适应度最大）的染色体作为父代之一。
需要进行两次选择得到杂交的两条父代染色体。
这样做可以保证算法不会过早收敛。
函数实现：
Individual Select(int ChromSize,Individual Pop[])
{
int Num_Selected,i,j,Chrom_Selected_From,Chrom_Selected_To,temp;
Individual *Chrom_Selected;

do{
Chrom_Selected_From=rand()%PopSize;
Chrom_Selected_To=rand()%PopSize;
if(Chrom_Selected_From>Chrom_Selected_To)
{
temp=Chrom_Selected_From;
Chrom_Selected_From=Chrom_Selected_To;
Chrom_Selected_To=temp;
}
Num_Selected=Chrom_Selected_To-Chrom_Selected_From+1;
}while(Num_Selected<=0);
Chrom_Selected=new Individual[Num_Selected];
for(i=0;i<Num_Selected;i++)
Chrom_Selected[i].chrom=new int[ChromSize];
for(i=0,j=Chrom_Selected_From;i<Num_Selected,j<Chrom_Selected_To+1;i++,j++)
{
Chrom_Selected[i]=Pop[j];
}
Order_Best_First(ChromSize,Num_Selected,Chrom_Selected);
Chrom_Selected[0].fitness=Fitness(Chrom_Selected[0].chrom,ChromSize);
return Chrom_Selected[0];
}
杂交：将两次选择得到的父代染色体进行杂交得到一条新的染色体，作为较新种群（并非新的种群）的一条染色体，杂交直到较新种群的染色体数等于原种群的染色体数。
杂交的详细方法：
假设选择得到的两条染色体分别为：Pop_Cross1，Pop_Cross2。
假设染色体的基因数为ChromSize，从0—ChromSize-1逐个考察染色体的基因
如果rand()%2=0新染色体的当前基因来自父代的第二条染色体，否则来自第一条染色体
函数实现：
Individual Cross(int chrom1[],int chrom2[],int ChromSize)
{
//;;;;;;;;杂交,接受的参数是两条染色体和染色体中基因的数目;;;;;;;
//;;;;;;;;返回一条染色体,及该染色体的适应度;;;;;;;;;;;;;;;;;;;;;
int i;
Individual Chrom_Return;
Chrom_Return.chrom=new int[ChromSize];
//;;;;;随机数为基数,当前基因来自第二条染色体,偶数则来自第一条染色体;;;;;;
for(i=0;i<ChromSize;i++)
{
if(rand()%2==1)
Chrom_Return.chrom[i]=chrom2[i];
else
Chrom_Return.chrom[i]=chrom1[i];
}
Chrom_Return.fitness=Fitness(Chrom_Return.chrom,ChromSize);
return Chrom_Return;
}
变异：对于杂交得到的较新种群的每条染色体，计算其（适应度/该种群中的最大适应度）并随即产生一个0—1的数，如果后者小于前者，则该条染色体需要进行变异（这样可以保证优秀的基因尽量保留）。
变异的特殊处理，随机产生一个0---ChromSize-1的数，如果该条染色体的该位基因为0变为1，否则继续上面的操作（保证向优化方向发展）。
函数实现：
void Variation(int chrom[],int ChromSize)
{
//;;;;;;;;;;;;产生一个随机位置进行变异;;;;;;;;;;
int location;
location=rand()%ChromSize;
if(chrom[location]==0)
chrom[location]=1;
}
保证放入背包物品体积和不超过背包容量函数详细实现：
传入参数为一条染色体，对于该条染色体，找出所有为1基因中适应度最小的基因并修改该基因为0。
函数实现如下：
void Guarantee(Individual Chrom,int ChromSize,int MaxVolume_Wallet)
{
//;;;用来保证背包中装入物品的体积不会超过背包的最大容积;;;;
//;;;如果某条染色体超标,逐个去掉效益最小的基因;;;;;;;;;;;;;
while(CurrentVolume(Chrom.chrom,ChromSize)>MaxVolume_Wallet)
{
Chrom.chrom[Min_Fitness_Location(Chrom.chrom,ChromSize)]=0;
}
}
参考资料：
多目标金华算法及其应用 ---------郑金华
演化程序-遗传算法和数据编码的结合------------美Z.米凯利维茨 著
周家驹 何险峰 译
网络资源：

程序源代码：
#include <iostream>
#include <stdio.h>
#include "math.h"
#include "time.h"
#include "stdlib.h"

using namespace std;

#define PopSize 8
#define Max 10000

typedef struct
{
char ObjectName[10];//物品名称
int Volume;//物品体积
int Benefit;//物品效益
}Object;
//标志物体的结构体

typedef struct
{
int *chrom;//染色体
int fitness;//适应度
}Individual;
//标志染色体的结构体

Object *object/*存储物品信息的数组*/;
Individual *oldpop,*newpop,best;

int MaxVolume(int Object_Num)
{
//求背包中体积最大的物品的体积
int max,i;
max=object[0].Volume;
for(i=1;i<Object_Num;i++)
{
if(object[i].Volume>max)
max=object[i].Volume;
}
return max;
}

//OK
int MinVolume(int Object_Num)
{
//求背包中体积最小的物品的体积
int min,i;
min=object[0].Volume;
for(i=1;i<Object_Num;i++)
{
if(object[i].Volume<min)
min=object[i].Volume;
}
return min;
}

//OK
void Malloc(int ChromSize)
{
//内存空间的分配
int i;
oldpop=new Individual[PopSize];
newpop=new Individual[PopSize];
for(i=0;i<PopSize;i++)
{
oldpop[i].chrom=new int[ChromSize];
newpop[i].chrom=new int[ChromSize];
}
best.chrom=new int[ChromSize];
}

//OK
int Fitness(int chrom[],int ChromSize)
{
//计算一条染色体的适应度
int i,fitness=0;
for(i=0;i<ChromSize;i++)
{
fitness+=object[i].Benefit*(chrom[i]);
}
return fitness;
}
//;;;;;;;;;;适应度的计算;;;;;;;;;;;;;;;
int SumFitness(Individual Pop[],int ChromSize)
{
//求一个种群的总适应度
int i,sumfitness=0;
for(i=0;i<PopSize;i++)
{
sumfitness+=Fitness(Pop[i].chrom,ChromSize);
}
return sumfitness;
}

int CurrentVolume(int chrom[],int ChromSize)
{
//计算当前方案背包中已放物品体积和
int i,volume=0;
for(i=0;i<ChromSize;i++)
{
volume+=object[i].Volume*(chrom[i]);
}
return volume;
}
//;;;;;;;;;;背包当前体积的计算;;;;;;;;;;;;;;;
int SumVolume(Individual *Pop,int ChromSize)
{
int i,sumvolume=0;
for(i=0;i<PopSize;i++)
{
sumvolume+=CurrentVolume(Pop[i].chrom,ChromSize);
}
return sumvolume;
}
int Volume_All_Object(int ChromSize)
{
int SumVolume=0,i;
for(i=0;i<ChromSize;i++)
SumVolume+=object[i].Volume;
return SumVolume;
}
void Initilize(int ChromSize,int PossibleNum)
{
//;;;;;;;;;初始化一个种群;;;;;;;;;;
srand((unsigned)time(NULL));
int i,j,location;
for(i=0;i<PopSize;i++)
for(j=0;j<ChromSize;j++)
{
oldpop[i].chrom[j]=0;
newpop[i].chrom[j]=0;
}

for(i=0;i<PopSize;i++)
{
for(j=0;j<PossibleNum;)
{
location=rand()%ChromSize;
if(oldpop[i].chrom[location]==0)
{
oldpop[i].chrom[location]=1;
j++;
}
}
}
}

void Order_Best_First(int ChromSize,int Pop_Size,Individual Pop[])
{
//;;;;;;;;;;;;;;选择优秀子代;;;;;;;;;;;;;;;;;
//;;;;;;;;;;排在前面的优于排在后面的;;;;;;;;;
Individual temp;
int i,j;
for(i=0;i<Pop_Size;i++)
for(j=0;j<Pop_Size-i-1;j++)
{
if(Pop[j].fitness<Pop[j+1].fitness)
{
temp=Pop[j];
Pop[j]=Pop[j+1];
Pop[j+1]=temp;
}
}
}

Individual Select(int ChromSize,Individual Pop[])
{
int Num_Selected,i,j,Chrom_Selected_From,Chrom_Selected_To,temp;
Individual *Chrom_Selected;

do{
Chrom_Selected_From=rand()%PopSize;
Chrom_Selected_To=rand()%PopSize;
if(Chrom_Selected_From>Chrom_Selected_To)
{
temp=Chrom_Selected_From;
Chrom_Selected_From=Chrom_Selected_To;
Chrom_Selected_To=temp;
}
Num_Selected=Chrom_Selected_To-Chrom_Selected_From+1;
}while(Num_Selected<=0);

Chrom_Selected=new Individual[Num_Selected];
for(i=0;i<Num_Selected;i++)
Chrom_Selected[i].chrom=new int[ChromSize];

for(i=0,j=Chrom_Selected_From;i<Num_Selected,j<Chrom_Selected_To+1;i++,j++)
{
Chrom_Selected[i]=Pop[j];
}
Order_Best_First(ChromSize,Num_Selected,Chrom_Selected);
Chrom_Selected[0].fitness=Fitness(Chrom_Selected[0].chrom,ChromSize);
return Chrom_Selected[0];
}

Individual Cross(int chrom1[],int chrom2[],int ChromSize)
{
//;;;;;;;;杂交,接受的参数是两条染色体和染色体中基因的数目;;;;;;;
//;;;;;;;;返回一条染色体,及该染色体的适应度;;;;;;;;;;;;;;;;;;;;;
int i;
Individual Chrom_Return;
Chrom_Return.chrom=new int[ChromSize];
//;;;;;随机数为基数,当前基因来自第二条染色体,偶数则来自第一条染色体;;;;;;
for(i=0;i<ChromSize;i++)
{
if(rand()%2==1)
Chrom_Return.chrom[i]=chrom2[i];
else
Chrom_Return.chrom[i]=chrom1[i];
}
Chrom_Return.fitness=Fitness(Chrom_Return.chrom,ChromSize);
return Chrom_Return;
}

void Variation(int chrom[],int ChromSize)
{
//;;;;;;;;;;;;产生一个随机位置进行变异;;;;;;;;;;
int location;
location=rand()%ChromSize;
if(chrom[location]==0)
chrom[location]=1;
}

int Min_Fitness_Location(int chrom[],int ChromSize)
{
int i,min_fitness=100000,min_fitness_location;
for(i=0;i<ChromSize;i++)
{
if(chrom[i]==1&&object[i].Benefit<min_fitness)
min_fitness_location=i;
}
return min_fitness_location;
}

void Guarantee(Individual Chrom,int ChromSize,int MaxVolume_Wallet)
{
//;;;用来保证背包中装入物品的体积不会超过背包的最大容积;;;;
//;;;如果某条染色体超标,逐个去掉效益最小的基因;;;;;;;;;;;;;
while(CurrentVolume(Chrom.chrom,ChromSize)>MaxVolume_Wallet)
{
Chrom.chrom[Min_Fitness_Location(Chrom.chrom,ChromSize)]=0;
}
}
int MaxFitness(Individual pop[])
{
int i,maxfitness=pop[0].fitness;
for(i=1;i<PopSize;i++)
{
if(pop[i].fitness>maxfitness)
maxfitness=pop[i].fitness;
}
return maxfitness;
}
void main()
{
//假定染色体产生变异的几率为10%,交叉的概率为70%
int Frequency=0,MaxVolume_Wallet/*背包最大容量*/,MaxVolume_Object,ChromSize/*物品总数*/,i,
j,TotalVolume=0/*所有物品的体积和*/,PossibleNum/*最优解的可能装入物品数*/;
int sum_fitness_old,sum_fitness_new;
FILE *fp;/*存储物品信息的文件的指针*/
Individual Pop_Cross1,Pop_Cross2;//用于杂交的两条染色体
srand((unsigned)time(0));

cout<<"请输入背包的最大容量:";
cin>>MaxVolume_Wallet;
fp=fopen("InheritData.dat","r");
fscanf(fp,"%d\n",&ChromSize);

object=new Object[ChromSize];
cout<<"物品信息:"<<endl<<" 物品名称 物品体积 物品效益"<<endl;
for(i=0;i<ChromSize;i++)
{
fscanf(fp,"%s %d %d\n",&object[i].ObjectName,&object[i].Volume,&object[i].Benefit);
cout<<" "<<object[i].ObjectName<<" "<<object[i].Volume<<" "<<object[i].Benefit<<endl;
TotalVolume+=object[i].Volume;
}
MaxVolume_Object=MaxVolume(ChromSize);
PossibleNum=MaxVolume_Wallet/MaxVolume_Object;
cout<<"Max volume of object:"<<MaxVolume_Object<<",Possible object Num be put in wallet:"<<PossibleNum<<endl;
//;;;;;;;;;;内存的分配;;;;;;;;;;;;;;;;;;;;;;;;;;
Malloc(ChromSize);
//;;;;;;;;;;;;;;;;;;初始种群的随机产生;;;;;;;;;;;;;;;;;;
Initilize(ChromSize,PossibleNum);
//;;;;;;;如果输入的背包最大容积小于物品的最小体积,则不能装入任何物品;;;;;;
cout<<"MinVolume:"<<MinVolume(ChromSize)<<endl;
if(MaxVolume_Wallet<MinVolume(ChromSize))
{
cout<<"the volume of wallet is too litter to put in any object!"<<endl;
for(i=0;i<ChromSize;i++)
best.chrom[i]=0;
}
//;;;;;;;如果输入的背包最大容积大于所有物品的体积和,则装入全部的物品;;;;;;
else if(MaxVolume_Wallet>Volume_All_Object(ChromSize))
{
cout<<"the volume of wallet is big enough to put in every object!"<<endl;
for(i=0;i<ChromSize;i++)
best.chrom[i]=1;
}
else
{
do
{
Pop_Cross1.chrom=new int[ChromSize];
Pop_Cross2.chrom=new int[ChromSize];
//;;;;;;;;;;;;;;;;;;计算适应度;;;;;;;;;;;;;;;;;;;;;;;;;;
//;;;;;;;;;;;;;;并保证种群的优异性;;;;;;;;;;;;;;;;;;;;;;
for(i=0;i<PopSize;i++)
{
Guarantee(oldpop[i],ChromSize,MaxVolume_Wallet);
oldpop[i].fitness=Fitness(oldpop[i].chrom,ChromSize);
}
for(i=0;i<PopSize;i++)
{
Pop_Cross1=Select(ChromSize,oldpop);
Pop_Cross2=Select(ChromSize,oldpop);
Guarantee(Pop_Cross1,ChromSize,MaxVolume_Wallet);
Guarantee(Pop_Cross2,ChromSize,MaxVolume_Wallet);
newpop[i]=Cross(Pop_Cross1.chrom,Pop_Cross2.chrom,ChromSize);
Guarantee(newpop[i],ChromSize,MaxVolume_Wallet);
}
//;;;;;;;;;;;;;;;;;;;;杂交操作结束;;;;;;;;;;;;;;;;;;;;;;
//;;;;;;;;;;;;;;;;;;;;变异操作开始;;;;;;;;;;;;;;;;;;;;;;
for(i=0;i<PopSize;i++)
{
if( (float)(rand()%100)/100 < (float)oldpop[i].fitness/MaxFitness(newpop)*0.6 )
{
Variation(newpop[i].chrom,ChromSize);
newpop[i].fitness=Fitness(newpop[i].chrom,ChromSize);
}
}
//;;;;;;;;;;;;;;;;;;;;变异操作结束;;;;;;;;;;;;;;;;;;;;;;
sum_fitness_old=SumFitness(oldpop,ChromSize);
sum_fitness_new=SumFitness(newpop,ChromSize);
for(i=0;i<PopSize;i++)
{
oldpop[i]=newpop[i];
}
Frequency++;
}while(/*Frequency<Max&&*/sum_fitness_old<sum_fitness_new);
cout<<"Frequency of Inherit:"<<Frequency<<endl;
Order_Best_First(ChromSize,PopSize,newpop);
}
best=newpop[0];
Guarantee(best,ChromSize,MaxVolume_Wallet);
cout<<"the object in wallet:"<<endl;
for(j=0;j<ChromSize;j++)
{
if(best.chrom[j]==1)
{
cout<<object[j].ObjectName<<" "<<object[j].Volume<<" "<<object[j].Benefit<<endl;
}
}
cout<<"Current Volume:"<<CurrentVolume(best.chrom,ChromSize)<<",Current Benefit:"<<Fitness(best.chrom,ChromSize)<<endl;

delete oldpop;
delete newpop;
fclose(fp);
}