文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 2006-0_1背包问题的遗传算法求解
侵权投诉

2006-0_1背包问题的遗传算法求解

0-1背包问题是计算机算法研究中N P 完备类的一个困难问题, 对这个问题国内外很多学者己经研究出了不少经典的方法, 但是这些传统的优化法存在一些缺点。本文介绍了近年来兴起的一种演化算法—遗传算法解决背包问题的基本思路, 井通过实例计算证明了此方法的可行性和有效性。

科技信息

高校理科研究

2006年第3期

0-1背包问题的遗传算法求解

鄂州大学图书馆 曾国清

[摘 要]0-1背包问题是计算机算法研究中NP完备类的一个困难问题,对这个问题国内外很多学者己经研究出了

不少经典的方法,但是这些传统的优化法存在一些缺点。本文介绍了近年来兴起的一种演化算法—遗传算法解决背包问题的基本思路,井通过实例计算证明了此方法的可行性和有效性。[关键词]背包问题 遗传算法

  背包问题是著名的NP-hard问题,对这个问题的求解前人己经研究出了不少的经典的方法,对该问题确实能得到很好的结果。但是这些传统的优化方法存在一些缺点:例如解析法是通过求解使目标函数梯度为零的一组非线性方程来进行搜索的。一般而言,若目标函数连续可微,解的空间方程比较简单,解析法还是可以用的。但是,若方程的变量有几十个或几百个就无能为力了;另一种典型的搜索方法是穷举法,该方法简单易行,即在一个连续的有限空间或离散无限搜索空间中,计算空间中每个点的目标函数值,且每次计算一个。显然,这种方法效率太低。许多实际问题所对应的搜索空间很大,不允许一点点地慢慢求解。领域,其全局最优性、可并行性、泛地应用。,的演化过程,,群和随机搜索机制。

本文将遗传算法应用于背包问题,并通过算例证明了该算法在解决该问题是比较有效的。

1.问题的描述

背包问题(knapsackProblem)的一般提法是:有一个“背包”,它能提供m种资源(如空间容积、载量等),各种资源的最大提供数量是bi,i=1,2,+,m,现要将n种“物资”放入“背包”中

2006-0_1背包问题的遗传算法求解

,单位第j项物资占用第i种资源的数量是Αij,j=1,2,+,n,而装入第j项物资的受益为cj,j=1,2,+,n。问:“背包”中应装入哪些“物资”,才能使受益最大?该问题的模型可表示为以下整数规划模型:

理、工业优化控制等领域。

遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体),并将每一个染色体编码成串的形式,再根据预定的目标函数对每个个体进行评价,给出一个适应值。算法将根据适应度值进行它的寻优过程,遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,。遗传算法的Ho。,低阶且适应值超过平均,这个结论称。

遗传算法是通过定义长度短、确定位数少、适应度值高的模式的反复抽样、组合来寻找最佳点,称这些使遗传算法有效工作的模式为积木块,是遗传算法构造答案的基木材料。但归根到底,要使遗传算法有效工作必须按照遗传算法的模式定理根据具体问题设计合理的编码方案。

3.遗传算法求解背包问题3.1编码

基因编码将n个xj的值顺序排列,就可构成背包问题的遗传编码。即我们使用的是等长度的2进制编码方法,编码串中1表示将对应的物品放入背包中,0表示不将其放入。

例如“111001110011”就代表一个解,‘已表示将第1、3、6、7、8和11、12放入背包中,其它的物品则不放入。

上述基因编码方案虽然比较直观,但对于任意一个编码串,或者由交叉、变异所产生的任意一个个体,由于它们不一定满足约束条件,就不一定表示可行解,也就是说这种编码方案会产生很多无效染色体。对于这些不满足约束条件的基因编码串,我们可以利用贪婪算法的思想,优先装入Ci Wi较大且xi=1的物品,直到超过背包的容量限制再装小下为止。对于基因编码中指示应装入而实际上己装不下的物品,

2006-0_1背包问题的遗传算法求解

