第
20
卷第
1
期
Vo
l.
20
No.1
控制与决策
2005
年
1
月
]an.
2005
Control
and
Decision
文章编号:
1001-0920(2005)01-0036-05
基于粒子群优化算法的约束布局优化
周驰,高亮,高海兵
(华中科技大学工业工程系,湖北武汉
43007
4)
摘
要
z
布局优化是
NP
难问题,也是复杂的非线性约束优化问题.针对这个问题.将新的基于粒子群优化的方法应
用于布局参数的优化,提出了适合粒子群优化的约束处理,并通过与直接搜索算法的混合.加强了算法在局部区域
的搜索能力.通过实例将该算法与乘子法以及基于遗传算法的布局优化方法进行了比较.仿真结果表明,该算法可以
提高布局优化问题解的质量,同时降低计算费用.
关键词:粒子群优化;布局优化』约束处理;局部搜索
中图分类号:
TP391;
TP18
文献标
t
只码
A
Parti
cI
e
swarm
optimization based
algorithm
for
constrained
layout
optimization
ZHOU
Chi ,
GAO
Liang
,
GAO
Hai-bing
(De
partment
of
1ndustrial
Engineering
,
Huazhong
University
of
Sc
ience
and
Technology
,
Wuhan
430074 ,
China.
Correspondent:
ZHOU
Chi,
E-mail:
cutecheng@163.com)
Abstract:
Layout
optimization
is
an
NP-hard
problem.
It
also
belongs
to
complex
nonlin~ar
constrained
optimization
problern.
1n view
of
this
problern
, a
new
rnethodology
based
on
particle
swarm
optimization
(PSO)
is
developed
to
optirnize
layout
parameters.
A
constraint
handling
strategy
suit
for
PSO
is
proposed.
Furtherrnore
,
improvernent
is
made
by
usÎng
direct
search
to
intensify
local
search
ability
of
PSO
algorithrn.
SimulatÎon
results
show
that
the
proposed
algorithm
improves
the
quality
of
the
solution
while
lowering
the
computational
cost.
Key
words:
particle
swarm
optimization;
layout
optimization;
constraints
handling;
local
search
1
~,
去一口
布局优化是经典的
NP
难问题.机械设计与制
造、工业工程、电子工程等领域的许多实际问题(如
机构设计、生产车间设备布局、集成电路设计等)可
转化为布局优化问题求解.因此,针对布局优化问题
的研究具有较好的应用前景.考虑实际应用,布局优
化问题往往包含多种实际约束,一般建模为高维、多
约束的复杂非线性优化问题.传统的优化算法(如线
性规划、二次规划、动态规划等〉仅适用于特定问题
的求解,且容易陷入局部最优.进化算法是常用的全
局优化算法,适用于各种复杂问题(包括约束优化问
题〉的求解.但是,进化算法复杂的进化操作(如选
择、复制、交叉、变异〉使其计算费用随问题的规模以
及复杂程度呈指数级增长.而且,由于其缺乏有效的
局部区域搜索机制,算法搜索后期容易出现收敛停
滞现象[1]
本文提出了基于粒子群优化
CPSO)
的约束布局
优化算法,结出了针对
PsO
算法的约束处理机制,
并通过与局部搜索算法(直接搜索〉的混合来提高算
法在局部区域精细搜索的能力.通过实例将该算法
与乘子法以及遗传算法进行了分析比较.仿真结果
表明,该算法在加速收敛的同时可提高解的精度.
2
约束布局优化问题的数学建模
以待布局物体的形心坐标作为待优化的参数,
收稿日期:
2004-02-15;
修回日期
2004-05-24.
基金项目
z
国家自然科学基金项目
(50305008).
作者简介:周驰
0981
一)
,男.湖北枣阳人.硕士生.从事群体智能、智能制造等研究
z
高亮
0974
一)
,男,山东临清
人,副教授,博士,从事运筹学与优化、需求链管理等研究.