万有引力搜索算法.ppt

万有引力搜索算法
第一页，共51页。
引力搜索算法GSA：A Gravitational Search Algorithm
第二页，共51页。
近几年，多种启发式优化方法得到发展，这些方法中很多是
根据自然中群体行为得到启示。
本节课介绍一种基于万有引力定律和质量相互作用的新的
优化算法—引力搜索算法。
引力搜索算法在2009年被首次提出，是一种基于万有引力
定律和牛顿第二定律的种群优化算法。该算法通过种群的
粒子位置移动来寻找最优解，即随着算法的循环，粒子靠
它们之间的万有引力在搜索空间内不断运动，当粒子移动
到最优位置时，最优解便找到了。
第三页，共51页。
Ⅰ. 启发式算法回顾
Ⅱ. 万有引力定律
Ⅲ. 引力搜索算法（GSA）
Ⅳ. 比较研究
Ⅴ. 实验结果
Ⅵ. 引力搜索算法的研究展望
第四页，共51页。
"Heuristic"是希腊语，意为“启发式”。启发式是寻找
好的（近似最佳）解的技术。对于那些受大自然的运行规律
或者面向具体问题的经验、规则启发出来的方法，人们常常
称为启发式算法。启发式算法是相对于最优化算法提出的。
很多实际的最优化问题的计算是复杂的。因此，解决这样问
题的实际方法是运用启发式算法，这样可以在合理的计算时
间内找到一个近似最优解。
启发式算法可以这样定义：一个基于直观或经验构造的算法，
在可接受的花费（计算时间和空间）下给出解决组合优化问
题每一个实例的一个可行解该可行解与最优解的偏离程度一
般不能被预计。
（Heuristic algorithms）
Ⅰ. 启发式算法
第五页，共51页。
启发式算法模拟物理或生物过程，例如一些著名的算法，遗传算法（GA）、模拟退火算法（SA）、蚁群算法（ACO）
粒子群优化算法（PSO）和细菌觅食算法（BFA）。
GA灵感来自于达尔文进化论；SA利用热力作用设计；ACO模拟蚂蚁觅食行为；BFA来自于搜索和最佳觅食细菌；PSO
模拟鸟群的行为。
上述提到的启发式算法都是随机行为。然而，Formato提出了基于引力运动的确定性的启发式搜索算法，中心引力优化（CFO）。
中心引力优化算法是根据物理运动学的模型建立的一个新型的优化算法，通过初始化若干随机质点，进行迭代，直至找到最优解。
第六页，共51页。
在一些随机算法中，像模拟退火算法（SA）搜索开始于
一个单一的初始点，并且以一个连续的方式继续。然而，
大多数启发式搜索算法用多个初始点以并行方式搜索。
例如，群为基础的算法使用类似于自然的鸟群或者鱼群
的一系列代理。
在一个以群为基础的算法，每一个体施行一系列的特殊运算，
并且分享这些信息给其他个体。这些操作大部分很简单，然
而它们的集体效应，称为群体智能，会产生令人惊讶的结果。
代理之间的局部相互作用提供了一个全局结果，它允许系统
解决问题不需要应用任何的中央控制器。这种情况下，个体
操作包括随机搜索、正反馈、负反馈和多元相互作用，进行
自组织。群体智能指许多简单个体通过相互合作产生复杂智
能行为的特性。
第七页，共51页。
我们可以在人群为基础的启发式算法识别两个常见问题：
勘探和开采。勘探有扩大搜索空间的能力，开采有寻找
最佳解决方案能力。在第一次迭代中，启发式搜索算法
勘探搜索空间寻找新的解。为了避免陷入局部最优的陷
阱，该算法必须在前几次迭代中使用勘探。因此，在以人
群为基础的启发式算法，勘探是一个重要的问题。通过勘
探和开采，算法调整自己的半最优点。要有高性能的搜索，
关键点是一个合适的勘探和开采之间的权衡。然而，所有
的以人群为基础的启发式搜索算法采用的勘探和开采方面，
他们使用不同的方法和操作。换句话说，所有的搜索算法
有一个共同的框架。
第八页，共51页。
从不同的角度来看，一个以群为基础的搜索算法的个体在
每次迭代中通过三个步骤来实现勘探和开采概念:
自适应，合作和竞争。在自我调整的步骤，每个个体（代理）提高其性能。在合作中，个体彼此合作形成的信息传递。最后，在竞争的一步，个体竞争生存。这些步骤通常随机形成，可以用不同的方式来实现。这些步骤从自然的启发，是以人群为基础的启发式算法的思想。这些概念，引导算法寻找全局最优。然而，一个算法在解决一些问题是好的，在解决另外一些问题则不行。因此，提出高性能的新启发式算法是非常受欢迎的。我们的目标是建立一个新的考虑到所提到的方面和基于引力规则的以群为基础的搜索算法。
第九页，共51页。
Ⅱ. 万有引力定律
万有引力定律是Newton于1687年在《自然哲学的数学原理》
上提出的，万有引力定律解释物体之间相互作用关系的定律，
是物体间由于它们的引力质量而引起的相互吸引力所遵循的
规律。自然界中任何两个物体