基于带变异算子粒子群优化算法的约束布局优化研究

计　　算　　机　　学　　报

CHIN ESE J OURNAL OF COMPU TERS

Vol.27No.7

J uly 2004

基于带变异算子粒子群优化算法的约束布局优化研究

李　宁

1),2)

　刘　飞1)　孙德宝

1)

1)(华中科技大学控制科学与工程系　武汉430070)

2)

(武汉理工大学计算机科学与技术学院　武汉430074)

收稿日期:2003204218;修改稿收到日期:2004204228.李　宁,男,1972年生,博士研究生,武汉理工大学讲师,主要研究方向为人工智能、演化计算、人工生命.E 2mail :zidong @tom.com.刘　飞,男,1979年生,硕士,主要研究方向为演化计算、计算机仿真.孙德宝,男,1941年生,教授,博士生导师,主要研究方向为人工智能、信号处理.

摘　要　该文研究二维带平衡及不干涉约束的圆集在圆容器内的布局优化问题(如卫星舱布局),属于NP 2Hard 问题,难于求解.文章提出了带变异算子的PSO 算法(PSO with Mutation Operator ),在算法搜索的后期引入变异算子,使算法摆脱后期易于陷入局部极优点的束缚,同时又保持前期搜索速度快的特性.将改进后的算法应用于约束布

局问题,建立了此类问题的粒子群算法,并进行了3个算例(其中一个为已知最优解的算例)的数值计算,验证了带变异算子PSO 算法在约束布局问题上的可行性和有效性.关键词　粒子群算法;变异算子;约束布局优化;圆集;全局优化中图法分类号TP391

A Study on the Particle Sw arm Optimization with Mutation Operator

Constrained Layout Optimization

L I Ning 1

),2)

　L IU Fei 1)　SUN De 2Bao 1

)

1)

(Depart ment of Cont rol Science &Engi neeri ng ,Huaz hong U niversity of Science &Technology ,W uhan 430070)

2)

(School of Com puter Science &Technology ,W uhan U niversity of Technology ,W uhan 430074)

Abstract 　Taking the layout problem of satellite cabins as background ,the authors studies the opti 2mal layout problem of circle group in a circular container with performance constraints of equilibrium ,which belong to NP 2hard problem.This paper extends the heuristic method called “Particle Swarm

Optimization ”

(PSO )to deal with the constrained layout optimization problem ,proposes the particle presentation for this problem and compares the PSO with G A.By adding the mutation operator to the PSO algorithm in the later phase of convergence ,the advanced algorithm can not only escape from the local minimum ’s basin of attraction of the later phase ,but also maintain the characteristic of fast speed in the early convergence phase.The experimental results indicate that the Mutation PSO is a more ef 2fective method for constrained optimal layout problem.

K eyw ords 　particle swarm optimization ;mutation operator ;constrained layout optimization ;circle group ;global optimization

1　引　言

布局问题属于NPH 问题,就是按一定的要求,

把一些物体最优地放置在一个空间内.布局可分为

二维布局和三维布局,它们一般要求待布物之间、待布物与容器之间不干涉,并尽量提高空间利用率,此类问题为无性能约束的布局问题.有一类问题除以上基本要求外,还需考虑其它的性能约束,如惯性、平衡性、稳定性等,我们称之为带性能约束布局问

题,简称约束布局问题,由于这类问题的解空间常为

非凸集,因此难于求解.目前较多的做法是应用启发式方法求其近似最优解,但结果均不太理想.

粒子群算法(Particle Swarm Optimization ,PSO )是一种新的进化计算技术,由K ennedy 和

Eberhart 提出[1],源于对鸟群捕食的行为研究.与遗传算法类似,PSO 是一种基于迭代的优化方法,系统初始化为一组随机解,通过迭代搜寻最优值,粒子在解空间追随最优的粒子进行搜索.PSO 有着个体数目少、计算简单、鲁棒性好等优点,在各类连续空间优化问题、神经网络训练、模糊系统控制、组合优化、机器人路径规划等领域中均取得了非常好的效果[2].本文将变异算子引入PSO 算法,应用于带性能约束的布局优化问题求解中,取得了很好的效果.

2　问题描述及数学模型

