遗传算法的01背包问题(c语言)

基于遗传算法得0・1背包问题得求解

摘要：

一、前言

组合优化问题得求解方法研究已经成为了当前众多科学关注得焦点，这不仅

在于其内在得复杂性有着重要得理论价值，同时也在于它们能在现实生活中广泛

得应用。比如资源分配、投资决策、装载设计、公交车调度等一系列得问题都可

以归结到组合优化问题中来。但就是，往往由于问题得计算量远远超出了计算机

在有效时间内得计算能力，使问题得求解变为异常得困难。尤其对于NP完全问题，

如何求解其最优解或就是近似最优解便成为科学潺焦点之一。

遗传算法已经成为组合优化问题得近似最优解得一把钥匙。它就是一种模拟

生物进化过程得计算模型，作为一种新得全局优化搜索算法，它以其简单、鲁棒性

强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算将地

位。

背包问题就是一个典型得组合优化问题，在计算理论中属于NP-完全问题，

其计算复杂度为°（2”），传统上采用动态规划来求解。设w[i]就是经营活动i所

需要得资源消耗,M就是所能提供得资源总量，p[i]就是人们经营活动i得到得利

润或收益，则背包问题就就是在资源有限得条件下，追求总得最大收益得资源有

效分配问题。

二、问题描述

背包问题（KnapsackProbIem）得一般提法就是：已知n个物品得重量（weight）

及其价值（或收益profit）分别为吗〉0与Pj>0,背包得容量（contain）假没设

为。>0,如何选择哪些物品装入背包可以使得在背包得容量约束限制之内所

装物品得价值最大？

该问题得模型可以表示为下述0/1整数规划模型：

目标函数：gx/（X,,x2…，瑞）=Zq巧

/=1

Evv/%/-Pi

(*)

X{e{01}«=1,2,…〃)

式中凡为07决策变量，£=1时表示将物品i装入背包中，a=0时则表示不将其

装入背包中。

三、求解背包问题得一般方法

解决背包问题一般就是采取动态规划、递归回溯法与贪心方法。动态规划可

以把困难得多阶段决策变换为一系列相互联系比较容易得单阶段问题。对于背包

问题可以对子过程用枚举法求解，而且约束条件越多，决策得搜索范围越小，求解

也越容易。它得主要缺点就是用数值方法求解时会随着状态变量得个数呈指数级

得增长，往往对于求解背包问题得实际问题就是不现实得。

使用递归回溯法解决背包问题得优点在于它算法思想简单，而且它能完全

遍历搜索空间，肯定能找到问题得最优解；但就是由于此问题解得总组合数有2n

个，因此，随着物件数n得增大，其解得空间将以2"级增长，当n大到一定程度

上，用此算法解决背包问题将就是不现实得。

使用贪心方法求解时计算得复杂度降低了很多，但就是往往难以得到最优解,

有时所得解与最优解相差甚远。因此，我们可以探索使用遗传算法解决物件数较

大得背包问题。

四、遗传算法简介

遗传算法(GeneticAlgorithms,GA)就是在1975年首次由美国密西根大学

得D°JoHolland教授与她得同事们借鉴生物界达尔文得自然选择法则与孟德尔

得遗传进化机制基础之上提出得。经过近30年得研究、应用，遗传算法已被广泛

地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工

业优化控制等领域。

遗传算法就是将问题得每一个可能性解瞧作就是群体中得一个个体(染色

体)，并将每一个染色体编码成串得形式，再根据预定得目标函数对每个个体进行

评价，给出一个适应值。算法将根据适应度值进行它得寻优过程，遗传算法得寻优

过程就是通过选择、杂交与变异三个遗传算子来具体实现得。它得搜索能力由选

择算子与杂交算子决定，变异算子则保证了算法能够搜索到问题空间得尽可能多

得点，从而使其具有搜索全局最优得能力。遗传算法得高效性与强壮性可由

Holland提出得模式定3里(SchemaTherem)与隐式并行性得以解释。在遗传算法

中，定义长度较短、低阶且适应值超过平均适应值得模式在群体中数目得期望值

按指数递增，这个结论称为遗传算法得基本定理。遗传算法就是通过定义长度短、

确定位数少、适应度值高得模式得反复抽样、组合来寻找最佳点，称这些使遗传

算法有效工作得模式为积木块，就是遗传算法构造答案得基本材料。但归根到底,

要使遗传算法有效工作必须按照遗传算法得模式定理(或积木块假设)根据具体

问题设计合理得编码方案。

在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群得大小、

染色体长、交叉率、变异率、最大进化代数等，这些参数对GA得性能都有很重要

得影响。在试脸中参数一般选取如下：种群大小N-20~100，交叉概率p,-0、4

~0、9，变异概率3、=0、00厂0、1,最大进化代数maxgen=100~500。

遗传算法就是具有“生成+检测”得迭代过程得搜索算法。它得基本处理流

程如图1所示。

图1、遗传算法得基本流程

遗传算法得基本流程描述如下：

(1)编码：将1解空间得解数据进行二进制编码，表达为遗传空间得基因型串(即

染色体)结构数据，如将数据9编码为“1001”；

(2)初始化种群：定义整数pop_size作为染色体得个数，并且随机产生

pop_size个染色体作为初始种群；

(3)评估种群中个体适应度：评价函数对种群中得每个染色体(chromosome)求

得其个体适应度〃fitness);

(4)选择：选择把当前群体中适应度较高得个体按某种规则或者模型遗传到下

一代种群中，这里所用得规则就是：染色体在种群中被选择得可能性与其

个体得适应度得大小成正比；

(5)交叉：定义参数上作为交叉操作得概率，由⑷选择得到得两个个体以概率

Pc交换各自得部分染色体,得到新得两个个体；

(6)变异：定义参数pm作为变异操作得概率，由⑸得到每个个体中得每个基因

值都以概率Pm进行变异；

(7)演化：经过选择、交叉与变异操作，得到一个新得种群，对上述步骤经过给定

得循环次数(maxgen)得种群演化，遗传算法终止。

五、背包问题得遗传算法求解描述

基于背包问题得模型(*),我们设计了针对于背包问题得染色体编码方法：

将待求解得各量X表示成长为n得二进制字符串x[j],j=1,2,…，nox[j]=0表

示物体j不放入背包内，x[j]=l表示物体j放入背包内。例如：111001100…

000111代表一个解，它表示将第1、2、3、6、7-n-2,n-1,n号物体放入背包

中，其它得物体则不放入。

根据遗传算法得基本流程，我们确定了求解背包问题得遗传算法：

步骤1、初始化过程

确定种群规模popsize、杂交概率上、变异概率Pm、染色体长度Ichrom

及最大进化代数maxgen;

读入背包问题得相关信息，如每个物体得重量weight^]、每个物体得收

益profit[j]与背包得容量contain,其中j=0,l,---(lchrom-1)；

1.3取x[j]=u(0,l))=0,1,,一(1①201-1),其中u(0,l)表示07整数得均匀分

布函数，即随机地生成数0或1,生成得x[j]串即可瞧为一个染色体个体。

若不满足模型(*)得约束条件，则拒绝接受，由1、2重新生成一个新得染

色体个体chrom;如果产生得染色体可行，则接受它作为种群得一名成员，经过

有限次得1、2抽样后，得到popsize个可行得染色体chrom,形成新得种群•<,

1、4置种群得代数gen=0;

步骤2、计算种群中个体适应度以及统计种群适应度情况

2、1按照下列公式计算种群中个体适应度：

Ichroin-1

weight=Xweightfj]*chromfjl(I);

j=0

lchrom-1

Zprofit[j]*chroiT(j]ifweight<contain

fitness-扁⑵

profitfj]*chroir(j]-alpha*(weight-contain)ifweight>contain

、j=°

公式⑵得下半部分即为适应度得惩罚函数，其中参数alpha>l.()o

