《遗传算法的0-1背包问题(c语言)091845412.pdf》由会员分享，可在线阅读，更多相关《遗传算法的0-1背包问题(c语言)091845412.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于遗传算法的 0-1 背包问题的求解 摘要：一、前言 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于 NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适
2、应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其计算复杂度为)2(On，传统上采用动态规划来求解。设wi是经营活动 i 所需要的资源消耗，M是所能提供的资源总量，pi是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。二、问题描述 背包问题(Knapsack Problem)的一般提法是：已知n个物品的重量（weight）及其价值（或收益profit）分别为0iw和0ip，背包的容量（contain）假设设为0ic，如何选择哪些物品装入背包可以使得在背包
3、的容量约束限制之内所装物品的价值最大 该问题的模型可以表示为下述0/1整数规划模型：目标函数：niiinxcxxxf121),(max),2,1(1,0t.s1nixpxwiniiii （*）式中ix为 0-1 决策变量，1ix时表示将物品i装入背包中，0ix时则表示不将其装入背包中。三、求解背包问题的一般方法 解决背包问题一般是采取动态规划、递归回溯法和贪心方法。动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。它的主要缺点是用数值方法求解时会随着状态变量的个数呈指数级的增长，往往
4、对于求解背包问题的实际问题是不现实的。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解；但是由于此问题解的总组合数有n2个，因此，随着物件数 n 的增大，其解的空间将以n2级增长，当 n 大到一定程度上，用此算法解决背包问题将是不现实的。使用贪心方法求解时计算的复杂度降低了很多，但是往往难以得到最优解，有时所得解与最优解相差甚远。因此，我们可以探索使用遗传算法解决物件数较大的背包问题。四、遗传算法简介 遗传算法(Genetic Algorithms，GA)是在1975 年首次由美国密西根大学的D。J。Holland 教授和他的同事们借鉴生物界
5、达尔文的自然选择法则和孟德尔的遗传进化机制基础之上提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应度值进行它的寻优过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的尽可能多的点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Ho
6、lland提出的模式定理(Schema Therem)和隐式并行性得以解释。在遗传算法中，定义长度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论称为遗传算法的基本定理。遗传算法是通过定义长度短、确定位数少、适应度值高的模式的反复抽样、组合来寻找最佳点，称这些使遗传算法有效工作的模式为积木块，是遗传算法构造答案的基本材料。但归根到底，要使遗传算法有效工作必须按照遗传算法的模式定理(或积木块假设)根据具体问题设计合理的编码方案。在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群的大小、染色体长、交叉率、变异率、最大进化代数等，这些参数对GA 的性能都有很重
7、要的影响。在试验中参数一般选取如下：种群大小N=20100，交叉概率cp=，变异概率mp=，最大进化代数maxgen=100500。遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图 1 所示。图1、遗传算法的基本流程 遗传算法的基本流程描述如下：（1）编码：将解空间的解数据进行二进制编码，表达为遗传空间的基因型串（即染色体）结构数据，如将数据9编码为“1001”；（2）初始化种群：定义整数 pop_size 作为染色体的个数，并且随机产生pop_size个染色体作为初始种群；（3）评估种群中个体适应度：评价函数对种群中的每个染色体（chromosome）求得其个体适应度)
8、(fitnessfi；（4）选择：选择把当前群体中适应度较高的个体按某种规则或者模型遗传到下一代种群中，这里所用的规则是：染色体在种群中被选择的可能性与其个体的适应度的大小成正比；（5）交叉：定义参数cp作为交叉操作的概率，由（4）选择得到的两个个体初始化种群 评估种群中个体适应度 选 择 编 码 交 叉 变 异 演 化 以概率cp交换各自的部分染色体，得到新的两个个体；（6）变异：定义参数mp作为变异操作的概率，由（5）得到每个个体中的每个基因值都以概率mp进行变异；（7）演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经过给定的循环次数（maxgen）的种群演化，遗传算法终止。
9、五、背包问题的遗传算法求解描述 基于背包问题的模型（*），我们设计了针对于背包问题的染色体编码方法：将待求解的各量X表示成长为n的二进制字符串 j x，j=1，2，n。0 j x表示物体 j 不放入背包内，1 j x表示物体 j 放入背包内。例如：0000111代表一个解，它表示将第 1、2、3、6、7n-2,n-1,n 号物体放入背包中，其它的物体则不放入。根据遗传算法的基本流程，我们确定了求解背包问题的遗传算法：步骤 1、初始化过程 1.1 确定种群规模 popsize、杂交概率cp、变异概率mp、染色体长度 lchrom 及最大进化代数 maxgen；1.2 读入背包问题的相关信息，如每
10、个物体的重量 weightj、每个物体的收益 profitj和背包的容量 contain，其中1)lchrom(,1,0j；1.3 取1)lchrom(,1,0j)1,0(u j x，其中)1,0(u表示 0-1 整数的均匀分布函数，即随机地生成数 0 或 1，生成的 j x串即可看为一个染色体个体。若不满足模型（*）的约束条件，则拒绝接受，由重新生成一个新的染色体个体 chrom；如果产生的染色体可行，则接受它作为种群的一名成员，经过有限次的抽样后，得到popsize个可行的染色体chrom，形成新的种群。置种群的代数gen=0；步骤 2、计算种群中个体适应度以及统计种群适应度情况 按照下列
11、公式计算种群中个体适应度：)1(1lchrom0j j chrom*j weightweight；)2(containifweight)containweight(*alpha j chrom*j profitcontainifweight j chrom*j profitfitness1lchrom0j1lchrom0j 公式（2）的下半部分即为适应度的惩罚函数，其中参数1.0alpha。按公式（3）计算种群的总体适应度，)3(i fitnesssumfitness1popsize0i 并且按照排序的方法统计出种群中的最大、最小适应度的染色体个体，分别标记为 maxpop、minpop；步骤
12、 3、选择操作 3.1 生成一个随机数 rand_Number，要求1_0Nuberrand；3.2 按照赌轮法选择个体，赌轮法的算法描述如下：int selection()i=0;cpcppp 1lchrom,0m pmppp 获取文件指返回 是 否 打开文件 读出物体重量信息 读出物体收益信息 读出背包容量信息 适应度和总重量置0 累加计算个体适应度总重量背包使用惩罚函数对个体是 返回个体适应度 输出种群的代数 gen 输出最大适应度个体的输出最大个体适应度最大最小总适应度都计数器 i=1 置最大适应度的编总适应度=总适应度+ilchrom-1 是 I 的适应度置最小适应度的编I 的适应度
13、i=i+1 返回 生成0，1之间的若返回实验成功 1 返回实验不成功 0 是 否 个体计数器 i=0 随机生成个体 i 染色体 计算生成个体的适应度 若背包不超重 接受个体，i=i+1 ipop_size 是 是 否 否 返回 个体编号 i=0，部分适应产生随机数 rand_Number 计算赌轮所在位置partsumwheel-poPartsum=partsum+个体计数器 i=i+1 返回被选择的个体 i-1 否 是 进行变异 返回变异或者原值 概率选择试验否 是 随机生成交叉位置两个父代个体按照交叉位置进行交叉，生概率选择试验保留两个父体成为新是 置个体编号 i=0 ipop_size
14、调用 selection 生成调用 crossover，交对每个个体的基因调置个体编号 i=i+2 生成新的种群完毕 是 是 调用 调用 initpop()置演化代数 gen=0 调用 statistics GenMaxgen 调用调用 statistics 新种群的最大适复制旧种群的最大适应度个体到新种群中最小置演化代数 gen=gen+1 调用 report()，itness;minfitness=pop0.fitness;minpop=0;maxfitness=pop0.fitness;maxpop=0;for(i=1;ipopsize;i+)itness;tmp_fit=popi.fi
15、tness;itness;maxpop=i;itness;minpop=i;n,gen);hromj);,(int)popmaxpop.fitness);printf(nThe knapsack weight is%d.nn,(int)popmaxpop.weight);/*生成初始种群*/void initpop()int i,j,ispop;double tmpWeight;hromj=rand()%2;arent1=0;arent2=0;oldpopi.cross=0;hrom);if(tmpWeight=contain)oldpopi.fitness=cal_fit(oldpopi.c
16、hrom);oldpopi.weight=tmpWeight;oldpopi.parent1=0;oldpopi.parent2=0;oldpopi.cross=0;ispop=true;itness;parent=parent+1;while(partsumwheel_pos&parentpopsize);return parent-1;/*交叉操作 */int crossover(unsigned int*parent1,unsigned int*parent2,int i)int j,cross_pos;if(execise(pc).(lchrom-2)cross_pos=rand()%
17、(lchrom-1);else cross_pos=lchrom-1;for(j=0;j=cross_pos;j+)hromj=parent1j;for(j=cross_pos+1;j=(lchrom-1);j+)hromj=parent2j;ross=cross_pos;return 1;/*变异操作*/int mutation(unsigned int alleles)if(execise(pm)if(alleles)alleles=0;else alleles=1;hrom,oldpopmate2.chrom,i);hromj=mutation(newpopi.chromj);hrom);if(tmpWeightoldmax)report(newpop,gen);getch();