论文研究-用人工蜂群算法求解带平衡约束的圆形布局问题 .pdf

所需积分/C币:9 2019-08-17 20:11:08 380KB .PDF
52
收藏 收藏
举报

用人工蜂群算法求解带平衡约束的圆形布局问题,王英聪,麦嘉辉,对于带平衡约束的圆形布局问题,本文采用定位定序的启发式方法结合人工蜂群算法的思路进行求解.对传统优化模型进行了调整,通过人工
国武技论文在线 http:/www.paper.edu.cn 为定位定序方式求解布局问题.本文采用ABC算法对待布圆进行排序,再按照占角规则求出 待布圆的位置 对于带平衡约束的圆形布局的问题,文献[9已经很详细的介绍了定序定位方式具体的 70求解步骤,本文在此基础上作了如下修改: 1)在布置第1个和第2个小圆时(两者相切),只需直接给出它们的位置即可,两者位 置为:(一n1,O)和(r1,0)根据占角规则第3个小圆必须同时与第1个和第2个小圆相切,由于 计算得到的两个可行位置对称,选取哪一个位置的效果都是一样的,故也可直接给出第3个 小圆的位冒 2)设(1,l2;,:)为已经布局了的k1个小圆的顺序,当要布置第k个小圆(k>3)时,则要 求小圆i至少与两个已经布局好的小圆相切山,因为小圆与已布局的小圆相切时,整个布局 般都会更加紧凑.般来说,两个已布局的小圆可确定两个位置放置小圆i,故放置第i个 小圆时最多有2xC1个位置可供选择到了布局后期,这些位置中有很多都是无效位置,必 须予以剔除.具体方法为:建立一个nⅫn禁忌表tbu来记录仼意两个已布局小圆所能确定的 80两个位置的使用情况,若两个位置都被使用,则在以后确定待布小圆位置时禁忌这两个小圆 3)由于小圆认有多个位置可供选择,则其可生成多种临时布局方案,根据公式(5)可计算 出仝部临时布局方案的包终半径,一般的做法是采用贪心策略选择包络半径最小的位置作为 小圆读的位置90,这样往往不能使最后的包络半径达到最优,只能快速地找到一个次优的包 终半径.为此,木文引入模拟退火策略12,在布局过程中以一定概率接受较差布局,该概率随 85着布局过程的进行逐渐变小 人工蜂群算法 人工蜂群算法概述 D. Karaboga在2005年成功地将蜜蜂的觅食行为应用到函数优化问题而提出人工蜂群 算法( Artificial Bee Colony Algorithm).算法中每个蜜蜂被看作是一个智能体 agent),通过 90群体中不同个体间的分工协作、角色转换、记忆等行为涌现出群体智能 蜂群的智能模型包含四个基本要素:食物源( Food sources)、侦査蜂( Scouter、引领蜂 Leader)、跟随蜂( Follower);三种基本行为:搜索食物源( Search)为食物源招募竇蜂( Recrui)、 放弃食物源( Abandon). 组合优化问题是指寻找一组离散变量的值,使得指定目标函数的解达到最优.许多重要 95实际应用和有理论研究价值的优化问题木身就具有组合性质.从模型上看,蜂样算法中角 色分⊥和合作机制具有离散性质,对采用离散化处理后的ABC算法,在许多组合优化问题中 得到了应用,并取得了优良的效果,例如旅行商问题(ISP)、网络路由优化问题13、背包问 题等 人工蜂群算法优化布局顺序 100 求解小圆的布局顺序实质上可转化为求解TSP问题的路径,人工蜂群算法在TSP问题上 得到了很好的效果51.TSP问题中的路径对应」小圆的布局顺序,路径长度对应于布局方 案的包络半径,路径节点讠对应于第i个待布置小圆.在此应用人工蜂群算法优化圆形布局顺 序 蜜蜂采蜜可以看作最短路径问题,蜜蜂得到一个路径(小圆的布局顺序)后,根据路径的 3 国武技论文在线 http:/www.paper.edu.cn 105长度(布局方案的包络半径),对食物源收益率进行更新(定义食物源收益率为包络半径的 倒数),并根据食物源收益率转换角色.建立角色矩阵role,记录下次迭代各个蜜蜂的角色.角 色依据此次迭代中各蜜蜂对应食物源的收益率选择,按照排名先后定义,其中排名靠前的 部分为引领蜂(30%),排名靠后的一部分为侦査蜂(40%),剩余蜜蜂为跟随蜂(30%)建立路径 记录矩阵path,依据所扮演的角色不同,蜜蜂构建路径的方式有所不同.从节点ⅸ(第i个已经 110放置小圆)转移到节点j(第j个待布置的小圆)的过程中,引领蜂完全重走上一次的路径, 跟随蜂和侦査蜂依据概率转移规则选择下一个节点,其计算如下 sn(t)[mn(t)]° 2Mmy/∈ allowed swallowed 0 otherwise 其中,p0表示第k个蜜蜂在时刻t由节点转移到节点j的概率;aoed表示第k个 蛮蜂在节点i的可行邻居节点,由蜜蜂还未访问过的节点组成(待布置的圆集).S2(,n(分 115别表小蜂群的控制信息和问题的启发信息,α,β分别是其权重参数,木文的a,β均设为1. 侦查蜂,Sn(t)=,l为蜜蜂木走过的节点个数 选择引领蜂的道路 可选择嵱径含引领蜂走过道路 跟随蜂,Sn() 不选择引领蜂的道路 可选择路径不含引领蜂走过道路 其中,γ表示引领蜂的引导性强弱,l为蜜蜂未走过的节点个数 由于布局对包络圆的半径和静平衡量均有要求,按照启发式信息:优先放置半径较大、 120质量较大的小圆可能会有更好的结果,因此令 7n(0=元xm1+xr,; 根据作者的计算经验,本文的y设为0.9,人设为0.01,4设为0.01 当概率计算岀来之后,通过轮盘赌策略选择岀下一个节点,直到得岀整条路径为止. 人工蜂群算法框架 125 设定迭代次数为κ,蜜蜂总数量为Ⅰ,初始化所有蜜蜂都为侦査蜂,随机选择路径(即随 机给出布局顺序),计算适应度、路径舞阵path和角色矩阵role fori=1toK{迭代K次; forj-1toL{/处理L只竇峰 fork=1ton{分步布局n个小圆,根据路径矩阵path和角色矩阵role,选取相应的方 130 式选择小圆.如果k等于1,2或3,直接给出小圆位置,否则根据第3节中的规则 2、3确定小圆位置 计算每个蜜蜂对应路径的收益率,并更新路径矩阵path和角色矩阵role 4 国武技论文在线 http:/www.paper.edu.cn 135 输出K次达代中的最住布局. 数值试验及结果分析 为了便于比较,本文采用日前文献中经常使用的4个带平衡约束的圆形布局算例.4个算 例的数据来自文献[7] 木文的蜜蜂群体选择10只蜜蜂,其中包括3只引领蜂、4只侦察蜂和3只跟随峰.迭代 140次数为50次,模拟退火算法的初始温度为50,衰减参数为0.9.以计算时间、包络半径和静不 平衡量作为衡量算法性能的标准.为了便于性能分析比较,将时间统一换算为CPU主频为 166M环境下的耗时,计算时间以s为计算单位,各种算法的计算结果如表1所示 表1各种算法的性能比较 145 Tab. 1 Performance comparison of various algorithms 布局圆个 性能指标IDE[3]MPSO4] LSPSO[s]QPQH[6ISS[7]ACO[10] 本文 n ABC T/s 28 55.2 184 3.13 R 120.71 120.71 120.71 120.71 2.70F03 7.60F048.5F-8 T/s 03.629176 8 R 31.967 31985 32.23 31981 31.954 319 31.9 6.90E-051.80E-027.00E-054.10E-03570E-14 T/s 52.48 2.16 R 1.0006510000151.000041.00000 3.78E03178E04 S 573 843.94 1128 1774 292.2 6265 R 2523 811.81 742.75 740.55 754 745.6 7.00E-043.90E032.00E-03540E-04400E-5 0 从以上各算法的计算结果可以得出,本文的算法无论在时间上还是在精度上都取得了比 较好的效果.对于算例1,本文的时间比之前的算法都快了690倍.对于算例2,本文比不上文 献[10的ACO,比它慢了4倍多.对于算例3,本文以较短的时间找到了最优布局.对于算例4, 150本文比文献[10]快了近1倍,而且精度也有所改进,与文献[6,7相比,结果稍差,但是速度快了 3倍. (a)算例1 (b)算例2 155 (a) Example I (b) Example 2 国武技论文在线 http:/www.paper.edu.cn 1 13 14 (c)算例3 (d)算例 (c) Example 3 (d) Example 4 图1本文算法求得的四个算例的最优布同 160 ig. I The optimal layout of the four examples solved by the al gorithm in this paper 结论 对」带平衡约束的圆形布局问题,木文采用定序定位的启发式方法与人工蜂群算法相结 合求解.在定位规则上引入禁忌策略和模拟退火策略,禁忌策略使得某些小圆不会被重复选 165中来计算待布小圆的位置,减少了算法的运行时间;模拟退火策略使得算法以一定概率接受 较差布局,增加了算法跳岀局部最优的能力.实验结果表明,本文在包络半径、静不平衡量 运行时间等指标取得了较好的效果 参考文献 170 [1] GAREYM R, JOHNSON D S. A guide to the theory of NP-completeness [M]. New York: Free-man, 1979 [2] KRONSJO L Computational complexity of scqucntial and parallcl algorithms [M]. Ncw York: John Wilcy Sons,1985:56 [3]刘建,黄文奇.利用改进的微分进化算法求解带半衡约束的圆形 packing问题.信息与控 制,2006,35(1):103-107 1754]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究「.讣算机学 报,2004,27(7):897-903 [S]周驰高亮高海兵基于粒子群伏化算法的约東布局优化[控制与决策,2005,201):36-40. [6] Huang wQ, Chen M Note on: An improved algorithm for the packing of unequal circles within a larger containing circlc. Computers Industrial Enginccring. 2006,50(3): 338-344 180[7]王奕首,史彦军朦弘飞.用改进的散射搜索法求解带平衡约束的圆形 Packing问题[计算机学 报,2009,32(6:1214-122 8 Huang WQ. Li Y, Li C Met al. New heuristics for packing unequal circles into cIrcula container[]. Computers and Operations Research, 2006,33(8): 2125-2142 [9]Yi-Chun Xu, Ren-Bin Xiao and Martyn Amos. A novel genetic algorithm for the layout 185 In proceedings of 2007 IEEE Congress on Evolutionary Computation( CEC2007): 3938-3942 Optimization problem L0」徐义春,肖人彬用蚁群算法求解带平衡约朿的圆形布局问题刂控制与决策,20(8,23(1:25-29 [Il Gcorgc J A, Gcorgc J M, Lamar B W. Packing diffcrcnt-sizcd circles into a rectangular containcr[J] European Journal of Operational Research, 1995, 84(3): 693-712 [12]谢云模拟退火算法综述[微机计算机信息,1998,14(5):66-68 190 113 Karaboga D An idea based on honey bee swarm for numerical optimization[R]. Kayseri, Turkey: Frciyes University, 2005 「14]丁海军,李峰磊蜂群算法在TSP问题上的应用及参数改进[J.中国科技信息,2008(3):241-243. [15]李峰磊蜂群算法的硏究亐应用[D].南京,河海大学道信与信息系统研究所,2008. [16]郑伟,刘静,曾跫潮.人工蜂群算法及其在组合优化中的应用研究凹.人原科技人学学报,2010 国武技论文在线 http:/www.paper.edu.cn 19531(6):467-471 「1η]胡中华,赵敏基于人工蜂群算法的TSP仿頁卩北京理工大学学报,2009,29(11):978-982.

...展开详情
试读 7P 论文研究-用人工蜂群算法求解带平衡约束的圆形布局问题 .pdf
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-用人工蜂群算法求解带平衡约束的圆形布局问题 .pdf 9积分/C币 立即下载
1/7
论文研究-用人工蜂群算法求解带平衡约束的圆形布局问题 .pdf第1页
论文研究-用人工蜂群算法求解带平衡约束的圆形布局问题 .pdf第2页

试读结束, 可继续读1页

9积分/C币 立即下载