计算机应用 ›› 2016, Vol. 36 ›› Issue (9): 2416-2421.DOI: 10.11772/j.issn.1001-9081.2016.09.2416

• 先进计算 • 上一篇    下一篇

基于改进Markov邻域的非线性0-1规划智能算法加速策略

李维鹏, 曾静, 张国良   

  1. 火箭军工程大学 控制工程系, 西安 710025
  • 收稿日期:2016-02-17 修回日期:2016-03-18 出版日期:2016-09-10 发布日期:2016-09-08
  • 通讯作者: 李维鹏
  • 作者简介:李维鹏(1992-),男,湖北武汉人,硕士研究生,主要研究方向:最优估计、移动机器人基于视觉的同时定位与地图创建;曾静(1973-),女,四川金堂人,副教授,博士,主要研究方向:最优估计、运筹学;张国良(1970-),男,四川金堂人,教授,博士,主要研究方向:智能机器人、先进控制、组合导航。

Intelligent algorithm acceleration strategy for nonlinear 0-1 programming based on improved Markov neighborhood

LI Weipeng, ZENG Jing, ZHANG Guoliang   

  1. Department of Control Engineering, Rocket Engineering University, Xi'an Shaanxi 710025, China
  • Received:2016-02-17 Revised:2016-03-18 Online:2016-09-10 Published:2016-09-08

摘要: 大规模非线性0-1规划问题求解时间较长,通过分析非线性0-1规划问题特点及算法寻优的Markov过程,提出一种基于改进Markov邻域的智能算法加速策略。首先,根据0-1规划问题解特点给出了非线性0-1规划问题的改写模型;随后,基于该模型给出了改进的Markov邻域,并推导和证明了改进邻域下任意两个状态之间的可达概率及其条件;最后,通过进一步分析非线性0-1规划模型并融合所提出的改进邻域,设计了采用Markov过程的智能算法的约束条件和目标函数递推更新策略对算法进行加速。采用不同算例进行多次测试,结果表明,在保持加速算法与原算法寻优效果相当的前提下,该策略对多种智能算法的寻优效率均有不同程度的提升。

关键词: 非线性0-1规划, Markov邻域, 智能算法加速, 递推更新

Abstract: In order to reduce the time consumption in solving the problem of large-scale nonlinear 0-1 programming, an intelligent algorithm acceleration strategy based on the improved Markov neighborhood was presented by analyzing the characteristics of nonlinear 0-1 programming and the Markov process of intelligent algorithm. First, a rewritten model of nonlinear 0-1 programming problem was given. Next, an improved Markov neighborhood was constructed based on the rewritten model, and the reachable probability between two random statuses with its conditions under the improved Markov neighborhood was derived and proven. With a further analysis of the structure of nonlinear 0-1 programming together with the improved Markov neighborhood, a recursive updating strategy of the constraint and objective function was designed to accelerate the intelligent algorithms. The experimental results illustrate that the proposed strategy improves the operating efficiency of intelligent algorithms while keeping a correspondence with the original algorithms in search results.

Key words: nonlinear 0-1 programming, Markov neighborhood, intelligent algorithm acceleration strategy, recursive update

中图分类号: