尜) PEKING UNIVERSITY 信息利用视角下的烟花算法研究 Research on Fireworks algorithms from the perspective of Information Utilization 北京大学计算智能实验室 李逸峰 运大学计算智能实验蜜 ma teingenee Laborales, Peng每y
信息利用视角下的烟花算法研究 Research on Fireworks Algorithms from the Perspective of Information Utilization 北京大学 计算智能实验室 李逸峰 1
目录 1引言 2信息利用与信息利用率 °3骨干烟花算法 4烟花个体的信息挖掘 °5烟花群体的信息交互 ·6总结 北示大旁计算智能实验蜜
目录 • 1 引言 • 2 信息利用与信息利用率 • 3 骨干烟花算法 • 4 烟花个体的信息挖掘 • 5 烟花群体的信息交互 • 6 总结 2
目录 1引言 1.1优化问题 -1.2烟花算法简介 2信息利用与信息利用率 °3骨干烟花算法 4烟花个体的信息挖掘 °5烟花群体的信息交互 ·6总结 北示大旁计算智能实验蜜
目录 • 1 引言 – 1.1 优化问题 – 1.2 烟花算法简介 • 2 信息利用与信息利用率 • 3 骨干烟花算法 • 4 烟花个体的信息挖掘 • 5 烟花群体的信息交互 • 6 总结 3
1.1优化问题 不失一般性,考虑最小化问题 mines.f(X) 其中Ω叫作定义域,搜索空间,候选集合或可行堿;∫叫作目标函教,损失函数, 效用函数或评估函数;f(X)叫作评估值或者适应度值。 很多实际应用中的优化问題其内在结构是未知的,这样的优化问題被称为黑箱 优化问題。黑箱优化问題不能通过基于梯度的方法解决。 北示大旁计算智能实验蜜
1.1 优化问题 • 不失一般性，考虑最小化问题 • 其中Ω叫作定义域，搜索空间，候选集合或可行域；f叫作目标函数，损失函数， 效用函数或评估函数；f(x)叫作评估值或者适应度值。 • 很多实际应用中的优化问题其内在结构是未知的，这样的优化问题被称为黑箱 优化问题。黑箱优化问题不能通过基于梯度的方法解决。 4
1.2烟花算法简介 烟花算法是谭营和朱元春在2010年正式提出的一种新型进化算法。 宅把烟花爆炸的过程抽象成搜索空间中寻优的过程。 相比于其他进化算法,它具有独特的爆炸搜索方式,以及竞争和合作共存的独 特算法框架。 FWA 火花 下一代花 爆炸搜 北示大旁计算智能实验蜜
1.2 烟花算法简介 • 烟花算法是谭营和朱元春在2010年正式提出的一种新型进化算法。 • 它把烟花爆炸的过程抽象成搜索空间中寻优的过程。 • 相比于其他进化算法，它具有独特的爆炸搜索方式，以及竞争和合作共存的独 特算法框架
1.2烟花算法简介 烟花算法主要通过迭代“烟花爆炸产生火花” 和“从火花中选出烟花”这两个步骤来使烟花 种群的适应度值越来越好。 初始化烟花 乞既具有进化算法中的选择(竞争)机制,也 爆炸产生火花 具有群体智能中的信息交互(合作)机制。 变异 从火花中选出下一代烟花 北示大旁计算智能实验蜜
1.2 烟花算法简介 • 烟花算法主要通过迭代“烟花爆炸产生火花” 和“从火花中选出烟花”这两个步骤来使烟花 种群的适应度值越来越好。 • 它既具有进化算法中的选择（竞争）机制，也 具有群体智能中的信息交互（合作）机制。 6 初始化烟花 变异 从火花中选出下一代烟花 爆炸产生火花
目录 2信息利用与信息利用率 2.1信息利用 2.2信息利用率 2.3信息利用率的理论分析 2.4经典算法的信息利用率与性能 3骨干烟花算法 4烟花个体的信息挖掘 °5烟花群体的信息交互 ·6总结 北示大旁计算智能实验蜜
目录 • 1 引言 • 2 信息利用与信息利用率 – 2.1 信息利用 – 2.2 信息利用率 – 2.3 信息利用率的理论分析 – 2.4 经典算法的信息利用率与性能 • 3 骨干烟花算法 • 4 烟花个体的信息挖掘 • 5 烟花群体的信息交互 • 6 总结 7
2.1信息利用 信息的管理与利用是黑箱优化的核心。 一全部信息来自于采样点的评估值 算法核心是根据历史信息确定下一步的采样分布 群体优化:群体是历史采样信息的载体,利用群体的信息生成下代个体 只有随机搜索不利用信息、。很多改进算法都声称自己比原来算法更多/更合理 地利用信息。 信息利用的具体方法唯以比较,我们以信息利用的比例切入研究 北示大旁计算智能实验蜜
2.1 信息利用 • 信息的管理与利用是黑箱优化的核心。 –全部信息来自于采样点的评估值 –算法核心是根据历史信息确定下一步的采样分布 • 群体优化：群体是历史采样信息的载体，利用群体的信息生成下代个体 • 只有随机搜索不利用信息。很多改进算法都声称自己比原来算法更多/更合理 地利用信息。 • 信息利用的具体方法难以比较，我们以信息利用的比例切入研究 8
22信息利用率 信息利用率=利用的信息/获得的信息、。 如果一个算法评估了四个点,然后比较其中两个点的适应度值的大小来决定下 次评估的点,那么大致可以认为它利用了1bit信息。而宅获得的信息是 4log|Y,其中Y是值域。信息利用率就是1/4og|Y| 利用的信息=下一次采样分布(方法)的不确定性(熵 °获得的信息=评估值的不确定性 但是由于评估之间未必相互独立,而且进化算法一般采取迭代结构,因此定义 会更复杂。 北示大旁计算智能实验蜜
2.2 信息利用率 • 信息利用率=利用的信息/获得的信息。 • 如果一个算法评估了四个点，然后比较其中两个点的适应度值的大小来决定下 一次评估的点，那么大致可以认为它利用了1bit信息。而它获得的信息是 4log|Y|，其中Y是值域。信息利用率就是1/ 4log|Y|。 • 利用的信息=下一次采样分布（方法）的不确定性（熵） • 获得的信息=评估值的不确定性 • 但是由于评估之间未必相互独立，而且进化算法一般采取迭代结构，因此定义 会更复杂。 9
2.2信息利用率 更新采样分布 更新采样分布 更新采样分布 X1 采样 22……X2 Y 目标函数的结构 其中X表示采样得到的点,Y1表示点对应的评估值,Z表示采样分布 北示大旁计算智能实验蜜
2.2 信息利用率 • 其中Xi表示采样得到的点，Yi表示点对应的评估值，Zi表示采样分布 10