下载  >  开发技术  >  其它  > 论文研究-蜂群遗传算法求解多选择背包问题 .pdf

论文研究-蜂群遗传算法求解多选择背包问题 .pdf 评分

蜂群遗传算法求解多选择背包问题,吴迪,杨欣宇,多选择背包问题是组合优化中的典型NP难题之一,本文采用蜂群遗传算法进行求解。该算法通过设置两个自适应变化的种群,雄蜂群负责�
国武技论文在线 就越应该放入背包。因此,根据此先验知识。由下式得到启发式因了 C 其中,α是系数,用来调整两个参数之问的关系。由上式可以看出,越大,代表第 个物品单位体积价值较大,体积相对于背包也小,放入背包的概率就越大;反之,放入背包 的概率就越小。 约束条件处理 由于约束条件的存在,随机产生的初始解不一定可行,所以如何处理约束条件是解决多 选择背包问题的关键。如果染色体中的物品的总体积超过了背包的体积,就会成为无效染色 体。木文的编码方案会产生很多不满足约束条件的染色体,所以,无效染色体需要按照某种 规则更换物品,直到选中物品的体积小于背包体积,变成有效染色体为止。这样,可以使搜 索总在可行解空间上进行,同时还可以不断增加其适应值。 解决办法是采用启发式因子把无效染色体转化为满足约東条件的有效染色体。根据计算 出来的启发式因子,对无效染色体的每个基因进行可行性判断,对不可行的基因进行修正 如果仍是无效染色体,继续重复前面的操作,直到变为有效染色体为止。这样,无效染色体 会在较短时间内变为质量较好的有效染色体 主动进化算子 启发式因子的作用是引导蜂后在进化的过程中能够主动地产生适应环境的变异。根据计 算出来的启发式因子,蜂后进行主动进化。实现方式为:计算第类物品的,按照一定 的变异概率,该基因修正为较大的即可。这样,峰后的每个基因都处理一遍,产生了一 个新的蜂后,新蜂后和旧蜂后的适应值比较,取较大的作为蜂后。主动进化算子和变异算子 实现方式类似,但主动进化算子克服了变异算子的小概率、随机性的缺点,能利用先验知识 进行定向变异,提高了遗传算法的求解效率。 抑制算子 蜂后为了维持地位,对适应值接近而且编码也类似的个体进行相似抑制,抑制阈值为。 具体抑制〕法是,若是雌蜂群中的个体和蜂后的拥挤距离小于等于,那么蜂后对该个 体实行抑制作,该个体突变,即以随机个体取代之。拥挤距离可以通过计算蜂后和被抑制 个体在多目标上的距离差之和来得到 没有被抑制的个体按照与蜂后相差的适应度值人小来确定其变异率和变异位置。原则 是,适应度和蜂后适应度差别越小的个体,其变异率越低,反之,变异率越髙。雌蜂群主要 是为了保持群体的多样性,避免种群早熟收敛,随时可以跳出局部峰值。 拥挤距离公式如下 ∑ 其中,参数是染色体的适应值,是染色体的基因数,即类物品。是蜂后的 第个基因位,是染色体的第个基因位。 国武技论文在线 精英保留策略 本文在双种群的之外,单独设置一个峰后,用来记录“当前最好”的个体即“精英”。 在每代进化完成,都要计算出双种群个体的适应度,用每个种群的最优个体与蜂后进行比较。 如果前者比后者还优秀,则用前者覆盖后者,作为新的“当前最好”个体,否则予以保留蜂 后,该策略能更好地改善遗传算法的收敛 算法流程 综上所述,蜂群遗传算法解决多选择背包问题的措述为: 在函数定义域内,随机产两个初始群体,即雄峰群体和雌蜂群体,冬有和 个个体,设置 在两个群体中选出适应度最大的个体为蜂后。 雄蜂群体首先经过轮盘选择操作,然后按给定的交叉率和蜂后进行均匀交叉操 作,产生一个雄性后代和一个雌性后代。没有和蜂后交义的雄性个体再按照一定的交叉率和 雌蜂群中的某个体交叉,同样宀生个雄性后代和个雌性后代。最后雄蜂稊体进行随杋变 异操作。其中,后代中不满足约束条件的个体,根据诱变因子进行修正操作 雌蜂群体按照锦标赛选择的方法把中产生的雌性后代和原雌蜂群体重组 为个个体的雌蜂群体。 在两个群体中再次选出适应度最大的个体与原蜂后比较,如果新选出的个体适 应度人,则为新蜂后,否则,原蜂后保持。 对个个体的新雌蜂群体,计算和蜂后的拥挤距离,如果在一定阈值之内, 予以突变。剎下的个体,按照模拟退火算法计算自适应变异率进行变异操作。对不满疋约束 条件的个体,根据启发因」进行修正架作 蜂后根据主动进化算子进行修正操作。若算法结束条件不满足,转到继 续执行;否则,输岀蜂后作为全局最优解。 算法结束。 该算法结构简单,关键是双和群的设计既能兼顾选择压力,使其较快进化,又能保持种 群多样性,及时跳出局部最优解。同冋时对不淸足约朿的个体实行修正操作,大大提高了算法 的执行效率。蜂后的交叉操作也有利于优良模式的保留。 仿真实验 为了验证蜂群遗传算法解决多选择背包问题的有效性,本文对参考文献[]中的一个 类物品的多选择背包典型实例进行仿真求解,并将求解结果与文献和中的传统遗传 算法和改进遗传算法进行比较。本文实验环境是 内存 的微型机上,使用 编程。 以下是该问题实例: 国武技论文在线 满足的约束条件为 通过多次实验,设置参数只体如下:蜂群遗传算法初始雄蜂群群体规模为,雌蜂群 群伓规模为ξ迭代过程中自适应不断减少旌蜂群規模,并增加雌蜂群规模。算法的最大 达代次数为,雄蜂群与蜂后的交叉率设置为,变异率为。算法独立运行次, 每次运行时间均小 其中某次适应值随迭代次数的变化曲线如图所示,迭代到次 时,本文算法已经找到最优解,取得了比较满意的效果。传统的遗传算法采用实数编码,轮 盘选择,单点交叉和单点变异算子,群体规模,求解这个问题的收敛效率非常低,传统 遗传算法求解某次收敛如图所示。 图 的某次运行结果曲线 图传统遗传算法的某次运行结果曲线 将求解结果与文猷和文献中的遗传算法和知识进化算法求解结果进行比较,结果 如衣所示 表文算法与文献的算法比较 比较方案 运行次数 最优解次数 最优解概率 文献中传统遗传 算法 文献中罚函数遗 传算汯 文献屮的知识进 化算法 本文 算法 国武技论文在线 从表可以看岀,这儿种算法都可以求得该实例的最优解,但传统遗传算法的求得最优 解的频率最低,即使进化代,找到最优解的概率也只有%,而且由于跳出局部最优 解的能力比较弱,即使増加进化代数,效果也不会太明显。相比较其他算法,本文算法寻找 到最优解的成功率更高,因为双种群的设置比较好的平衡了选择压力和种群多样性之间的矛 盾,而且蜂后对雌蜂群体的排挤操作和辶动进化更加有利于启发式的跳出局部最优解。但是, 算法运行时间稍长,平均近,主要是对不行解的约束处理占用了大量时间。 结论 针对多选择背包问题的特点,本文利用蜂群遗传算法对其进行求解。测试结果表明,本 文算法求解多选择背包问题是高效可行的,虽然不能的找到最优解,但考虑到多选择 背包问题约束条件的类型多而特殊,这已是比较好的结果了,同时也拓展了蜂群遗传算法的 新的应用领域。 参考文献 刘建芹贺毅朝顾莤莤基于离散微粒群算法求解背包问题研究,计算机工程与设计 叶宇风多重群体遗传算法在多选择背包问题中的应用计算机工程与设计 飽江宏用遗传算法实现罚函数法解多选择背包问题计算机程与设计 马慧民许圣良黄忠林徐梦君多选择背包问题的知识进化算法上海电机学院学报 王硏王志刚差异演化算法求解多选择背包问题科学技术与工程 韩燕燕马良赵小强多选择背包问题的人工蜂群算法·计算机应用研究 矢迪姜永增宋广军基J蜂群遗传算法的背包问题.计算机工程与科学 玄光男程润伟于歆杰等遗传算法与工程优化北京清华大学岀版社