修改其基因编码串中对应的xi为0。由此可产生一些新的基因编码串,井且这些新编码串总是相对来说质量比较好的,特别是它们肯定满足问题的约束条件。

3.2选择操作

选择操作的第一步是计算适应度。在被选集中每个个体具有一个选择概率,这个选择概率取决于种群中个体的适应度及其分布。

本例中,采用轮盘赌选择方法。该方法是目前遗传算法中最基本也是最常用的选择方法。在该方法中,各个个体的选择概率和其适应度值成正比。

设群体大小为n,其中个体i的适应度值为f,则i被选择的概

式中,xj为0-1决策变量,xj=1表示将物资j放入背包中,xj=0表示不将物资j放入背包中。

2.遗传算法

遗传算法(GeneticAlgorithnzs,GA)作为一种解决复杂问

题的有效方法是在1975年首次由美国密西根大学的D.J.Hol2land教授和他的同事们借鉴生物界自然选择和进化机制基础之上提出的,它是基于生物进化中自然选择、适者生存和物种遗传思想的搜索算法。经过近30年的研究遗传算法己被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图像处

—242—

第1页

你可能喜欢

  • 背包问题
  • 量子遗传算法
  • 小生境遗传算法
  • 神经网络遗传算法
  • 遗传算法论文

热门文档

相关文档

  • 基于遗传算法求解0_1背包问题的算法探讨

    2006-0_1背包问题的遗传算... 2页 1财富值 遗传算法求解0-1背包问题 暂无...介绍贪婪算法和基本遗传算法求解背包问题介绍贪婪算法和基本遗传算法求解背包问题隐藏...

  • 基于遗传算法求解0_1背包问题

    基于遗传算法求解0_1背包问题 姓专 名:叶奇 业:电气工程与自动化 指导教师:宋潇潇 论文主要工作要点1 要点2 要点3 总结 2/20 研究目的与 意义 遗传算法的 ...

  • 遗传算法求解0-1背包问题

    遗传算法求解0-1背包问题_金融/投资_经管营销_专业资料。遗传算法求解0-1背包问题遗传算法——解决 0-1 背包问题 北京科技大学物流工程系 2013.6.11 一、 实例...

  • 遗传算法求解背包问题

    四、使用遗传算法解决“0-1 背包问题”的思路:0-1 背包的解可以编码为一串 0-1 字符串(0:不取,1:取) ;首先,随机产生 M 个 0-1 字符串,然后评价 这些...

  • 遗传算法求解背包问题

    遗传算法求解背包问题_IT/计算机_专业资料。利用遗传算法求解0/1背包问题开始 初始化 调用保证放入背包物 品体积和不超过背包 容量函数 达到算法终止条 件? 是 结...

  • 【论文】基于遗传算法的0/1背包问题求解

    该文给出了背包问题基于0/1规划的数学模型,提出了解决该问题的二重结构编码的混合遗传算法;该算法在传统遗传编码方式的基础上提出了一种改进的编码方式二重结构编码,...

  • 遗传算法求解01背包问题

    遗传算法求解 01 背包问题一、问题描述 01 背包问题属于组合优化问题的一个例子, 求解 01 背包问题的过程可以被视作在很多可行解当中 求解一个最优解。01 背包...

  • 基于贪心策略的遗传算法求解0-1背包问题

    基于贪心策略的遗传算法求解 0-1 背包问题摘要:本文针对简单遗传算法的不足之处采用经过贪心算法改进的遗传算法求解 0-1 背包问题, 使用一组 0-1 背包问题经典...

  • 遗传算法求解背包问题

    基于遗传算法求解0_1背包问... 3页 免费 多背包问题的遗传算法求解 5页 免费...如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...

  • 基于贪心算法的改进遗传算法解决背包问题

    关键词:背包问题 贪心算法 简单遗传算法 改进遗传算法 1 问题描述 2 简单遗传算法(SGA)解决 0-1 背包问题 2.1 操作过程 用遗传算法来解决...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email