2022年遗传算法在求解背包问题中应用 .pdf

《2022年遗传算法在求解背包问题中应用 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法在求解背包问题中应用 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本栏目责任编辑： 唐一东人工智能及识别技术电脑知识与技术年第卷第期 （ 总第期）遗传算法在求解背包问题中应用王怀军， 丁中文（ 廊坊师范学院数信基础教学部， 河北 廊坊 ； 廊坊师范学院数信计算机系， 河北 廊坊 ）摘要 ： 该文先对演化计算的基本概念进行了简要介绍， 然后详细介绍了遗传算法的基本原理、应用及其基本结构。最后， 利用遗传算法的思想， 对传统的背包问题求解进行了详细的分析， 按照遗传算法的基本结构， 设计编码、 确定适应值函数、确定变异和杂交操作， 同时还给出了其非遗传算法（ 递归算法） 和遗传算法运行结果， 并进行了综合分析。关键词 ： 演化计算 ； 遗传算法； 背包问题中图分

2、类号：文献标识码：文章编号：（） ， （ ，； ，）： ， ， ， ，（） ， ：；演化计算和遗传算法简介大自然是我们解决各种问题时获得灵感的源泉。几百年来， 将生物界所提供的答案应用于实际问题求解已被证明是一个成功的方法 ， 并且已形成一个专门的科学分支 仿生学 （） 。演化计算正是基于这种思想而发展起来的一种通用的问题求解方法。它采用简单的编码技术来表示各种复杂的结构， 并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。而作为演化计算的重要分支， 遗传算法（，）则是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术。遗传算法的基本原理如下：在遗

3、传算法的执行过程中， 每一代有许多不同的种群个体（ 染色体 ） 同时存在。这些染色体中哪个保留（ 生存 ） 、 哪个淘汰（ 死亡） ， 是根据它们对环境的适应能力来决定的， 适应性强的有更多的机会保留下来。适应性强弱是通过计算适应性函数（）的值来判别的 ， 这个值称为适应值。适应值函数（）的构成与目标函数有密切关系， 往往是目标函数的变种。主要的遗传算子有如下几种：）选择（）算子又称复制（）、 繁殖算子。 选择是从种群中选择生命力强的染色体， 产生新种群的过程。选择的依据是每个染色体的适应值大小， 适应值越大， 被选中的概率就越大， 其子孙在下一代产生的个数就越多。选择的方法根据不同的问题，

4、采用不同的方案。最常见的方法有比率法、排列法和比率排列法。）杂交（）算子又称重组（）、 配对（）算子。当许多染色体相同或后代的染色体与上一代没有多大差别时， 可通过染色体重组来产生新一代染色体。染色体重组分两个步骤进行： 首先 ， 在新复制的群体中随机选取两个染色体， 每个染色体由多个位（基因）组成 ； 然后 ， 沿着这两个染色体的基因随机取一个位置， 二者互换从该位置起的末尾部分基因。例如， 有两个用二进制编码的个体和， 长度，。随机选择一个整数 ， 设， 经杂交后变为：遗传算法的有效性主要来自选择和杂交操作， 尤其是杂交， 在遗传算法中起着核心作用。）变异（）算子。选择和杂交算子基本上完成

5、了遗传算法的大部分搜索功能， 而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率， 随机改变字符串某个位置上的值。在二进制编码中， 就是将变成， 将变成。变异发生的概率极低 （ 一般取值在 之间 ） 。它本身是一种随机搜索， 但与选择、 杂交算子结合在一起， 就能避免由选择和杂交算子引起的某些信息的永久性丢失， 从而保证了遗传算法的有效性。遗传算法的研究工作主要集中在以下几个方面：）基础理论： 包括进一步发展遗传算法的数学基础， 从理论和试验研究它们的计算复杂性。）分布并行遗传算法： 遗传算法在操作上具有高度的并行性， 许多研究人员都在探索在并行机和分布式系统上高效执行遗传收稿日

6、期 ：基金项目 ： 廊坊师范学院青年专项基金项目（）作者简介 ： 王怀军 （） ， 男 ， 江苏连云港人， 廊坊师范学院数信基础教学部教师， 主要研究方向： 计算机算法； 丁中文 （） ， 男 ，安徽无为人， 廊坊师范学院数信计算机系教师， 主要研究方向： 计算机算法和软件体系结构。电脑知识与技术， ：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 人工智能及识别技术本栏目责任编辑： 唐一东算法的策略。）分类系统： 分类系统属于

7、基于遗传算法的机器学习中的一类， 包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。）遗传神经网络： 包括连接权、 网络结构和学习规则的进化。遗传算法与神经网络相结合， 正成功地用于从时间序列分析来进行财政预算。）演化算法： 模拟自然进化过程可以产生鲁棒的计算机算法演化算法。 遗传算法是其三种典型的算法之一， 其余两种算法是进化规划（，）和进化策略（，）。这三种算法是彼此独立地发展起来的。进化规划最早由美国的、和提出 ； 进化策略则由德国的和建立。具体应用也很广。遗传算法的基本结构遗传算法的基本结构主要可分为遗传操作非重叠的演化算法和遗传操作重叠的演化算法。结合本文的示

8、例， 以下仅给出一种遗传操作重叠的演化算法。随机初始化种群（），；计算（）中个体的适应值；（不满足终止条件）根据个体的适应值及选择策略计算（）内每个个体的选择概率；（；）设能被整除根据选择概率在（）中选择两个父体；，；（）执行繁殖操作， 即将两个父体每一位进行变异后插入到新群体（）中；执行杂交操作， 并依概率对两杂交后代串中的每一位进行变异， 然后再将产生的两个后代插入到新群体（）中；计算（）中个体的适应值； 背包问题在传统的背包问题中， 需对容量为的背包进行装载。即从个物品中选取装入背包的物品， 每件物品的重量为， 价值为。对于可行的背包装载， 背包中物品的总重量不能超过背包容量， 最佳装载

