烟花算法爆炸因子分析及改良 余俊 九州大学艺术工学府 日本学术振兴会特别研究员 Email: yujun@kyudai jp
烟花算法爆炸因子分析及改良 余 俊 九州大学 艺术工学府 日本学术振兴会 特别研究员 Email: yujun@kyudai.jp
目录 烟花算法 爆炸因子分析及改进 两种新爆炸策略 烟花算法优化多峰问题 基于推测点加速烟花算法 总结
目录 • 烟花算法 • 爆炸因子分析及改进 • 两种新爆炸策略 • 烟花算法优化多峰问题 • 基于推测点加速烟花算法 • 讨论 • 总结
Fitness 进化计算 最优解 进化计算 种基于种群的优化算法; ·通过模拟优胜劣汰来逐步寻求最优解; ·非确定性,具有一定的随机性 ·经典算法:遗传算法,进化策略,遗传编程等; (JR東海提供) 三菱航空機(株)提供) 实例 ·N70O系新干线 三菱航空机
进化计算 • 一种基于种群的优化算法； • 通过模拟优胜劣汰来逐步寻求最优解； • 非确定性，具有一定的随机性； • 经典算法：遗传算法，进化策略，遗传编程等； • …….. Fitness 最优解 进化计算 实例 • N700系新干线 • 三菱航空机 • ………….. （JR東海提供） （三菱航空機（株）提供） 4
般优化框架 选择 否 初始化进《机出子代 终止 是 条件 输出最优解 fitness评价 ftes评价
一般优化框架 初始化 fitness评价 进化机制产出子代 （交叉，重组） 终止 条件? 选择 是 否 输出最优解 fitness评价
烟花算法 ·2010年被首次提出 ·核心思想∵模拟烟花的爆炸来寻求最优解; ·每一个烟花的爆炸被视为对局部区域的一次搜索。 好的爆炸 (exploitation:在狭窄的爆炸振幅之内 随机地产生大量的花火个体( (spark individuals)o ★ 差的爆炸 (exploration在宽广的爆炸振幅之内 随机地产生少量的花火个体。 ★ 烟花个体 由烟花个体( firework individuals)的 fitness自适应地决定
烟花算法 • 2010年被首次提出； • 核心思想：模拟烟花的爆炸来寻求最优解； • 每一个烟花的爆炸被视为对局部区域的一次搜索。 search space 烟花个体 花火个体 好的爆炸(exploitation): 在狭窄的爆炸振幅之内 随机地产生大量的花火个体(spark individuals)。 差的爆炸(exploration):在宽广的爆炸振幅之内 随机地产生少量的花火个体。 由烟花个体(firework individuals)的fitness自适应地决定
优化框架(烟花算法) 突变花火个体 ★ Search Space Search Space \.o Search Space 白a)随机生成初始烟花种群; (b)爆炸操作产生花火个体和突变操作产生突变花火个体; 从(b)中选择下—代烟花种群,并反复执行(b和()直到终止条件被满足
优化框架(烟花算法) (a) (b) (c) (a) 随机生成初始烟花种群； (b) 爆炸操作产生花火个体和突变操作产生突变花火个体； (c) 从(b)中选择下一代烟花种群，并反复执行(b)和(c)直到终止条件被满足。 突变花火个体
目录 烟花算法 爆炸因子分析及改进 两种新爆炸策略 烟花算法优化多峰问题 基于推测点加速烟花算法 总结
目录 • 烟花算法 • 爆炸因子分析及改进 • 两种新爆炸策略 • 烟花算法优化多峰问题 • 基于推测点加速烟花算法 • 讨论 • 总结
爆炸因子(最小化问题为例 决定每一个烟花个体的爆炸振幅以及生成的花火个体数量 最大的爆炸幅度 ·爆炸振幅 Ai= Ax f(x1)-mn+5 ★ a1(f(x)-ym)+5 ·花火数量 总的花火个体的数量 M=x=m-/a)+ la×M)ifM<axM 体 =1(ma-f()+ and M, round(b x Mn) if bx M<Mi round (M; others 烟花个体 search space ·花火个体生成 ymi:当前种群最优 fitness △=2+m04)是受影响的维度|m:￥前神样最s 0<a<b<1且烟花个体数:n
爆炸因子(最小化问题为例) 决定每一个烟花个体的爆炸振幅以及生成的花火个体数量 search space 烟花个体 花火个体 • 爆炸振幅 • 花火数量 • 花火个体生成 and 𝑘是受影响的维度 最大的爆炸幅度 总的花火个体的数量 y𝑚𝑖𝑛: 当前种群最优fitness ymax: 当前种群最差fitness 0 < a < b < 1 且 烟花个体数：n
Zheng S.Q., Janecek A, Li J.Z. and Tan Y. Dynamic search in fireworks algorithm, 2014 IEEE Congress on Evolutionary Computation, Beijing, China, pp. 3222-3229 July 6-11, 2014) 动态烟花算法( dyn FWA) 增大最优烟花个体爆炸振幅 减小最优烟花个体爆炸振幅 ★ 当最优烟花个体好于 只针对最优烟花个体当最优烟花个体差于 最优花火个体 最优花火个体 通过动态改变最优烟花的爆炸振幅来提高搜索效率
动态烟花算法(dynFWA) 只针对最优烟花个体 增大最优烟花个体爆炸振幅 减小最优烟花个体爆炸振幅 当最优烟花个体好于 最优花火个体 当最优烟花个体差于 最优花火个体 通过动态改变最优烟花的爆炸振幅来提高搜索效率 Zheng S.Q., Janecek A., Li J.Z. and Tan Y. Dynamic search in fireworks algorithm, 2014 IEEE Congress on Evolutionary Computation, Beijing, China, pp. 3222-3229 (July 6-11, 2014)
Jun Yu and hideyuki Takagi, Acceleration for Fireworks Algorithm Based on Amplitude Reduction Strategy and Local Optima-basec election Strategy, 8th International Conference on Swarm Intelligence, Fukuoka, Japan, pp 477-484 ( uly 27-August 1, 2017) 爆炸振幅递减策略 ) if FEcur <c A max Others exploitation exploration Anax:最大的爆炸幅度 Ear:当前已评价的 fitness数 FE:最大的 fitness/h数 ★ ★ ★ C常数 FEcur 2C* FEmar maximum amplitude gradually reduced amplitude unchanged 不论烟花个体的 fitness6优劣,他们的爆炸振幅逐次递减 注:烟花个体产生的花火数量依然由他们的 fitnessE适应地决定
爆炸振幅递减策略 不论烟花个体的fitness的优劣，他们的爆炸振幅逐次递减 𝐴𝑖 = ቐ 𝐴𝑚𝑎𝑥 ∗ 1 − 𝐹𝐸𝑐𝑢𝑟 𝐹𝐸𝑚𝑎𝑥 , 𝑖𝑓 𝐹𝐸𝑐𝑢𝑟 < 𝑐 ∗ 𝐹𝐸𝑚𝑎𝑥 𝐴𝑚𝑎𝑥 ∗ 1 − 𝑐 , 𝑂𝑡ℎ𝑒𝑟𝑠 𝐴𝑚𝑎𝑥 : 最大的爆炸幅度 𝐹𝐸𝑐𝑢𝑟 : 当前已评价的fitness次数. 𝐹𝐸𝑚𝑎𝑥 : 最大的fitness次数. 𝑐: 常数 注：烟花个体产生的花火数量依然由他们的fitness自适应地决定 exploitation → exploration Jun Yu and Hideyuki Takagi, "Acceleration for Fireworks Algorithm Based on Amplitude Reduction Strategy and Local Optima-based Selection Strategy," 8th International Conference on Swarm Intelligence, Fukuoka, Japan, pp.477-484 (July 27 - August 1, 2017)