一种求解非线性整数规划的分布估计算法.doc

一种求解非线性整数规划的分布估计算法.doc一种求解非线性整数规划的分布估计算法摘要:分布估计算法是遗传算法和统计学习的结合,通过统计学习的手段建立解空间内个体分布的概率模型,对概率模型随机采样产生新的群体,如此反复进行,实现群体的进化。将分布估计算法推广应用到整数规划的解空间中,提出一种求解整数规划的新算法,经数值实验表明该算法有效。?? 关键词:分布估计算法;非线性整数规划;概率模型;解空间?? 中图分类号:O224;TP183文献标识码:B文章编号:1004-373X(2008)10-129-03?オ? MethodofEstimationDistributionAlgorithmforSolvingNonlinearIntegerProgramming?? XIONGShengwu1,LIUMingfang1,LIUXinliang2?? (,WuhanUniversityofTechnology,Wuhan,430070,China;?? ,NationalUniversityofDefenseTechnology,Changsha,410073,China)?オ? Abstract:EstimationofDistributionAlgorithms(EDAs).?? Keywords:estimationofdistributionalgorithms;nonlinearintegerprogramming;probabilitymodel;solutionspace?? 1引言?? 整数规划是数学规划中较复杂的一大类问题。Murty[1]证明了非线性规划问题为NP-hard问题,作为其子集的非线性整数规划也必为NP-hard问题,求解该问题精确解的算法具有指数复杂度。整数规划广泛应用于许多工程领域,如资源管理、生产调度、可靠性优化、目标分配、超大规模集成电路设计等。对于变量规模较小的整数规划,传统的求解方法有分支定界法、割平面法和隐枚举法等。但对于较大规模的问题,传统的方法比较耗时,近年来随着进化计算的发展,许多学者运用遗传算法(GA)、模拟退火算法(SA)、微粒群算法(PSO)、蚁群算法(AA)等方法来求解整数规划问题[2-6]。遗传算法吸取了生物进化和遗传变异论的研究成果,是一种群体性全局寻优方法,但算法执行到一定阶段后向最优解收敛速度缓慢,且遗传算法的性能依赖于遗传因子(选择概率、交叉概率、变异概率、种群规模、染色体长度等)的取值,并且会出现早熟收敛情况。模拟退火算法模拟物质材料的冷却