2、2按公式⑶计算种群得总体适应度，

popsize-1

sumfitness=^fitness[il(3)

i=0

并且按照排序得方法统计出种群中得最大、最，J、适应度得染色体个体，分别标

记为maxpop、minpop;

步骤3、选择操作

3.1生成一个随机数rand_Number,要求0vrand_Nuber<1;

3.2按照赌轮法选择个体，赌轮法得算法描述如下:

intselection()

i=0;//个体得编号

sum=0;//部分个体适应度得累加与

//根据随机数与群体得总适应度确定赌轮得位置

wheeI-pos=rand_Number*sufitness;

whilesum<wheel-pos&&i<=popsize

{i=i+1；

sum=sum+fitness［i］;//fitness为第i个个体得适应度

)

returni_1;//选择了个体iT

)

3、3重复两次操作3、1、3、2,生成两个个体作为交叉操作得父代；

步骤四、交叉操作

4、1根据事先定义好得交叉概率Pc，为了确定就是否进行交叉操作，则生成

［0,1］得随机数pp,若pp<Pc,则进行4、2交叉操作，否则将两个父代保留为下

一代得两个个体；

4、2随机生成［0,lchrom-l］得整数作为交叉点，对两个父代个体交叉生成新

得两个个体；

4、3重复pop_size/2次4、1、4、2便可生成pop_size个个体组成新得种

群；

步骤五、变异操作

5、1根据事先定义好得变异概,率Pm，为了确定新种群上得每个个体上得每个

基因就是否进行变异操作，则生成［0,1］得随机数pp,若pp<Pm，则进行5、2

变异操作，否则基因不变异；

5、2基因变异操作为原基因若为1,则新基因则变异为0,若原基因为0,则新

基因变异为0；

步骤6、演化

6、1按步骤2得方法计算新种群得个体适应度与总体适应度情况，尤其就是

找出新种群中最大适应度得个体与最小适应度得个体;

6、2若旧种群得最大个体适应度〉新种群得最大个体适应度，把旧种群得最

大适应度得个体代替新种群中得最小适应度得个体，否则进行6、3；

6、3种群得代数gen=genm+1,若gen)Maxgen,则结束种群得演化，否则转到

步骤2。

六、遗传算法求解得实现

1、遗传算法得主要参数

#definepopsize80//种群得规模

#definepc0>7//杂交概,率

#definepm0、1〃变异概率

#defineIchrom50〃染色体长度

#definemaxgen5000〃最大进化代数

doubIeaIpha;〃计算适应度时使用得惩罚函数系数

2、数据结构

(1)背包信息:

〃背包问题中物体重量、收益、背包容量

intweight[Ichrom],profit[lchrom],contain;

⑵种群个体结构体

structpopuIation

（

unsignedintchrom[Ichrom];〃染色体

doubIefitness;//适应度

unsignedintparentl,parent2,cross;//又义亲、交叉点、

）；

⑶父代种群与新生代种群

〃父代种群、新生代种群

structpopulationoIdpop[popsize],newpop[popsize];//pop_size为种群

大小

⑷适应度信息

〃种群得总适应度、最小、最大适应度

doubIesumfitness,ninfitness,maxfitness;

//一个种群中最大与最小适应度得个体编号

intminpop,maxpop;

3、主要函数说明

(1)、intread_infort)

功能：从文件knapsack、txt中读出背包信息(物体重量、收益、背包容量)；

参数：无；

返回值：返回读取文件馆息就是否正确；

流程图：见图2。

图2、read_infor()流程图

(2)doubIecaI_fit(unsignedint*chr)

功能：种群中个体适应度计笄；

参数：unsignedint*chr就是染色体个体得指针，根据指针所指向得染色体计算

个体得适应度；

返回值：染色体个体适应度得大小;

流程图：见图30

适应度与总重量置0

累加计算个体适应度

与背包得总重量

使用惩罚函数对个体

适应度进行处理

返回个体适应度

