Computer Science and Application 计算机科学与应用, 2013, 3, 326-330 http://dx.doi.org/10.12677/csa.2013.38057 Published Online November 2013 (http://www.hanspub.org/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. 12th, 2013; revised: Nov. 3rd, 2013; accepted: Nov. 9th, 2013 Copyright © 2013 Xiaoning Ma et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unre- 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 among 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 f XXR fRR 这里 min max :| ,1, kkk , X xxxk n min k 。 n: 问题的维数; x :问题可行域第k维下界; ma k x x : 问题可行域 k维上界;Npop:种群的大小; f x:待 优化的目标函数。 APO 算法包括三个部分:初始化种群,计算每个 个体所受合力,按合力的大小和方向运动。 在初始化种群阶段,设 ,1 ,2, ,, iii in X txtxtxt 为个体 i在时刻t的位置,则 ,ik x 表示个体 i在k维的 位置分量。设为个体 i 在时刻 t的速度,则表示个体 i在k维的速度分量。 设 ,1 , ,, ii in Vtv ttvt ,ik v ,2i v ,ij k F 为个体 j对个体 i在k维的作力。在初始化状态, 个体间作用力为0,个体所受合力也为 0。 在计算个体所受合力阶段,首先需计算个体质 量。而个体质量是一用户定义的有关其适应值得函 数,即 ,0, iii mgfx m , best i worst best fx fx fx fx i me i (1) 个体间的作用力计算表达式如下: , , , , , ijijk ij k ijijk Gm mr F Gm mr j i j i f xfx f xfx ,ijibest , (2) 式中 ,,ij ki kj k rxx 为个体i到个体j在第k维上的距离, 若个体j的适应值优于个体i的适应值, ,ij k F 表现为引 力,即个体j吸引个体i;反之,则,ij k F 表现为斥力,即 个体j排斥个体i。式(2)不仅给出了个体间作用力的大 小,还给出了作用力方向。从式(2)还可以看出,最优 个体不受其它个体的作用力。 最后,计算种群中个体(除最优个体外)所受其他 个体的作用力的合力,表达式如下: ,, 1, , Npop ik ijk jji F Fibe st (3) 在计算个体运动阶段,在牛顿第二定律的速度方 程中引入一个(0,1)之间的随机变量α,服从(0,1)正态分 布,这样,该算法则为一种随机算法。具体的,除最 优个体外,任意个体i在t + 1时刻每一维的速度和位移 的进化方程如下: ,,, 1, ikikik i vtvt Fm ibest (4) ,,, 11 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 x 为适应值最优 个体, 为适应值最差个体,计算质量的函数如下: worst x Step4 根据式(5)计算个体的下一代位置; Step5 计算个体适应值,更新种群最优个体及其 Open Access 327 引入距离因素的拟态物理学算法 适应值; Step6 如果没有达到结束条件,进化代数 t = t + l, 返回步骤 Step2;否则,停止计算,并输出最优结果。 拟态物理学算法是一种基于拟态物理学方法的 随机搜索算法。该算法将所优化问题的每个解看作一 个有质量、速度和位移的个体,通过建立引斥力规则, 整个种群在虚拟力的合力作用下向着更好的搜索区 域移动。 3. 加入距离因素的作用力规则 拟态物理学算法对于有的函数的优化结果精度 不够,对于有的函数的优化结果的鲁棒性不好,本文 主要对 APO 算法中的这两个不足之处做了改进。在 原APO 算法中,规定适应值优的个体质量大,适应 值差的个体质量小。作用力规则为:适应值较优个体 吸引适应值较差个体,适应值较差个体排斥适应值较 优个体,同时,适应值最优个体具有绝对吸引力,吸 引种群其他所有个体,而其本身则不受其他个体吸引 或排斥。本文在 APO 算法的这种引斥力规则上,制 定了新的作用力规则,第一种模型是:当个体之间的 距离大于某一值时,个体之间可能受引力作用,也有 可能受斥力作用,由适应值决定,适应值优的个体吸 引适应值差的个体,适应值差的个体排斥适应值优的 个体。当个体之间的距离小于某一值时,个体之间只 受斥力作用,并且是适应值差的个体排斥适应值优的 个体,适应值优的个体对适应值差的个体没有作用 力。第二种模型是:当个体之间的距离大于某一值时, 个体之间可能受引力作用,也可能受斥力作用,由适 应值决定,适应值优的个体吸引适应值差的个体,适 应值差的个体排斥适应值优的个体。当个体之间的距 离小于某一值时,个体之间只受引力作用,并且适应 值优的个体吸引适应值差的个体,而适应值差的个体 对适应值优的个体没有作用力。两种模型都只是改变 了APO 算法的作用力规则,质量函数不变。且个体 质量随适应值的变化而变化,即个体的适应值越小, 其质量就越大。希望通过这两个模型使优化结果的精 度更好,使优化结果的鲁棒性更好,下面分别介绍下 两种模型。 3.1.模型一 作用力规则:当个体 i和个体 j之间的距离 ij ra 时,个体之间既可能是引力作用也可能是斥力作用。 当ij ra 时,个体之间只受斥力作用,并且是适应值 差的个体排斥适应值优的个体,适应值优的个体对适 应值差的个体没有作用力。其中 。 ij i j rxx 作用力方程为: 当ij ra时, , , ijij ij ijij Gm mr F Gm mr () () () () j i j i f xfx f xfx (6) 当ij ra 时,只受斥力作用 , 0, ij ij ij ij mm Gxx r F j i f xf ther x o (7) 其中 是参数,通过实验来确定它的最好值,a 是一 个很小的常量。根据式(6)可以看出,若个体j的适应 值优于个体 i的适应值,则 ij F 表现为引力,即个体j 吸引个体 i,反之 ij F 表现为斥力,即个体 j排斥个体i。 根据(7)式可得, ij F 表现为斥力,即个体j排斥个体 i, 又规定了个体 j的适应值比个体 i的适应值差,所以 说适应值差的个体排斥适应值优的个体,这样可以使 适应值优的个体远离适应值差的个体,然后适应值优 的个体就可以避开适应值差的个体的区域,向着其他 的区域继续搜索。将模型一记为APO1。 3.2. 模型二 作用力规则为:当个体i和个体j之间的距离 ij ra时,个体之间既有引力作用也有斥力作用。当 ij ra 时,个体之间只受引力的作用,并且适应值优 的个体吸引适应值差的个体,而适应值差的个体对适 应值优的个体没有作用力。 作用力方程为: 当ij ra时, , , ijij ij ijij Gm mr F Gm mr j i j i f xfx f xfx (8) 当ij ra 时,只受引力作用 , 0, ij ji ij ij mm Gxx r F j i f xfx er oth (9) Open Access 328 引入距离因素的拟态物理学算法 根据式(8)可以看出,若个体j的适应值优于个体 i的适应值,则ij F 表现为引力,即个体j吸引个体 i, 反之 ij F 表现为斥力,即个体 j排斥个体 i。根据(9)式 可得, ij F 表现为引力,即个体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个测试函数如下: 2 11 1 1 20exp0.2 1 expcos 2π20 , n i i n i i fx x n x e n 21sin|| , n ii i fxxx 22 12 31 11001 , n ii i i fxx xx 2 1 2 41 1 2 2 1 1 π10sin π1 110sin π1 ,10,100, 4, n i i in n i i fxy y n yy ux 2 1 2 51 1 2 22 1 1 0.1 sinπ31 1sin 3π11sin2π ,10,100,4. n i i in n n i i fxxx xx x ux 表1列出了测试函数的名称及最优值的参数。具 体的实验环境为:种群大小为30,维数为 30,算法 对每个测试函数独立运行 30次,每次的最大截止代 数为 1500。f1(x)、f3(x)、f4(x)和f5(x)函数的 G取10, f2(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. 测试函数 函数 函数名 搜索范围 最小值 f1(x) Ackley [−32, 32]n 0 f2(x) Schwefel [−500, 500]n −12569.5 f3(x) Rosenbrock [−30, 30]n 0 f4(x) Penalized F1 [−50, 50]n 0 f5(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. |