论文研究-多目标拆卸线平衡问题的Pareto细菌觅食算法.pdf

所需积分/C币:30 2019-07-22 21:20:27 1.38MB .PDF
收藏 收藏
举报

拆卸线平衡问题的优化涉及多个目标。为克服传统方法在求解多目标拆卸线平衡问题时不能很好地处理各子目标间冲突及易于早熟等不足,提出了一种多目标细菌觅食优化算法。该算法采用Pareto非劣排序技术对种群进行分级,并结合拥挤距离机制评价同级个体的优劣。为提高算法收敛性能,在趋向性操作结束后引入精英保留策略保留优秀个体,并采用全局信息共享策略引导菌群不断向均匀分布的Pareto最优前沿趋近。通过不同规模算例的对比分析,验证了算法的有效性与优越性。
第11期 胡扬,等:多目标坼卸线平衡问题的 Pareto细菌觅食算法 3267 (11) P,计算目标函数值,求出种群的非劣解集NDS(P),限制其规 模丨MDS(P)丨≤UB。,赋予外部解集过滤器初值PFS=NDS 当m个月标函数对应的cdl都计算完成后,即可得到解S(P),并限制其规模|PFS|≤LB 的拥挤距离: b)按照2.3节中的2),对细菌群体P进行趋向性操作得 cd(S)=∑cd1(S) 12)到种群P(LM) 于是,个体价的规则设定为;对于级数不同的解,级数越的非劣解焦MmS(P(M+1),并限制NP(M+1)1≤ 小则解越优;对于级数相同的解,拥挤距离越大则解越优 UBn4,更新外部解集过滤器。 2.3算法结构 d)用2.2节所述个体评价规则对P(LM2+1)进行选择运 1)初始可行解生成在ⅦBO算法中,将细菌在觅食坏算,将其规模缩小到 NUM POP 境中所处的位冒描述为问题的解,用一个一维数组表示。该数 e)P(LM2+1)群体进行全局信息共享,LM。=LM+1,如 组是将每一个拆卸任务对应的任务序号按照任务拆卸顺序进果M<N,返回步骤b);否则进入步骤f)。 行排序得到的。为了保证初始种群的多样性,从而使初始搜索 f)细菌群体进行繁殖操作,LM。=LM灬+1,LM=0,如果 空间更为广阔,在构造初始解序列的过程中,仅考虑仁务优先LMn<Nn,返回步骤b);否则进入步骤g)。 关系这约東条件。具体生成步骤为:a)选取无前序任务约 g)细菌群休进行驱散操仵,LM。=LM,-1,LM灬=LM。= 束的任务构成候选任务集;b)将候选任务集屮作业时间超过0,如果M。<N,返回步骤b);否则流程结束,输出外部解集 工作站剩余可分配时间的任务从任务集中移除,形成可分配任过滤器中的解。 务集;c)从可分配任务集中随机选择一个任务进行分配 算法流程如图1所示。 2)趋向性操作细菌在当前位置的基础上,運过不断旋 丌始 转和游动,寻找食物富集的区域并避开有毒的物质,这种行为 称为趋向性,其实质是细菌对当前解的邻域搜索过程。具体操 参数初始化 作步骤为 否 LM<N a)计算细菌i的初始适应度值并储存。 b)细菌i旋转后,向随机方向游动一步长,计算移动后细 菌的适应度。 K LM<N c)判断是否达到最大步数AS,若是则进人步骤d);否则 是 判断新的适应度是否更好。若是则沿着当前方向继续游动 否 步长;否则向随机方向游动一步长,重复步骤c)。 LM<N d)i=i+1,判断i≤NUM_POP。若是则返回步骤a);否则 是 本次趋向性操作完成,输出所有细菌的当前位置。 趋向性操作 3)精英保留略及外部解集过滤在种群的更新过程 求非劣解集 繁殖操作 驱散操作 中,引入精英策略保留优秀个体。将执行趋问性操作前种群中 更新外部 解集过滤器 的非劣个体合并到执行趋向性操作后的种群中,求出合并后的 种群所对应的非劣解,并将其放入外部解集过滤器中,然后剔 选择运算 LM=LM+1 LM,LMn+ LM==O 除过滤器中由于新解的放入而处于受支配地位的解,以此完成 「信息共享 外部解集过滤器的更新。为了防止随着迭代过程的进行,Pa LMELM+1 reto解集的规模不断扩大而导致算法开销加剧。设定非劣解 集的规模上限为UB。,设定外部解集过滤器的规模上限为 结束 IiBw。为∫提升算法的收敛性能,在完成外部解集过滤器的史 图1MBFO算法流程 新后,引入全局信息共亨策略,利用外部解集过滤器中拥挤距 离最大的个体引导细菌群体向最优区域趋近。 3算法验证 4)繁殖操作及驱散操作细菌个体在进行N次趋向性 本文采用 MATLAB7.l对MFO算法进行编程实现,运行 換作后进入繁殖期,繁殖过程遵循优胜劣汰法则,即处丁食物 缺乏地区的细菌因为饥饿最终被淘汰。具体为:将细菌种群按 按境为 Windows7系统, Intel core2.20 GHz CPU,2 GB RAM。 通过不同规模算例的对比分析,骑证所提算法的求解性能。 照2.2节的个体评价规则进行排序,保留前半部分群体,保留 下来的细菌进行一次分裂增殖,从而又形成一个数日为NUM 3.1小规模算例 POP的完整细菌种群。在完成N次繁殖操作后,以一定的概 文献[2,9]分别采用遗传算法和蚁群算法求解了包含八 率∥将细菌个体驱散到觅食空间的江意位置。引人驱散操个任务的PC机拆卸案例(P8问题),该案例的具休参数述 作,可有效擗免搜索过程陷入局部最优。 参见文献1。上述文献在建模阶段增加了空闲时间目祘函 数以及操作方向改变次数月标函数f5,描述为 2.4算法流程 4=∑(C7- 基于 Pareto的多目标细菌觅食优化算法流程如下 )设定算法参数NUM_POP、CT、NS、P、UBad、UBm、N、 j=∑hk,Kk (14) Nn、N。初始化迭代次数LM=LMn=LM=0,生成初始种群 3268· 计算机应用研究 第33卷 其中:R4表示第个位置上操作方向的变动性;r2表示编号为四个指标与解3相同根据 Pareto占优的思想,解1攴配解3, PA的零件的操作方向代码。给出的四种最优分配方案如表1同理解2支配解4。因此文献L2,9所求得的最优解实际只有 所示。在进行MBFO算法小规模算例测试时,将算法参数设置两个。这是因为文献中的两种方法在进行多目标间题处理时 NUM_POP=10, NS=6, Pe=0. 1, URds=10,UBpy=8, N 把多目标冋题转换成了具有优先权值的单目标问题,因而求得 8,N=4,Na=2。求得了含有八个非劣解的Preo解集,如表的最优解仅保证了fJ2和三个指标的最优,而忽视了其他 所示 两个指标。而用MBFO算法求得的问题的 Pareto最优解集 表1文献L2,9中P8问题的解 屮不仅包含了文献[2,9]屮方法求得的两个最优解(表2屮的 序号任务分配方案12 解3和5),还给出了/3指标更小的解67和8,以及/5指标更 1[1,5,3,6,2,8,7,4]33 025 小的解和4。另外,不难发现解6在∫3指标上取得突破的同 2[1,5,3,2,6,8,7,4]33 19275 时,其f指标却大嗝增大,这是因为在多目标优化中,各个子 3[1,5,2,6,3.8,74]33 777 19265 6565 目标间往往存在博弈关系,一个子目标的改善可能引起其他子 4[1,5,2,3,6,8,7,4]33 19395 11 标性能的降低,同时满足所有目标的最优往往是不可能的。 表2MBFO求得的P8问题的 Pareto解集 3.2大规模算例 序号任务分配方案 4 f5 为验证所提MBFO算法求解大规模问题时的性能,对文 J1 1[1,3,2,5,6,8,7,4]37 19235 l1 献[10]中含有52个任务的高速电子套结机拆卸实例进行測 试。该文献在问题建模过程中考虑∫工作站的拆卸成本,引人 2[1,3,2,6,5,8,7,4]37 19025 平滑率的概念衡量作业负荷的均衡性,用闲置率衡量拆线的 3[1,5,3,2,6,8,7,4 192751 利用率。出于可比性的考虑,将上述三个日标函数引入木文算 3,5,2,6,8,7,4]841 1919551 法,关于目标函数以及套结机实例的其体描述参见文献[10]。 5[1,5,3,6,2,8,7,4]33 19025 lI 权衡搜索能力和收敛性能,经多次测算,将算法参数设置 6[1,3,6,5,2,8,7,4]117 18735 T NUM_POP=20, NS=8, Pd=0.1, UB d,=10, UB =10, N= n=4,Na=2。求得的Paet最优平衡方案如表3所示。 8[1,2,6,3,5,8,7,4]45 19015 l1 平衡方案的 Pareto最优前沿及与文献[10]中多目标ACO算法 分析表1中的数据可发现,解1中指标优于解3,其余的求解性能对比如图2所小。 表3MBFO求得的套结机实例 Pareto解集 序号 任务分配方案 F 1137,42,21,36,32,16,3]→[18,47,29,28,46,39,44,14,15,3,27,1l→[2,1,12,4,19]→[3,25,35,45,52,26→ 「49,43,23,38,51,40,34、22,50,48,41][17,30,7,24,8,9,13]10,6,5,20) 0.05790.959144.018 32,33,26,21,37→[4,28,29,36,3,31、14,18]→[25,16,39,15,1,12]→[27,35,42,19,47,46,11.45,49,51→[23 243,44,52,30,9]→2,40,38,17,50,41,48,34,2,7,248,13]→20,10,5,5 0.05790.9295142.698 3121,29,36,18,37,3,39,14]→[4.47.1131,45,42,23,46,3,43,52]→[26,28.15,32,16.25]→[30.44,38,49,27,2 1]→[51,12,40,35,9,41]→[17,50,19,48,34,22,24,8,7.,13,10]→[6,20,5 0.05790.8832141.132 421.3.4.3.25118.09.42,14.31,1.39.52.36,45,471-3.21.23.121-34,35.28,15,24,45,4,43.30→ [27,25,38,32,19,16,49,17]→9,51,40,41,8,50,48,2,7,13]→[10,5,20,6] 0.05790.9860164.010 37,42,21,36,32,6,33]→18,47,28,29,4,15,14,11,31,5 ,2]→[9,43,19,12,34 [35,23,38,45,30,25]·49,51,40,17,24,22,50,41,7,48,8,13][10,5,6,20 0.05790.9678144.150 6121,29,36,18,37,33→26,4,47,46,42,39,3,2,141]→4,32,16,30,1,28,31→[1,23,52,15,45,27,25,38,431→ 0.05790.9811 154.080 713221021.28,430308,3;5,1441,32712:0121-13.52.2.23.91-138.4,0.05790.971146.84 14,26,11,36,3,47]→2,46,3,31,1,45,52,27]→[1 8 43,23,19,49,51,40,41]_[34,35,50,2,7,24,48,8,38,17,13]→10,5,6,20 0.05790.9781 152.394 彐最大值 通过表3中数据及图2中算法性能对比可知,ⅥBFO算法 165 最小值 求出的拆卸线闲置率均为0.0579,开启的工作站数目为7 文献[10]中ACO算法求出的闲置率最高为0.1757,开启工作 145 站数目为8个;MBFO算法求出的平均平滑率为0.9573,高于 0.83 ACO算法求出的0.9232的平均平滑率,说明MBFO算法求得 0.98 MBFO ACO 算 的分配方案具有更好的负荷均衡性能;MBFO算法求出的平均 (a)平衡案的 Pareto最优前沿 b)平滑率对比 拆卸成本为148.583,而ACO算法求出的平均拆卸成本为 175 315,说明采用ⅥBFO算法求得的分配方案能够更好地节 0.16 ·最小值 165 ◆最小值约生产成本。综上所述,本文所提MWFO算法对所有三项指标 0.14 160 的求解性能均优于文献[I0]中的ACO算法 0.1 150 0.08 145 对上述不同规模算例的对比验算,验证了本文所提 0.06 135 算法的性能。求解过程能够不局限于某一或某几个目标的最 算法 算法 优化,兼顾多目标间的冲突,给出侧重点不同、分布范围较广的 (u)闲置率对比 )拆卸成本对 多组解,从而使得决策人员能够根据生产实际情况选择出最恰 图2 Parcto最优前沿及性能对比 当的实施方案 第11期 胡扬,等:多目标坼卸线平衡问题的 Pareto细菌觅食算法 3269 [6 Kalayci C B, Polat O, Gupta S M. A hybrid genetic algorithm for se- 4结束语 quencc-dependent disassembly line balancing problem_ J]. Annals of Operations Research, 2014, 242(2 ): 321-354 针对传统方法在求解多目标DBP时不能兼顾全局目标 7] Kalayci C B, Gupta S M. Artificial bee colony algorithm for solving 以及在求解大规模问题时易早熟等不足.本文提出了一种多目 sequence-dependent disassembly line balancing problem[J]. Expert 标细菌觅食优化算法。主要成果为:a)构建了基于 Pareto的 Systems with Applications, 2013, 40(18): 7231-7241 MBFO算法求解多目标DBP,拓展了解决间题的新途径;b)针[8- Kalayci C B, Gupta S M. A tabu search algorithm for balancing a se 对冋题的约束特点论述了可行解的构造策略,建立了基于a uence-dependent disassembly line [J]. Production Planning reto非劣点以及拥挤距离机制的个体评价规则,引人精英保留 Control,2014,25(2):149-160 策略提升收敛性能,通过三种換作的锨套运算结合全局信息共[9]M( Govern s m, Gupta S M. Ant colony optimization for disassembly 享策略求出分布均匀的 Pareto最优前湑;c)经不同规模问题测 equencing with multiple objectives[ J. Intemational Journal of Ad 试,验证了算法的有效性与优越性,能够为生产者提供多样化 vanced Manufacturing Technology, 2006, 30(5): 481-496 的决策空间,具有较强的应用前景。 [10]丁力平,谭建荣,冯毅雄,等.基于 Pareto蚁群算法的拆卸线平衡 参考文献: 多日标优化[打].计算机集成制造系统,2000,15(7):1406-1413. [11 Passino K M. Biomimicry of bacterial foraging for distributed optimi [1 Gungor A, Gupta S M. Disassembly line in product recovery[J]. In zation and control[ J]. IEEE Control Systems, 2002, 22(3): 52- ternational Journal of Production Research, 2002, 40(11): 2569 [12]易军,李太福.求解作业杰间调度的变邻域细菌觅食优化算法 [2 Mc Govern S M, Gupla S M. A balancing melhod and ge nel ic alg rithm for disassembly line balancing[ J. European Journal of Ope [J].机城工猩学报,2012,48(12):178-183 rational research,2007,179(3):692-708. [13 Atasagun Y, Kara Y. Bacterial foraging optimization algorithm for as [3 Bentaha M L, Battaia O, Dolgui A. Lagrangian relaxation for stocha sembly line balancing[ J]. Neural Computing and Applications tic disassembly line balancing problem[ J]. Procedia CIRP, 2014 2014,25(1):237-250 17:56-60 [14]崔逊学.多月标进化算法及其应用[M].北京:国防工业出版社 [4 Ozccylan E, Paksoy T, Bektas 'T. Modeling and optimizing the inte- grated problem of closed-loop supply chain network design and disa [15]陈雄兵,陈友玲,鲁香珍.基于NSGA-Ⅱ算法的可重构装璽线计划 sembly line balancing[ J. Transportation Research Part E:Lo 排序问题研究「J.计算机应用研究,2011,28(11):4138-4141 gistics and Transportation Review, 2014, 61: 142-164 [16 Saif U, Guan Zailin, Iil Weiqi, el al. Parelo hased artificial hee [5 Bentaha M L, Battaia O, Dolgui A. Disassembly line balancing and colony algorithm for multi objective single model assembly line balan sequencing under uncertainty [I]. Procedia CIRP, 2014, 15: 239 ing with uncertain task times[ J]. Computers Industrial Eng neering,2014,76:1-1 (上接第3264页)非光滑优化问题,因此极大地扩展了传统神经[4. Forti M, Tesi a. New conditions for global stability of neural networks 网络的应用范围。 with application to lincar and quadratic programming problems [J] 木文证明了所提出的神经网络存在全局解,而且随着时间 IEEE Trans on Circuits and System 1984 31(2): 182-185 变化,在可行域外的初始点运动轨迹进入可行域,并且最终停 [5 Wilson G. Quadratic programming analogs[J]. IEEE Trans on Cir- 留在可行域中。最后利用能量函数的思想证明了恻络最终收 cuits Systems, 1986, 33(9): 907 [6 Forti M, Nislri P, Quinearnpoix M. Generalized neural network for 斂到平復点,并且平衡点集与关键点集一致。此外,如果目标 nonsmooth nonlinear programming problems[J. IEEE Trans on Cir 两数是凸兩数,那么平衡点就是问题的最优解。 cuits and Systems, 2004, 51(93: 1741-175 [71 Xue Xiaoping Bian Wei. Subgradient-based neural networks for nons blems[ J. IEEE Trans on Circuits and System,2008,55(8):2378-2391 [8 Bian Wei, Xue Xiaoping. Subgradient-based neural networks for nons- 「J1.| EEE Trans on Ne 50010001500200025003000 Network,2009,20(6):1024-1038 运行次数 图5实验3的状态向量x(的运动轨迹 [9 Zhang Shengwei, Constantinides A G. Lagrange programming neural networks[ J_. IEEE Trans on Circuits and Systems, 1992, 39(7) 参考文献 441-452 [1] Tank D W, Hopfileld JJ. Simple ' optimization networks: an L 10 J Huang Yuancan, Yu Chang. Improved Lagrange nonlinear progran A/D converter, signal decision cireuit, Hnd a linear programming cir ming neural networks for inequality constraints[ C]//Proc of Interna lional JoinT Conference on Neural NeTworks. 2007 cuit J. IEEE Trans on Circuits and System, 1986, 33(5): 533- [I]黄远灿.一种新型的 Lagrange非线性规划神经网络[J].电子学 541. 报,2002,30(1):27-29 [2 Kennedy M P, Chua L O. Ncural networks for nonlincar programming [12]黄远灿. Lagrange神经网终的稳定性分析J].控制与决蕞,2005, [J. IEEE Trans on Circuits and System, 1988, 35(5): 554-562 20(5):545-548 [3] Chua l c, Lin guinean. Nonlinear programming without computation3」边伟,奏泗甜,莽小平.非光滑疣化及其变分分析LM.哈尔滨:哈 [J. IEEE Trans on Circuits and System, 1995, 42(7): 354-366 尔滨工业大学出版社,2014:59-6

...展开详情
试读 5P 论文研究-多目标拆卸线平衡问题的Pareto细菌觅食算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-多目标拆卸线平衡问题的Pareto细菌觅食算法.pdf 30积分/C币 立即下载
1/5
论文研究-多目标拆卸线平衡问题的Pareto细菌觅食算法.pdf第1页

试读结束, 可继续读1页

30积分/C币 立即下载 >