图3、函数cal_fit得流程图

⑶、voidstatistics(structpopuIation*pop)

功能：群体适应度得最大最小值以及其她信息；

参数：structpopulation*pop就是种群■指针，根据指针所指向得种群信息统计

群体适应度得信息；

返回值：无；

流程图：见图40

⑷、voidreport(structpopulation*pop,intgen)

功能：报告种群得适应度信息，尤其就是最大个体适应度、最大适应度个体得染色

体信息；

参数：structpopulation*pop就是种群指针，根据指针所指向得种群报告群体

适应度得信息，gen就是表示此种群所在得演化代数

返回值：无;

流程图：见图

50

图4、函数statisties得流程图

输出种群得代数gen

图5、函数report得流程图

(5)、voidinitpop()

功能：生成初始种群；

参数：无;

返回值：无;

流程图：见图60

图6、函数initpop流程图

(6)intexecise(doubIeprobabiIity)

功能：概率选择试脸，以概率probabiIity做随机试验，判断就是否进行交叉或变

异操作；

参数：doubleprobabiIity为交叉概率或变异概＞

返回值:试验就是否成功，0代表不试脸成功，将不做交叉或者变异操作，1代表试

验成功，即进行交叉或者变异操作；

流程图：见图70

图7、函数execise得流程图

⑺、intselection。ntpop)

功能：在父代种群中选择个体，规则为适应度越大骞个体被选择得概率越大;

参数：intpop为父代种群；

返回值：父体中被选择潺个体i;

流程图：见图80

图8、函数selection得流程图

(8)、intcrossover(unsignedint*parent1,unsignedint*parent2.int

i)

功能：两个父代个体在染色体得第i个位置进行交叉，生成两个新个体；

参数：unsignedint*parent1,unsignedint*parent2分别为两个父代染色体

指针，指针指向父代个体得染色体，i为新种群得个体编号；

返回值：交叉就是否成功;

流程图：见图90

图9、函数crossover得流程图

(9)intmutation(unsignedintaIIeIes)

功能：根据变异概率进行变异操作；

参数：unsignedintaIIeIes就是染色体上得基因型，在这里就就是。或1得取

值；

返回值：变异后得基因型；

流程图：见图10。

图10、函数mutation得流程图

(10)、voidgeneration()

功能：综合选择、交叉、变异等操作，生成新得种群;

参数：无；

返回值：无；

流程图：见图11。

图11、函敷generation得流程图

(11)、voidmain()

功能：遗传算法得主函数；

参数：无;

返回值：无；

流程图：见图11。

图12、主函数main得流程图

七、成果说明

1、程序开发环境

开发环境：VisualC++6、0（把Fortran程序改为VC）

操作系统:Windows2003ProfessionaI

2、程序性能对比

运行时间与加速比（如表1所示）

进程数P（个）194

运行时间1（秒）129s78s38s

加速比S1、653、38

表1、运行时间与加速比

3、程序运行结果:

实例数据：

假设物体得重量Weight、物体得收益Profit与背包得容量Contain分别为:

Weight={80,82,85,70,72,70,66,50,55,25,

50,55,40,48,50,32,22,60,30,32,

40,38,35,32,25,28,30,22,50,30,

45,30,60,50,20,65,20,25,30,10,

20,25,15,10,10,10,4,4,2,1)

Profit={220,208,198,192,180,180,165,162,160,158,

155,130,125,122,120,118,115,110,105,101,

100,100,98,96,95,90,88,82,80,77,

75,73,72,70,69,66,65,63,60,58,

56,50,30,20,15,10,8,5,3,1)

Contain=1000,

如何选择哪些物品装入该背包可使得在背包得容量约束限制之内所装物品得

总价值最大？

传统得算法（动态规划、递归回溯法与贪心算法所得结果:

总价苞为3077,总重量为999。

2001年张铃，张钱教授在计算机学报上发表得《佳点集遗传算法》所得结杲

总价值为3103,总重量为1000。