为了说明问题,下面给出一个以人造卫星舱布

局设计为背景的带约束的二维布局问题,可以简化为一个所谓转动圆桌平衡摆盘问题[3].如图1所示,在一个半径为R ,以角速度ω转动的圆桌上布置n 个圆盘(简称图元)X i ,i ∈I ={1,2,…,n},建立平面直角坐标系XO Y.设第i 个图元的形心为O i =(x i ,y i )

T

∈䦂W P M athA UA p 2,其半径和质量分别

为r i 和m i ,则X i =F (O i ,r i ),设各图元的质心与形心重合.要求这n 个图元应尽量趋向圆桌的中心,图元与桌面固定,并满足如下约束:(1)各图元之间不发生干涉;(2)图元不超出桌面;(3)布置后系统的静不平衡应小于某一允许值[δJ ].

图1　图元布局示意

以上约束使得该问题的解空间通常是非凸、非

连续的集合,其一般性数学模型如下:

求X i (i ∈I ),使其满足

min f (X i )=max

x 2i +y 2

i +r i

(1)

s.t .

①图元之间的不干涉条件:

f 1(X i )=r i +r j -(x i -x j )2+(y i -y j )2Φ0

　　　　　　i ≠j ;　i ,j ∈I

(2)

　　②图元与桌面外缘之间的不干涉条件:

f 2(X i )=

x 2i +y 2

i +r i -R Φ0,i ∈I (3)

　　③静不平衡条件:

f 3(X i )=

∑

n

i =1

m i x i

2

+

∑

n

i =1

m i y i

2

-[δJ ]Φ0

(4)

3　带变异算子的粒子群算法

3.1　基本粒子群算法

粒子群算法由K ennedy 和Eberhart 于1995年

提出[1],该算法模拟鸟集群飞行觅食的行为,通过鸟之间的集体协作使群体达到目的.

在PSO 系统中,每个备选解被称为一个“粒子”(particle ),多个粒子共存、合作寻优(近似鸟群寻找食物),每个粒子根据它自身的“经验”和相邻粒子群的最佳“经验”在问题空间中向更好的位置“飞行”,搜索最优解.

PSO 算法的数学表示如下[2]:

设搜索空间为D 维,总粒子数为n.第i 个粒子位置表示为向量X i =(x i 1,x i 2,…,x i D );第i 个粒子迄今为止搜索到的最优位置为P i =(p i 1,p i 2,…,p i D ),整个粒子群迄今为止搜索到的最优位置为P g =

(p g 1,p g 2,…,p g D ),第i 个粒子的位置变化率(速

度)为向量V i =(v i 1,v i 2,…,v i D ).每个粒子的速

度和位置按如下公式进行变化(“

飞行”):v i d (t +1)=w ×v i d (t )+c 1×rand ()×

[p i d (t )-x i d (t )]+c 2×rand ()×[p g d (t )-x i d (t )](5)

x i d (t +1)=x i d (t )+v i d (t +1)

　　1Φi Φn ,1Φd ΦD (6)

其中,c 1,c 2为正常数,称为加速因子;rand ()为[0,1]之间的随机数;w 称惯性因子,w 较大适于对解

空间进行大范围探查(exploration ),w 较小适于进

行小范围开挖(exploitation ).第d (1Φd ΦD )维的位置变化范围为[-X M A X d ,X M A X d ],速度变化范围为[-V M A X d ,V M A X d ](即在迭代中若v i d 和x i d 超出了边界值,将之设为边界值).

粒子群初始位置和速度随机产生,然后按公式(5),(6)进行迭代,直至找到满意的解.目前,常用的

8

98计　　算　　机　　学　　报2004年

Clerc[5]和van den Bergh[6]对于PSO的收敛性和稳定性作了初步分析,并给出了一些保证PSO算法收敛的参数条件.本文实验中PSO算法均采用文献[5]所推荐的参数,加速因子c1=c2=1.49,惯性因子w=0.729.

3.2　带变异算子的粒子群算法

