用遗传算法解决0-1背包问题

《用遗传算法解决0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实现遗传算法的0-1背包问题求解及其改进姓名：学号：班级：提交日期：201?年6月27旦_实现遗传算法的0-1背包问题求解摘要：研究了遗传算法解决0-1背包问题中的几个问题:1）对于过程中不满足重量限制条件的个体的处理，通过代换上代最优解保持种群的进化性2）对于交换率和变异率的理解和处理方法，采用逐个体和逐位判断的处理方法3）对于早熟性问题，引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4）一种最优解只向更好进化方法的尝试。通过实际计其比较表明，本文改进遗传算法在背包问题求解中具有

2、很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法关键词：遗传算法；背包问题；优化1.基本实现原理：一、问题描述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当屮求解一个最优解。01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi,其价值为Vi,背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背的容量C。在选择装入背的物品

3、时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。其数学模型为：c的餅下f=l•其中1=Ir2.r3.r40-1背包问题传统的解决方法奋动态规划法、分支界限法、冋溯法等等。传统的方法不能奋效地解决0-1背包问题。遗传算法（GeneticAlgorithms）则是一种适合于在火量的可行解屮搜索最优（或次优）解的有效算法。二、遗传算法特点介绍：遗传算法（GeneticAlgorithm,GA｝是1962年Holland教授首次提出了GA算法的思想

4、是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。基本遗传算法求解步骤：Step1参数设置：在论域空间上定义一个适应度函数/（x）,给定种群规模W，交叉率Pc和变异率Pm，代数r;Step2初始种群：随机产生＜7中的W个染色体slzs2,sN，组成初始种群5=｛slzs2,…,sN｝，置代数计数器Step3计算适应度：S中每个染色体的适应度f（）;SteP4判断：若终止条件满足，则取5中适应度最大的

5、染色体作为所求结果，算法结束。Step5选择•复制：按选择概率PU,）所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做/V次，然后将复制所得的W个染色体组成群体51;Step6交叉：按交叉率所决定的参加交叉的染色体数c，从中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体52;Step7变异：按变异率Pm所决定的变异次数m，从52中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体53;Step8更新：将群体53作为新一代种群，即用S

6、3代替5,转步3;遗传算法是一种仿生算法，即模拟生命演化的算法，它从一个代表问题初始解的初始种群出发，不断重复执行选择，杂交和变异的过程，使种群进化越来越接近某一目标既最优解，如果视种群为超空间的一组点，选择、杂交和变异的过程即是在超空间中进行点集之间的某种变换，通过信息交换使种群不断变化，遗传算法通过模拟达尔文“优胜劣汰，适者生存”的原理激励好的结构，同时寻找更好的结构，作为一种随机的优化与搜索方法，遗传算法有着其鲜明的待点。一遗传算法一般是直接在解空间搜索，而不像图搜索那样一般是在问题空间搜索，最

7、后才找到解（如果搜索成功的话）。一遗传算法的搜索随机地始于搜索空间的一个点集，而不像图搜索那样固定地始于搜索空间的初始节点或终止节点，所以遗传算法是一种随机搜索算法。一遗传算法总是在寻找优解（最优解或次优解），而不像阁搜索那样并非总是耍求优解,而一般是设法尽快找到解（当然包括优解b所以遗传算法乂是一种优化搜索算法。一遗传算法的搜索过程是从空间的一个点集（种群）到另一个点集（种群）的搜索，而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索，适合大规模并行计算，而且这种种群到种

8、群的搜索有能力跳出局部最优解。一遗传算法的适应性强，除需知适应度函数外，几乎不需要其他的先验知识。一遗传算法长于全局搜索，它不受搜索空间的限制性假设的约束，不要求连续性，能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。3.程序步骤：一、使用基本遗传算法解决0-1背包问题：1：打开数据文件2:设罝程序运行主界面3:调用初始化种群模块3-1:按照一定的种群规模和染色体长度以基因为单位用随机产生的0-1对个体赋值3-2:调用计算适应度函数