- 1 -
中国科技论文在线
基于模拟退火的改进群搜索优化算法#
郑慧杰1，刘弘1,2，郑向伟1,2**
基金项目：国家自然科学基金（）,教育部博士点基金项目(),省自然科学基
金（）资助
作者简介：郑慧杰，（1987-），女，硕士研究生，主要研究方向：进化计算，计算机辅助设计
通信联系人：刘弘，（1955-），女，教授、博士生导师，主要研究方向：计算智能,计算机辅助设计等
（1. 山东师范大学信息科学与工程学院，济南 250014；
2. 山东省分布式计算机软件新技术重点实验室，济南 250014） 5
摘要：针对标准群搜索优化算法（GSO）易陷入局部最优以及效率较低等问题，提出基于模
拟退火的改进群搜索优化算法，其主要的改进为：在搜索最优值的过程中，将模拟退火算法
引入发现者的搜索模式，通过以一定的概率接受劣解，能有效跳出局部极值点，从而强化算
法的全局搜索能力；将趋势预测思想加入到发现者和部分加入者中，使其不再盲目更新，提
高寻优性能。通过常用的测试函数测试，不管是在低、高维情况下，都体现出了比 PSO，GA，10
PGSO，GSO 更好的收敛效果和寻优性。将该算法应用于群体动画中，为群体动画的实现提供
了新的思路和方法。
关键词：群体智能；群搜索优化算法；模拟退火；群体动画
中图分类号：TP18
15
An improved group search optimizer algorithm Based on
Metroplis rule
ZHENG Huijie1, LIU Hong1,2, ZHENG Xiangwei1,2
(1. School of Information Science and Engineering,Shandong Normal University, JiNan 250014;
2. Shandong Provincial Key Laboratory for NovelDistributed Computer Software Technology, 20
JiNan 250014)
Abstract: According to the problem that the standard Group Search Optimizer algorithm(GSO)
easily traps in a local optimum and has low effieicency,an improved group search optimizer
algorithm with Metroplis rule which is based on GSO is presented in this major
improvement is that the Metroplis rule is introduced in the searching mode of producer which is in 25
the process of seaching optimal order to strengthening the global search capability and
then jumping out of local extrame point,the Metroplis rule can jump out of the local optimum by
accepting a certain probalility inferior ,predictive model is accepted by the
producer,which makes the producer no longer blindly update and improves the performance of
set of benchmark functions are employed to evaluate the improved 30
matter in the low and high dimensional case,the optimization of this improved algorithm has better
global convergence than PGSO algorithm,GSO algorithm and GA algorithm is
applied to group animation and provides new ideas and methods for the realiztion of group
animation.
Keywords: swarm intelligence; group search optimizer algorithm; simulated annealing algorithm; 35
group animation
0 引言
近年来，群体动画作为新兴的技术领域，越来越多的被人们所关注，它被广泛用于电视、
电影和游戏中的虚拟人群和动物群体的模拟上。对于群体动画，手绘每个个体路径轨迹是繁40
琐且困难的，而且人们通常希望群体聚集在一起移动，例如群体游荡、觅食或攻击等实例。
随着群智能（Swarm Intelligence）研究的发展，典型的群体智能算法如 Dorigo 提出的蚁群
算法【1】(Ant Colony Algorithm)、Kenndy 与 Eberthart 提出的粒子群算法【2】(Particle Swarm
- 2 -
中国科技论文在线
Optimizer Algorithm)以及 Karaboga 提出的人工蜂群算法【3】(Artificail Bee Colony Algorithm)
已被广泛的应用到群体动画中。在 2006 年， 和 源于群居动物如鸟、鱼、狮子45
等的觅食行为提出了群搜索优化算法(Group Search Opimizer,GSO)【4】。本文将其算法进行改
进，并应用于群体动画中，提出一种新的能够快速逼真的实现群体动画的新方法。
标准 GSO 算法经过标准测试函数的测试在高维多模态型问题上具有明显优势【4】，但是
其算法较为复杂，耗时较多，而且优化效果不够理想，并且在低维问题上寻优性能较差。目
前，对标准 GSO 算法的改进算法有：限域拟牛顿法混合的 LGSO【5】、快速群搜索优化算法50
（QGSO）[6]、快速被动群搜索优化算法（QGSOPC）[7]和带趋势预测的群搜索优化算法
（PGSO）[8]。其中， LGSO 利用角度搜索，寻优效果较差，且效率较低。QGSO、QGSOPC
以及 PGSO 存在大部分寻优算法共同的问题：容易陷入局部的极小值，影响计算效率，降低
了算法的优化性能。本文综合上述多种算法，对标准 GSO 进行了改进，提出了一种新的基
于模拟退火的改进 GSO 算法，其能有效的跳出局部极值点束缚而最终找到全局最优解；搜55
索方式的改变，提高了寻优速率；同时，还使发现者的更新策略不再盲目，而且将趋势预测
加入其更新策略中，提高了算法的精度和优化速度，增强了优化性能。
1 基于模拟退火的改进群搜索优化算法
标准群搜索优化算法
GSO 算法的框架主要建立在 Prouducer-Scrounger 模型【4】上，将群成员分为三类：发现60
者，即发现食物；加入者，即加入(追随)发现者分享食物；游荡者。每次迭代过程中，当前
位置最佳的个体为此次迭代的发现者，加入者根据一定的更新策略向发现者靠近，而游荡者
则在迷失区域内随机的游荡。在每次迭代中，所有个体都是平等的，可以在这三种角色中切
换。
GSO 算法与其他群智能算法相比，虽然在多模态、高维函数优化问题有明显优势，但65
是其算法较为复杂，耗时较多，而且优化效果不够理想。
基于模拟退火的改进群搜索优化算法
通过对群搜索成员主要工作性质的分析，采用基于 Metroplis 准则和带趋势预测思想对
其发现者进行了有效的改进，在每次更新时，加入者和游荡者采用保留较优者策略，同时，
采用了按照步长搜索的快速搜索方式，形成了改进的群搜索优化算法：MPGSO。 70
Metroplis 准则
Metroplis 准则【9】是 Metropolis 等人于 1953 年提出的。先将粒子相对位置表征的初始状
态作为固体的当前状态，在这种状态下的能量是 iE 。之后，该粒子在摄动装置随机选取下，
位移发生随机的一个微小的变化，得到一个新的状态下的能量为 jE 。如果 iE 小于 jE ，则
接受这一变化；如果 iE 大于 jE ，则要根据固体处于该状态的几率 P 来判断。 75
exp( / )i jp E E KT= − （）
其中，K 是 Boltzmann 常数，T 是温度。
基于模拟退火的改进 GSO（MPGSO）
根据群成员工作性质，针对发现者、加入者和游荡者，介绍算法流程。
- 3 -
中国科技论文在线
1）发现者。由于当前位置最优者为发现者，加入者根据发现者的位置更新自己位置，80
及时向发现者靠近，所以发现者位置的更新对于位置寻优来说最为重要。发现者最优位置的
更新，极有可能将发现者引导至某一局部极值点，从而产生错误搜索更新位置，最终导致陷
入局部最优而使寻优性能下降。为了解决这一问题，本算法将 Metropolis 准则引入发现者的
搜索更新模式中，并使用趋势预测思想，在迭代过程中，发现者的移动方向作为预测下一发
现者的经验值保存起来，使发现者以独自的更新策略进行位置更新。同时，利用快速搜索的85
步长搜索方式代替角度搜索方式。
在每次迭代时，对于已经记录下的往代中位置最优的发现者，利用趋势预测思想，根据
公式（）更新位置。
1 1
1 2 1
2
( )k k k ki i best best
k k k
i best i
V cV c r X X
X X rV
− −= + −
= + （）
其中，
k n
iX R∈ 是第 i 个群成员在第 K 次迭代中的位置， k niV R∈ 是第 i 个群成员在第90
K 次迭代中的经验， kbestX 是第 K 次迭代中最优群成员的位置， 1c 、 2c 为常量系数， 1r 是
随机分布的[0,1]向量。
同时，对于更新计算得到的 kiX 是否要作为本次迭代中群成员的新位置，根据引入的
Metropolis 准则的优值增量 fΔ = 1( ) ( )k ki if X f X −− 计算得出，其中 ( )f X 为目标函数。若
fΔ <0 ，则接受 kiX 作为第 i 个群成员第 k 次迭代时的新位置，否则以概率95
exp( / )f MaxIter−Δ 接受 kiX 作为第 i 个群成员第 k 次迭代时的新位置，即公式（），从
而既能将好的移动方向作为经验保存起来，预测到更好的移动位置，又能达到有效地跳出局
部极小值点的目的。 { 1 11, (exp( ( ) ( )/ ) ) ( ( ) ( )),k k k k ki i i i ikiX if f X f X MaxIter rand or f X f Xki X otherwiseX − −− − > <= （）
2）加入者。加入者的职责就是收到发现者消息，及时向发现者靠近。在此，随机选择100
极小部分加入者使用带趋势预测思想，按照公式（）进行位置更新；剩余加入者采用随
机搜索，按照公式（）进行更新。同时，利用快速搜索的步长搜索方式替代角度搜索方
式。
1 1
3 ( )
k k k k
i i best iX X r X X
− −= + − （）
如果 1( ) ( ) 0k ki if X f X −− > ，则不选择更新，即 1k ki iX X −= 。否则，进行更新。 105
3）游荡者。游荡者的职责是随机地在觅食区域游弋，以便能搜索到发现者忽视的最优
值，在一定程度上也能有效的跳出局部极小值。游荡者根据公式（）以随机步长进行变
异更新计算。
1
4
2
5 / (4 / )
k k
i iX X r step mutationflag
mutationflag r n n k
−= + ⋅ ⋅
= < + （）
其中， 4r 、 5r 均为 n 维[0,1]均匀分布向量，mutationflag为标志各维是否变异的布尔110
值。对于新产生的 kiX ，如果 1( ) ( ) 0k ki if X f X −− > ，则不选择更新，即 1k ki iX X −= 。否则，
- 4 -
中国科技论文在线
进行更新。
2 算法分析
为了验证本算法的可行性，接下来将通过与遗传算法 GA、微粒群算法 PSO、标准群搜
索优化算法 GSO、带趋势预测的群搜索优化算法 PGSO 进行相应测试函数的寻优比较，证115
明 MPGSO 在不仅在高维情况下具有优越性，而且在低维情况下也有较好的寻优效果。
测试函数和参数设置
本文选择 3 个典型测试函数进行优化实验，Sphere 函数,Rosenbrock 函数，Rastrigin 函
数。它们的定义（其中 n 是函数维数）及其性质如下所示：
Sphere 函数： 120
2
1
1
( )
n
i
i
f x x
=
=∑
， 100 100ix− ≤ ≤ ， 1min( ) 0f =
Rosenbrock 函数：
1
2 2 2
2 1
1
( ) [100( ) ( 1) ]
n
i i i
i
f x x x x
−
+
=
= − + −∑
， 30 30ix− ≤ ≤ ， 2min( ) 0f =
Rastrigin 函数：
2 2
3
1
( ) ( 10cos(2 ) 10)
n
i i
i
f x x xπ
=
= − +∑
， − ≤ ≤ ， 3min( ) 0f = 125
测试中，各算法的参数设置如下：GA 根据 自带的 GADST（Genetic
Algorithm and Direct Search Toolbox），其中，参数设置为 intermediate crossover，参数 migration
rate 为 0，其他参数采用默认值。PSO 根据 PSOT 粒子群优化工具箱里的标准 PSO，参数采
用默认值【8】。所有算法的种群规模设置为 50。在 30 维函数优化时的迭代次数为 3000，在
300 维函数优化时的迭代次数为 60000。 130
实验结果及各算法比较
在 30 维、迭代次数 3000 的函数优化时，算法连续运行 50 次的平均结果与标准差如表
1 所示。
表 1 函数 f1~f3 在低维情况下运行 50 次的结果平均值（标准差） 135
Tab1 The average(SD) results of function f1~f3 running 50 times in low-dimensional case
测试函数 GA PSO GSO PGSO MPGSO
1( )f x （）
-45
（-44）
-9
（-8）
-21
(-20)
-23
(-22)
2 ( )f x (+3)
()
()
()
()
3 ( )f x ()
()
()
-20
(-20)
-23
(-22)
由表 1 可以看出，本文算法在测试函数 1( )f x ~ 3 ( )f x 测试下，较之 GA、GSO、PGSO
都有明显优势。
在 300 维、迭代次数 60000 的函数优化时，算法连续运行 10 次的平均结果与标准差如140
表 2 所示。
- 5 -
中国科技论文在线
表 2 函数 f1~f3 在高维情况下运行 10 次的结果平均值（标准差）
Tab2 The average(SD) results of function f1~f3 running 10 times in high-dimensional case
测试函数 GA PSO GSO PGSO MPGSO
1( )f x ()
-10
(-9)
()
-15
(-14)
-15
(-15)
2 ( )f x +4 (+3)
+3
(+3)
+3
(+3)
+3
()
()
3 ( )f x ()
+3
()
+3
()
-21
(-21)
-21
(-21)
145
由表 2 可以看出，本文算法在测试函数 2 ( )f x ~ 3 ( )f x 测试下，较之 GA、PSO、GSO、
PGSO 也有较好优势，且标准差较好，对于 1( )f x ，本文算法也具有较高的稳定性。
下图 1~图 3 为标准 GSO 算法与 MPGSO 算法对各个函数在低维情况下优化过程的曲线
对比。
150
图 1 对于 Sphere 函数在低维情况下的优化过程曲线对比图
Comparison figure of the Sphere function in the case of low-dimensional curves of optimization process
图 2 对于Rosenbrock 函数在低维情况下的优化过程曲线对比图 155
Comparison figure of the Rosenbrock function in the case of low-dimensional curves of optimization process
- 6 -
中国科技论文在线
图 3 对于Rastrigin函数在低维情况下的优化过程曲线对比图
Comparison figure of the Rastrigin function in the case of low-dimensional curves of optimization process 160
下图 4~图 6 为标准 GSO 算法与 MPGSO 算法对各个函数在高维情况下优化过程的曲线
对比。
图 4 对于Sphere 函数在高维情况下的优化过程曲线对比图 165
Comparison figure of the Sphere function in the case of high-dimensional curves of optimization process
图 5 对于Rosenbrock 函数在高维情况下的优化过程曲线对比图
Comparison figure of the Rosenbrock function in the case of high-dimensional curves of optimization 170
process
- 7 -
中国科技论文在线
图 6 对于Rastrigin函数在高维情况下的优化过程曲线对比图
Comparison figure of the Rastrigin function in the case of high-dimensional curves of optimization process 175
通过对图 1~图 6 的对比，可以清晰地看出 MPGSO 算法对于标准 GSO 算法无论在低维、
还是高维的情况下，都有较好寻优效果。
同时，为了证明 MPGSO 算法不仅保持标准 GSO 算法在高维情况下的寻优优势，而且
在低维情况下也有较好的性能，在 3 维情况下，MPGSO 算法与标准 PSO 算法进行相应比较。180
其中，设置种群大小为 20，每个测试函数运行 30 次，每次运行 1000 代，维数为 3，参数 r
为 1，m 为 4，得到的结果,取平均值，并计算其标准差，得到各个函数用标准 PSO 算法和
MPGSO 算法优化的结果，见表 3。
表 3 MPGSO 与标准 PSO 在 3维情况下的优化结果 185
Tab 3 The results of MPGSO and the standard PSO in the case of three dimension
Sphere 函数 Rosenbrock 函数 Rastrigin 函数
PSO MPGSO PSO MPGSO PSO MPGSO
最小值 -26 -32 0
平均值 -22 -18 -31
标准差 -21 +02 -13 -31
通过上表，可以看出 MPGSO 算法在低维（即 3 维）情况下，比标准 PSO 算法表现出
更好的寻优优势。
综上实验结果所示，本文改进的算法（即 MPGSO 算法）无论在低维还是高维，在搜索190
性能上优于其他 4 种算法，有较好寻优性能。
3 仿真实验
在上述分析与研究的基础上，对本文的 MPGSO 算法进行了仿真模拟实验，在 Microsoft
Visual 2003 环境中，基于 ACIS 和 HOOPS 环境将 MPGSO 算法中用于群体动画
的聚集现象中。实现效果如图 7、图 8。其中，绿色个体为目标食物，图 7 为粒子群体随机195
初始状态，图 8 为粒子群体运行 100 次时的群体状态。
- 8 -
中国科技论文在线
图 7 粒子群体初始状态（绿色为目标点）
Fig 7 The initial state of particles(the green is the target point)
200
图 8 粒子群体运动状态（绿色为目标点）
Fig 8 Motion state of particles(the green is the target point)
仿真实验结果表明，基于 MPGSO 算法的群体动画是可行的，能够形象表现出群体的人205
工智能性，并能真实的再现群体聚集等行为。
4 结束语
MPGSO 基于 Metropolis 准则以及将带趋势预测思想应用到发现者位置更新策略中去，
同时采用步长搜索模式，不仅在高维上继续保持了算法的高效性，而且在低维上也有较好的
寻优效果，并在碰撞避免等情况下将其应用于群体动画中，为群体动画的实现提供了新的思210
路和方法。GSO 在诞生至今已被实践证明是一种有效的方法，但是在日后工作中无论在理
论研究、提高算法性能以及应用于实践等方面还有很多工作和问题等待解决。
[参考文献] (References)
[1] Colorni,Dorigo A,Maniezzo optimization by ant colonies[C].Proceedings of the First European 215
Conference on Artificial ,France:1991:134-142.
[2] Kenndy J,Eberhart R Swarm Optimization[C].Proceedings of the 1995 IEEE International
Conference on Neural ,NJ,USA:1995:1942-1948.
[3] CAMAZINE S,SNDYD model of collective nectar source by honey bees:selt-organization through simple
rules[J].Journal of Theoretical Biology,1991,149(4):547-571. 220
[4] He S,Wu Q H,Saunders J Search Optimizer:An Optimization Algorithm Inspired by Animal
Searching Behavior[J].IEEE Transactions on Evolutionary Computation,,13(5):973-990.
[5] 房娟艳,曾建潮,崔志华.混合群搜索优化算法及其应用研究[D]. 太原科技大学.2010
Fang Juanyan,Zeng Jianchao,Cui group search optimization algrithm and its appliction[D].Taiyuan
University of Technology 225
[6] QIN Guang,LIU Feng,LI quick group search optimizer and its application to the optimal design of
double layer grid shells[C].The Second International Symposium on Computational Mechanics,Hong
Kong&Macao,China,2009.
[7] 刘锋，覃广，李丽娟.快速被动群搜索优化算法及其在空间结构中的应用[J].工程设计学
- 9 -
中国科技论文在线
报.2010,17(6):420-425 230
Liu Feng,Tan Guang,Li group search optimizer with passive congregation and its application in
spatial structures[J].Engineering ,17(6):420-425
[8] 张雯雰,朱朝晖.带趋势预测的群搜索优化算法[J].信息技术.:48-51
Zhang Wenfen,Zhu search optimizer algrorithm with predictive model[J].Information
:48-51. 235
[9] .Metropolis N,Rosenbluth A W,Rosenbluth M N,Teller A H and Teller of states calulations for
fast computing machines[J].JchemPhys,1953,21:1087-1091.
[10] He S,Wu Q H,A Novel Group Search Opitimizer Inspired by Animal Behavioural Ecology[C].2006 IEEE
Congress on Evolutionary Computation,2006:4415-4421
[11] Hai Shen,Yunlong Zhu,Ben Niu,,An improved group search optimizer for mechanical design 240
optimization problems[J].Progress in Natural Science,2009,19:91-97.
[12] 张雯雰,滕少华,李丽娟.改进的群搜索优化算法[J].计算机工程与应用.2009,45(4):48-52.
Zhang WenFen,Teng Shaohua,Li group search algorithm[J].Computer Engineering and
,45(4):48-52
[13] HE S,PREMPAIN,WU Q improved particle swarm optimizer for mechanical design optimization 245
problems[J].Engineering Optimization,2004,36(5):585-605
[14] De Jong K analysis of the behavior of a class of generic adaptive systems[D].University of
Michigan,1975.