我们算法所得结果：总价值为3103,总重量为1000。

我们所求得最优解得个体分配情况为：

110101011110110110110111111101000010100110000

01000

算法最大迭代次数总价值为总重量为

传统得算法4003077999

佳点集算法7031031000

遗传算法7531031000

八、收获、体会与课题展望

在本课题中，我们圻究了如何用遗传算法求解组合优化问题中得背包问题。

我们可以瞧出在求解背包问题上显示了超出想象、良好得搜索能力，它具有收敛

快、搜索速度快得特点，在试脸中取得了比动态规划、递归回溯法与贪心法等更

好得求解效果。

然而在一般情况下，使用基本遗传算法解决背包问题时，得到问题得近似解

也不能满足逼近最优解得要求。如何改进基本遗传算法使它所求得得解逼近最优

解，成为我们当前亟待解决得问题，也就是我们将来得课题中所要研究得重要问

题。

//knapsack、cpp:Definestheentrypointfortheconsoleapplication、

//

#include"stdafxsh"

#include<AfxWin、h>

#include<stdIib、h>

#include<math,h>

#include<time>h>

#include<conio、h>

#include<stdio、h>

//重要常量参数

#definepopsize200〃种群得规模

#definepc0、618〃杂交^率

#definepm0、03//变异概率

#defineIchrom50〃染色体长度

#definemaxgen1000//最大进化代数

structpopulation

unsignedintchrom[Ichrom];〃染色体

doubleweight；〃背包重量

doubIefitness；//适应度

unsignedintparentl,parent2,cross；//又又亲、交叉，点、

）；

//新生代种群、父代种群

structpopulationoIdpop[popsize],newpop[popsize];

〃背包问题中物体重量、收益、背包容量

intweight[Ichrom],profit[Ichrom],contain;

〃种群彳导总适应度.最小，最大、平均适应度

doubIesumfitness,minfitness,maxfitness,avgfitness;

〃计算适应度时使用得惩罚函数系数

doublealpha;

〃一个种群中最大与最小适应度得个体

intminpop,maxpop;

/*读入背包信息，并且计算惩罚函数系数*/

voidread_infor()

(

FILE*fP；

intj;

〃获取背包问题信息文件

if((fp二fopen("knapsack、txt","r"))=NULL)

(

〃读取文件失败

AfxMessageBox('ThenotfoundMB_0K,NULL);

return;

)

〃读入物体收益信息

for(j=0;j<lchrom;j++)

(

fscanf(fp,"%d".&profit[j]);

1

//读入物体重量信息

for(j=0;j<lchrom;j++)

(

fscanf(fp,"%d".&weight[j]);

)

//读入背包容量

fscanf(fp,飞d”,&contain)；

fcIose(fp);

1

〃根据计算得个体重量，罚断此个体就是否该留在群体中

doublecaI_weight(unsignedint*chr)

intj;

doublepop_weight;〃背包重量

pop_weight=0;

for(j=0；j<lchrom；j++)

(

pop_weight=pop_weight+(*chr)*weight[j];

chr++;

)

returnpopv/eight;

}

/*种群中个体适应度计算*/

doublecal_fit(unsignedint*chr)

(

intj;

doublepop_profit;//适应度

pop_profit=0;

//pop_weight=0;

for(j=0;j<lchrom;j++)

(

pop_profit=pop_profit+(*chr)*profit[j];

//pop_weight=pop_weight+(*chr)*weight[j];

chr++;

)

returnpop_profit;

1

/*群体适应度得最大最小值以及其她信息*/

voidstatistics(structpopulation*pop)

{

inti;

doubletmp_fit;

sumfitness=pop[0]、fitness;

minfitness=pop[0]>fitness；

minpop=0;

maxfitness=pop[0]、fitness;

maxpop=0;

for(i=1;i<popsize;i++)

{

〃计算种群得总适应度

sumfitness=sumfitness+pop[i]、fitness;

tmpfit=pop[i]%fitness;

〃选择种群中最大适应度得个体

if((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))

maxfitness二pop[i]、fitness;

maxpop=i;

)

〃选择种群中最小适应度得个体

if(tmp_fit<minfitness)

(

minfitness=pop[i]fitness；

minpop=i;

)

〃计算平均适应度

avgfitness=sumfitness/(fIoat)popsize;

1

//printf("\nthemaxpop=%d;",maxpop);

//printf("\ntheminpop=%d;",minpop)；

//printf("\nthesumfitness=%f\n",sumfitness);

}

〃报告种群信息

voidreport(structpopulation*pop,intgen)

intj;

intpop_weight=0;

printf("thegenerationis%d、\n",gen)；//—出种群得代数

//输出种群中最大适应度个体得染色体信息

printf("Thepopulation'schromis:\n");

for(j=0;j<Ichrom;j++)

(

if(j%5=0)

{printfC");)

printfpop[maxpop]、chrom[j]);

)

〃输出群体中最大适应度

printf("\nThepopulation'smaxfitnessis$d、",(int)pop[maxpop]、

fitness);

printf("\nTheknapsackweightis$d、\n\n",(int)pop[maxpop]weight);

I

/*生成初始种群*/

voidinitpop()

(

inti,j,ispop；

doubletmpWeight;

//变量用于判断就是否为满足条件得个体

ispop=faIse；

//生成popsize个种群个体

for(i=0;i<popsize;i++)

while(!ispop)

for(j=0;j<lchrom;j++)

oIdpop[i]^chrom[j]=rand()%2;//随机生成个体得染色体

oldpop[i]、parent1=0;//双亲

oldpop[i]、parent2=0;

oldpop[i]、cross=0;//交叉点

)

〃选择支量小于青包容量得个体，即满足条件

tmpWeight=cal_weight(oIdpop[i]chrom)；

if(tmpWeight<=contain)

oldpop[i]、fitness=caI_fit(oIdpop[i]、chrom);

oldpop[i]、weight=tmpWeight;

oldpop[i]、parent1=0;

oldpop[i]、parent2=0;

oldpop[i]、cross=0;

ispop=true,

}

)

〃此个体可以加入到种群中

ispop=faIse;

)

)

/*遗传操作*/

〃概率选择试脸

intexecise(doubIeprobabiIity)

(

doubIepp；

//如果生成随机数大于相应得概率则返回真，否则试脸不成功

pp=(double)(rand()X20001/20000.0)；

if(pp<=probabiIity)return1；

return0;

)

//选择进行交叉操作得个体

intselection(intpop)

(

doublewheel_pos,rand_Number,partsum；

intparent;

//赌轮法选择

rand_Number=(rand()%2001)/2000、0;

wheeI_pos=rand_Numbe<*sumfitness;//赌轮大小

partsum=0;

parent=0;

do{

partsum=partsum+oIdpop[parent]、fitness;

parent=parent+1;

}while(partsum<wheeI_pos&&parent<popsize);

returnparent-1;

}

/*交叉操作*/

intcrossover(unsignedint*parent1,unsignedint*parent2,inti)

(

intj,cross_pos;

if(execise(pc))

(

〃生成交叉位置0,1,、、、(lchrom-2)

cross_pos=rand()%(lchrom-1);

)

eIsecross_pos=lch^om-1;

for(j=0；j<=cross_pos；j++)

(〃保留复制；

〃包括在概率选择不成功时，父体完全保留

newpopfi]>chrom[j]=parent1[j];

)

for(j=cross_pos+1;j<=(Ichrom-1);j++)

(

〃从交叉点开始交叉

newpop[i]chrom[j]=parent2[j];

)

〃记求交又位置

newpop[i]>cross=cross_pos;

return1;

)

/*变异操作*/

intmutation(unsignedintaIIeIes)

(

if(execise(pm))

(

if(aIIeles)

aIIeles=0;

eIsealleles=1;

)

〃返回变异值，或者返回原值

returnalleles;

)

/*群体