约束优化问题的遗传算法求解

《约束优化问题的遗传算法求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第1期西北农林科技大学学报(自然科学版)Vol.33No.12005年1月Jour.ofNorthwestSci-TechUniv.ofAgri.andFor.(Nat.Sci.Ed.)Jan.2005X约束优化问题的遗传算法求解宋松柏,蔡焕杰,康艳(西北农林科技大学水利与建筑工程学院,陕西杨凌712100)[摘要]应用遗传算法基本原理,采用锦标赛选择、算术交叉、均匀交叉、均匀变异和非均匀变异算子,设计了一般非线性规划和整数规划问题的通用求解算法,应用Matlab6.0编制了相应的求解软件。实例测试结果表明,该算法可以应用于一般的非线性规划和整数规划问题。

2、[关键词]非线性规划;整数规划;约束优化;遗传算法[中图分类号]O224[文献标识码]A[文章编号]1671-9387(2005)01-0150-05目前,应用遗传算法(GeneticAlgorithm,GA)往是根据具体优化模型中约束条件的特征,选择适处理有约束优化问题尚无统一的方法。常用的处理合的遗传算子或设计相应的遗传算子,选用上述方约束方法有修复不可行解法、改变遗传算子法和惩法进行优化问题的求解。本研究基于Fernando[1～6][7]罚函数法。修复不可行解法的主要缺点是不同Jimnez的研究,对一般非线性规划(Nonlinear类的求解问题有不同的修复

3、算法,修复算法依赖于ProgrammingProblem,NPP)和整数规划(Integral所求问题;改变遗传算子法在求解复杂的非线性优ProgrammingProblem,IPP)约束优化问题的GA求化问题及设计相应的遗传算子时是非常困难的;惩解进行探讨,应用Matlab6.0编制了相应的求解软罚函数法针对不可行解的个体,在计算个体适应度件。以期为非线性规划和整数规划问题求解提供参时,施加某种惩罚,降低该个体的适应度,使其被遗考。传到下一代群体的机会减少,经过若干次迭代计算,1NPP和IPP问题求解的标准形式种群最后逐渐收敛于可行解。因此,实际中应用GA求解约

4、束优化问题时,往NPP和IPP问题求解的标准形式可以表示为:目标函数Minf(x1,⋯,xj,⋯,xn)约束条件gi(x1,⋯,xj,⋯,xn)≤0,i=1,2,⋯,m(1)lj≤xj≤uj,j=1,2,⋯,n式中,m,n分别为约束数和决策变量数;x1,⋯,xj,若约束为gi(x1,⋯,xj,⋯,xn)≥0的形式,两边⋯,xn为决策变量,对于整数规划,取值为介于[lj,同乘以-1,则可转换为-gi(x1,⋯,xj,⋯,xn)≤0uj]的整数值,其中[lj,uj]为变量的取值范围;gi(x1,的形式。⋯,xj,⋯,xn)为不等式约束左边项,左边项可以是(3)约束为“

5、=0”的形式线性,也可以是非线性。若约束为gi(x1,⋯,xj,⋯,xn)=0的形式,可用采用以下方法将一般模型转换为标准形式。gi(x1,⋯,xj,⋯,xn)≤02个约束替代,对于(1)目标函数最大化gi(x1,⋯,⋯,xj,⋯,xn)≥0对于目标函数最大化问题,可用其负值的最小gi(x1,⋯,xj,⋯,xn)≥0,可用方法(2)转换为化问题替代,求解后,将结果再反号,则为原目标函-gi(x1,⋯,xj,⋯,xn)≤0,因此,gi(x1,⋯,xj,⋯,数的最大化值。即Maxf(x1,⋯,xj,⋯,xn)=gi(x1,⋯,xj,⋯,xn)≤0xn)=0最后被转换为

6、。-{Minf(x1,⋯,xj,⋯,xn)}。-gi(x1,⋯,xj,⋯,xn)≤0(2)约束为“≥0”的形式X[收稿日期]2003-12-08[基金项目]国家自然科学基金资助项目(50179031);高等学校全国优秀博士学位论文作者专项基金(200052);西北农林科技大学2004年优秀科研人才专项基金(04ZR014)[作者简介]宋松柏(1965-),男,陕西永寿人,副教授,硕士,主要从事水文水资源研究。E-mail:SSB6533@yahoo.com.cn第1期宋松柏等:约束优化问题的遗传算法求解151s+1。2NPP和IPP问题的GA求解2.1.6选择采用

7、锦标赛选择(TournamentNPP和IPP问题的GA算法步骤如下所述。Selection),首先在[1,Popsize]内随机产生tourn个2.1NPP问题的GA算法个体序号{k1,k2,⋯ktourn},按照最优保存策略2.1.1初始化群体在满足式(1)约束条件的解空(ElitismStrategy)选取个体mate1和mate2。本文约0间,选择一个初始解x=(x1,x2,⋯,xj,⋯,xn)作为定最优保存策略的原则为:¹2个可行解个体,其初始群体个体Start-population(i),i=1,2,⋯,评价适应度值小的个体优于评价适应度值大的个Pop

8、size。