知识卡片

普通读书笔记卡 · 3756.d

EDA收敛结论依赖证明条件

理解等级:高级

EDA 的全局收敛结论不能脱离证明假设引用:本节的一般结论针对无穷大种群及比例、截断或二元锦标赛选择;PBIL、UMDA、FDA 又各有算法与问题类型限定,例如 FDA 的全局最优证明针对可加性分解问题。应用到有限种群或其他目标函数前,应先核对假设是否成立。

几个条件的含义:

  • 无穷大种群:分析时不考虑有限样本带来的抽样误差,因此结论不能直接搬到实际的有限种群;
  • 比例选择:按适应度占总和的比例作为被选中的概率;
  • 截断选择:只取适应度排在前面一定比例的个体;
  • 二元锦标赛选择:每次随机抽两个个体,留下较优者;
  • 可加性分解问题:目标函数能写成若干个只含少量变量的子函数之和。
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 9 章《9.3 基于分布估计算法的收敛性分析及多目标优化问题》(源文件:`_epub-src/EPUB/xhtml/chapter9_0005.xhtml`) - 结论依据:本节将一般 EDA 结论置于无穷大种群和指定选择机制下,并单独说明 PBIL、UMDA、FDA 的分析;FDA 的全局最优结论限定在可加性分解问题。 - 原始内容:针对一般的EDA,Zhang等证明了EDA在种群规模无穷大时的收敛性,认为采用这3种选择机制(比例选择、截断选择、二元锦标赛选择)选择优势群体时,该算法可以达到全局收敛 [ 5 6 - 5 7 ] 。