摘要
文中作者主要针对一类组合优化问题,分析了伊藤算法的收敛性理论和达到最优解的期望运行时间.首先将研究的组合优化问题转化为图模型,在图模型的基础上研究了伊藤算法的各种算子设计方法,阐明了伊藤算法的漂移算子、波动算子的寻优过程,给出了几种算子转移所服从的概率分布;然后在转移概率的基础上,利用离散鞅的极限分布给出了伊藤算法几乎必然收敛行为分析;最后研究了1个粒子的情况下,伊藤算法达到最优解的期望运行时间的上界,其取决于粒子半径的设置,并结合具体的参数设置,分析了伊藤算法参数选择的重要性.
This paper provides some theoretical results on the convergence and runtime of ITO algorithm for one class of combinatorial optimization.First the combinatorial optimization problem is shift to directed graphic model,which is the base to design the operator of ITO algorithm.The transform probability of wave operator and move operator is studied in detail.The analysis yields insight into the optimized process.The almost sure convergence to the global optimum is obtained by changing the search process of ITO algorithm to the discrete sub-martingale.Furthermore,the expected time need by 1 particle ITO algorithm for the considered class of combinatorial optimization is analyzed,and for the One-Max problem,the runtime is linear to the problem size.
出处
《计算机学报》
EI
CSCD
北大核心
2011年第4期636-646,共11页
Chinese Journal of Computers
基金
国家自然科学基金项目(60873114)
中国博士后基金(20080440073)
天津市自然科学基金(09JCYBJC27700)
晨光计划(20065004116-03)资助
关键词
伊藤算法
收敛性分析
运行时分析
波动算子
漂移算子
ITO algorithms
convergence analysis
runtime analysis
wave operator
move operator
