计算机科学与探索 ›› 2013, Vol. 7 ›› Issue (9): 854-864.DOI: 10.3778/j.issn.1673-9418.1306004

• 学术研究 • 上一篇    

求解非线性混合整数规划的算法设计与仿真

王纯子1+,郭  伟1,张  斌2   

  1. 1. 西安工程大学 管理学院,西安 710048
    2. 西安建筑科技大学 管理学院,西安 710055
  • 出版日期:2013-09-01 发布日期:2013-09-04

Algorithm Design and Simulation of Solving Nonlinear Mixed Integer Programming Problem

WANG Chunzi1+, GUO Wei1, ZHANG Bin2   

  1. 1. School of Management, Xi’an Polytechnic University, Xi’an 710048, China
    2. School of Management, Xi’an University of Architecture and Technology, Xi’an 710055, China
  • Online:2013-09-01 Published:2013-09-04

摘要: 针对目标函数具有多峰值、变量规模较大的非线性混合整数规划问题,设计了一种序贯选择式的扩展时间Petri网模型,并给出了该模型的构建算法。改进了传统的蚁群算法,并引入遗传演化的思想,设计了局部和全局演化算子,提出了基于非线性混合整数规划问题的最优解搜索算法。该算法解决了离散变量和连续变量的进化问题,同时保证了搜索广度和收敛速度。仿真结果表明,该算法在求解准确性、普适性、稳定性以及收敛速度方面具有更好的性能,适应于解决复杂的大规模非线性混合整数规划问题。

关键词: 非线性混合整数规划, 扩展时间Petri网, 蚁群算法, 遗传算法, 最优路径搜索

Abstract: For the nonlinear mixed integer programming problem with multi-peak objective function and large-scale variables, this paper designs a sequentially selected extended time Petri net (ETPN) model, and proposes its modeling algorithm. This paper also improves the traditional ant colony algorithm and designs partial and overall evolution operators by combining with genetic algorithm, then proposes the optimal searching algorithm based on nonlinear mixed integer programming problem, which solves the evolution problem of both discrete variables and continuous variables, as well as ensures the search range and convergence rate. The result of simulation shows that the new solving algorithm of nonlinear mixed integer programming has better accuracy, universality, stability and high convergence rate, which is suitable for complicated and large-scale questions.

Key words: nonlinear mixed integer programming, extended time Petri net, ant colony algorithm, genetic algorithm, optimization path search