引入距离因素的拟态物理学算法 The Distance Factor of Artificial Physics Optimization

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Computer Science and Application 计算机科学与应用, 2013, 3, 326-330

http://dx.doi.org/10.12677/csa.2013.38057 Published Online November 2013 (//www.abtbus.com/journal/csa.html)

The Distance Factor of Artificial Physics Optimization

Xiaoning Ma, Liping Xie, Jianchao Zeng

Complex System and Computational Intelligence Laboratory, Taiyuan University of Science and Technology, Taiyuan

Email: maxiaoning_9@126.com

Received: Oct. 12 th, 2013; revised: Nov. 3rd, 2013; accepted: Nov. 9th, 2013

stricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract: Artificial Physics Optimization (APO) algorithm is a global optimization algorithm by physico-mimetics-

inspired. APO algorithm is a stochastic optimization algorithm. The virtual forces among individuals are defined by

Newton’s gravity law and a reaction rule is established amo ng them. On the basis of the APO, it introduces a new pa-

rameter, the distance between individuals. And as the distance between the individuals differs, force changes between

individuals. The simulation results indicate the validity of the approach.

Keywords: Artificial Physics Optimization; Attraction; Repulsion; Global Optimization

引入距离因素的拟态物理学算法

麻晓宁，谢丽萍，曾建潮

太原科技大学复杂系统与计算智能实验室，太原

Email: maxiaoning_9@126.com

收稿日期： 2013 年10 月12日；修回日期： 2013 年11月3日；录用日期： 2013 年11月9日

摘要：拟态物理学算法是受拟态物理学启发的一种全局优化算法，是一种随机优化算法，基于牛顿万有引力

定律定义了个体之间的虚拟作用力，制定了作用力规则。本文在拟态物理学算法的作用力规则的基础上，引入

了一个新的参数，即个体之间的距离，并且随着个体间距离的不同，个体之间的作用力也随之变化，实验结果

表明在这种新的作用力规则下算法的有效性。

关键词：拟态物理学算法；引力；斥力；全局优化算法

1. 引言

在当今社会，优化问题已经存在于各个领域，这

也一直是人们探讨和研究的课题。且随着科学技术及

工程应用的不断发展，人们对优化技术的要求也越来

越高。传统的优化方法已经不能解决这些复杂优化问

题。人类通过长期对自然界各种自然现象的观察和理

解，逐步向大自然学习，通过对自然规律、生命进化

过程、生物智能行为的借鉴和模拟，构造的用于求解

复杂问题的各种计算模型。常见的启发式算法包括模

拟自然进化机制的进化计算，典型的有遗传算法 [1] ，

模拟生物群体智能行为的群体智能算法典型的有蚁

群算法、微粒群算法 [2] ，还有模拟物理化学原理的算

法，典型的有模拟退火算法 [3]、类电磁算法[4]、中心

力算法 [5]、引力搜索算法[6]和人工化学过程算法以及

模拟人类内部复杂系统的算法等等。这些启发式算法

中，除模拟退火算法是单点搜索算法外，其余算法都

是基于种群的搜索算法，除中心力算法是确定性方法

外，其余算法都是随机搜索算法。

近年来谢丽萍等受拟态物理学方法的启发，通过

建立拟态物理学方法与基于种群的优化算法之间的

* 基金项目：山西省青年科学基金(2011021014-1)、太原科技大学

博士启动基金(20112009 )。

Open Access

326

引入距离因素的拟态物理学算法

映射关系，设计了一种模拟物理规律的随机优化算

法，基于拟态物理学的全局优化算法 (Artificial Physics

Optimization, APO) [7,8]，建立了 APO 算法的统一框架。

由于拟态物理学算法对有些函数的优化结果还不够

好，所以本文在拟态物理学算法的基础上对拟态物理

学算法的作用力规则进行了改进，在原有的作用力规

则上加入一些新的作用力规则，使得新的作用力规则

和个体之间的距离产生了关系。最后给出仿真实验，

说明该方法的有效性。

2 ．拟态物理学算法

基于拟态物理学的优化算法

拟态物理学的全局优化算法 (Artificial Physics

Optimization, APO) [9,10]中基于万有引力定律定义个体

之间的虚拟作用力，建立了个体之间的引斥力规则，

即适应值较好个体吸引适应值较差个体，适应值较差

个体排斥适应值较好个体。在 APO 算法的框架下，

样本个体在所制定的虚拟力规则的作用下在问题的

可行域内搜索全局最优点。

考虑全局优化问题：





min:, :

nnl

XXR fRR 

这里



min max

:| ,1,

kkk ,

xxxk n  

min

。

n ：

问题的维数；

：问题可行域第 k 维下界； ma

：

问题可行域 k维上界；Npop：种群的大小；





x ：待

优化的目标函数。

APO 算法包括三个部分：初始化种群，计算每个

个体所受合力，按合力的大小和方向运动。

在初始化种群阶段，设

 







,1 ,2,

iii in



txtxtxt 

为个体 i在时刻 t 的位置，则 ,ik

表示个体 i 在k维的

位置分量。设为个体 i

在时刻 t 的速度，则表示个体 i在k维的速度分量。

设

 

,1 ,

ii in

Vtv ttvt 

, ik



,2 i



, ij k

为个体 j 对个体 i在k维的作力。在初始化状态，

个体间作用力为 0 ，个体所受合力也为 0。

在计算个体所受合力阶段，首先需计算个体质

量。而个体质量是一用户定义的有关其适应值得函

数，即









,0,

iii

mgfx m 



best i

worst best

fx fx

me i





 (1)

个体间的作用力计算表达式如下：

ijijk

ij k

ijijk

Gm mr





  











xfx



 ,ijibest 

(2)

式中 ,,ij ki kj k

rxx



 为个体i到个体j在第k维上的距离，

若个体 j的适应值优于个体i的适应值， ,ij k

表现为引

力，即个体 j吸引个体i；反之，则,ij k

表现为斥力，即

个体 j 排斥个体i。式(2)不仅给出了个体间作用力的大

小，还给出了作用力方向。从式 (2) 还可以看出，最优

个体不受其它个体的作用力。

最后，计算种群中个体 (除最优个体外 )所受其他

个体的作用力的合力，表达式如下：

Npop

ik ijk

jji

Fibe





 st (3)

在计算个体运动阶段，在牛顿第二定律的速度方

程中引入一个 (0,1) 之间的随机变量α，服从(0,1)正态分

布，这样，该算法则为一种随机算法。具体的，除最

优个体外，任意个体 i 在t + 1时刻每一维的速度和位移

的进化方程如下：





,,,

ikikik i

vtvt Fm

ibest



 

 (4)









,,,

ikik ik

xt xtvt

ibest

 



(5)



为惯性权重，且





0, 1



 。

APO 算法的流程如下：

Stepl 初始化种群：种群个体每一维的初始位置

和速度在问题可行域中随机选择；计算个体适应值，

并选出种群最优个体；进化代数 t = 0；

Step2 计算个体所受合力；

Step2.1 根据式 (1)计算个体质量；

Step2.2 根据式(2)计算个体所受其他个体的作用

力；

Step2.3 根据式 (3)计算个体所受合力；

Step3 根据式 (4)计算个体的下一代速度；

1 ，best

为适应值最优

个体，为适应值最差个体，计算质量的函数如下：

worst

Step4 根据式 (5)计算个体的下一代位置；

Step5 计算个体适应值，更新种群最优个体及其

Open Access 327

引入距离因素的拟态物理学算法

适应值；

Step6 如果没有达到结束条件，进化代数 t = t + l，

返回步骤 Step2 ；否则，停止计算，并输出最优结果。

拟态物理学算法是一种基于拟态物理学方法的

随机搜索算法。该算法将所优化问题的每个解看作一

个有质量、速度和位移的个体，通过建立引斥力规则，

整个种群在虚拟力的合力作用下向着更好的搜索区

域移动。

3. 加入距离因素的作用力规则

拟态物理学算法对于有的函数的优化结果精度

不够，对于有的函数的优化结果的鲁棒性不好，本文

主要对 APO 算法中的这两个不足之处做了改进。在

原 APO 算法中，规定适应值优的个体质量大，适应

值差的个体质量小。作用力规则为：适应值较优个体

吸引适应值较差个体，适应值较差个体排斥适应值较

优个体，同时，适应值最优个体具有绝对吸引力，吸

引种群其他所有个体，而其本身则不受其他个体吸引

或排斥。本文在 APO 算法的这种引斥力规则上，制

定了新的作用力规则，第一种模型是：当个体之间的

距离大于某一值时，个体之间可能受引力作用，也有

可能受斥力作用，由适应值决定，适应值优的个体吸

引适应值差的个体，适应值差的个体排斥适应值优的

个体。当个体之间的距离小于某一值时，个体之间只

受斥力作用，并且是适应值差的个体排斥适应值优的

个体，适应值优的个体对适应值差的个体没有作用

力。第二种模型是：当个体之间的距离大于某一值时，

个体之间可能受引力作用，也可能受斥力作用，由适

应值决定，适应值优的个体吸引适应值差的个体，适

应值差的个体排斥适应值优的个体。当个体之间的距

离小于某一值时，个体之间只受引力作用，并且适应

值优的个体吸引适应值差的个体，而适应值差的个体

对适应值优的个体没有作用力。两种模型都只是改变

了 APO 算法的作用力规则，质量函数不变。且个体

质量随适应值的变化而变化，即个体的适应值越小，

其质量就越大。希望通过这两个模型使优化结果的精

度更好，使优化结果的鲁棒性更好，下面分别介绍下

两种模型。

3.1 ．模型一

作用力规则：当个体 i和个体 j之间的距离 ij

ra 

时，个体之间既可能是引力作用也可能是斥力作用。

当 ij



时，个体之间只受斥力作用，并且是适应值

差的个体排斥适应值优的个体，适应值优的个体对适

应值差的个体没有作用力。其中。

ij i j

rxx 

作用力方程为：

当 ij

ra 时，

ijij

Gm mr





  





() ()

xfx



 (6)

当 ij



时，只受斥力作用



Gxx



 



 

 







ther

 x

(7)

其中是参数，通过实验来确定它的最好值， a



是一

个很小的常量。根据式 (6)可以看出，若个体j的适应

值优于个体 i 的适应值，则 ij

表现为引力，即个体 j

吸引个体 i，反之 ij

表现为斥力，即个体 j排斥个体 i。

根据 (7) 式可得， ij

表现为斥力，即个体 j排斥个体 i，

又规定了个体 j的适应值比个体 i的适应值差，所以

说适应值差的个体排斥适应值优的个体，这样可以使

适应值优的个体远离适应值差的个体，然后适应值优

的个体就可以避开适应值差的个体的区域，向着其他

的区域继续搜索。将模型一记为 APO1 。

3.2. 模型二

作用力规则为：当个体 i和个体j之间的距离

ra 时，个体之间既有引力作用也有斥力作用。当



时，个体之间只受引力的作用，并且适应值优

的个体吸引适应值差的个体，而适应值差的个体对适

应值优的个体没有作用力。

作用力方程为：

当 ij

ra 时，

ijij

Gm mr





  







xfx



 (8)

当 ij



时，只受引力作用



Gxx



 



 

 







xfx



oth

(9)

Open Access

328

引入距离因素的拟态物理学算法

根据式 (8) 可以看出，若个体j的适应值优于个体

i 的适应值，则 ij

表现为引力，即个体 j吸引个体 i，

反之 ij

表现为斥力，即个体 j排斥个体 i 。根据(9)式

可得， ij

表现为引力，即个体 j吸引个体 i，又规定

了个体 j 的适应值比个体 i的适应值好，也就是适应

值好的个体吸引适应值差的个体。将模型二记为

APO2 。

新的作用力规则下算法的流程如下：

Stepl 初始化种群：种群个体每一维的初始位置

和速度在问题可行域中随机选择；计算个体适应值，

并选出种群最优个体；进化代数 t = 0；

Step2 计算个体所受合力；

Step2.1 根据式 (1) 计算个体质量；

Step2.2 根据式 (6 )(7)或(8)(9)计算个体所受其他

个体的作用力；

Step2.3 根据式 (3) 计算个体所受合力；

Step3 根据式 (4)计算个体的下一代速度；

Step4 根据式 (5)计算个体的下一代位置；

Step5 计算个体适应值，更新种群最优个体及其

适应值；

Step6 如果没有达到结束条件，进化代数 t = t + l，

返回步骤 Step2 ；否则，停止计算，并输出最优结果。

4. 仿真实验

为了测试该算法的优化效果，使用了 5 个基准函

数。这 5个测试函数如下：



1 1

20exp0.2

expcos 2 π 20 ,

fx x





 















 





2 1 sin|| ,

fxxx









2 2

1 2

1 1001 ,

ii i

fxx xx





 







 

 





 





π 10sin π1

110sin π 1

,10,100, 4,

fxy y













 







 





 





0.1 sin π 31

1sin 3 π11sin2π

,10,100,4.

in n

fxxx

xx x















  











表 1 列出了测试函数的名称及最优值的参数。具

体的实验环境为：种群大小为 30 ，维数为 30，算法

对每个测试函数独立运行 30 次，每次的最大截止代

数为 1500 。f1(x)、f3(x)、f4(x)和f5(x)函数的 G取10，

f 2 (x )函数的G取0.5。通过多次试验取经验值



e − 005 ， a = 0.001。

APO1 、 APO2 与APO比较

仿真结果如下表 2 。

由表 2 可以看出，对于Ackley函数 APO1和APO2

解的精度优于 APO，且 APO1 和 APO2 的鲁棒性也好

于 APO ；对于 Rosenbrock 函数 APO1 和APO2 解的

精度优于 APO ，且 APO1 的鲁棒性最好；对于 Penalized

F1 函数 APO1 和APO2 解的精度优于APO；对于

Schwefel 函数和 Penalized F2函数 APO1 和APO2 解

的精度没有 APO 的优，但是 APO1 和APO2 的鲁棒

性比 APO 的好。由此可见，APO1 和APO2优化了

Ackley 函数、 Rosenbrock 函数和 Penalized F1函数的

解的精度，虽然对于 Schwefel 函数和 Penalized F2 函

数解的精度没有得到优化，但是鲁棒性得到了提高。

总的来说， APO1 和APO2 是有效的算法。

5. 结论

本文在拟态物理学算法的基础上，对拟态物理学

算法的作用力规则进行了研究，提出了两种不同的模

型，并对这两种模型进行了仿真实验，采用了 5 个不

同的测试函数，由实验结果可以得出，这两种模型是

Table 1. Test functions

表 1. 测试函数

函数函数名搜索范围最小值

f 1 ( x ) Ackley [−32, 32]n 0

f 2 ( x) Schwefel [−500, 500]n −12569.5

f 3 ( x ) Rosenbrock [−30, 30]n 0

f 4 (x) Penalized F1 [−50, 50]n 0

f 5 (x) Penalized F2 [−50, 50] 0



Open Access 329

引入距离因素的拟态物理学算法

Open Access

330

Table 2. APO1、APO1 and APO the result comparison

表 2. APO1 、APO1 与 APO 结果比较

函数最优值平均适应值平均方差

APO 5.887218e −016 2.604092e+000 9.943840e−001

APO1 5.887218e −016 5.513974e−001 4.507650e−001 f1(x)

APO2 5.887218e −016 5.887218e−016 0

APO − 7.665673e+003 −6.180069e+003 2.041997e+002

APO1 − 4.862661e+003 −4.333314e+003 5.191162e+001 f2(x)

APO2 − 5.539441e+003 −4.614296e+003 7.481079e+001

APO 2.878916e+001 2.899009e+001 7.045900e − 003

APO1 2.877266e+001 2.897656e+001 1.156162e − 002 f3(x)

APO2 2.877117e+001 2.898832e+001 7.683555e −003

APO 1.110928e+000 1.467692e+000 2.833554e − 002

APO1 1.053196e+000 1.457818e+000 3.320685e − 002 f4(x)

APO2 1.106578e+000 1.439854e+000 3.350685e − 002

APO 2.821070e+000 2.900961e+000 5.744124e − 003

APO1 2.802731e+000 2.906163e+000 5.629977e − 003 f5(x)

APO2 2.833573e+000 2.907812e+000 3.141676e − 003

有效的。在后续的实验中可以通过改变参数， G值等

对函数进行进一步的优化。

参考文献 (References)

[1] Jiang, Z.Y., Cai, Z.X. and Wang, Y. (2010) Hybrid self-adaptive

orthogonal genetic algorit hm for solving global optimization

problems. Journal of Software, 21, pp. 1296-1307.

[2] Mo, S.M., Zeng, J.C. and Xie, L.P. (2012) Extended particle-

swarm optimization algorithm. Control Theory & Applications,

29 , pp. 811-816.

[3] Ma, S.D., Gong, G.H., Han, L. and Song, X. (2011) Hybrid

strategy with ant colony and simulated annealing algorithm and

its improvement in target assignment. Systems Engineering and

Electronics , 33, pp. 1182-1186.

[4] Birbil, S.I. and Fang, S.C. (2003) An electromagnetism-like

mechanism for global optimization. Journal of Global Optimiza-

tion , 2, 263-282.

[5] Formato, R.A. (2007) Central force optimization: An emmeta-

heuristic with application in applied electromagnetics. Progress

in Electromagnetics Research , 77, 425-428.

[6] Rashedi, E. (2009) GSA: A gravitational search algorithm. In-

formation Sciences , 179, 2232-2248.

[7] 谢丽萍 , 曾建潮 (2010) 受拟态物理学启发的全局优化算法.

系统工程理论与实践

, 30, 2276-2282.

[8] 谢丽萍, 曾建潮 (2011) 基于拟态物理学方法的全局优化算

法 .

计算机研究与发展

, 48, 848-854.

[9] Xie, L.P., Tan, Y., Zeng, J.C., et al. (2011) The convergence ana-

lysis of artificial physics optimisation algorithm. International

Journal of Intelligent Information and Database Systems , 5,

536-554.

[10] Xie, L.P., Zeng, J.C. and Formato, R.A. (2011) Convergence

analysis and performance of the extended artificial physics op-

timization algorithm. Applied Mathematics and Computation, 218,

4000-4011.