分析式(5)不难发现,如果邻居子群的历史最优粒子位置P l在较长时间内未发生变化,则粒子群很接近P l时,其速度更新将主要由w×v i d(t)来决定,w<1时速度将越来越小,因此粒子群表现出强烈的“趋同性”,当粒子数较少时,表现在优化性能上就是收敛速度快,但易陷入局部极值点.文献[6]证明了基本PSO是无法保证收敛到局部极值的,并提出了保证收敛到局部极值的GCPSO算法,但其更易于陷入局部极值,在对多峰函数的测试中表现不佳.当所求解问题的约束使得解空间为非凸集合时,这一缺点尤其明显.同时,文献[6]中提出了Multi2 start PSO,每迭代若干次后,保留粒子群的历史最优位置,粒子全部重新初始化,以提高粒子的多样性,扩大搜索空间,摆脱局部最优点的吸引,保证收敛到全局最优,但粒子群的全部初始化将完全破坏当前粒子的结构,使得收敛速度大大减缓,搜索精度也大大降低.

考虑到这一点,本文引入变异算子,与遗传算法类似,在子群的历史最优粒子位置P l连续无变化或变化极小时,若粒子群出现较严重聚集情况,则保留历史最优粒子位置P l,将粒子中少部分维重新随机初始化,以此来增强全局搜索能力,摆脱局部极值点的吸引,同时又不降低收敛速度和搜索精度.定义带变异算子的粒子群算法如下:

If L ogjamS tep>=M axS tep

If M ax Rad对子群内所有粒子的所有维,按几率ρ进行重新随

机初始化位置和速度;

L ogjamS tep=0;

Else

按式(5),(6)更新粒子位置和速度;

End

Else

按式(5),(6)更新粒子位置和速度;

End

其中,L ogjam S tep为子群历史最优粒子位置P l连续不变化或变化极小的迭代次数,M axS tep为连续不变化次数的阈值;M ax Rad为子群半径,即群内所有粒子到历史最佳位置P l的欧几里得空间距离的最大值,定义如下

M ax Rad=max

i=1,2,…,n1∑

D

d=1

(p l d-x i d)2

　　　n1为邻居群粒子数(7) BorderRad为判断群内粒子聚集程度的群半径阈值.

变异率ρ、连续不变化次数阈值M axS tep和半径阈值BorderRad的选择将对算法的性能产生很大的影响,过大的ρ和BorderRad以及过小的M axS tep都会影响算法的收敛速度和搜索精度,而如果ρ和Bor2 derRad过小或M axS tep过大则都不利于实现提高全局搜索能力的目的.

根据作者对Rastrigrin,Rosenbrock,Griewank 等高维、多峰测试函数的实验经验,变异率ρ采用1/(2D)～2/D(D为问题空间的维数)左右的值,能获得很好的效果,即平均一个粒子只有0.5～2维数据发生变异,本文实验中均采用2/D;过高的变异率将使得搜索时间大大增加,Multi2start PSO可以看作变异率ρ=100%的特例.连续不变化次数阈值M axS tep取5～20之间时,通常能取得较高搜索成功率和较短的搜索时间,本文实验均采用10.而聚集距离阈值BorderRad则与问题空间中局部极小值的分布密度及均匀否有关,本文实验中根据经验选取

BorderRad=∑

D

d=1

(X M ax d)21000.

4　算法实现过程

为计算方便,本文采用极坐标系,即对粒子进行极坐标系编码.设有n个待布圆,则搜索空间为2n 维.每个圆的位置用其圆心的极坐标表示为(l j,

θ

j

),l j∈[-(R-r j),(R-r j)],θj∈[

-π/2,π/2] (j为待布圆的下标).适值函数如下:

Φ(X

i

)=F(X i)+∑

3

i=1

λ

i

f i(X i)u i(f i)(8)

998

7期李　宁等:基于带变异算子粒子群优化算法的约束布局优化研究

u i (f i )=

0,f i (X i )Φ01,

f i (X i )>0

,　i ∈I ,

其中,λi (λ1=1,λ2=1

,λ3=0.01)是惩罚因子.适应

度函数值越小,所得解越优.算法实现流程如图2所示.

图2　带变异算子PSO 算法流程图

5　算　例

例1.　引用文献[7]的算例.该文采用人机交

互的遗传算法进行布局优化.图面圆容器半径R =50mm ,圆形待布物(图元)为7个.设静不平衡量J 的允许值为[δJ =3.4g ・mm ],待布物的其它数据和布局结果如表1(a )所示(文献[7]群体规模M =40,本文带变异算子PSO 粒子数M =60).

