万有引力搜索算法ppt.ppt

15.2 5.2 比较比较PSOPSO与与RGARGAl我们应用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 Algorithm3近几年，多种启发式优化方法得到发展，这些方法中很多是根据自然中群体行为得到启示。本节课介绍一种基于万有引力定律和质量相互作用的新的优化算法引力搜索算法。引力搜索算法在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和产生加速度 的所有力。图图115虽然，惯性质量，主动引力质量，被动引力质量有概念上的区别，但是没有实验可以清楚的证明它们之间的不同。追溯到广义相对论上，假设惯性质量和被动引力质量是等价的，这就是所知道的弱等价原理。斯坦-达尔德广义相对论也假定惯性质量和主动引力质量是等价的，这个等价有时称为强等价原理。16.引力搜索算法（GSA）受万有引力定律启发，提出了一种新型群体智能优化算法引力搜索算法。引力搜索算法在求解优化问题时，搜索个体的位置和问题的解相对应，并且还要考虑个体质量。个体质量用于评价个体的优劣，位置越好，质量越大。由于引力的作用，个体之间相互吸引并且朝着质量较大的个体方向移动，个体运动遵循牛顿第二定律。随着运动的不断进行，最终整个群体都会聚集在质量最大个体的周围，从而找到质量最大的个体，而质量最大个体占据最优位置。因此，算法可以获得问题的最优解。在GSA，每个代理有4个规格：位置，惯性质量，主动引力质位置，惯性质量，主动引力质量和被动引力质量量和被动引力质量。每个个体的位置对应一个问题的解决方法，它们的引力和惯性质量确定应用的适应度函数。换句话说，每个个体呈现一个解决方法，并且算法通过适当的调节引力和惯性质量。17引力搜索算法属于群体智能优化算法，而群体智能优化算法最显著的特点是强调个体之间的相互作用。这里，相互作用可以是个体间直接或间接的通信。在引力搜索算法中，万有引力相当于是一种信息传递的工具，实现个体间的优化信息共享，整个群体在引力的作用下进行优化搜索。信息的交互过程不仅在群体内部传播了信息，而且群体内所有个体都能处理信息，并根据其所得到的信息改变自身的搜索行为，这样就能使得整个群体涌现出一些单个个体所不具备的能力和特性，也就是说，在群体中，个体行为虽然简单，但是个体通过得到的信息相互作用以解决全局目标，信息在整个群体的传播使得问题能够比由单个个体求解更加有效的获得解决。183.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引力搜索算法的目的并不是为了模拟万有引力定律，而是利用万有引力定律的特点去解决优化问题。算法受万有引力定律的启发，但是不拘泥于万有引力公式的原始表达式。在算法中引力与两个个体质量的乘积成正比和它们的距离成反比的优化效果更好。此外，万有引力常数不在固定不变，而是随着迭代次数单调递减，算法的优化效果更好。在计算个体受到的万有引力合力时，算法只考虑质量较大的个体产生的引力。因为在引力搜索算法中，当引力较大时，或者有质量较大的个体，或者两个个体间的距离较小。质量大的个体占据较优的位置，并且代表较好的解。算法仅考虑来自质量较大的个体的引力，可以消除因距离较小而引力较大的影响，引导其他个体向质量较大的个体方向移动。在引力的不断作用下，整个群体逐渐向质量较大的个体方向逼近，最终搜索到问题的最优解。243.2 算法的流程基本引力搜索算法主要包含三个组成部分：群体初始化、计算个体质量和所受的引力以及个体运动更新。算法的主要实现步骤如下：步骤1 随机初始化群体中各个体的位置，个体的初始速度为零步骤2 个体最适值（个体的适应度函数值）步骤3 更新G(t),best(t),worst(t),Mi(t)步骤4 计算个体所受到的合力步骤5 计算加速度和速度步骤6 更新个体位置步骤7 若满足终止条件，则输出当前结果并终止算法，否则转向步骤2.25上述程序的结构流程如图2所示。图226对引力搜索算法的特点做如下总结：（1）每个搜索个体都赋予4个状态变量，分别为位置、速度、加速度和质量。位置用于表示位置的解，速度用于更新位置，加速度用于更新速度质量用于评价个体的优劣。（2）整个群体总是寻找质量最大的个体，无论是最大值优化问题还是最小值优化问题，都可以通过质量函数的定义，将优化目标转换为搜索质量最大的个体。（3）从引力搜索算法设计的起源来看，算法主要是对万有引力定律的模拟，是将物理原理和优化思想相结合而产生的。引力搜索算法最显著的特点是整个群体依靠个体之间的引力作用进行寻优，引力相当于一种优化信息的传递工具，根据算法的设计，个体的质量越大，引力也越大。因此，在引力作用下，整个群体能够向质量最大的个体方向移动，从而能够搜索到问题的最优解。（4）引力搜索算法的流程简单，参数设置少，可以很好的和各种优化问题相结合，易于实现。27除了上述这些特点之外，引力搜索算法也具有智能优化算法一些共同的特点。例如，引力搜索算法对目标函数没有特别要求，不要求函数具有连续和可导等数学性质，甚至有时连有没有解析表达式都不做要求，而且对问题中不确定的信息具有一定的适应能力，因此，算法的通用性比较强。此外，从算法实现的方法来看，引力搜索算法可以采用串行或者并行的方法实现，可以根据具体问题，设计出合理的算法实现方法。284.比较研究 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源于物理现象。314.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是单位阶跃函数33GSA 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 4高维单峰函数最小值搜索结果（函数维数n为30，最大迭代次数为1000）38n=30时，GSA,PSO,RGA对最小化优化结果的比较图3，图4n=30时，GSA,PSO,RGA对最小化优化结果的比较39 （2 2）多峰高维函数）多峰高维函数 多峰函数有很多局部极小点并且几乎都很难优化，我们进行了在 至 上的局部极小值以指数形式增加的实验，函数维数设置为30，平均适应度函数是最佳解的中间值，最后一次迭代函数在表5中显示，对 ，和 ，GSA的表现比其他的算法更好，而对函数 ，GSA无法自身调整已取得理想的好的结果。40表表5 5测试高维多峰函数最小值搜索结果（函数的维数n为30，最大迭代次数为1000）41图5n=30时，GSA,PSO,RGA对最小化优化结果的比较图6n=30时，GSA,PSO,RGA对最小化优化结果的比较42（3 3）多峰低维函数）多峰低维函数 表6表示了表3的GSA,RGA,PSO的多峰低维函数基准函数建的比较，在图7和图8，结果表明RGA,PSO和GSA有相同解并且大部分性能相同表6，表表3 3基准函数的最小化结果基准函数的最小化结果，（函数的维数n为如表1中所示，最大迭代次数为1000）43图7n=4时，GSA,PSO,RGA对最小化优化结果的比较图8n=4时，GSA,PSO,RGA对最小化优化结果的比较445.3 5.3 与与CFOCFO比较比较 先来比较GSA与CFO，在相同条件下是很难比较区分这两种算法。CFO是一个确定性的算法，有很多性质并依赖于初始群的生成和群的规模，特别是随着问题的复杂性与维数增加,CFO对于群规模和初始条件更敏感。而且，在这种条件下，CFO必须以一个较大的群规模以获得一个可接受的，合理的结果。这也就意味着，在用CFO解决问题前，我们应知道一些先验信息来建立群数量或多次尝试运行算法来获得合适的群值。而GSA是一种随机搜索算法，一种可以广泛的应用于一个固定的小规模人口问题的优化算法。正是由于上述原因，在相同条件下不能比较GSA与CFO对高维函数的优化。因此，我们在低维问题上比较这两种算法。45 在CFO，在步骤0位置矢量充满了在，每个坐标轴的探针均匀分布。在GSA，初始值是随机的，代理数和迭代次数的最大值设置分别为60和500，（因为CFO需要一个大规模种群，故取代理次数为60）。GSA的参数设置在前一节已给出，对于CFO，。注意到，我们在比较GSA和CFO对Formato 提出的函数时，需要一些适用于CFO的先验函数信息来进行函数的优化。表表7 7表示，表示，CFOCFO的随机初始化结果（不是均匀分布的初始的随机初始化结果（不是均匀分布的初始化）平均超过化）平均超过3030分，如表分，如表7 7所示，所示，CFOCFO在所得结果不能呈现在所得结果不能呈现随机初始化时好的结果，并对初始化条件有重要影响：对随机初始化时好的结果，并对初始化条件有重要影响：对于三个函数每一个算法的性能在图于三个函数每一个算法的性能在图9-119-11中表示，这些结果中表示，这些结果显示，除了函数显示，除了函数 ，外，外，GSAGSA比比CFOCFO有更好的解。有更好的解。46表表7 7，表，表1-31-3的一些函数的最小化结果，最大迭代次数为的一些函数的最小化结果，最大迭代次数为500500图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运行优化结果495.4 5.4 结论结论 近几年，已经研究了多种启发式优化方法，有些优化方法的灵感来自于自然群集行为，本文中总结了一种新的优化算法，即引力搜索算法（GSA），GSA的构造是基于万有引力定律和质量相互作用的概念。对GSA，我们有独立的群系统，利用重力引力作用，系统中每个质量可以看到其他质量的情况。因此，万有引力是一种传递不同质量之间信息的工具。为了评价我们的算法，我们设置不同的标准基准函数进行研究。通过GSA在大多数情况下得到的结果提供了更好的结果，并与PSO，RGA及CFO进行比较。50.引力搜索算法的研究展望引力搜索算法的研究展望 引力搜索算法有望成为继遗传算法，蚁群优化算法和微粒群优化算法等算法之后又一个优秀的智能优化算法，将会得到更多的国内外研究者的关注。但算法自提出以来，至今也只有短短的几年发展时间（2009年提出）。和几个成熟的算法比较而言，引力搜索算法还很年轻，还有很多的工作需要进一步研究和探讨：6.1 6.1算法的理论研究算法的理论研究 虽然引力搜索算法在求解很多问题时表现出良好的优化效果，但是其相关的理论研究比较少。算法的数学基础还很薄弱。需要对引力搜索算法的机理、收敛性、收敛速度等理论进行系统研究，阐明算法的工作原理和性态，为算法的发展和应用提供相应的理论依据。516.2 6.2 算法的改进算法的改进 高效的引力搜索算法的开发，例如对算法核心的迭代方程（包括速度和位置的更新方程）进行改进，给出算法参数自适应调整策略等。应深入分析引力搜索算法和其他算法（包括传统优化方法和智能优化算法）在优化原理、搜索模式和优化能力等方面的互补性，在此基础上，设计出基于引力搜索算法的混合型算法或融入新型优化思想的引力搜索算法。6.3 6.3 算法的应用算法的应用 目前，引力搜索算法的应用研究还处于起步阶段，所求解的问题相对有限，实际应用还未挖掘出其真正的潜力。基于算法良好的优化性能，其应用前景将十分广阔。一方面应拓宽和深化算法的应用领域，将其更广阔更深入地用于电力系统、机械设计、自动控制、通信网络和生物信息等领域；另一方面将算法用于求解多目标优化问题。52在现实问题中，存在大量的多目标优化问题，而这些问题具有重要的意义。引力搜索算法可以为优化问题的求解提供新方法，而这些应用研究对算法的理解和改进具有重要意义。此外，已经有学者开始尝试将引力搜索算法用于求解离散优化问题，将算法推广到离散优化领域，为求解离散问题提供新方法。但是如何设计有效的操作算子，需要进一步分析和研究。引力搜索算法时一种新兴的智能优化算法，目前算法还有很多未完善的方面，需要对其进行深入分析和研究。