万有引力搜索算法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 AGravitationalSearchAlgorithm 2 3 近几年 多种启发式优化方法得到发展 这些方法中很多是根据自然中群体行为得到启示 本节课介绍一种基于万有引力定律和质量相互作用的新的优化算法 引力搜索算法 引力搜索算法在2009年被首次提出 是一种基于万有引力定律和牛顿第二定律的种群优化算法 该算法通过种群的粒子位置移动来寻找最优解 即随着算法的循环 粒子靠它们之间的万有引力在搜索空间内不断运动 当粒子移动到最优位置时 最优解便找到了 4 启发式算法回顾 万有引力定律 引力搜索算法 GSA 比较研究 实验结果 引力搜索算法的研究展望 5 Heuristic 是希腊语 意为 启发式 启发式是寻找好的 近似最佳 解的技术 对于那些受大自然的运行规律或者面向具体问题的经验 规则启发出来的方法 人们常常称为启发式算法 启发式算法是相对于最优化算法提出的 很多实际的最优化问题的计算是复杂的 因此 解决这样问题的实际方法是运用启发式算法 这样可以在合理的计算时间内找到一个近似最优解 启发式算法可以这样定义 一个基于直观或经验构造的算法 在可接受的花费 计算时间和空间 下给出解决组合优化问题每一个实例的一个可行解该可行解与最优解的偏离程度一般不能被预计 Heuristicalgorithms 启发式算法 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 引力搜索算法的流程简单 参数设置少 可以很好的和各种优化问题相结合 易于实现 2020 2 5 27 28 除了上述这些特点之外 引力搜索算法也具有智能优化算法一些共同的特点 例如 引力搜索算法对目标函数没有特别要求 不要求函数具有连续和可导等数学性质 甚至有时连有没有解析表达式都不做要求 而且对问题中不确定的信息具有一定的适应能力 因此 算法的通用性比较强 此外 从算法实现的方法来看 引力搜索算法可以采用串行或者并行的方法实现 可以根据具体问题 设计出合理的算法实现方法 29 4 比较研究4 1粒子群算法 PSO PSO启发于模拟社会行为 这种优化方法更新粒子群 通过操作者根据从环境中获得的最适信息 为了群个体可以移向最优解 在PSO中 和的计算如下 15 16 ri1 ri2是 0 1 范围的随机变量 c1 c2是位置常数 w是惯性权重 pbesti表示第i个质子的最佳位置 gbest表示群中所有质子的最佳位置 30 从 16 式 我们发现每个质子尝试更新它的位置 Xi 用当前位置和第i个质子最佳位置pbesti之间的距离以及当前位置与gbest之间的距离 31 GSAvsPSOGSA和PSO的优化在搜索空间通过个体移动获得 然而移动规则是不同 一些重要的不同如下 a PSO代理的方向计算仅用两个最佳位置pbesti和gbest GSA的基于整体合力的所有其他代理获得 b PSO应用一种存储器来更新速度 pbesti gbest 然而 GSA无存储 在更新中仅需要代理的当前位置起作用 c PSO执行更新不需要考虑解之间的距离 GSA的力与解之间距离成反比 d 两个算法的搜索理念是不同的 PSO模拟鸟的行为 GSA源于物理现象 32 4 2CFO算法中心引力优化CFO是确定性多维搜索算法 它的模型是穿越搜索空间重力影响下的探针 在开始时 初始探位置用一个确定方式计算 对于初始化 根据式 17 在零时刻每一个坐标轴的位置矢量排列充满均匀分布的探针 d 1 n p 1 17 fiti是探针i的适应度函数 它必须最大化 n是维数 N是探针数量 在CFO 每一次迭代 探针进行评估 M用适用度函数计算 即式 18 是t时刻探针i的质量 18 33 随后 加速度更新应用式 19 一个新位置计算应用式 20 是时间t探针i的加速度 是时间t探针i的位置 是两个常数 19 20 G是引力常数 Rij t 是t时刻探针i和j之间的欧氏距离 U是单位阶跃函数 34 GSAvsCFO 两者的探索位置和加速度都来源于在引力场中的质点运动 但它们使用不同的构想 1 其中一个主要的不同是CFO是固有的确定性的并且没有应用任何随机参数在它的构想 GSA是随机搜索算法 2 加速度和运动表现以及群体计算 GSA不同于CFO 3 CFO初始探针位置分布是系统的 基于确定性的规则 在算法收敛有很大影响 GSA初始分布是随机的 4 CFO的G是常数 GSA中是控制参数 35 实验结果5 1基准函数表1 表3中的基准函数是测试实验所用到的基准函数 在这些表中 n代表函数的维数 S是的子集 表1和表2中函数除了之外最小值都是0 的最小值为并且除了 和以外 它们的最优位置都为 和的最优位置为 的最优位置为 表1 单峰测试函数 36 表2 高维多峰测试函数 表3 多峰低维测试函数 37 三个算法应用到基准函数 结果如下 1 单峰高维函数到是单峰高维函数 这种情况下 因为有其他方法来专门设计优化单峰函数 因此单峰函数搜索算法的收敛速度比最终结果更重要 在表4中显示 GSA对所有函数的运行结果要比RGA和PSO要好 GSA的收敛速度可由图3 4得出 根据这些图表 GSA比其他算法更快的找到全局最优 因此GSA有较高的收敛速度 从表4的结果显示 除了F5之外 基于权值的引力优化算法对其他的4个基准函数的搜索结果明显好于引力搜索算法的搜索结 仿真效果如图3 4所示 38 表4高维单峰函数最小值搜索结果 函数维数n为30 最大迭代次数为1000 39 n 30时 GSA PSO RGA对最小化优化结果的比较 图3 图4 n 30时 GSA PSO RGA对最小化优化结果的比较 40 2 多峰高维函数多峰函数有很多局部极小点并且几乎都很难优化 我们进行了在至上的局部极小值以指数形式增加的实验 函数维数设置为30 平均适应度函数是最佳解的中间值 最后一次迭代函数在表5中显示 对 和 GSA的表现比其他的算法更好 而对函数 GSA无法自身调整已取得理想的好的结果 41 表5测试高维多峰函数最小值搜索结果 函数的维数n为30 最大迭代次数为1000 42 图5n 30时 GSA PSO RGA对最小化优化结果的比较 图6n 30时 GSA PSO RGA对最小化优化结果的比较 43 3 多峰低维函数表6表示了表3的GSA RGA PSO的多峰低维函数基准函数建的比较 在图7和图8 结果表明RGA PSO和GSA有相同解并且大部分性能相同 表6 表3基准函数的最小化结果 函数的维数n为如表1中所示 最大迭代次数为1000 44 图7n 4时 GSA PSO RGA对最小化优化结果的比较 图8n 4时 GSA PSO RGA对最小化优化结果的比较 45 5 3与CFO比较 先来比较GSA与CFO 在相同条件下是很难比较区分这两种算法 CFO是一个确定性的算法 有很多性质并依赖于初始群的生成和群的规模 特别是随着问题的复杂性与维数增加 CFO对于群规模和初始条件更敏感 而且 在这种条件下 CFO必须以一个较大的群规模以获得一个可接受的 合理的结果 这也就意味着 在用CFO解决问题前 我们应知道一些先验信息来建立群数量或多次尝试运行算法来获得合适的群值 而GSA是一种随机搜索算法 一种可以广泛的应用于一个固定的小规模人口问题的优化算法 正是由于上述原因 在相同条件下不能比较GSA与CFO对高维函数的优化 因此 我们在低维问题上比较这两种算法 46 在CFO 在步骤0位置矢量充满了在 每个坐标轴的探针均匀分布 在GSA 初始值是随机的 代理数和迭代次数的最大值设置分别为60和500 因为CFO需要一个大规模种群 故取代理次数为60 GSA的参数设置在前一节已给出 对于CFO 注意到 我们在比较GSA和CFO对Formato提出的函数时 需要一些适用于CFO的先验函数信息来进行函数的优化 表7表示 CFO的随机初始化结果 不是均匀分布的初始化 平均超过30分 如表7所示 CFO在所得结果不能呈现随机初始化时好的结果 并对初始化条件有重要影响 对于三个函数每一个算法的性能在图9 11中表示 这些结果显示 除了函数 外 GSA比CFO有更好的解 47 表7 表1 3的一些函数的最小化结果 最大迭代次数为500 图9 n 5时 GSA PSO RGA对随机最小化的比较 48 图10 n 5时 GSA PSO RGA对随机最小化的比较 图11 n 2时 GSA PSO RGA对随机最小化的比较 49 对于高维函数的优化 CFO应用大量的搜索来运行 由于CFO的确定性 它在最初的几个迭代收敛 表8总结概括了对代理次数N不同的30维的研究结果 在表4 6 通过比较平均最值的结果 我们可以看出 除了 GSA提供更好的解法 CFO在前几次迭代中收敛 在局部最优并不能自调整 表8对表1 3的CFO运行优化结果 50 5 4结论 近几年 已经研究了多种启发式优化方法 有些优化方法的灵感来自于自然群集行为 本文中总结了一种新的优化算法 即引力搜索算法 GSA GSA的构造是基于万有引力定律和质量相互作用的概念 对GSA 我们有独立的群系统 利用重力引力作用 系统中每个质量可以看到其他