万有引力搜索算法ppt.ppt

1,5.2 比较PSO与RGA,我们应用GSA到这些最小化函数，并且比较RGA与PSO所得出的结果，在这些情况，群体大小设置为 。维数 ，表1,2的函数最大迭代次数为1000，表3为500，在PSO中 ，惯性因素 从0.9到0.2线性下降，在RGA应用算法交叉算子，高斯交换以及轮盘算法，交叉和变异的概率分别为0.3和0.1. 在GSA,G用(21)式表示， 为100， 。 是所有迭代次数 (21),引力搜索算法 GSA：A Gravitational Search Algorithm,3,近几年，多种启发式优化方法得到发展，这些方法中很多是 根据自然中群体行为得到启示。 本节课介绍一种基于万有引力定律和质量相互作用的新的 优化算法引力搜索算法。 引力搜索算法在2009年被首次提出，是一种基于万有引力 定律和牛顿第二定律的种群优化算法。该算法通过种群的 粒子位置移动来寻找最优解，即随着算法的循环，粒子靠 它们之间的万有引力在搜索空间内不断运动，当粒子移动 到最优位置时，最优解便找到了。,4,. 启发式算法回顾 . 万有引力定律 . 引力搜索算法（GSA） . 比较研究 . 实验结果 . 引力搜索算法的研究展望,5,“Heuristic“是希腊语，意为“启发式”。启发式是寻找 好的（近似最佳）解的技术。对于那些受大自然的运行规律 或者面向具体问题的经验、规则启发出来的方法，人们常常 称为启发式算法。启发式算法是相对于最优化算法提出的。 很多实际的最优化问题的计算是复杂的。因此，解决这样问 题的实际方法是运用启发式算法，这样可以在合理的计算时 间内找到一个近似最优解。 启发式算法可以这样定义：一个基于直观或经验构造的算法， 在可接受的花费（计算时间和空间）下给出解决组合优化问 题每一个实例的一个可行解该可行解与最优解的偏离程度一 般不能被预计。,（Heuristic algorithms）,. 启发式算法,6,启发式算法模拟物理或生物过程，例如一些著名的算法，遗传算法（GA）、模拟退火算法（SA）、蚁群算法（ACO） 粒子群优化算法（PSO）和细菌觅食算法（BFA）。 GA灵感来自于达尔文进化论；SA利用热力作用设计；ACO模拟蚂蚁觅食行为；BFA来自于搜索和最佳觅食细菌；PSO 模拟鸟群的行为。 上述提到的启发式算法都是随机行为。然而，Formato提出了基于引力运动的确定性的启发式搜索算法，中心引力优化（CFO）。 中心引力优化算法是根据物理运动学的模型建立的一个新型的优化算法，通过初始化若干随机质点，进行迭代，直至找到最优解。,7,在一些随机算法中，像模拟退火算法（SA）搜索开始于 一个单一的初始点，并且以一个连续的方式继续。然而， 大多数启发式搜索算法用多个初始点以并行方式搜索。 例如，群为基础的算法使用类似于自然的鸟群或者鱼群 的一系列代理。 在一个以群为基础的算法，每一个体施行一系列的特殊运算， 并且分享这些信息给其他个体。这些操作大部分很简单，然 而它们的集体效应，称为群体智能，会产生令人惊讶的结果。 代理之间的局部相互作用提供了一个全局结果，它允许系统 解决问题不需要应用任何的中央控制器。这种情况下，个体 操作包括随机搜索、正反馈、负反馈和多元相互作用，进行 自组织。群体智能指许多简单个体通过相互合作产生复杂智 能行为的特性。,8,我们可以在人群为基础的启发式算法识别两个常见问题： 勘探和开采。勘探有扩大搜索空间的能力，开采有寻找 最佳解决方案能力。在第一次迭代中，启发式搜索算法 勘探搜索空间寻找新的解。为了避免陷入局部最优的陷 阱，该算法必须在前几次迭代中使用勘探。因此，在以人 群为基础的启发式算法，勘探是一个重要的问题。通过勘 探和开采，算法调整自己的半最优点。要有高性能的搜索， 关键点是一个合适的勘探和开采之间的权衡。然而，所有 的以人群为基础的启发式搜索算法采用的勘探和开采方面， 他们使用不同的方法和操作。换句话说，所有的搜索算法 有一个共同的框架。,9,从不同的角度来看，一个以群为基础的搜索算法的个体在 每次迭代中通过三个步骤来实现勘探和开采概念: 自适应，合作和竞争。在自我调整的步骤，每个个体（代理）提高其性能。在合作中，个体彼此合作形成的信息传递。最后，在竞争的一步，个体竞争生存。这些步骤通常随机形成，可以用不同的方式来实现。这些步骤从自然的启发，是以人群为基础的启发式算法的思想。这些概念，引导算法寻找全局最优。然而，一个算法在解决一些问题是好的，在解决另外一些问题则不行。因此，提出高性能的新启发式算法是非常受欢迎的。我们的目标是建立一个新的考虑到所提到的方面和基于引力规则的以群为基础的搜索算法。,10,. 万有引力定律 万有引力定律是Newton于1687年在自然哲学的数学原理 上提出的，万有引力定律解释物体之间相互作用关系的定律， 是物体间由于它们的引力质量而引起的相互吸引力所遵循的 规律。自然界中任何两个物体都是相互吸引的，万有引力普 遍存在于任意两个有质量的物体之间。万有引力定律表示如下： 自然界中任何两个物体都是相互吸引的，引力的大小和这两个 物体的质量的乘积成正比，和它们之间距离平方成反比。 数学表达式为：,（1）,其中，F表示两个物体间的引力大小，G表示万有引力常数， M1，M2分别表示两个物体的质量，R表示两个物体之间的距离。,11,牛顿第二定律：当一个力F作用在一个质子上，它的加速度,依赖于力和它的质量M：,（2）,根据（1）和（2），增加两个质子之间的距离意味着减少 他们之间的万有引力。 此外，由于引力减少的影响，引力常数的实际值依赖于宇宙 的实际时间，方程（3）给出了降低引力常数与时间关系：,（3）,其中G(t)是在时间t引力常数的值，G(t0)是在t0时万有引力常数。,12,理论物理学中定义三种质量： 主动引力质量，,是对物体重力场的强度的测量，小的主动,物体的重力场比大的主动引力质量的重力场弱。,小的被动,被动引力质量的物体比大的被动引力质量的物体,改变快。,引力质量的,被动引力质量，,是对物体重力场中物体相互作用的强度的测量，,受到的力小。,惯性质量,是当有一个力作用在物体，改变她位置的移动的,力的测量，大的,惯性质量的物体改变它移动的更慢，,小的惯性,13,考虑到以上提到的三种质量定义，我们重新定义牛顿定律。 万有引力Fij通过物体j作用在物体i，与j 的主动引力质量和 i 被动引力质量乘积成正比，与它们之间距离成反比。,与Fij成正比，与i 惯性质量成反比，则（1）（2）式 重新定义如下：,（4）,（5）,和,分别代表质子i 的主动引力质量，质子j 的被动引力质量，,代表质子i 的惯性质量。,虽然，惯性质量，主动引力质量，被动引力质量有概念上的区别，但是 没有实验可以清楚的证明它们之间的不同。追溯到广义相对论上，假设 惯性质量和被动引力质量是等价的，这就是所知道的弱等价原理。 斯坦-达尔德广义相对论也假定惯性质量和主动引力质量是等价的，这个 等价有时称为强等价原理。,14,在图1中，F1j是作用在M1到Mj的力，F1是作用在M1和产生 加速度 的所有力。,图1,15,虽然，惯性质量，主动引力质量，被动引力质量有概念上的 区别，但是没有实验可以清楚的证明它们之间的不同。追溯 到广义相对论上，假设惯性质量和被动引力质量是等价的， 这就是所知道的弱等价原理。斯坦-达尔德广义相对论也假定 惯性质量和主动引力质量是等价的，这个等价有时称为强等价 原理。,16,.引力搜索算法（GSA） 受万有引力定律启发，提出了一种新型群体智能优化算法 引力搜索算法。引力搜索算法在求解优化问题时，搜索 个体的位置和问题的解相对应，并且还要考虑个体质量。 个体质量用于评价个体的优劣，位置越好，质量越大。由于 引力的作用，个体之间相互吸引并且朝着质量较大的个体 方向移动，个体运动遵循牛顿第二定律。随着运动的不断 进行，最终整个群体都会聚集在质量最大个体的周围，从 而找到质量最大的个体，而质量最大个体占据最优位置。 因此，算法可以获得问题的最优解。 在GSA，每个代理有4个规格：位置，惯性质量，主动引力质 量和被动引力质量。每个个体的位置对应一个问题的解决方法， 它们的引力和惯性质量确定应用的适应度函数。换句话说，每 个个体呈现一个解决方法，并且算法通过适当的调节引力和 惯性质量。,17,引力搜索算法属于群体智能优化算法，而群体智能优化算法 最显著的特点是强调个体之间的相互作用。这里，相互作用 可以是个体间直接或间接的通信。在引力搜索算法中，万有 引力相当于是一种信息传递的工具，实现个体间的优化信息 共享，整个群体在引力的作用下进行优化搜索。信息的交互 过程不仅在群体内部传播了信息，而且群体内所有个体都能 处理信息，并根据其所得到的信息改变自身的搜索行为，这 样就能使得整个群体涌现出一些单个个体所不具备的能力和 特性，也就是说，在群体中，个体行为虽然简单，但是个体 通过得到的信息相互作用以解决全局目标，信息在整个群体 的传播使得问题能够比由单个个体求解更加有效的获得解决。,18,3.1 算法的模型,引力搜索算法首先在解空间和速度空间分别对位置和速度 进行初始化，其中位置表示问题的解。例如，d维空间中 的第i 个搜索个体的位置和速度分别表示为,，,分别表示个体i 在第d 维的位置分量和速度,其中，,和,分量。通过评价各个个体的目标函数值，确定每个个体的 质量和受到的引力，计算加速度，并更新速度和位置。,19,（1）计算质量,个体i 的质量定义如下：,（6）,（7）,其中，,和,分别表示在第t 次迭代时第i 个个体的,best(t)和worst(t)表示在第t次迭代时所有个体中最优适应 度函数值和最差适应度函数值，对最小化问题，其定义如下：,（8）,（9）,适应度函数值和质量。,20,（2）计算引力,算法源于对万有引力定律的模拟，但不拘泥于物理学中的 万有引力公式的精确表达式。在第d 维上，个体j 对个体i 的 引力定义如下：,（10）,其中，G(t)表示在t 次迭代时万有引力常数的取值， G(t)=G(G0，t), Rij(t)表示个体i和j 之间的欧氏距离，,是一常数，,防止分母为零。,21,在第d维上，个体i 所受的合力为：,（11）,其中，randj表示在0,1之间服从均匀分布的一个随机变量,kbest表示个体质量按降序排在前k个的个体，并且k的取值随 迭代次数线性减小，初值为N，终值为1。,22,（3）计算加速度,根据牛顿第二定律，个体i 在第d维的加速度方程为：,（12）,（4）更新速度和位置,（13）,（14）,其中，r表示在0,1之间服从均匀分布的一个随机变量。,23,引力搜索算法的目的并不是为了模拟万有引力定律，而是利 用万有引力定律的特点去解决优化问题。算法受万有引力定 律的启发，但是不拘泥于万有引力公式的原始表达式。在算 法中引力与两个个体质量的乘积成正比和它们的距离成反比 的优化效果更好。此外，万有引力常数不在固定不变，而是 随着迭代次数单调递减，算法的优化效果更好。 在计算个体受到的万有引力合力时，算法只考虑质量较大的 个体产生的引力。因为在引力搜索算法中，当引力较大时， 或者有质量较大的个体，或者两个个体间的距离较小。质量 大的个体占据较优的位置，并且代表较好的解。算法仅考虑 来自质量较大的个体的引力，可以消除因距离较小而引力较 大的影响，引导其他个体向质量较大的个体方向移动。在引 力的不断作用下，整个群体逐渐向质量较大的个体方向逼近， 最终搜索到问题的最优解。,24,3.2 算法的流程,基本引力搜索算法主要包含三个组成部分：群体初始化、 计算个体质量和所受的引力以及个体运动更新。算法的 主要实现步骤如下： 步骤1 随机初始化群体中各个体的位置，个体的初始速度为零 步骤2 个体最适值（个体的适应度函数值） 步骤3 更新G(t),best(t),worst(t),Mi(t) 步骤4 计算个体所受到的合力 步骤5 计算加速度和速度 步骤6 更新个体位置 步骤7 若满足终止条件，则输出当前结果并终止算法，否则 转向步骤2.,25,上述程序的结构流程如图2所示。,图2,26,对引力搜索算法的特点做如下总结： （1）每个搜索个体都赋予4个状态变量，分别为位置、速度、 加速度和质量。位置用于表示位置的解，速度用于更新位置， 加速度用于更新速度质量用于评价个体的优劣。 （2）整个群体总是寻找质量最大的个体，无论是最大值优化 问题还是最小值优化问题，都可以通过质量函数的定义，将优 化目标转换为搜索质量最大的个体。,（3）从引力搜索算法设计的起源来看，算法主要是对万有引 力定律的模拟，是将物理原理和优化思想相结合而产生的。引 力搜索算法最显著的特点是整个群体依靠个体之间的引力作用 进行寻优，引力相当于一种优化信息的传递工具，根据算法的 设计，个体的质量越大，引力也越大。因此，在引力作用下， 整个群体能够向质量最大的个体方向移动，从而能够搜索到问 题的最优解。 （4）引力搜索算法的流程简单，参数设置少，可以很 好的和各种优化问题相结合，易于实现。,27,除了上述这些特点之外，引力搜索算法也具有智能优化算法 一些共同的特点。例如，引力搜索算法对目标函数没有特别 要求，不要求函数具有连续和可导等数学性质，甚至有时连 有没有解析表达式都不做要求，而且对问题中不确定的信息 具有一定的适应能力，因此，算法的通用性比较强。此外， 从算法实现的方法来看，引力搜索算法可以采用串行或者并行 的方法实现，可以根据具体问题，设计出合理的算法实现方法。,28,4. 比较研究 4.1 粒子群算法（PSO） PSO启发于模拟社会行为，这种优化方法更新粒子群，通过 操作者根据从环境中获得的最适信息，为了群个体可以移向 最优解。在PSO中， 和 的计算如下：,（15）,（16）,ri1,ri2是0,1范围的随机变量，c1,c2是位置常数，w是惯性权重。 pbesti表示第i 个质子的最佳位置， gbest表示群中所有质子的最佳位置。,29,从（16）式， 我们发现每个质子尝试更新它的位置（Xi）， 用当前位置和第i 个质子最佳位置pbesti之间的距离以及 当前位置与gbest之间的距离。,30,GSA vs PSO GSA和PSO的优化在搜索空间通过个体移动获得，然而 移动规则是不同，一些重要的不同如下： a. PSO代理的方向计算仅用两个最佳位置pbesti和gbest， GSA的基于整体合力的所有其他代理获得。 b. PSO应用一种存储器来更新速度（pbesti,gbest）,然而， GSA无存储，在更新中仅需要代理的当前位置起作用。 c. PSO执行更新不需要考虑解之间的距离；GSA的力与解之 间距离成反比。 d. 两个算法的搜索理念是不同的，PSO模拟鸟的行为，GSA 源于物理现象。,31,4.2 CFO 算法 中心引力优化CFO是确定性多维搜索算法。它的模型是穿越 搜索空间重力影响下的探针。在开始时，初始探位置用一个 确定方式计算。对于初始化，根据式（17），在零时刻每一 个坐标轴的位置矢量排列充满均匀分布的探针，,d=1.n， p=1.,（17）,，,fiti 是探针i 的适应度函数，它必须最大化。,n是维数，N是探针数量，在CFO，每一次迭代，探针进行评估。 M用适用度函数计算，即式（18）， 是t时刻探针i 的质量。,（18）,32,随后，加速度更新应用式（19）， 一个新位置计算应用式（20），,是时间t探针i 的加速度,是时间t探针i 的位置,是两个常数。,（19）,（20）,G是引力常数，Rij(t)是t时刻探针i和j 之间的欧氏距离。 U是单位阶跃函数,33,GSA vs CFO,两者的探索位置和加速度都来源于在引力场中的质 点运动，但它们使用不同的构想 （1）其中一个主要的不同是CFO是固有的确定性的 并且没有应用任何随机参数在它的构想，GSA是随机 搜索算法。 （2）加速度和运动表现以及群体计算，GSA不同于CFO。 （3）CFO初始探针位置分布是系统的（基于确定性 的规则），在算法收敛有很大影响。GSA初始分布是 随机的。 （4）CFO的G是常数，GSA中是控制参数。,34,. 实验结果 5.1 基准函数 表1表3中的基准函数是测试实验所用到的基准函数。在这些表中，n代表函数的维数，S是 的子集。表1和表2中函数除了 之外最小值都是0， 的最小值为 并且除了 , 和 以外，它们的最优位置 都为 ， 和 的最优位置 为 ， 的最优位置 为,表1，单峰测试函数,35,表2，高维多峰测试函数,表3，多峰低维测试函数,36,三个算法应用到基准函数，结果如下： （1）单峰高维函数 到 是单峰高维函数，这种情况下，因为有其他方法来专门设计优化单峰函数，因此单峰函数搜索算法的收敛速度比最终结果更重要。 在表4中显示，GSA对所有函数的运行结果要比RGA和PSO要好，GSA的收敛速度可由图3,4得出，根据这些图表，GSA比其他算法更快的找到全局最优，因此GSA有较高的收敛速度。从表4的结果显示，除了F5之外，基于权值的引力优化算法对其他的4个基准函数的搜索结果明显好于引力搜索算法的搜索结，仿真效果如图3,4所示,37,表4高维单峰函数最小值搜索结果 （函数维数n为30，最大迭代次数为1000）,38,n=30时，GSA,PSO,RGA对最小化 优化结果的比较,图3，,图4,n=30时，GSA,PSO,RGA对最小化 优化结果的比较,39,（2）多峰高维函数 多峰函数有很多局部极小点并且几乎都很难优化，我们进行了在 至 上的局部极小值以指数形式增加的实验，函数维数设置为30，平均适应度函数是最佳解的中间值，最后一次迭代函数在表5中显示，对 ， 和 ，GSA的表现比其他的算法更好，而对函数 ，GSA无法自身调整已取得理想的好的结果。,40,表5测试高维多峰函数最小值搜索结果 （函数的维数n为30，最大迭代次数为1000）,41,图5 n=30时，GSA,PSO,RGA对最小化 优化结果的比较,图6 n=30时，GSA,PSO,RGA对最小化 优化结果的比较,42,（3）多峰低维函数 表6表示了表3的GSA,RGA,PSO的多峰低维函数基准函数建的比较，在图7和图8，结果表明RGA,PSO和GSA有相同解并且大部分性能相同,表6，表3基准函数的最小化结果，（函数的维数n为如表1中所示，最大迭代次数为1000）,43,图7 n=4时，GSA,PSO,RGA对最小化 优化结果的比较,图8 n=4时，GSA,PSO,RGA对最小化 优化结果的比较,44,5.3 与CFO比较,先来比较GSA与CFO，在相同条件下是很难比较区分这两种算法。 CFO是一个确定性的算法，有很多性质并依赖于初始群的生成和群的规模，特别是随着问题的复杂性与维数增加, CFO对于群规模和初始条件更敏感。而且，在这种条件下，CFO必须以一个较大的群规模以获得一个可接受的，合理的结果。这也就意味着，在用CFO解决问题前，我们应知道一些先验信息来建立群数量或多次尝试运行算法来获得合适的群值。 而GSA是一种随机搜索算法，一种可以广泛的应用于一个固定的小规模人口问题的优化算法。正是由于上述原因，在相同条件下不能比较GSA与CFO对高维函数的优化。因此，我们在低维问题上比较这两种算法。,45,在CFO，在步骤0位置矢量充满了在，每个坐标轴的探针均匀分布。在GSA，初始值是随机的，代理数和迭代次数的最大值设置分别为60和500，（因为CFO需要一个大规模种群，故取代理次数为60）。GSA的参数设置在前一节已给出，对于CFO， 。注意到，我们在比较GSA和CFO对Formato 提出的函数时，需要一些适用于CFO的先验函数信息来进行函数的优化。,表7表示，CFO的随机初始化结果（不是均匀分布的初始化）平均超过30分，如表7所示，CFO在所得结果不能呈现随机初始化时好的结果，并对初始化条件有重要影响：对于三个函数每一个算法的性能在图9-11中表示，这些结果显示，除了函数 ， 外，GSA比CFO有更好的解。,46,表7，表1-3的一些函数的最小化结果，最大迭代次数为500,图9. n=5时，GSA,PSO,RGA对 随机最小化的比较,47,图10， n=5时，GSA,PSO,RGA对 随机最小化的比较,图11， n=2时，GSA,PSO,RGA对 随机最小化的比较,48,对于高维函数的优化，CFO应用大量的搜索来运行，由于CFO的确定性，它在最初的几个迭代收敛。表8总结概括了对代理次数N不同的30维的研究结果，在表4-6，通过比较平均最值的结果，我们可以看出，除了 ， ， ，GSA提供更好的解法，CFO在前几次迭代中收敛，在局部最优并不能自调整。,表8 对表1-3的CFO运行优化结果,49,5.4 结论,近几年，已经研究了多种启发式优化方法，有些优化方法的灵感来自于自然群集行为，本文中总结了一种新的优化算法，即引力搜索算法（GSA），GSA的构造是基于万有引力定律和质量相互作