遗传算法的01背包问题c语言.docx
《遗传算法的01背包问题c语言.docx》由会员分享，可在线阅读，更多相关《遗传算法的01背包问题c语言.docx（34页珍藏版）》请在冰点文库上搜索。
遗传算法的01背包问题c语言
基于遗传算法得0-1背包问题得求解
摘要:
一、前言
组合优化问题得求解方法研究已经成为了当前众多科学关注得焦点,这不仅在于其内在得复杂性有着重要得理论价值,同时也在于它们能在现实生活中广泛得应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列得问题都可以归结到组合优化问题中来。
但就是,往往由于问题得计算量远远超出了计算机在有效时间内得计算能力,使问题得求解变为异常得困难。
尤其对于NP完全问题,如何求解其最优解或就是近似最优解便成为科学得焦点之一。
遗传算法已经成为组合优化问题得近似最优解得一把钥匙。
它就是一种模拟生物进化过程得计算模型,作为一种新得全局优化搜索算法,它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点,奠定了作为21世纪关键智能计算得地位。
背包问题就是一个典型得组合优化问题,在计算理论中属于NP-完全问题,其计算复杂度为
传统上采用动态规划来求解。
设w[i]就是经营活动i所需要得资源消耗,M就是所能提供得资源总量,p[i]就是人们经营活动i得到得利润或收益,则背包问题就就是在资源有限得条件下,追求总得最大收益得资源有效分配问题。
二、问题描述
背包问题（KnapsackProblem）得一般提法就是:
已知n个物品得重量（weight）及其价值（或收益profit）分别为
与
背包得容量（contain）假设设为
如何选择哪些物品装入背包可以使得在背包得容量约束限制之内所装物品得价值最大？
该问题得模型可以表示为下述0/1整数规划模型:
目标函数:
（*）
式中
为0-1决策变量,
时表示将物品
装入背包中,
时则表示不将其装入背包中。
三、求解背包问题得一般方法
解决背包问题一般就是采取动态规划、递归回溯法与贪心方法。
动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易得单阶段问题。
对于背包问题可以对子过程用枚举法求解,而且约束条件越多,决策得搜索范围越小,求解也越容易。
它得主要缺点就是用数值方法求解时会随着状态变量得个数呈指数级得增长,往往对于求解背包问题得实际问题就是不现实得。
使用递归回溯法解决背包问题得优点在于它算法思想简单,而且它能完全遍历搜索空间,肯定能找到问题得最优解;但就是由于此问题解得总组合数有
个,因此,随着物件数n得增大,其解得空间将以
级增长,当n大到一定程度上,用此算法解决背包问题将就是不现实得。
使用贪心方法求解时计算得复杂度降低了很多,但就是往往难以得到最优解,有时所得解与最优解相差甚远。
因此,我们可以探索使用遗传算法解决物件数较大得背包问题。
四、遗传算法简介
遗传算法（GeneticAlgorithms,GA）就是在1975年首次由美国密西根大学得D。
J。
Holland教授与她得同事们借鉴生物界达尔文得自然选择法则与孟德尔得遗传进化机制基础之上提出得。
经过近30年得研究、应用,遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。
遗传算法就是将问题得每一个可能性解瞧作就是群体中得一个个体（染色体）,并将每一个染色体编码成串得形式,再根据预定得目标函数对每个个体进行评价,给出一个适应值。
算法将根据适应度值进行它得寻优过程,遗传算法得寻优过程就是通过选择、杂交与变异三个遗传算子来具体实现得。
它得搜索能力由选择算子与杂交算子决定,变异算子则保证了算法能够搜索到问题空间得尽可能多得点,从而使其具有搜索全局最优得能力。
遗传算法得高效性与强壮性可由Holland提出得模式定理（SchemaTherem）与隐式并行性得以解释。
在遗传算法中,定义长度较短、低阶且适应值超过平均适应值得模式在群体中数目得期望值按指数递增,这个结论称为遗传算法得基本定理。
遗传算法就是通过定义长度短、确定位数少、适应度值高得模式得反复抽样、组合来寻找最佳点,称这些使遗传算法有效工作得模式为积木块,就是遗传算法构造答案得基本材料。
但归根到底,要使遗传算法有效工作必须按照遗传算法得模式定理（或积木块假设）根据具体问题设计合理得编码方案。
在运行遗传算法程序时,需要对一些参数作事先选择,它们包括种群得大小、染色体长、交叉率、变异率、最大进化代数等,这些参数对GA得性能都有很重要得影响。
在试验中参数一般选取如下:
种群大小N=20~100,交叉概率
=0、4~0、9,变异概率
=0、001~0、1,最大进化代数maxgen=100~500。
遗传算法就是具有“生成+检测”得迭代过程得搜索算法。
它得基本处理流程如图1所示。
图1、遗传算法得基本流程
遗传算法得基本流程描述如下:
（1）编码:
将解空间得解数据进行二进制编码,表达为遗传空间得基因型串（即染色体）结构数据,如将数据9编码为“1001”;
（2）初始化种群:
定义整数pop_size作为染色体得个数,并且随机产生pop_size个染色体作为初始种群;
（3）评估种群中个体适应度:
评价函数对种群中得每个染色体（chromosome）求得其个体适应度
;
（4）选择:
选择把当前群体中适应度较高得个体按某种规则或者模型遗传到下一代种群中,这里所用得规则就是:
染色体在种群中被选择得可能性与其个体得适应度得大小成正比;
（5）交叉:
定义参数
作为交叉操作得概率,由（4）选择得到得两个个体以概率
交换各自得部分染色体,得到新得两个个体;
（6）变异:
定义参数
作为变异操作得概率,由（5）得到每个个体中得每个基因值都以概率
进行变异;
（7）演化:
经过选择、交叉与变异操作,得到一个新得种群,对上述步骤经过给定得循环次数（maxgen）得种群演化,遗传算法终止。
五、背包问题得遗传算法求解描述
基于背包问题得模型（*）,我们设计了针对于背包问题得染色体编码方法:
将待求解得各量
表示成长为
得二进制字符串
j=1,2,…,n。
表示物体j不放入背包内,
表示物体j放入背包内。
例如:
111001100…000111代表一个解,它表示将第1、2、3、6、7…n-2,n-1,n号物体放入背包中,其它得物体则不放入。
根据遗传算法得基本流程,我们确定了求解背包问题得遗传算法:
步骤1、初始化过程
1.1确定种群规模popsize、杂交概率
、变异概率
、染色体长度lchrom及最大进化代数maxgen;
1.2读入背包问题得相关信息,如每个物体得重量weight[j]、每个物体得收益profit[j]与背包得容量contain,其中
;
1.3取
其中
表示0-1整数得均匀分布函数,即随机地生成数0或1,生成得
串即可瞧为一个染色体个体。
若不满足模型（*）得约束条件,则拒绝接受,由1、2重新生成一个新得染色体个体chrom;如果产生得染色体可行,则接受它作为种群得一名成员,经过有限次得1、2抽样后,得到popsize个可行得染色体chrom,形成新得种群。
1、4置种群得代数gen=0;
步骤2、计算种群中个体适应度以及统计种群适应度情况
2、1按照下列公式计算种群中个体适应度:
;
公式
（2）得下半部分即为适应度得惩罚函数,其中参数
。
2、2按公式（3）计算种群得总体适应度,
并且按照排序得方法统计出种群中得最大、最小适应度得染色体个体,分别标记为maxpop、minpop;
步骤3、选择操作
3.1生成一个随机数rand_Number,要求
;
3.2按照赌轮法选择个体,赌轮法得算法描述如下:
intselection（）
{
i=0;//个体得编号
sum=0;//部分个体适应度得累加与
//根据随机数与群体得总适应度确定赌轮得位置
wheel-pos=rand_Number*sufitness;
whilesum{i=i+1;
sum=sum+fitness[i];//fitness为第i个个体得适应度
}
returni-1;//选择了个体i-1
}
3、3重复两次操作3、1、3、2,生成两个个体作为交叉操作得父代;
步骤四、交叉操作
4、1根据事先定义好得交叉概率
为了确定就是否进行交叉操作,则生成[0,1]得随机数pp,若
则进行4、2交叉操作,否则将两个父代保留为下一代得两个个体;
4、2随机生成
得整数作为交叉点,对两个父代个体交叉生成新得两个个体;
4、3重复pop_size/2次4、1、4、2便可生成pop_size个个体组成新得种群;
步骤五、变异操作
5、1根据事先定义好得变异概率
为了确定新种群上得每个个体上得每个基因就是否进行变异操作,则生成[0,1]得随机数pp,若
则进行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//变异概率
#definelchrom50//染色体长度
#definemaxgen5000//最大进化代数
doublealpha;//计算适应度时使用得惩罚函数系数
2、数据结构
（1）背包信息:
//背包问题中物体重量、收益、背包容量
intweight[lchrom],profit[lchrom],contain;
（2）种群个体结构体
structpopulation
{
unsignedintchrom[lchrom];//染色体
doublefitness;//适应度
unsignedintparent1,parent2,cross;//双亲、交叉点
};
（3）父代种群与新生代种群
//父代种群、新生代种群
structpopulationoldpop[popsize],newpop[popsize];//pop_size为种群大小
（4）适应度信息
//种群得总适应度、最小、最大适应度
doublesumfitness,minfitness,maxfitness;
//一个种群中最大与最小适应度得个体编号
intminpop,maxpop;
3、主要函数说明
（1）、intread_infor（）
功能:
从文件knapsack、txt中读出背包信息（物体重量、收益、背包容量）;
参数:
无;
返回值:
返回读取文件信息就是否正确;
流程图:
见图2。
图2、read_infor（）流程图
（2）doublecal_fit（unsignedint*chr）
功能:
种群中个体适应度计算;
参数:
unsignedint*chr就是染色体个体得指针,根据指针所指向得染色体计算个体得适应度;
返回值:
染色体个体适应度得大小;
流程图:
见图3。
图3、函数cal_fit得流程图
（3）、voidstatistics（structpopulation*pop）
功能:
群体适应度得最大最小值以及其她信息;
参数:
structpopulation*pop就是种群指针,根据指针所指向得种群信息统计群体适应度得信息;
返回值:
无;
流程图:
见图4。
（4）、voidreport（structpopulation*pop,intgen）
功能:
报告种群得适应度信息,尤其就是最大个体适应度、最大适应度个体得染色体信息;
参数:
structpopulation*pop就是种群指针,根据指针所指向得种群报告群体适应度得信息,gen就是表示此种群所在得演化代数
返回值:
无;
流程图:
见图5。
图4、函数statistics得流程图
图5、函数report得流程图
（5）、voidinitpop（）
功能:
生成初始种群;
参数:
无;
返回值:
无;
流程图:
见图6。
图6、函数initpop流程图
（6）、intexecise（doubleprobability）
功能:
概率选择试验,以概率probability做随机试验,判断就是否进行交叉或变异操作;
参数:
doubleprobability为交叉概率或变异概率
返回值:
试验就是否成功,0代表不试验成功,将不做交叉或者变异操作,1代表试验成功,即进行交叉或者变异操作;
流程图:
见图7。
图7、函数execise得流程图
（7）、intselection（intpop）
功能:
在父代种群中选择个体,规则为适应度越大得个体被选择得概率越大;
参数:
intpop为父代种群;
返回值:
父体中被选择得个体i;
流程图:
见图8。
图8、函数selection得流程图
（8）、intcrossover（unsignedint*parent1,unsignedint*parent2,inti）
功能:
两个父代个体在染色体得第i个位置进行交叉,生成两个新个体;
参数:
unsignedint*parent1,unsignedint*parent2分别为两个父代染色体指针,指针指向父代个体得染色体,i为新种群得个体编号;
返回值:
交叉就是否成功;
流程图:
见图9。
图9、函数crossover得流程图
（9）、intmutation（unsignedintalleles）
功能:
根据变异概率进行变异操作;
参数:
unsignedintalleles就是染色体上得基因型,在这里就就是0或1得取值;
返回值:
变异后得基因型;
流程图:
见图10。
图10、函数mutation得流程图
（10）、voidgeneration（）
功能:
综合选择、交叉、变异等操作,生成新得种群;
参数:
无;
返回值:
无;
流程图:
见图11。
图11、函数generation得流程图
（11）、voidmain（）
功能:
遗传算法得主函数;
参数:
无;
返回值:
无;
流程图:
见图11。
图12、主函数main得流程图
七、成果说明
1、程序开发环境
开发环境:
VisualC++6、0（把Fortran程序改为VC）
操作系统:
Windows2003Professional
2、程序性能对比
运行时间与加速比（如表1所示）
进程数p（个）
1
2
4
运行时间t（秒）
129s
78s
38s
加速比s
1、65
3、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
算法
最大迭代次数
总价值为
总重量为
传统得算法
400
3077
999
佳点集算法
70
3103
1000
遗传算法
75
3103
1000
八、收获、体会与课题展望
在本课题中,我们研究了如何用遗传算法求解组合优化问题中得背包问题。
我们可以瞧出在求解背包问题上显示了超出想象、良好得搜索能力,它具有收敛快、搜索速度快得特点,在试验中取得了比动态规划、递归回溯法与贪心法等更好得求解效果。
然而在一般情况下,使用基本遗传算法解决背包问题时,得到问题得近似解也不能满足逼近最优解得要求。
如何改进基本遗传算法使它所求得得解逼近最优解,成为我们当前亟待解决得问题,也就是我们将来得课题中所要研究得重要问题。
//knapsack、cpp:
Definestheentrypointfortheconsoleapplication、
//
#include"stdafx、h"
#include
#include
#include
#include
#include
#include
//重要常量参数
#definepopsize200//种群得规模
#definepc0、618//杂交概率
#definepm0、03//变异概率
#definelchrom50//染色体长度
#definemaxgen1000//最大进化代数
structpopulation
{
unsignedintchrom[lchrom];//染色体
doubleweight;//背包重量
doublefitness;//适应度
unsignedintparent1,parent2,cross;//双亲、交叉点
};
//新生代种群、父代种群
structpopulationoldpop[popsize],newpop[popsize];
//背包问题中物体重量、收益、背包容量
intweight[lchrom],profit[lchrom],contain;
//种群得总适应度、最小、最大、平均适应度
doublesumfitness,minfitness,maxfitness,avgfitness;
//计算适应度时使用得惩罚函数系数
doublealpha;
//一个种群中最大与最小适应度得个体
intminpop,maxpop;
/*读入背包信息,并且计算惩罚函数系数*/
voidread_infor（）
{
FILE*fp;
intj;
//获取背包问题信息文件
if（（fp=fopen（"knapsack、txt","r"））==NULL）
{
//读取文件失败
AfxMessageBox（"Thenotfound",MB_OK,NULL）;
return;
}
//读入物体收益信息
for（j=0;j{
fscanf（fp,"%d",&profit[j]）;
}
//读入物体重量信息
for（j=0;j{
fscanf（fp,"%d",&weight[j]）;
}
//读入背包容量
fscanf（fp,"%d",&contain）;
fclose（fp）;
}
//根据计算得个体重量,判断此个体就是否该留在群体中
doublecal_weight（unsignedint*chr）
{
intj;
doublepop_weight;//背包重量
pop_weight=0;
for（j=0;j{
pop_weight=pop_weight+（*chr）*weight[j];
chr++;
}
returnpop_weight;
}
/*种群中个体适应度计算*/
doublecal_fit（unsignedint*chr）
{
intj;
doublepop_profit;//适应度
pop_profit=0;
//pop_weight=0;
for（j=0;j{
pop_profit=pop_profit+（*chr）*profit[j];
//pop_weight=pop_weight+（*chr）*weight[j];
chr++;
}
returnpop_profit;
}
/*群体适应度得最大最小值以及其她信息*/
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{
//计算种群得总适应度
sumfitness=sumfitness+pop[i]、fitness;
tmp_fit=pop[i]、fitness;
//选择种群中最大适应度得个体
if（（tmp_fit>maxfitness）&&（（int）（tmp_fit*10）%10==0））
{
maxfitness=pop[i]、fitness;
maxpop=i;
}
//选择种群中最小适应度得个体
if（tmp_fit{
minfitness=pop[i]、fitness;
minpop=i;
}
//计算平均适应度
avgfitness=sumfitness/（float）popsize;
}
//printf（"\nthemaxpop=%d;",maxpop）;
//printf（"\ntheminpop=%d;",minpop）;
//printf
升级会员 