9、是指所装入的物品价值最高， 即取得最大值， 约束条件为。其中为或， 表示物品是否被选中， 。背包问题是一个复杂问题。 在研究过程中设计了两个求解该问题的算法（ 具体实现略） 。一个是递归算法， 用穷举的方法从所有解中找出最优解， 另一个是遗传算法， 以求最快找出比较优的解。求解背包问题的遗传算法的具体实现）染色体的编码： 采用二进制编码， 染色体的每一位表示一个物品， 该位为“” 时表示不选中该物品， 而该位为“” 时则表示选中该物品。所以染色体的长度等于物品的总数目。）适应值的计算： 当染色体是“ 存活的” 即该染色体所表示的选中的物品的总重量没有超过背包的重量上限时， 其适应值为其所表示的

10、选中的物品的总价值， 否则为。）杂交算子： 随机选择两条染色体， 随机选取一个杂交位， 将两条染色体在杂交位之后的所有位进行交换， 即单点杂交的方式。）变异算子： 随机选取一个杂交位， 将该位进行反置， 即“” 变为“” ， 或者“” 变为“” 。）选择办法： 根据各条染色体的选择概率的大小， 采用轮盘的方式选取， 选择概率由适应值决定。）复制 ： 按选择概率和轮盘的选择办法， 直接从父代染色体中选取相等数量的子代染色体。实验结果在 下编程实现上面的算法， 得到的结果如下：采用递归程序求解， 可得到最优解如下（ 物品按顺序从开始编号） ： 采用遗传算法时得结果如下：）当种群数量（） 为时实验次

11、数 ： 解的价值 ： 去掉最低的和最高的， 解的平均值为：该解同最优解相差：， 约为）当种群数量（） 为时实验次数 ： 解的价值 ： 王怀军等 ： 遗传算法在求解背包问题中应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 本栏目责任编辑： 唐一东人工智能及识别技术电脑知识与技术年第卷第期 （ 总第期）（ 上接第页）聂鹏，耿文波指纹识别技术浅谈电脑知识与技术：学术交流，（）：曾建一指纹识别技术的研究自动化技术与应用，（）：， ，

12、（）： ，（）： ， ，（）： ， ， （），（）：姚凯指纹识别技术研究哈尔滨理工大学，杨长春自动指纹识别系统预处理关键技术的研究激光与红外，（）：杨丹，张小洪基于小波多尺度积的边缘检测算法计算机科学，（）：去掉最低的和最高的， 解的平均值为：该解同最优解相差：， 约为）当种群数量（） 为且演化代数由增至时实验次数 ： 解的价值 ： 去掉最低的和最高的， 解的平均值为：该解同最优解相差：， 约为）当种群数量（） 为、 演化代数为， 但变异数量增加一倍即到时实验次数 ： 解的价值 ： 去掉最低的和最高的， 解的平均值为：该解同最优解相差：， 约为结果分析由于物品数量较大（个 ） ， 故用递归程序

13、求解速度比较缓慢， 当物品数量达到以上时 ， 经过相当长的时间仍无法完成计算，说明穷举法对于大规模问题已经无能为力。然而采用遗传算法求解则十分迅速， 而且求得的较好解已十分接近最优解。如第一次的， 第二次的， 而第三次的已经就是最优解， 由此可以看出遗传算法在求解大规模问题时与传统算法相比较的明显优势。其次 ， 关于参数的设定 影响演化算法的最优化参数设置的主要障碍之一是参数之间的非线性相互作用。由以上实验可以看出 ， 当种群数量增加时， 由于参与竞争的模式增多， 所求得的解也更靠近最优解； 当种群演化代数增加时， 通过杂交和变异产生的参与竞争的新的模式也在增多， 故所求得的解也同样更靠近最优

14、解， 但显然 ， 增加种群数量的效果会更好些； 但当增加变异数量时，所求得的解增加没有以上两个明显， 这说明过多的变异不一定会使结果趋向最优的趋势变快。而且我们还可以很明显的看到， 上面参数对结果的影响都是非线性的。这一切都说明演化算法本质上是一个动态的适应的过程， 任何一个在演化中固定不变饿参数设置都不可能是最优的， 在演化过程的不同阶段应具有不同的合适的参数设置， 而且参数之间的相互影响非常复杂， 是非线性的。在针对特定的问题定制演化算法并在寻找问题的解的过程中修改控制演化搜索的设置及其策略参数时， 适应的方法是一种很好的方法， 但同样不存在“ 最好”的自适应的方法。总结本文根据遗传算法的

15、基本思路， 探讨了遗传算法在解决背包问题上的应用， 同时通过其同传统算法之一递归算法的比较以及对控制参数的重新设置， 分析了遗传算法的在解决大规模问题上的优点以及控制参数的难点， 对类似问题的解决提供了一种参考。值得注意的是遗传算法收敛性的研究， 长时期以来仅仅局限在二进制编码方式下通过选择控制参数来改进和提高其收敛性能， 但影响其收敛性的不仅仅是控制参数还有选定的遣传算子结构、性能和编码方式等， 编码方式通过遗传算子的作用间接影响算法的收敛性能。因此， 我们有理由相信将自适应的方法应用与演化算法中将会在一定程度上提高算法的性能。参考文献 ：陈根社，陈新海遗传算法的研究与进展信息与控制，（）：方建安，邵世煌采用遗传算法学习的神经网络控制器控制与决策，（）： ，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -