遗传算法的01背包问题c语言之欧阳美创编.docx
《遗传算法的01背包问题c语言之欧阳美创编.docx》由会员分享，可在线阅读，更多相关《遗传算法的01背包问题c语言之欧阳美创编.docx（33页珍藏版）》请在冰点文库上搜索。
遗传算法的01背包问题c语言之欧阳美创编
基于遗传算法的0-1背包问题的求解
时间：
2021.01.01
创作：
欧阳美
摘要：
一、前言
组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。
但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。
尤其对于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（"Thefileisnotfound",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（"\nthesumfitness=%f\n",sumfitness）;
}
//报告种群信息
voidreport（structpopulation*pop,intgen）
{
i
升级会员 