　　对该算例进行了40次运算,结果如表1(c )所示,每次均满足约束条件,平均外包络圆半径为32149mm .

表1　例1的计算结果

(a )例1数据及布局结果

序

号图元r (mm )m (g )

文献[7]布局结果

x (mm )

y (mm )

本文布局结果

x (mm )

y (mm )

110.0100.00-12.88317.02014.36716.453211.0121.008.84719.773-18.521-9.560312.0144.0020.6620.0002.113-19.730411.5132.00-8.379-19.43019.874-4.34059.590.25-1.7430.503-19.27111.24168.572.2512.368-18.9-3.94022.1577

10.5

110.25

-21.639

-1.799

-0.946

2.824

(b )例1布局结果性能比较

计算方法外包络圆半径(mm )

静不平衡(g ・mm )

干涉量

计算时间

(s )

文献[3]方法32.8370.102001735文献[7]方法32.6620.029001002带变异算子

PSO

31.985

0.0182

1002

(c )例1运算40次结果分布情况

外包络圆半径(mm )

次数

外包络圆半径(mm )

次数

Φ32.3

10(32.9,33.1]2(32.3,32.5)16(33.1,33.3]

2(32.5,32.7]5>33.3

3

(32.7,32.9]

2

注.　

为便于比较,计算时间均折算到主频166M 的微机(下同),带变异算子PSO 方法计算到外包络圆半径为32.66时计算时间为760s ,此时的静不平衡量为0.033.

例1结果中,无论是在外包络圆半径、静不平衡还是计算时间上,本文PSO 均优于文献[7]提出的人机交互的遗传算法.

图3　例1的几何布局

例2.　引用文献[8]的算例.该文采用十进制

编码的控制参数自适应遗传算法进行布局优化.图面圆容器半径R =880mm ,圆形待布物为40个图元.设静不平衡量J 的允许值为[δJ =20g ・

mm ],待布物的其它数据和布局结果如表2(a )所示(文献[8]群体规模M =60,本文带变异算子PSO 粒子数M =100).

09计　　算　　机　　学　　报2004年

序

号r(mm)m(kg)带变异算子PSO布局结果x(mm)y(mm)

110611192.9710 211212-69.9240 3913.034-478.285 410511-291.74821.066 5938343.517-351.055 610310-251.143674.025 *******.268-252.9 38-619.634-421.032 911713725.0620 10816127.487175.174 117358.251-104.181 ********.612-206.946 1310911-151.494-350.475 1410410-486.096278.028 *******-406.944-378.282 1611012-531.39627.583 1711412-281.428-570.129 187535.186-82.365 19826349.187-668.540 2012014494.958-527.668 2110811-696.916236.466 22867-43.153196.294 23938-143.066-725.316 2410010-433.688-159.158 2510210-741.8580.000 2610611292.820431.997 2711112-540.511495.023 2810711154.296-671.681 2910911-317.971463.365 3091841.295-271.016 3111112103.622538.523 32918215.467-213.844 3310110540.248306.466 3491858.125341.687 3510811-235.120227.217 3611412510.413520.918 3711813-29.219725.331 38857300.625240.313 39877234.066-494.031 409411.043119.080

(b)例2布局结果性能比较

计算方法

外包络圆

半径(mm)

静不平衡

(g・mm)

干涉量

计算时间

(s)文献[7]方法870.3310.00600001358

文献[8]方法874.83011.39500001656

带变异算子PSO843.9400.003502523注.　本文PSO方法计算到外包络圆半径为870时,计算时间为1253s,此时静不平衡量为0.

00422.

图4　例2的几何布局

例3.　为了进一步验证带变异算子PSO方法的有效性,本文引用文献[8]的已知最优解的算例.在半径为R=125mm的大圆(容器)中,布置5个小的待布物图元.待布物数据和布局结果如表3所示(文献[8]群体规模M=60,本文带变异算子PSO 粒子数M=60).

由图5可见,本文PSO布局结果几乎可无限接近最优结果,这进一步说明了PSO的有效性.

