遗传算法求解背包问题.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;ii]=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;iChrom_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
#include
#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;imax)
max=object[i].Volume;
}
return max;
}

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

//OK
void Malloc(int ChromSize)
{
//内存空间的分配
int i;
oldpop=new Individual[PopSize];
newpop=new Individual[PopSize];
for(i=0;iitness(int chrom[],int ChromSize)
{
//计算一条染色体的适应度
int i,fitness=0;
for(i=0;i0;i体积的计算;;;;;;;;;;;;;;;
int SumVolume(Individual *Pop,int ChromSize)
{
int i,sumvolume=0;
for(i=0;ie+=object[i].Volume;
return SumVolume;
}
void Initilize(int ChromSize,int PossibleNum)
{
//;;;;;;;;;初始化一个种群;;;;;;;;;;
srand((unsigned)time(NULL));
int i,j,location;
for(i=0;ii=0;i
//;;;;;;;;;;排在前面的优于排在后面的;;;;;;;;;
Individual temp;
int i,j;
for(i=0;iIndividual 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;irom;i ChromSize)
{
//;;;;;;;;杂交,接受的参数是两条染色体和染色体中基因的数目;;;;;;;
//;;;;;;;;返回一条染色体,及该染色体的适应度;;;;;;;;;;;;;;;;;;;;;
int i;
Individual Chrom_Return;
Chrom_Return.chrom=new int[ChromSize];
//;;;;;随机数为基数,当前基因来自第二条染色体,偶数则来自第一条染色体;;;;;;
for(i=0;ichrom[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;iid 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 MaxFitnessIndividual pop[])
{
int i,maxfitness=pop[0].fitness;
for(i=1;imaxfitness)
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<<"物品信息:"< "<
Malloc(ChromSize);
//;;;;;;;;;;;;;;;;;;初始种群的随机产生;;;;;;;;;;;;;;;;;;
Initilize(ChromSize,PossibleNum);
//;;;;;;;如果输入的背包最大容积小于物品的最小体积,则不能装入任何物品;;;;;;
cout<<"MinVolume:"<llet is too litter to put in any object!"<Volume_All_Object(ChromSize))
{
cout<<"the volume of wallet is big enough to put in every object!"<oldpop[i],ChromSize,MaxVolume_Wallet);
oldpop[i].fitness=Fitness(oldpop[i].chrom,ChromSize);
}
for(i=0;is2,ChromSize,MaxVolume_Wallet);
newpop[i]=Cross(Pop_Cross1.chrom,Pop_Cross2.chrom,ChromSize);
Guarantee(newpop[i],ChromSize,MaxVolume_Wallet);
}
//;;;;;;;;;;;;;;;;;;;;杂交操作结束;;;;;;;;;;;;;;;;;;;;;;
//;;;;;;;;;;;;;;;;;;;;变异操作开始;;;;;;;;;;;;;;;;;;;;;;
for(i=0;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;inewpop);
}
best=newpop[0];
Guarantee(best,ChromSize,MaxVolume_Wallet);
cout<<"the object in wallet:"<