伊藤算法关键技术研究

论文摘要

伊藤算法以描述布朗运动的伊藤随机过程为基础,是一类新型的元启发式进化算法,其关键问题是漂移算子和波动算子的设计。把伊藤随机过程映射为优化算法,一方而驱使每个粒子能在局部空间内进行搜索寻优,这就是波动算子的设计问题；另一方面驱使粒子群朝着最优解的方向前进,即伊藤过程的宏观趋势项漂移算子的设计问题。伊藤算法在数值优化问题的求解方而有很好的效果,本文以TSP问题为例,研究其求解组合优化问题,提出邻域最优解相关性度量方法,以此为基础,讨论了伊藤算法中漂移算子和波动算子的设计、粒子半径计算方法以及吸引点的选取等,分析了算法在不同参数取值情况下的算法性能以及种群多样性。试验结果表明伊藤算法对对称TSP问题的求解获得了较好的结果,尤其是结合局部搜索算法后其性能得到了很大程度的改进。进一步从理论上分析其收敛性及获得最佳解的平均期望时间。采用随机过程中的鞅理论、马氏过程综合分析单个粒子和粒子系统的动力学行为,证明了伊藤算法的强收敛性。结合图模型得到了伊藤算法在求解一类组合优化问题时期望的时间上界,考虑在参数设置情形下算法功能的变化,演化算法和遗传算法分析中的一些理论可以移植到伊藤算法,从而使其收敛性理论进一步得到丰富。结合CMA-ES等演化策略的思想,在优化基本伊藤算法数学模型和流程的基础上,改进了算法模型的描述,提出了新的离散型伊藤微分公式,即采用离散化的伊藤随机微分公式来描述伊藤算法的迭代过程。基于该模型,我们设计了一种高效的伊藤算法,数值试验表明,改进的算法增强了粒子系统的多样性,更适应于求解复杂函数优化问题。对于有噪声污染的函数优化问题,分析了传统优化方法应用于随机优化存在的问题,针对这些问题,提出了融合元模型的伊藤算法。其中噪声机制的克服不需要模型多次运行,直接基于种群来对函数的Landscape进行平滑处理,从而利用算法的种群特性来降低函数的噪声。试验结果表明：对于小噪声而言,CMA-ES和ITO-MR算法性能相当,对于中等噪声和大噪声而言,ITO-MR算法具有更优的噪声克服性能,而且求解精度高,收敛速度快。

论文目录

• 摘要
• Abstract
• 1 引言
• 1.1 背景和意义
• 1.2 元启发式算法研究现状
• 1.3 主要工作和创新点
• 1.4 论文的组织结构
• 2 伊藤算法及其理论分析
• 2.1 伊藤算法的基本思想
• 2.1.1 伊藤过程
• 2.1.2 伊藤过程的抽象
• 2.1.3 伊藤算法
• 2.1.4 伊藤算法的框架
• 2.1.5 伊藤算法理论描述
• 2.2 伊藤算法关键算子设计
• 2.2.1 粒子半径
• 2.2.2 漂移算子
• 2.2.3 波动算子
• 2.2.4 环境温度变化的设计
• 2.2.5 粒子吸引点的设计
• 2.3 伊藤算法与其他算法的异同
• 2.3.1 初始化策略
• 2.3.2 抽样化策略
• 2.3.3 生成策略
• 2.4 本章小结
• 3 求解TSP问题的伊藤算法与性能分析
• 3.1 引言
• 3.2 组合优化问题及其有向图模型
• 3.3 TSP问题及其搜索空间的特征
• 3.3.1 空间相关性度量搜索
• 3.3.2 最优解的邻域结构分析
• 3.4 伊藤算法相关参数的设计与分析
• 3.4.1 算法思想及流程介绍
• 3.4.2 粒子半径设计
• 3.4.3 波动算子设计
• 3.4.4 漂移算子设计
• 3.4.5 波动的最大和最小强度的选取
• 3.4.6 退火表设计
• 3.5 参数敏感度配置及种群多样性实验
• 3.5.1 波动下界和上界设置的影响
• 3.5.2 全局漂移策略和局部漂移策略的影响
• 3.5.3 种群多样性度量及分析
• 3.6 实验结果及分析
• 3.6.1 不同算法的对比实验
• 3.6.2 融合局部搜索技术的伊藤算法
• 3.7 收敛性及时间复杂性分析
• 3.7.1 收敛性分析
• 3.7.2 时间复杂性分析
• 3.8 本章小结
• 4 无噪声环境下伊藤算法性能分析
• 4.1 引言
• 4.2 改进的伊藤算法
• 4.2.1 伊藤算法新的描述模型
• 4.2.2 选择漂移吸引点
• 4.2.3 调节扩散系数矩阵
• 4.3 在BBOB算法测试平台中的实验
• 4.3.1 参数设置
• 4.3.2 实验步骤
• 4.4 实验仿真结果及分析
• 4.5 本章小结
• 5 有噪声环境下伊藤算法性能分析
• 5.1 引言
• 5.2 协方差矩阵自适应进化策略
• 5.3 噪声模型分析
• 5.4 融合元模型的伊藤算法
• 5.4.1 ITO-MR算法思想
• 5.4.2 基于元模型噪声克服机制
• 5.5 实验仿真过程
• 5.5.1 参数设定
• 5.5.2 实验结果及分析
• 5.6 本章小结
• 附图
• 6 总结与展望
• 6.1 主要研究工作
• 6.2 展望
• 作者在攻读博士学位期间发表的文章
• 参考文献
• 致谢