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