...展开详情
所需积分/C币:7 上传时间:2019-08-21 资源大小:228KB
举报 举报 收藏 收藏
分享 分享
论文研究-蜂群遗传算法求解多选择背包问题 .pdf

蜂群遗传算法求解多选择背包问题,吴迪,杨欣宇,多选择背包问题是组合优化中的典型NP难题之一,本文采用蜂群遗传算法进行求解。该算法通过设置两个自适应变化的种群,雄蜂群负责�

立即下载
论文研究-基于改进的蜂群遗传算法求解多选择背包问题.pdf

多选择背包问题是组合优化中的典型NP难题之一。针对传统蜂群算法存在的收敛速度慢、易陷入局部最优的缺点,提出改进策略。改进的算法通过设置两个自适应变化的种群雄蜂群和雌蜂群,雄蜂群负责与蜂后交叉操作以保持种群的选择压力,雌蜂群负责自适应变异操作以保持种群多样性,蜂后则根据启发式规则主动进化以局部寻优。根据算法实现的核心思想,仿真实验结果表明,提出的改进算法可以有效避免陷入局部最优,同时通过实例也验证了算法的可行性和有效性。

立即下载
论文研究-0-1背包问题的萤火虫群优化算法.pdf

根据群集智能优化原理, 给出了一种基于萤火虫寻优思想的新算法——萤火虫群优化算法, 并针对0-1背包问题进行求解。经仿真实验并与蜂群算法、蚁群算法和微粒群算法进行了比较, 获得了满意的结果, 这说明了算法在0-1背包问题求解上的有效性和具有更快的收敛速度, 拓展了萤火虫群优化算法的应用领域。

