文档介绍：引力搜索算法 GSA:AGravitationalSearchAlgorithm近几年,多种启发式优化方法得到发展,这些方法中很多是根据自然中群体行为得到启示。本节课介绍一种基于万有引力定律和质量相互作用的新的优化算法—引力搜索算法。引力搜索算法在2009年被首次提出,是一种基于万有引力定律和牛顿第二定律的种群优化算法。该算法通过种群的粒子位置移动来寻找最优解,即随着算法的循环,粒子靠它们之间的万有引力在搜索空间内不断运动,当粒子移动到最优位置时,最优解便找到了。2Ⅰ.启发式算法回顾Ⅱ.万有引力定律Ⅲ.引力搜索算法(GSA)Ⅳ.比较研究Ⅴ.实验结果Ⅵ.引力搜索算法的研究展望3"Heuristic"是希腊语,意为“启发式”。启发式是寻找好的(近似最佳)解的技术。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法,人们常常称为启发式算法。启发式算法是相对于最优化算法提出的。很多实际的最优化问题的计算是复杂的。因此,解决这样问题的实际方法是运用启发式算法,这样可以在合理的计算时间内找到一个近似最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(计算时间和空间)下给出解决组合优化问题每一个实例的一个可行解该可行解与最优解的偏离程度一般不能被预计。(Heuristicalgorithms)Ⅰ.启发式算法4启发式算法模拟物理或生物过程,例如一些著名的算法,遗传算法(GA)、模拟退火算法(SA)、蚁群算法(ACO)粒子群优化算法(PSO)和细菌觅食算法(BFA)。GA灵感来自于达尔文进化论;SA利用热力作用设计;ACO模拟蚂蚁觅食行为;BFA来自于搜索和最佳觅食细菌;PSO模拟鸟群的行为。上述提到的启发式算法都是随机行为。然而,Formato提出了基于引力运动的确定性的启发式搜索算法,中心引力优化(CFO)。中心引力优化算法是根据物理运动学的模型建立的一个新型的优化算法,通过初始化若干随机质点,进行迭代,直至找到最优解。5我们可以在人群为基础的启发式算法识别两个常见问题:勘探和开采。勘探有扩大搜索空间的能力,开采有寻找最佳解决方案能力。在第一次迭代中,启发式搜索算法勘探搜索空间寻找新的解。为了避免陷入局部最优的陷阱,该算法必须在前几次迭代中使用勘探。因此,在以人群为基础的启发式算法,勘探是一个重要的问题。通过勘探和开采,算法调整自己的半最优点。要有高性能的搜索,关键点是一个合适的勘探和开采之间的权衡。然而,所有的以人群为基础的启发式搜索算法采用的勘探和开采方面,他们使用不同的方法和操作。换句话说,所有的搜索算法有一个共同的框架。7从不同的角度来看,一个以群为基础的搜索算法的个体在每次迭代中通过三个步骤来实现勘探和开采概念:自适应,合作和竞争。在自我调整的步骤,每个个体(代理)提高其性能。在合作中,个体彼此合作形成的信息传递。最后,在竞争的一步,个体竞争生存。这些步骤通常随机形成,可以用不同的方式来实现。这些步骤从自然的启发,是以人群为基础的启发式算法的思想。这些概念,引导算法寻找全局最优。然而,一个算法在解决一些问题是好的,在解决另外一些问题则不行。因此,提出高性能的新启发式算法是非常受欢迎的。我们的目标是建立一个新的考虑到所提到的方面和基于引力规则的以群为基础的搜索算法。8Ⅱ.万有引力定律万有引力定律是Newton于1687年在《自然哲学的数学原理》上提出的,万有引力定律解释物体之间相互作用关系的定律,是物体间由于它们的引力质量而引起的相互吸引力所遵循的规律。自然界中任何两个物体都是相互吸引的,万有引力普遍存在于任意两个有质量的物体之间。万有引力定律表示如下:自然界中任何两个物体都是相互吸引的,引力的大小和这两个物体的质量的乘积成正比,和它们之间距离平方成反比。数学表达式为:(1)其中,F表示两个物体间的引力大小,G表示万有引力常数,M1,M2分别表示两个物体的质量,R表示两个物体之间的距离。9牛顿第二定律:当一个力F作用在一个质子上,它的加速度依赖于力和它的质量M:(2)根据(1)和(2),增加两个质子之间的距离意味着减少他们之间的万有引力。此外,由于引力减少的影响,引力常数的实际值依赖于宇宙的实际时间,方程(3)给出了降低引力常数与时间关系:(3)其中G(t)是在时间t引力常数的值,G(t0)是在t0时万有引力常数。10