摘要
提出了一种求解混合整数非线性规划MINLP问题的混合优化算法GASimplex,由遗传算法模块GASolver和单纯形算法模块SimplexSolver两部分组成。该算法首先确定MINLP模型的整数变量和复杂变量,使得固定这些变量后可以将原问题转化为一线性规划子问题,在此基础上应用GASolver实现对整数变量和复杂变量的优化,而其适应函数则可以通过求解编码对应的线性规划子问题SimplexSolver来得到。这样,一方面由于在遗传算法中引入了局部搜索过程,极大增加了GASimplex整体收敛速度,而且对于非凸的MINLP问题,可以在理论上保证得到解的全局最优性;另一方面,模型约束条件是通过SimplexSolver求解得到,故约束条件的存在一般不会增加遗传算法处理的复杂度,可有效的处理约束的MINLP问题。通过对一MINLP模型仿真分析,证明该算法不仅具有很快的收敛速度,而且能得到全局的次最优解,更适合处理一类复杂的MINLP问题。
A new hybrid algorithm, namely the GASimplex, for solving the Mixed Integer Nonlinear Programming （MINLP）problems is proposed. GASimplex involves two interwoven levels of optimization, namely the GASolver （GeneticAlgorithms） and the SimplexSolver （Simplex method）. GASimplex algorithm partitions the MINLP model into two parts by selecting integer variables and complicated variables in model appropriately, thus the complicated variables and integral variables can be optimized using the technique of Genetic Algorithms, while the remainder of primal MINLP model can be transformed into a sub-linear problem that solved by the traditional simplex search method. It means that GASimplex not only can avoid the final solution trapping into one of its local optima, but also can make a good trade off between exploration and exploitation. It is proved that GASimplex algorithm can get a global sub-optimal solution by testing a special MINLP benchmark formulation. Further more, GASimplex also can deal well with the non-convex and non-smooth MINLP model,and more appropriate for solving the large-scale M1NLP problems.
出处
《系统仿真学报》
EI
CAS
CSCD
北大核心
2005年第8期1859-1863,共5页
Journal of System Simulation
基金
863项目(2002AA529170)
国家自然基金(50274057)
关键词
混合整数非线性规划
混合全局优化算法
遗传算法
单纯形方法
整数变
复杂变量
mixed integer nonlinearprogramming
hybrid global optimization
genetic algorithms
simplex method
integer variable
complicated variable
