设为首页 加入收藏

1. 引言

在当今社会，优化问题已经存在于各个领域，这也一直是人们探讨和研究的课题。且随着科学技术及工程应用的不断发展，人们对优化技术的要求也越来越高。传统的优化方法已经不能解决这些复杂优化问题。人类通过长期对自然界各种自然现象的观察和理解，逐步向大自然学习，通过对自然规律、生命进化过程、生物智能行为的借鉴和模拟，构造的用于求解复杂问题的各种计算模型。常见的启发式算法包括模拟自然进化机制的进化计算，典型的有遗传算法^[1]，模拟生物群体智能行为的群体智能算法典型的有蚁群算法、微粒群算法^[2]，还有模拟物理化学原理的算法，典型的有模拟退火算法^[3]、类电磁算法^[4]、中心力算法^[5]、引力搜索算法^[6]和人工化学过程算法以及模拟人类内部复杂系统的算法等等。这些启发式算法中，除模拟退火算法是单点搜索算法外，其余算法都是基于种群的搜索算法，除中心力算法是确定性方法外，其余算法都是随机搜索算法。

近年来谢丽萍等受拟态物理学方法的启发，通过建立拟态物理学方法与基于种群的优化算法之间的映射关系，设计了一种模拟物理规律的随机优化算法，基于拟态物理学的全局优化算法(Artificial Physics Optimization, APO)^[7,8]，建立了APO算法的统一框架。由于拟态物理学算法对有些函数的优化结果还不够好，所以本文在拟态物理学算法的基础上对拟态物理学算法的作用力规则进行了改进，在原有的作用力规则上加入一些新的作用力规则，使得新的作用力规则和个体之间的距离产生了关系。最后给出仿真实验，说明该方法的有效性。

2．拟态物理学算法

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

拟态物理学的全局优化算法(Artificial Physics Optimization, APO)^[9,10]中基于万有引力定律定义个体之间的虚拟作用力，建立了个体之间的引斥力规则，即适应值较好个体吸引适应值较差个体，适应值较差个体排斥适应值较好个体。在APO算法的框架下，样本个体在所制定的虚拟力规则的作用下在问题的可行域内搜索全局最优点。

考虑全局优化问题：

这里。n：问题的维数；：问题可行域第k维下界；：问题可行域k维上界；N_pop：种群的大小；：待优化的目标函数。

APO算法包括三个部分：初始化种群，计算每个个体所受合力，按合力的大小和方向运动。

在初始化种群阶段，设

为个体i在时刻t的位置，则表示个体i在k维的位置分量。设为个体i在时刻t的速度，则表示个体i在k维的速度分量。设为个体j对个体i在k维的作力。在初始化状态，个体间作用力为0，个体所受合力也为0。

在计算个体所受合力阶段，首先需计算个体质量。而个体质量是一用户定义的有关其适应值得函数，即，为适应值最优个体，为适应值最差个体，计算质量的函数如下：

(1)

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

(2)

式中为个体i到个体j在第k维上的距离，若个体j的适应值优于个体i的适应值，表现为引力，即个体j吸引个体i；反之，则表现为斥力，即个体j排斥个体i。式(2)不仅给出了个体间作用力的大小，还给出了作用力方向。从式(2)还可以看出，最优个体不受其它个体的作用力。

最后，计算种群中个体(除最优个体外)所受其他个体的作用力的合力，表达式如下：

(3)

在计算个体运动阶段，在牛顿第二定律的速度方程中引入一个(0,1)之间的随机变量α，服从(0,1)正态分布，这样，该算法则为一种随机算法。具体的，除最优个体外，任意个体i在t + 1时刻每一维的速度和位移的进化方程如下：

(4)

(5)

为惯性权重，且。

APO算法的流程如下：

Stepl 初始化种群：种群个体每一维的初始位置和速度在问题可行域中随机选择；计算个体适应值，并选出种群最优个体；进化代数t = 0；

Step2 计算个体所受合力；

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

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

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

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

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

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

Step6 如果没有达到结束条件，进化代数t = t + l，返回步骤Step2；否则，停止计算，并输出最优结果。

