摘要：针对伊藤算法在求解离散组合优化问题时效率较低、收敛性较差等缺陷,本文提出的改进伊藤算法引入了协同扩散过程的漂移系数,采用局部搜索能力强的爬山法确定波动系数,将漂移和波动同步进行,当找到可行解之后再进行一定程度的波动.为了验证算法的有效性,将改进后的伊藤算法用于求解带软时间窗的车辆路径问题.仿真结果表明,改进后的算法效率更高,收敛速度更快,算法稳定性和健壮性也更好.此外,本文还根据马尔科夫链移向吸引元的性质及其各状态之间的转换关系,探讨了构造伊藤随机微分方程的马尔科夫链近似模拟算法及其收敛性证明.

关键词：伊藤算法 漂移算子 波动算子 收敛性分析 带软时间窗车辆路径问题 

单位：武汉大学计算机学院 湖北武汉430079 河池学院计算机与信息工程学院 广西宜州546300 广西混杂计算与集成电路设计分析重点实验室 广西南宁530006