立即下载
论文研究-多选择背包问题的人工蜂群算法.pdf

多选择背包问题是组合优化中的NP难题之一,采用一种新的智能优化算法——人工蜂群算法进行求解。该算法通过雇佣蜂、跟随蜂和侦察蜂的局部寻优来实现全局最优。基于算法实现的核心思想,用MATLAB编程实现,对参考文献的算例进行仿真测试。与其他算法进行了比较,获得了满意的结果。这说明了算法在解决该问题上的可行性与有效性,拓展了人工蜂群算法的应用领域。

立即下载
背包问题蜂群优化算法

针对基本粒子群算法在背包问题上表现的不足,在基本粒子群算法的基础上运用模糊规则表加入了新 的扰动因子,提出了一种新的算法———模糊粒子群算法。该算法结合了模糊控制器中输入/输出的模糊化处理 和粒子群寻优的特点,为实际问题提供了新的解决手段。将模糊粒子群算法应用于0-1 背包问题上,通过多组 实例数据进行测试,验证表明了本算法具有良好的有效性和鲁棒性。

立即下载
ModbusTCP/RTU网关设计

基于UIP协议栈,实现MODBUS联网,可参考本文档资料,有MODBUS协议介绍

立即下载
html+css+js制作的一个动态的新年贺卡

该代码是http://blog.csdn.net/qq_29656961/article/details/78155792博客里面的代码,代码里面有要用到的图片资源和音乐资源。

立即下载
iCopy解码软件v1.0.1.7.exe

解ic,id,hid卡密码破解ic,id,hid卡密码破解ic,id,hid破解ic,id,hid卡破解ic,id,hid卡密码密码卡密码破解ic,id,hid卡...

立即下载
分布式服务框架原理与实践(高清完整版)

第1章应用架构演进1 1.1传统垂直应用架构2 1.1.1垂直应用架构介绍2 1.1.2垂直应用架构面临的挑战4 1.2RPC架构6 1.2.1RPC框架原理6 1.2.2最简单的RPC框架实现8 1.2.3业界主流RPC框架14 1.2.4RPC框架面临的挑战17 1.3SOA服务化架构18 1.3.1面向服务设计的原则18 1.3.2服务治理19 1.4微服务架构21 1.4.1什么是微服务21 1.4.2微服务架构对比SOA22 1.5总结23 第2章分布式服务框架入门25 2.1分布式服务框架诞生背景26 2.1.1应用从集中式走向分布式.26?

立即下载
Camtasia 9安装及破解方法绝对有效

附件中注册方法亲测有效,加以整理与大家共享。 由于附件大于60m传不上去,另附Camtasia 9百度云下载地址。免费自取 链接:http://pan.baidu.com/s/1kVABnhH 密码:xees

立即下载
电磁场与电磁波第四版谢处方 PDF

电磁场与电磁波第四版谢处方 (清晰版),做天线设计的可以作为参考。

立即下载
压缩包爆破解密工具(7z、rar、zip)

压缩包内包含三个工具,分别可以用来爆破解密7z压缩包、rar压缩包和zip压缩包。

立即下载
source insight 4.0.0087 注册机序列号Patched(2017/10/17)

最新的sourceinsight4.0.0087和谐license及和谐文件。真正的4087版本,使用附件中的license文件,替换sourceinsight4.exe

立即下载
Java项目经验汇总(简历项目素材)

Java项目经验汇总(简历项目素材)

立即下载
支付宝转账demo-实现提现功能

支付宝单笔转账,实现提现功能,自己用到,所以分享给大家,希望可以帮到大家。(内有demo实例,望大家多多提意见)

立即下载
算法第四版 高清完整中文版PDF

《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 第4版具体给出了每位程序员应知应会的50个算法 提供了实际代码 而且这些Java代码实现采用了模块化的编程风格 读者可以方便地加以改造

立即下载
计算机中丢失api-ms-win-crt-runtime-l1-1-0.dll的修复方案

计算机中丢失api-ms-win-crt-runtime-l1-1-0.dll的修复方案

立即下载
最新的微信小程序源码

最新的微信小程序源码70多个很多行业都有加后台

立即下载
http://pan.baidu.com/s/1jIykf2I

视频剪贴工具Bigasoft_Tota_Video_Converter.rar用于图像的剪贴合并

立即下载
LostCraft_安徽信息工程学院大一学弟学妹专用

LostCraft为安徽信息工程学院大一下学期课程内原有代码,,由于一些学弟学妹们懒得去敲,我就照着书本把它敲了下来,亲测通过。如果下载后运行不了,自己百度去吧!!!

立即下载