拟态物理学算法是一种基于拟态物理学方法的随机搜索算法。该算法将所优化问题的每个解看作一个有质量、速度和位移的个体，通过建立引斥力规则，整个种群在虚拟力的合力作用下向着更好的搜索区域移动。

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

拟态物理学算法对于有的函数的优化结果精度不够，对于有的函数的优化结果的鲁棒性不好，本文主要对APO算法中的这两个不足之处做了改进。在原APO算法中，规定适应值优的个体质量大，适应值差的个体质量小。作用力规则为：适应值较优个体吸引适应值较差个体，适应值较差个体排斥适应值较优个体，同时，适应值最优个体具有绝对吸引力，吸引种群其他所有个体，而其本身则不受其他个体吸引或排斥。本文在APO算法的这种引斥力规则上，制定了新的作用力规则，第一种模型是：当个体之间的距离大于某一值时，个体之间可能受引力作用，也有可能受斥力作用，由适应值决定，适应值优的个体吸引适应值差的个体，适应值差的个体排斥适应值优的个体。当个体之间的距离小于某一值时，个体之间只受斥力作用，并且是适应值差的个体排斥适应值优的个体，适应值优的个体对适应值差的个体没有作用力。第二种模型是：当个体之间的距离大于某一值时，个体之间可能受引力作用，也可能受斥力作用，由适应值决定，适应值优的个体吸引适应值差的个体，适应值差的个体排斥适应值优的个体。当个体之间的距离小于某一值时，个体之间只受引力作用，并且适应值优的个体吸引适应值差的个体，而适应值差的个体对适应值优的个体没有作用力。两种模型都只是改变了APO算法的作用力规则，质量函数不变。且个体质量随适应值的变化而变化，即个体的适应值越小，其质量就越大。希望通过这两个模型使优化结果的精度更好，使优化结果的鲁棒性更好，下面分别介绍下两种模型。

3.1．模型一

作用力规则：当个体i和个体j之间的距离时，个体之间既可能是引力作用也可能是斥力作用。当时，个体之间只受斥力作用，并且是适应值差的个体排斥适应值优的个体，适应值优的个体对适应值差的个体没有作用力。其中。

作用力方程为：

当时，

(6)

当时，只受斥力作用

(7)

其中是参数，通过实验来确定它的最好值，是一个很小的常量。根据式(6)可以看出，若个体j的适应值优于个体i的适应值，则表现为引力，即个体j吸引个体i，反之表现为斥力，即个体j排斥个体i。根据(7)式可得，表现为斥力，即个体j排斥个体i，又规定了个体j的适应值比个体i的适应值差，所以说适应值差的个体排斥适应值优的个体，这样可以使适应值优的个体远离适应值差的个体，然后适应值优的个体就可以避开适应值差的个体的区域，向着其他的区域继续搜索。将模型一记为APO1。

3.2. 模型二

作用力规则为：当个体i和个体j之间的距离时，个体之间既有引力作用也有斥力作用。当时，个体之间只受引力的作用，并且适应值优的个体吸引适应值差的个体，而适应值差的个体对适应值优的个体没有作用力。

作用力方程为：

当时，

(8)

当时，只受引力作用

(9)

根据式(8)可以看出，若个体j的适应值优于个体i的适应值，则表现为引力，即个体j吸引个体i，反之表现为斥力，即个体j排斥个体i。根据(9)式可得，表现为引力，即个体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列出了测试函数的名称及最优值的参数。具体的实验环境为：种群大小为30，维数为30，算法对每个测试函数独立运行30次，每次的最大截止代数为1500。f₁(x)、f₃(x)、f₄(x)和f₅(x)函数的G取10，f₂(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个不同的测试函数，由实验结果可以得出，这两种模型是

表1. 测试函数

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

有效的。在后续的实验中可以通过改变参数，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 particleswarm 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 Optimization, 2, 263-282.

[5]       Formato, R.A. (2007) Central force optimization: An emmetaheuristic with application in applied electromagnetics. Progress in Electromagnetics Research, 77, 425-428.

[6]       Rashedi, E. (2009) GSA: A gravitational search algorithm. Information 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 analysis 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 optimization algorithm. Applied Mathematics and Computation, 218, 4000-4011.

NOTES

^*基金项目：山西省青年科学基金(2011021014-1)、太原科技大学博士启动基金(20112009)。