例3约束布局问题的可行解空间是一个典型的非凸、非连续空间,所对应全局最优解和常见局部最优解分别如图6中情况1和情况2所示.分别采用基本Local PSO、Multi2Start PSO和带变异算子的PSO对该问题进行优化,最大迭代次数为1000,粒子数为60,搜索结束条件为外包络圆半径小于121且图元之间无干涉或迭代次数达到1000三种算法各做50次实验,对比结果如表3(c)所示.

表3　例3的计算结果(a)例3数据及布局结果

〗序号r(mm)m(g)

最优布局(已知)

x(mm)y(mm)

文献[8]遗传算法

x(mm)y(mm)

带变异算子PSO

x(mm)y(mm)

120.7120.710.000.000-0.5858-1.0580.00000.0000 250.0050.0070.710.0065.97926.1790.000070.7107 350.0050.000.0070.71-26.25268.06170.7107-0.0000 450.0050.000.00-70.7127.1-66.40.0000-70.7107 550.0050.00-70.710.00-66.685-26.886-70.71070.0000

(b)例3布局结果性能比较

计算方法

外包络圆

半径(mm)

静不平衡

(g・mm)

干涉量

(mm)

计算时间

(s)

文献[8]方法123.2001.26500008文献[9]方法121.4340.0010000306带变异算子PSO120.7110.0027120287

(c)三种PSO对比实验结果

计算方法

达到全局最优

成功率(%)

搜索成功的

平均时间(s)基本Local PSO54273 Multi2Start PSO62728

带变异算子PSO72296

109

7期李　宁等:基于带变异算子粒子群优化算法的约束布局优化研究

图5　例3

的几何布局

图6　例3优化的两类结果

　　结果表明对该布局优化问题而言,在1000次迭

代内,带变异算子PSO 达到全局最优的成功率比Local PSO 和Multi 2Start PSO 都高出许多;成功搜索全局最优的平均时间比Local PSO 略长,但比Multi Start PSO 短许多.

从以上3个算例可以看出:在外包络圆半径、满足静不平衡约束、搜索时间和平均搜索结果等方面,利用PSO 所得到的结果都是较令人满意的.特别是对于复杂的布局问题(40个圆的算例),PSO 可大大减小外包络圆半径.而改进后的带变异算子PSO 方法,则在保持基本PSO 搜索快速性和搜索精度的同时进一步提高了搜索成功率,可见带变异算子PSO 算法为求解工程复杂布局问题提供了一种有效的方法和途径.

6　结　论

分析PSO 方法及本文提出的带变异算子PSO 方法,可以看出它与G A 等其他演化算法的最大不同在于:

(1)迭代运算中只涉及到初等运算,且运算量非常少;

(2)每个个体(粒子)能直接获取子群历史经验和个体历史经验,比在其他方法中使用精英集(elitism )的方法更有效;

(3)整个粒子群被分为若干子群,且子群之间有一定重叠,子群之间的相互联系使收敛于局部最优解的几率大大减少,搜索成功率因此得以提高.

(4)本文提出带变异算子的PSO 算法,通过对

历史最优粒子位置P l 的变化过程和粒子群的聚集程度进行分析,来判断粒子群是否已收敛于某个局

部最优的点.当粒子群已收敛于某局部最优点时,保留历史最优粒子位置P l ,重新初始化少部分粒子,以摆脱局部最优点的束缚,既能保持粒子群原有基本

结构的同时又能扩大搜索范围,在提高多样性的同时保证搜索精度.若在不计搜索时间的情况下,该方法和Multi 2Start PSO 一样能保证收敛到全局最优.

(5)由于带变异算子的PSO 先对判断P l 是否

连续不变化进行判断,因此迭代运算过程中计算粒子群聚集程度的运算出现次数很少,对运算量的增加很少.相反,由于能及时判断是否已收敛于局部最优点,并迅速摆脱它的束缚,在提高搜索成功率的同时,搜索速度也有提高.实验表明该改进算法是非常有效的,尤其是对粒子数比较少的情况.

正因为如此,本文将带变异算子PSO 方法应用于有约束布局问题求解中,取得了很好的效果,有着运算速度快、鲁棒性好、所获得的解质量高等诸多优点,对解决工程实践中出现的布局问题而言是一种非常有参考意义的方法.

