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

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

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