引力场优化算法GFA20151127hxm

1、引力场算法Gravitation Field Algorithm1报告人：胡雪梅指导教师：王岩日期:2015/11/252021/8/14纲要n背景n算法n实验22021/8/14纲要n背景n算法n实验32021/8/14背景4郑明. 引力场算法及其在生物信息学中的应用D. 吉林大学, 2013.参考链接：http:/ 优化算法是当今的重要研究课题，能够从海量数据中获得所需最优解，也是极具挑战的工作。 优化算法定义：给定某一待解问题，求该问题的最优解，此问题一般以N 元变量方程形式给出。若N 远大于1，则该方程在N 维空间中解的个数并不唯一，甚至是无穷个解。为获得所需方程评价标准最大值或最小值

2、所使用的计算机方法即为优化算法。 例如：解析法、解析法、直接法、数值计算法、各种启发式搜索算法等等。2021/8/14背景6 大规模数据优化问题启发式搜索算法效果最佳，也是研究热点与难点。 启发式搜索算法：模拟退火算法、遗传算法、粒子群算法存在的问题：1）容易陷入局部最优2）运算时间过长亟需引进一种新的算法来弥补这些缺陷。引力场优化算法GFA2021/8/14纲要n背景n算法n实验72021/8/14算法8算法描述 引力场优化算法的思想来源于被大多数天文学家所接受的行星形成理论：太阳系星云盘模型SNDM。SNDM 模型：数十亿年前不存在太阳系，仅有灰尘和星云飘移在宇宙之中。然后灰尘在自身引力作

3、用下进行凝聚，长时间后形成岩石，这是太阳系一个标志性时期。之后岩石迅速开始加快凝聚和碰撞，并吸附周围的小石块，岩石越积越大最终形成太阳系的所有行星。2021/8/14算法9u 所有灰尘u 灰尘的质量u 灰尘间的引力作用u 引力场作用大小u 小灰尘推离开大灰尘u 小灰尘被大灰尘吸收u 形成行星u 行星之间相互吸收形成最大的行星u 所有可行解u 解的质量（评价函数）u 比例移动u 距离参数u 自转u 吸收u 局部最优解u 全局最优解SNDM模型GFA算法SNDM模型与引力场优化算法定义对照表GFA就是上述理论的数学抽象模型框架下所提出的优化算法。2021/8/14算法10算法四大步骤：初始化灰尘群

4、体解空间分解算子移动算子吸收算子2021/8/14算法11 初始化灰尘群体2021/8/14算法12 解空间分解算子 2021/8/14算法13 解空间分解算子一维随机分组法一维平均分组法二维随机分组法6G 时二维空间平均分组最大公约数法2021/8/14算法14 解空间分解算子 2021/8/14算法15 移动算子 GFA 算法中的这一部分决定在某一组内的所有灰尘哪一个是峰值并规定此峰值为中心灰尘，其他灰尘为周围灰尘。同时让周围灰尘受中心灰尘的引力作用向中心灰尘移动。 灰尘的位置信息的改变会让移动的周围灰尘本身的值发生变化，通过质量函数的运算，也会不断改变原有周围灰尘的质量值。如果在改变的过

5、程中某个周围灰尘的质量超过了中心灰尘，它将取代中心灰尘成为所在组新的中心，原有中心灰尘降格为周围灰尘，本组所有周围灰尘运动方向发生改变，指向新的中心灰尘。移动策略： iiPaceMdisdisi表示两个多维解向量之间的直接向量差2021/8/14算法16 2021/8/14算法17一个周围灰尘跨过最优解的情况 GFA算法中移动算子的自转系数也是由中心灰尘作用在周围灰尘之上的。作用方式是把周围灰尘推离开中心灰尘，但推开的方向不一定是原来前进方向。max20.0618withdrawdis被推开的最大距离：自转系数： maxmaxmax,110.03,1factorfactor ifactorfa

6、ctor ifactor ifactor ifactor注意：移动算子运行结束之后需要加一个检验，检验新的位置是否仍然在解空间之中2021/8/14算法18 吸收算子 当周围灰尘与中心灰尘之间的距离足够小之时，比如小于一个阈值，或者是一定的移动算子迭代次数内中心灰尘与周围灰尘仍未靠拢，则周围灰尘被中心灰尘吸收 吸收算子吸收结束之后，直接进入解空间分解算子的下一次迭代，所有没有被删除的灰尘都将降格为周围灰尘并重新分组。若算法收敛或满足结束条件，算法结束。 2021/8/14算法19GFA算法流程和步骤介绍如下： 随机初始化灰尘。 用随机分组分解法分解解空间。 执行移动算子。 对每一个移动后的灰尘

7、颗粒执行吸收算子操作。 对每一个没有被吸收的周围灰尘按照自转系数概率执行自转操作。 若本组内满足组内收敛条件则转入(7)，否则转入(3)。 若已满足 GFA 算法结束条件，结束。否则转入(2)算法结束条件： 整个算法迭代一定次数，如 50 次。 整个空间灰尘足够少，如小于等于 5 个。2021/8/14纲要n背景n算法n实验202021/8/14实验21测试函数：2112111222112312411110.2cos 2510011010cos 2cos140002020DDiiiiDiiDiiiiDiiiDDiiiixxDDfxfxxxfDxxxxfifeee Sphere 函数：Rosen

8、brock 函数：Rastrigin 函数：Griewangk 函数：Ackley 函数：2021/8/1422实验2021/8/14实验23单极值评价方法：平均方差：标准差：平均高斯差： 211nioptiiMSEf xfxn211()1niiSTDxXn 2101,2niixtMGEGE xnGE xedt其中2021/8/1424实验2021/8/1425实验2021/8/1426实验多极值实验2021/8/14总结nGFA算法是一种模拟目前被普遍接受的行星形成理论星云盘模型的启发式搜索算法。n特点 收敛速度快、简单函数和多峰值函数收敛效果好n四大步骤 随机初始化灰尘、解空间分解、移动算子、吸收算子n测试 单极值条件下测试5个函数，并与GA和SA算法进行比较，前4个函数效果均