本文所提出的带变异算子PSO 中,群半径阈值BorderRad 的取值比较困难些,依赖于问题空间中局部最优点的分布情况,本文实验中根据经验进行选取,而且在搜索过程中固定不变.对于问题空间中局部最优点分布均匀的情况效果很好,而对于局部最优分布不均匀的情况则相对差些.寻找一种合适的自适应方法在寻优过程中对其进行调整,是对算法做进一步改进的工作.

参

考文献

1

Kennedy J.,Eberhart R.C..Particle swarm optimization.In :Proceedings of IEEE International Conference on Neural Networks ,Perth Australia ,1995,1942～1948

2Eberhart R.C.,Shi Y..Particle swarm optimization :Develop 2

2

09计　　算　　机　　学　　报2004年

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

ments ,applications and resources.In :Proceedings of the Congress on Evolutionary Computation 2001,2001,81～863

Teng Hong 2Fei ,Sun Shou 2Lin ,G e Wen 2Hai ,Zhong Wan 2Xie.Layout optimization for the dishes installed on a rotating table.Sci 2ence in China (Series A ),1994,37(10):1272～12804

Kennedy J..Small worlds and mega 2minds :Effects of neighbor 2hood topology on particle swarm performance.In :Proceedings of the Congress on Evolutionary Computation ,Washington DC ,USA ,1999,1931～19385

Clerc M.,Kennedy J..The particle swarm ———Explosion ,stabili 2ty ,and convergence in a multidimensional complex space.IEEE Transactions on Evolutionary Computer ,2002,6(1):58～736

van den Bergh F..An analysis of particle swarm optimizers[Ph.D.dissertation ].Department of Computer Science ,University of Pre 2toria ,South Africa ,20027

Qian Zhi 2Qin ,Teng Hong 2Fei ,Sun Zhi 2Guo.Human 2computer in 2

teractive genetic algorithm and its application to constrained layout optimization.Chinese Journal of Computers ,2001,24(5):553～559(in Chinese )

(钱志勤,滕弘飞,孙治国.人机交互的遗传算法及其在约束布

局优化中的应用.计算机学报,2001,24(5):553～559)

8

Tang Fei ,Teng Hong 2Fei.A modified genetic algorithm and its ap 2plication to layout optimization.Journal of Software ,1999,10(10):1096～1102(in Chinese )

(唐　飞,滕弘飞.一种改进的遗传算法及其在布局优化中的应

用.软件学报,1999,10(10):1096～1102)

9Yu Yang ,Cha Jian 2Zhong ,Tang Xiao 2J un.Learning based GA and application in packing.Chinese Journal of Computers ,2001,24(12):1242～1249(in Chinese )

(于　洋,查建中,唐晓君.基于学习的遗传算法及其在布局中

的应用.计算机学报,2001,24(12):1242～1249

)

L I Ning ,born in 1972,Ph.D.can 2didate ,lecturer.His research interests in 2clude artificial intelligence ,evolutionary computation and artificial life.

L IU Fei ,born in 1979,M.S.His research interests in 2clude evolutionary computation and computer simulation.

SUN De 2B ao ,born in 1941,professor ,Ph.D.supervisor.His research interests include artificial intelligence ,signal pro 2cessing.

B ackground

　　The project ,“Computer 2Aided Optimized Collocating Sys 2

tem of Deck ’s Devices ”,in order to improve the capability of overall scheme ’s design relevant to shipping ,is intended to help designers with an optimized collocation of deck ’s devices ,result 2ing in maximal efficiency of devices pertinent to deck.Therein 2to ,the optimized layout of devices on deck ,considering many optimal variables and complex constrained conditions involved ,is a two 2dimensions constrained layout optimization problem as well as a vital one in this project.By way of advancing the Par 2

ticle Swarm Optimization with mutation operator ,the authors settle the planar constrained layout optimization problem prefer 2ably ,enabling the system to carry through the layout design of deck in a more effective and more efficient way.Moreover ,when it faces many problems including the formation control of multi 2robots ,vehicle routing problem ,the wavelet neural net 2work training and so forth ,this algorithm is considered to be a good one for its outstanding effects.

3

097期李　宁等:基于带变异算子粒子群优化算法的约束布局优化研究