约束优化问题的改进混合遗传算法.pdf

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

1、过程控制化工自动化及仪表，2010，37(7)：13—16ControlandInstrumentsinChemicalIndustry约束优化问题的改进混合遗传算法范小勤8，汪小红6，尹洁8(广州番禺职业技术学院a．基础课部．b．机械与电子系，广州511483)摘要：提出了罚函数与修复的混合策略，改进了罚函数，给出了种群早熟度评价指标，对遗传算法的交叉算子进行了改进，解决了单一使用罚函数方法求约束优化问题所遇到的困难，方便了遗传算法在约束优化问题中的应用，提高了遗传算法在机械及工程中应用的适应性。数值实验证明，该方法比传统的遗传算法处理约束优化问题效率高

2、。关键词：约束优化；罚函数；修复；遗传算法中图分类号：0221文献标识码：A文章编号：1000-3932(2010)07-0013．．041引言在机械、化工及其它工程等应用中，常涉及到优化问题。对很多问题进行数学建模后，都可以抽象为一个数值约束函数的优化问题。一般而言，约束函数的优化问题可以描述为下列数学模型：Minf(z)S．t．hi(z)=0(i=1，2。⋯，＆)既x)90(，：1,2，⋯，m)(1)算=(善，，z2，⋯，at：。)Ⅳ?≤≈≤Z实践表明，遗传算法求解约束优化问题的计算效率很高。在使用遗传算法优化时，必须对这些约束条件进行处理。目前还没有

3、处理约束问题的一般方法，需要根据具体问题具体分析，常用如下策略：罚函数策略、改进遗传算子策略、修复策略，等等⋯。罚函数策略是通过对不可行解施加某种惩罚，使目标惩罚值增大(求极小值问题)，经过不断迭代，种群逐渐收敛于可行解。但这类算法中惩罚函数及惩罚系数的选取较困难，如静态罚函数法、动态罚函数法等。改进遗传算子策略是设计针对问题的表达方式以及专门的遗传算子来维持染色体的可行性，从而解决可行性问题的一个合理办法。许多领域中的实际工作者采用这一策略构成了非常成功的遗传算法，这已经是一个十分普遍的趋势。但是该方法遗传搜索受到了可行域的限制。修复策略是通过一些修复法

4、将随机产生的不可行解及遗传算子作用后的不可行解修复成可行解，或将一定比例的不可行解按某种原则用可行解取代。与改变算子法类似，这类算法的缺点是修复法依赖于所求解的问题，对于具有复杂约束的优化问题，设计修复算法较困难。如上所述，处理约束优化问题的方法众多，各有优缺点。总体上来说，就通用性而言，罚函数法是处理约束优化问题最常用的方法，本质上它是通过惩罚不可行解约束问题转化为无约束问题。在约束算法中，惩罚技术用来在每一代的种群中保持部分不可行解，使遗传搜索可以从可行域和不可行域两边来达到最优解。惩罚策略的关键问题是如何设计一个惩罚函数P(算)，从而能有效地引导遗传

5、搜索达到解空间的最好区域。2罚函数的构造罚函数的基本思想：对在解空间中无对应可行解的个体，计算其适应值时，给一罚函数，以降低该个体的适应值，使该个体遗传到下一代的机会减少‘2

6、。2．1外点罚函数法外点罚函数是通过一系列的罚因子，求罚函数的极值点来逼近原约束问题的最优点。因为它是从可行域外部向约束边界靠拢的，所以称外点罚函数法。外点罚函数法既可以求含等式约束优化问题，还可以求混合约束优化问题。对于模型(1)通过引入罚函数，可转化为如下无约束优化问题：‘“Minfix)+肘∑

7、jl：(x)+肘∑[min(O，g；(z))]2(2)2．2内点罚函数法内点罚函数法

8、的基本思想是用可行域内的点来逼近最优解，要求初始点位于可行域内，这样即使经过有限步后没有求得最优解，但可以将其作为近似最优解。对于约束优化模型(1)，用内点罚函数法，先处理约束等式。收稿日期：2010-06-01(修改稿)·14·化工自动化及仪表第37卷h。(石)=0可以表达为h．(z)+占≥0(i=1，2，⋯，t)(3)一h，(*)+占≥0(i=1，2，⋯，^)(4)式中：占——一个很小的实数。将上述不等式与模型(1)中的gJ(戈)≥0结合起来，还记为g，(茗)≥0，此时i=1，2，⋯，k，⋯，m+2后，则用内点罚函数法，模型(1)转化为如下无约束优化问

9、题：肘iIlf(z)+卢m善+2i丽12．3混合罚函数法㈦(5)混合罚函数法综合了外点罚函数的初始点可以任取和内点罚函数法的可以求近似最优解的优点，将约束问题转化为无约束问题。模型(1)采用此法，转化为如下无约束优化问题：，^m川甜@)+．寿荟卟小)]2+rj；1南～fr．}=li‘8I、冉’2．4罚函数的改进为了很好地解决罚因子的确定，将罚因子选为变量戈的函数。为了加快收敛速度，不仅采用外插法，并借鉴“多级惩罚”思想口1，对违反约束较大的给予较大的惩罚而违反约束较小的给予较小的惩罚，改进惩罚函数为：p(x)=∑Mihi(z)1+∑Njmax{o，一gJ(

10、石)}其中，Mi：T———掣旦L—一(i：1，2，⋯，^)∑Ihi