求解多维0_1背包问题的人工鱼群算法 (1)_第1页
求解多维0_1背包问题的人工鱼群算法 (1)_第2页
求解多维0_1背包问题的人工鱼群算法 (1)_第3页
求解多维0_1背包问题的人工鱼群算法 (1)_第4页
求解多维0_1背包问题的人工鱼群算法 (1)_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第40卷第 1 7 期 2010年 9 月 数学的实践与认识 M A T H E M A T IC S INP R A C T IC EA N D T H E O R Y V ol. 40 , N o . 17 Sep . , 2010 求解多维 0一 1 背包问题的人工鱼群算法 李春梅, 马 良 (上海理工大学管理学院, 上海 200093) 摘要: 对于多维 住1 背包问题, 国内外学者提出了诸如模拟退火 ?遗传算法 ?蚁群 算法以及其他启发式算法. 给出一种新的智能寻优方法 ?人工鱼群算法. 算法 通过各人工鱼的局部寻优, 从而在群体 中体现出全局最优.描述了人工鱼群算法的 具体步骤并编程实现, 通过多维背包算例进行了求解测试, 获得了满意的效果. 关键词:多维 O一 1 背包问题;人工鱼群算法;优化 1引言 多维 0一 1背包问题 (M ul ti 一 Di m ensi onalo一 1K napsa c k probl e m )是一个典型的组合优化问 题, 有着广泛的实际应用背景, 如项 目 决策与规划 ?材料切割 ?资源分配 ?货物装载等问题, 并且还常常与其他相关间题结合加以研究. 因此, 寻找有效解决多维 0一 1 背包问题的算法具 有重要的理论价值和应用背景. 背包间题的描述有多种形式, 其中一般的多维整数背包间题可以在有界的前提下化成等 价的多维 0一 1 背包问题.迄今为止, 对于 一 1 背包间题的求解, 人们已提出了许多有效地解决 该问题的算法. 一般的经典算法, 如枚举法, 分支定界法, 动态规划法等, 仅适用于小规模的 0一 1 背包 间题, 并且算法实现比较复杂, 在实际应用中存在很大的局限性.因此, 对于大规模的 0一 1 背包间题, 人们为了寻求在较短时间内得到较优解, 提出了多种启发式算法, 例如遗传算 法 ?禁忌搜索 ?模拟退火 ?神经网络 ?蚁群算法等 l , 这类算法特点是通过模拟 自然生态系 统机制 以求解复杂优化问题的仿生优化算法, 主要是面向具有大规模应用背景的问题. 20 0 2 年, 李晓磊等人提出了一种新型的自 适应寻优算法 一 人工鱼群算法 l z ( A r t血i a l F i s卜sw a r m A 坛 o r i thm , A FsA), 它是一种基于动物自治体的优化方法, 能够较好地解决非线 性函数优化等问题. 它具有对初值要求低 ?参数选择不敏感 ?鲁棒性强以及全局收敛性好等 诸多优点. 由于人工鱼群算法的上述特点, 它可以被应用于各种不同领域的复杂间题 ! 一 9!. 因此, 本文在此基础上, 提 出了一种用人工鱼群思想求解 维 一 1 背包问题的智能优化算法, 为多 维 0一 1 背包 间题 的求解提供了一种新的解决手段. 2多维 0一 1 背包问题 将一个 维 0一 1 背包问题可以描述为: 收稿 日期:201压 冬10 资助项目:国家自然科学基金 (70871081 ) ;上海市重点学科建设资助项 目 ( 530504) 1, 6 数 学 的 实 践 与 认 识40卷 已知 n 个价值为 巧( j 二1,2, ,川 的物品, 个容量大小为 q # 二1,2, ,n )的容器, 第 J 个物品所占第 葱 个容器的容积大小为 w汀 .应如何选择物品装入这 二个容器, 使得装入 的总价值最大. 问题的数学模型为: n ma x f ( x 1,x 2 , ,珠)一 艺 二 j= 1 几 艺 勺? J= 1 x, %o,1, 葱=l, 2, , m j 二1, 2, 二 物品的编号; :容器的编号;马:第j 个物品的价值;c : 第 个容器的容积;叭j : 第j 个物品所占第 葱 个容器的容积大小;x j :0 一 1 决策变量, 当物品 j被选择装入时, x j 二1, 否则, 肠 二0 . 3 人工鱼群算法 3.1 算法思想 在一片水域中, 鱼往往能够 自 行或尾随其它鱼找到营养物质多的地方, 因而鱼生存数目 较多的地方一般就是本水域中富含营养物较多的地方. 人工鱼群算法就是根据这一特点, 通 过构造人工鱼来模拟鱼群的觅食 ?聚集以及追尾行为, 从而实现全局寻优. 鱼的 3 种生存行为: l )觅食行为:一般情况下在水里随机的自由游动, 通过视觉或味觉感知水中食物量或浓 度, 一旦发现目标, 就会向着目标方向快速游去. 2) 聚集行为:鱼在游动过程中自 然地聚集成群进行集体觅食和躲避公害. 3 )追尾行为:当其中一条或几条鱼发现食物时, 其临近的鱼会尾随其后快速的游去, 进 而导致更远处的鱼也尾随游去. 3 . 2 算法描述 每条人工鱼个体的状态X = z l ,几, , 几, 即背包间题欲寻优的变量, 它代表了一个 候选方案, 其中, 夙 二0 表示该方案中未选择第 乞 种物品, 及 = l 表示该方案中选择了第 乞 种 物品; 目标函数值 y = f ( X )表示人工鱼当前状态的食物浓度 FC , 即该方案的收益;人工鱼 凡 和人工鱼 凡 之间的距离为 , ,一 ? 全 ( 二 *一 :? ) 2 丫 允=1 V i s u a l 表示人工鱼的感知距离;S t e P 表示人工移动的步长;占 表示拥挤度因子;肠yN um be r 表 示人工鱼每次移动最大的试探次数. 算法有 3 种行为描述和一个公告板, 具体如下: l )觅食行为 设人工鱼的当前状态为 X , 在其感知范围内 (即 成, 三v 坛 # 成)随机的选择一个状态 凡 , 若此时的食物浓度大于当前状态时, 则向该方向前进一步, 执行 (l ) ;反之, 再重新随机选择状 17期李春梅, 等:求解多维 0 - 1 背包问题的人工鱼群算法 197 态 凡 , 判断是否满足前进条件, 若反复了 肠yN um be r 后, 仍不满足前进条件, 则随机移动一 步, 即人工鱼 凡 的下一步状态 弋+1= 夙+1,1,夙+l,2. ,乙+l, . 夙无 m i n(1,乙?+ 1) 及* = 易 夙?兴易 (l) 了l 少 ? t 一一 k+ 及 2) 群聚行为 人工鱼的当前状态为 弋, 在其感知范围内 (即 成, 三叭翎a l )的伙伴数目n I以及探索 到的中心位置 X c e n t er, 计算出中心位置的食物浓度 (FC ) , 若满足 Y c enter 几f 全占 K( O 丫 ( o 1? 几f 则表明伙伴 % max 具有较高的食物浓度且其周围不太拥挤, 就朝 尤 ma x 方向前进一步, 执行 (3);否则, 执行觅食行为. f 夙 *夙?一z m ax. * #+, 一 飞 m n( ,夙 *+ ) 夙 #笋 Z m 一# (3) 4) 公告板 公告板用来记录最优人工鱼个体的状态. 人工鱼个体在寻优过程 中, 每次行动一次后就 将当前状态的食物浓度与公告板上的进行比较, 若优于公告板状态, 则用此时食物浓度替代 公告板状态, 从而记录下历史最优 的状态. 对人工鱼当前所处的环境进行评价, 即模拟执行群居行为 ?追尾行为, 然后选择行动后 食物浓度值较大的行为来执行, 缺省行为方式为觅食行为. 3 . 3算法流程 根据上述定义, 背包问题的鱼群算法主要步骤可描述如下 : 步骤 1设置人工鱼群的群体规模 Y , 每次移动最大的试探次数 肠yN um be r , 迭代次数 N um ber, 人工鱼的感知距离 V i s u a l , 拥挤度因子 衣 步骤 2 初始化迭代次数, 在可行域范 围内随机生成 N 个人工鱼个体, 形成初始鱼群, 即 产生 N 组 夙;(其中乞 = l,2, , N ;k : = 1,2, ,n) 否则, 终止迭代, 输出计算结 果 ( 公告板上的 FC 值). 4 算例测试 为测试算法的有效性, 本文用 M a t l a b软件编程实现, 并在 W i n d o w X P 系统下求解了多 维 0一 1背包问题的算例. 测试算例均可从h t tp: /el i b. zi b. de/pub/pa c k a ges/m 卜t estda t a/i p/sa c 94一 sui te/i ndex. 玩m 吓 载. 例 1 四维背包问题( 如表 1 所示) 表 l 4 0 9 1 3 12 3 18 25 1 1 8 1 1 4 9 8 2 1 61 5 8 1 0 42 6 4 8 0 1 0 1 1 6 9 2 4 18 6 0 8 2 1 6 2 1 7 0 9 2 2 4 1 5 6 0 4 8 4 3 010 0 6 3 8 39 5 4 0 8 12 1 5 0 1 2 0 3 0 4 0 6 8 0 6 4 4 1 5 8 2 8 0 20 0 0 38 5 2 7 20 0 3 4 1 2 4 61 18 15 3 8 10 4 8 0 3 0 6 1 3 0 3 5 4 P j56 0 1 125 6 8 3 2 8 4 7 12 2 19 6 4 1 2511 5 8 2 22 63 1 13 2 42 0 86 42 1 03 8 1 2 6 49 3 16 7 2 7 l 49108116 9 0 2 1 9 2 03 2 08180 该测试中的鱼群规模 N二 20 0 , 每次移动最大的试探次数 肠yN um be r 二 5 0 , 迭代次数 N um be r 二3 0 0, 人工鱼的感知距离 V i su a l = 6, 拥挤度因子 占 二0.6 1 8, 运行后可得最优解 34 1 8. ? ? ? ? ? ? 期? 迭 代 次 数 南豆 知渝 左一南一 谕 一 万劫 二 一 亩 一 亩一 勃 透代次斌 图 l 例 2 十维背包问题 间题数据可参见h t tp: /el i b. zi b. de/pub/pa咖 罗s/m 卜testdata/i p/sae94 - sui te/pbs. dat. 该测试中的鱼群规模 N = 10 0 , 每次移动最大的试探次数 升yNum be r = 5 0 , 迭代次数 N um be r 二3 0 0, 人工鱼的感知距离 V i s u a l = 6, 拥挤度因子 占 二 0. 61 8 , 运行后可得最优解 2 1 3 9 . 测试算例表明, 本文的人工鱼群算法对于求解多维 0一 1 背包问题是有效的.同时, 使用一 定的种群规模和迭代次数均可得到最优解, 并且寻优过程具有较好的收敛性. 1 7 期李春梅, 等:求解多维 压1 背包向题的人工鱼群算法1 9 9 5 结束语 仆1 背包间题是一个 N P 难题, 本文针对多维 压 1 背包间题的特点设计了基于 M a t l a b环 境的人工鱼群算法. 经大量算例测试, 算法对于该问题具有较好的性能. 同时, 可以设想, 若 对人工鱼群算法进行合理的设计, 也能用于其它一些 NP 难题的求解, 这对于科学与工程中 的许多问题都具有重要的意义. 参考文献 l 马良 , 朱刚, 宁爱兵.蚁群优化算法 M .北京:科学出版社, 2008 . 冈 李晓磊一 种新型的智能优化方法 一 人工鱼群算法 D .浙江大学博士论文, 200 3 , 1. 3(S ed F妞 rzi. Ef f i ei entjob sehedul ing in 盯 i d eom puti ng w i th m odi f ied a r t if ieia l f ish sw a rm a l 盼 rithm J) .In t er n a t i onalJourna l ofC om putor The o 叮 a n d Eng i

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论