设备布局离散优化问题的粒子群算法研究

生产物流

第23卷第12期2006年12月

机　械

　设　计

JOURNALOFMACHINEDESIGNVol.23　No.12

Dec.　2006

设备布局离散优化问题的粒子群算法研究

曾议,竺长安,沈连婠,齐继阳

(中国科技大学精密机械与精密仪器系,安徽合肥　230027)

3

摘要:设备布局设计是制造系统设计的重要组成部分,设备布局是否合理对整个制造系统的总体功效起着非常重要

的影响。粒子群优化算法(PSO)是一种新的群智能优化算法,常用于求解连续空间极值问题,近来正逐渐进入组合优化领域。利用多维实数编码及映射方法将连续PSO算法应用于求解设备环形布局问题,为此类离散优化问题的求解提供了一种新的思路。利用GA中的杂交策略扩展PSO算法,提高了PSO算法性能。通过实例计算和结果比较,说明了该算法能有效地求得设备环形布局问题的优化解,是一种行之有效地算法,有很好的实用价值。

关键词:单向环形设备布局;离散优化;改进粒子群优化算法中图分类号:TH18;TP301　　文献标识码:A　　文章编号:1001-2354(2006)12-0004-03　　设备布局设计在国内一直是被忽视的一个领域,事实上,

设备布局设计是制造系统设计的重要组成部分,设备布局是否合理对整个制造系统的总体功效起着非常重要的影响。Tompkins和White指出因设备布局不合理所产生的运行费用占制造系统整体运行费用的20%～50%,使这一费用减少10%～30%;理的效率,,[1],,;优良,缩小制造系统所占用的空间,减少制造系统建设的费用。反之,若设备布局设计不合理,将会导致过量的中间储存,物料流动的阻碍,生产时间的延长和生产效率的降低。因此,探讨研究制造系统的设备布局具有重要的理论意义和应用价值。

设备布局根据物流设备的不同,可以分为线性单行布局、线性多行布局、U型布局和环型布局[2]。无论哪种布局形式,确定设备的具体位置则是设备布局设计的关键所在。由于设备布局问题具有非线性、NP-Hard的特性,其解空间存在“组合爆炸”现象,适合采用SA(模拟退火)、GA(遗传算法)、ACA(蚁群算法)等启发式算法[3～7]。文中尝试使用一种新的方法求解环型布局的离散优化问题,设计了一种基于粒子群优化算法的离散优化方法,并通过对子群划分的改进和增加子群交配策略提高算法寻优能力。实验结果表明,此算法能快速有效地求解该问题,效果令人满意。

应度函数值,;每个粒子还有一个速度(evolutionary

)。随机初始化一定

,然后通过迭代找到最优解。在每一次,粒子通过跟踪两个“极值”来更新自己的速度和位置。一个是粒子本身所找到的个体最优解pBest,一个是整个种群目前找到的全局最优解gBest。计算公式如下:

d

vt+vtd[]+c1 rand1() (pbest-xtd[])+1[]=ω

c2 rand2() (gbest-xtd[])

dvt+1[

(1)(2)(3)(4)

]=

ddd

vmax[]　　　vt+1[]>vmaxddd-vmax[]　　vt+1[]<-vmax

ddd

xt+vt+1[]=xt[]+λ1[]dxt+1[

d

xmax[]d-xmax[]

dd

xt+1[]>xmaxddxt+1[]<-xmax

]=

设目标搜索空间为一N维空间,则d=1,2,…,N;v[]是

d

粒子的速度,x[]是粒子的位置。常数vmax是粒子每一维的最大速度,决定粒子在一个循环中最大的移动距离,由用户设定。粒

dd

子的位置变化范围被限定为[-xmax,xmax]。rand1()和rand2()

是两个独立的介于[0,1]之间的随机数。学习因子c1,c2是非负

λ为约常数。非负数ω为惯性因子,随迭代次数增加逐渐减小。束因子,调节λ可控制算法收敛速度。参照Clerc等的研究,取

dd[8]

c1=c2=2.05,λ=0.729,vmax=xmax。算法可用伪代码表示如下:

For每个粒子

1　粒子群优化算法

粒子群优化算法(particleswarmoptimization,PSO)最早

由Kennedy和Eberhart在1995年提出。算法的基本思想源于对人工生命(artificiallife)的研究,模拟鸟类觅食时群落与环境

(swarmintelligence)以及个体之间的互动行为,属于“群智能”

算法的一种(另一种为蚁群算法)。将每个优化问题的解比作

(particle)。所有粒子都有一搜索空间中的一只鸟,称为“粒子”

个适应值(fitnessvalue),即粒子在解空间的位置坐标对应的适

3收稿日期:2006-01-25;修订日期:2006-07-21

随机生成粒子位置;初始化速度和pBest;

End

初始化gBest;

Do

For每个粒子

　计算其适应度函数值;

　If(适应度值优于粒子历史最佳值)　Begin

基金项目:安徽省自然科学基金(03044106)

作者简介:曾议(1978-),男,重庆人,中国科学技术大学精密机械与精密仪器系博士研究生,研究方向为制造业信息化、CIMS。

生产物流

2006年12月

　　pBest=当前粒子位置;

曾议,等:设备布局离散优化问题的粒子群算法研究

5

现象。针对这一弱点,受GA的启发,将粒子群合理划分为若干子群,各子群之间通过相互交配进行信息交流,适当加强解的多样性,扩大搜索范围,以避免陷入局部最优。建立一个进化池,根据设定的抽取比例Pcrossover选取任意两个子群中一定数量的非最优粒子作为双亲粒子进入进化池两两杂交,产生同样数目的新粒子。这样既保护了子群中的精英,又扩展了进化搜索的范围。杂交算子如下:

Xchild1=αXparent1+βXparent2Xchild2=αXparent2+βXparent1

　　记录其适应度值为粒子历史最佳值;　End

End

计算当前粒子群中的最优粒子;

If(当前最优粒子优于群历史最优粒子)Begin

　　　gBest=当前最优粒子位置;

记录其适应度值为群历史最佳值;

End

For每个粒子

(5)(6)(7)(8)

按式(1),(2)更新粒子速度;按式(3)更新粒子位置;

End

While(小于最大迭代次数且解的质量未满足要求)

Vchild1=αVparent1+βVparent2Vchild2=αVparent2+βVparent1

其中:α,β都是l维实数向量,且α+β=1。它们有两种取值方式:(1)由用户设定,为简化算法,可令α,β所有分量相等且为常数。(2)α,β等于l,由算法随机生成。()2　设备布局问题的PSO算法

2.1　粒子的多维实数编码及映射

PSO是一种鲁棒性强、制造系统布局设计需要考虑多种因素,既包括系统运行费用最小、在制品在系统中停留时间最短等定量要求,又包括布局的美观性、操作的舒适性、生产的安全性等定性要求,它是一个多目标优化问题。一般情况下分为两个阶段:第一个阶段主要考虑定量要求,解决设备最优布局序列问题,该阶段主要通过各种算法加以解决;第二阶段主要考虑定性问题,虚拟现实技术能够很好地解决这一问题。

3.1　问题描述

化算法,化问题中的应用还不多。的PSO。文献[9]使用改进的连续空间PSO题,但制造系统的环型设备布局问题属于离散组合优化范畴,连续PSO算法无法直接应用。因此,设计了一种粒子的多维实数编码方法,实现从粒子到设备布局形式的映射,使PSO算法成功应用到离散的设备布局问题求解中。

对有k种零件、l台设备的单向环型布局问题,令粒子对应的位置向量为X=(x1,x2,…xi…,xl),即一个l维向量。各维坐标分量xi皆为实数,且xi∈[0,xmax](xmax一般为l的整数倍),其大小顺序即对应设备的排列顺序。例如,k=3,l=5(3种零件,5台设备),设某粒子对应的X为:

零件编号

X

i

安徽某军工企业为完成某项工程,组建了柔性加工工段,该工段需要加工10种零件,根 …… 此处隐藏：8596字，全部文档内容请下载后查看。喜欢就下载吧 ……