一种改进的模拟退火粒子群算法在有约束函数
优化问题中的应用
司呈勇1, 2，杨东升1, 3，田红军1, 2，汪镭1, 2，吴启迪1, 2
(1. 同济大学 电子与信息工程学院，上海，201804；
2. 同济大学 嵌入式系统与服务计算教育部重点实验室，上海，200092；
3. 上海经济和信息化委员会，上海，200040)
摘要：针对有约束函数优化不可行解的处理问题，提出一种改进的基于模拟退火思想的约束处理技术，并结合改进粒子群算法进行了具体的实例验证。仿真结果表明：所提方法具有较好的可行性。
关键词：模拟退火；粒子群算法；约束优化；惩罚函数
中图分类号：TP18 文献标志码：A 文章编号：1672-7207(2011)S1-0175-05
An improved PSO algorithm with simulated annealing for constrained function optimization
SI Cheng-yong1, 2, YANG Dong-sheng1, 3, TIAN Hong-jun1, 2, WANG Lei1, 2, WU Qi-di1, 2
(1. College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China;
2. Key Laboratory of Embedded System and Service Computing, Ministry of Education,
Tongji University, Shanghai 200092, China;
3. Shanghai Economic and Information Committee, Shanghai 200040, China)
Abstract: To solve the problem of infeasible solutions in the constrained function optimization, a constraint-handling technique based on simulated annealing is proposed. The improved particle swarm optimization is also used to verify the effectiveness of this technique. The experimental results show that the proposed algorithm is suitable for solving such problems.
Key words: simulated annealing; particle swarm optimization; constrained optimization; penalty function
约束优化问题(Constrained optimization problems，COPs)是一类广泛存在于实际工程中又较难求解的问题，因而对其研究具有重要的理论和实际意义。群体智能(Swarm intelligence)算法是近十几年发展起来的仿生模拟进化的新型算法，与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系[1-3]。在进化过程中，它不需要所求问题的任何信息，而仅需要目标函数的信息，不受搜索空间是否连续或可微的限制就可找到最优解。因此，群智能算法被广泛应用于组合优化、自动控制、管理科学、规划设计、人工生命以及模式识别和社会科学等多个领域[4-6]。粒子群算 法[7](Particle swarm optimization，PSO)是一种基于群体智能理论(Swarm intelligence)的全局优化方法，由Kennedy等受鸟群觅食行为的启发于1995年提出的[8]。其核心思想就是群体中个体之间的信息共享能提供进化的优势。粒子群算法以其收敛速度快和设置参数少的特征，在最近十几年内得到了快速发展。但由于粒子群自身的局限性，其在有约束函数优化中的应用一直受到限制。目前，对于进化算法性能的评价也常常针对一些无约束的benchmark函数[9]。本文作者在前人研究的基础上，尝试对粒子群算法进行改进，通过对模拟退火参数根据解的可行性进行实时变化。
1 约束处理技术
1.1 约束优化问题描述
一般地，一个带约束的优化问题(Constrained optimization problems)可以描述为[10]：
遵循的约束为
gj(x)≤0; j=1, …, l (1)
hj(x)=0; j=l+1, …, p (2)
其中：
，为决策变量；
为决策空间或者搜索空间。一般，S为Rn中的n维长方体：li≤xi≤ui, i=1, …, n；f(x)为目标函数，gj(x)≤0为第j个不等式约束条件；hj(x)=0为第j个等式约束条件；l表示不等式约束条件的个数，p和l表示等式约束条件的个数。
1.2 约束处理
在采用进化算法解决有约束函数优化问题方面，人们已经做了很多研究[11-13]。其中研究的关键是对不可行解的处理以及可行个体与不可行个体之间的比较。因为进化算法本身缺乏明确的约束处理机制，是一种无约束的搜索技术，在处理有约束的函数优化问题时，必须结合一定的约束处理技术，由此得到较理想的结果。
利用(外部)罚函数降低不可行解的质量是处理约束优化问题的主要方法之一[10]。该方法通过修改评估函数将约束问题变成无约束问题，即
(3)
penalty(x)为外部惩罚函数，当没有违背约束的情况发生时，penalty(x)为0，否则为正数(假定目标是求最小值)；F为可行区域。
一般来说，基于进化算法的约束处理技术将等式约束条件转换为如下不等式约束条件来处理，即：
≤0 (4)
其中：
为等式约束条件的容忍值，一般取较小的正数。通常，群体中的个体x违反第j个约束条件的程度可表示为：
(5)
构造罚函数的基本函数集如上所示，但是，在罚函数的设计及如何将之应用于不可行解等细节上仍存在着很大差别。
本文采用的是模拟退火惩罚方法，并将所有的个体统一化。即不分别设计可行个体与不可行个体的评估函数，只是以惩罚函数的违背程度作为评价其性能的标志。具体评价函数如下：
(6)
其中，
的设计是关键。每一代中适应值最大的部分个体(精英个体)的可行性会直接影响下一代的惩罚效果，即的取值。若其可行，则取固定值，否则按下式计算：
(7)
其中：
和
分别为不可行精英个体的对应函数值与违反约束值；
取(1,10)的整数，本例中 取1。
据以上换算，则可使惩罚项penalty(x)与函数值f(x)在同一数量级上，为下一代的可行性判断带来便利。
2 改进PSO算法描述
2.1 改进PSO算法简介
PSO初始化为一群随机粒子，然后，粒子们根据对个体和群体的飞行经验的综合分析来动态调整自己的速度，在解空间中进行搜索，通过迭代找到最优解。在每一次迭代中，粒子通过跟踪2个“极值”来更新自己：一个是个体极值pbest，即粒子自身目前所找到的最优解；另一个是全局极值gbest，即整个种群目前找到的最优解。在找到这2个最优解时，粒子根据如下的公式来更新自己的速度和新的位置：
(8)
(9)
其中：下标i代表第i个粒子，下标j代代数；c1和c2为学习因子，通常
和
，r1和r2是介于[0,1]的随机数；
为粒子pi在第j维个体极值的坐标；
是群体在第j维的全局极值的坐标。
下面分别从初始化和w(t)进行算法改进。
2.1.1 初始化
一般地，人们对进化算法的初始化并不重视。一种简单的初始化方法是在可能解的状态空间里随机均匀抽样。现在很多人在进行进化算法设计时，总是习惯地采用这种方法，而且很多时候这种方式都是有效的。但在解决实际问题时，一些已知的知识可能会更有利于求解。对于本文的测试，均采用平均初始化，但函数G12除外。因为若采用平均初始化，其总是在第一代就求出最优解。
2.1.2 惯性权重w(t)的改进
粒子群算法在求解无约束优化问题即寻找全局最优点时具有强大的优越性，但是，为了得到更好的性能，它的一些缺点(如早熟等)需要克服。
惯性权重w(t)可以对算法的全局搜索能力和局部搜索能力进行平衡调整，因此，该参数对算法的性能影响很大。
当w(t)较大，其具有较强的开发能力，适合在寻优初期进行较大范围的搜索；当w(t)较小时，其具有较好的探索能力，适合在寻优末期进行较精细化搜索。目前，对惯性权重w(t)的研究包括以下几种方法：线性调整、非线性调整和随机调整。
Shy等[14]发现，线性递减的惯性权重在寻找动态环境时并不是特别有效。而相应地，一个非线性的惯性权重可能具有更好的搜寻效果。其前提是：其应该满足基本的条件，即前期w(t)较大，后期w(t)较小。为此，定义以下函数：
(10)
(11)
其中：iter和iter _max分别代表进化代数和最大进化代数。
t与进化代数iter的关系以及惯性权重w(t)与t的关系分别见图1与图2。
2.2 流程图
该算法具体流程如图3所示。
图1 t与进化代数iter的关系
Fig.1 Relationship between t and iter
图2 t与非线性权重w(t)的关系
Fig.2 Relationship between t and w(t)
3 改进算法在有约束函数优化中的比较
3.1 改进算法所得结果
本文所采用的测试函数为国际公认的benchmark function[15]。
本文选择种群大小N=100，代数G=300，C1=C2=2，ωmax=0.9，ωmin=0，每次重复运行10次。初始种群采用网络模板(即平均分布)形式。所得结果与经典的SR(Stochastic ranking)的结果[15]比较见表1。
3.2 讨论与分析
通过表1可以看出：本文所提出的改进PSO算法结合简单的约束处理技术，在有约束的函数优化中取得了较好的结果。在以上6个测试函数中，对于函数g04，g08，g11和g12，改进算法在各项指标上均相同或处于领先；而对于g06，在其他各项指标均一致的情况下，虽然标准差比SR算法的大，但是，其寻优代数明显减少。对于g09，改进算法在标准差、最差值与寻优代数上占有优势，在最优值、均值和最差值方面均比SR算法的低。对于g12，改进算法的寻优代数比SR的多，但其他各项指标均优于SR。
表1 改进PSO与SR有约束测试函数结果比较
Table 1 Results compared between PSO and SR
图3 改进PSO算法的基本流程图
Fig.3 Flow chart of improved PSO
对于函数g12，因为其解的可行条件是有且仅有一组p，q和r，所列不等式成立。所以，在求解这个问题时，仅利用了可行和不可行进行判断。在具体求解时，利用了w(t)和r1=r2及保存最优解的方法。由于没有惩罚函数，适应值仅以目标函数值决定。若利用平均初始化，则可在第1代即求出最优值(5,5,5)。为了更进一步比较，在本例中，采用随机初始化的方式。这也充分说明，利用某些先验知识可以有助于求解，使求解时间缩短和求解过程简单化。
另外，对于算法中的参数r1和r2，若考虑一定的耦合影响也许会得到较好的效果。但是，没有τ对结果的影响大，这主要是因为τ直接决定了对解可行性的限制，所以，最重要的是确定τ的数量级。从以上结果也可以看出：本文的方法是正确的。
4 结论
对于一个含约束的函数优化问题，采用单纯的进化算法是不能很好解决的，所以，要充分结合约束处理技术，对问题进行再分解。本文在约束处理技术和进化算法上均作了改进，并尝试验证惩罚函数的参数确定问题，得到了较满意的结果。群智能优化算法是一种很有优势的算法，但由于其产生是基于一定的仿生进化思想，导致理论原理和数学基础均比较薄弱，对于相关参数进行理论性证明和研究有待进一步进行。
参考文献：
[1] 唐超礼. 群智能算法及其在函数优化中的应用研究[D]. 淮南: 安徽理工大学电子与信息工程学院, 2007: 2-10.
TANG Chao-li. Research on swarm intelligence algorithms and its application in function optimization[D]. Huainan: Anhui University of Science and Technology. College of Electronics and Information, 2007: 2-10.
[2] 张燕, 康琦, 汪镭, 等. 群体智能[J]. 冶金自动化, 2005, 29(2): 1-4.
ZHANG Yan, KANG Qi, WANG Lei, et al. Swarm intelligence[J]. Metallurgical Industry Automation, 2005, 29(2): 1-4.
[3] 梁艳春, 吴春国, 时小虎, 等. 群智能优化算法理论与应用[M]. 北京: 科学出版社, 2009: 1-5, 75-106.
LIANG Yan-chun, WU Chun-guo, SHI Xiao-hu, et al. The theory and application of swarm intelligence optimization algorithms[M]. Beijing: Science Press, 2009: 1-5, 75-106.
[4] 黄友锐. 智能优化算法及其应用[M]. 北京: 国防工业出版社, 2008: 1-8.
HUANG You-rui. Intelligent optimization algorithms and their application[M]. Beijing: National Defense Industry Press, 2008: 1-8.
[5] 英吉布雷切特. 计算智能导论[M]. 2版. 谭营, 等译. 北京: 清华大学出版社, 2010: 221-314.
Engelbrecht A P. Computational intelligence: An introduction[M]. 2nd ed. TAN Ying, et al, trans. Beijing: Tsinghua University Press, 2010: 221-314.
[6] 吴启迪, 汪镭. 群体智能计算模式及应用[M]. 南京: 江苏教育出版社, 2006: 2-10.
WU Qi-di, WANG Lei. Computing model and application of swarm intelligence[M]. Nanjing: Jiangsu Education Publishing House, 2006: 2-10.
[7] 纪震, 廖惠连, 吴青华. 粒子群算法及其应用[M]. 北京: 科学出版社, 2009: 167-199.
JI Zhen, LIAO Hui-lian, WU Qing-hua. Particle swarm optimization and its application[M]. Beijing: Science Press, 2009: 167-199.
[8] Kennedy J, Fberhart R A. Particle swarm optimization[C]//IEEE International Conference on Neural Networks. Piscataway, NJ, 1995: 1942-1948.
[9] Akbari R, Ziarati K. A rank based particle swarm optimization algorithm with dynamic adaptation[J]. Journal of Computational and Applied Mathematics, 2011, 235(8): 2694-2714.
[10] 王勇, 蔡自兴, 周育人, 等. 约束优化进化算法[J]. 软件学报, 2009, 20(1): 11-29.
WANG Yong, CAI Zi-xing, ZHOU Yu-ren, et al. Constrained optimization evolutionary algorithms[J]. Journal of Software, 2009, 20(1): 11-29.
[11] Michalewicz Z. Evolutionary computation techniques for nonlinear programming problems[J]. International Transactions in Operational Research, 1994, 1(2): 223-240.
[12] Michalewicz Z, Dasgupta D, Riche R G L. Evolutionary algorithms for constrained engineering problems[J]. Computers & Industrial Engineering Journal, 1996, 30(4): 851-870.
[13] Michalewicz Z, Fogel D B. How to solve it: Modern heuristics[M]. Berlin: Springer, 2004: 231-270.
[14] Shi Y, Eberhart R C. Particle swarm optimization with fuzzy adaptive inertia weight[C]//Proceeding of Workshop on Particle Swarm Optimization. Indianapolis, 2001: 101-106.
[15] Runarsson T P, YAO Xin. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2000, 4(3): 284-294.
(编辑 陈灿华)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：国家自然科学基金资助项目(70871091, 61075064, 61034004, 61005090)；教育部博士点基金资助项目(20100072110038)；教育部留学回国人员科研启动基金资助项目；教育部新世纪人才计划项目
通信作者：司呈勇(1986-)，男，山东郓城人，博士研究生，从事群体智能优化方面的研究；电话：021-69585590；Email: sichengyong@163.com
