比例选择策略下分布估计算法的收敛性分析

摘要

分布估计算法(EDA)是一种新型的随机优化算法,迄今为止,其改进算法和应用成果丰硕,但理论研究相对较少.针对这一现状,本文从概率统计的角度研究了分布估计算法中与收敛相关的问题.从数学上给出了算法中有关收敛性的具体定义和严格证明,论文主要内容如下. 1.研究EDA理论模型的收敛性及收敛速度.具体结论有,比例选择EDA能依概率收敛到全局最优解集.离散情形下, EDA收敛速度由目标函数在解空间上的第二大取值与最大值的比值决定;连续情形下,若目标函数连续, EDA的收敛速度由最优解集的e邻域内的一固定点取值与其邻域外的最大值的比值决定.针对实际应用中通用的构建概率模型的迭代方法,利用大数定律从理论上分析了该方法的可行性,并通过数值实验验证了该迭代方法的有效性. 2.基于马尔可夫链理论,研究了有限种群EDA进化过程中的种群极限行为.对于经典的有限种群比例选择分布估计算法(EDA-FP-PS),证明了它不能依概率收敛到全局最优解集,但种群收敛到最优解集的概率存在着上下界,并给出了其表达式.对于本文改进的EDA-FP-PS算法,证明了它能依概率收敛到全局最优解集.其次,对算法中种群达到最优解的首中时进行了研究,改进的EDA-FP-PS的平均首中时存在着上下界,而经典EDA-FP-PS首中时的无条件期望无界. 3.通过数值实验对理论分析结果进行了简单验证,实验结果与理论分析结论基本一致.实验结论有:对于同一测试函数,当种群规模达到一定程度时(至少为问题规模的8倍),不同问题规模下最优概率(种群收敛到最优解集的频率)的差异在10-2以内;对于不同的测试函数,大致上符合种群规模与问题规模的比值越大,最优概率越大,而达到概率1时的临界规模比有所差别.

目录

声明

第1章 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 研究内容及结构

第2章 分布估计算法

2.1 分布估计算法原理

2.2 选择策略

2.3 离散型分布估计算法的分类

2.4 本章小结

第3章 分布估计算法理论分析

3.1 理论模型描述

3.2 收敛性分析

3.3 收敛速度分析

3.4 概率迭代方法

3.5 本章小结

第4章 基于马尔可夫的EDA收敛性研究

4.1 马尔可夫链基础理论

4.2 EDA-FP-PS模型描述

4.3 EDA-FP-PS的收敛性分析

4.4 EDA-FP-PS的平均首中时

4.5 数值模拟

4.6 本章小结

第5章 总结与展望

5.1 主要结论

5.2 展望

致谢

参考文献

攻读硕士学位期间发表论文