基于遗传算法的一种新的约束处理方法

基于遗传算法的一种新的约束处理方法

苏勇彦1，王攀1，范衠2

（1武汉理工大学 自动化学院， 湖北 武汉 430070） （2丹麦理工大学 机械系 哥本哈根）

摘 要：本文针对目前的约束处理方法中存在的问题，提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难，使得约束处理问题简单化。实例测试结果表明，该约束处理方法的有效性。

关键词：遗传算法、约束处理、可行解、不可行解、两种群混合交叉

1引言

科学研究和工程应用中许多问题都可以转化为求解一个带约束条件的函数优化问题[1]。遗传算法（Genetic Algorithm）与许多基于梯度的算法比较,具有不需要目标函数和约束条件可微,且能收敛到全局最优解的优点 [2]，因此，它成为一种约束优化问题求解的有力工具。目前，基于GA的约束处理方法有拒绝策略，修复策略，改进遗传算子策略以及惩罚函数策略等。但是这些方法都存在一些问题[3]：修复策略对问题本身的依赖性，对于每个问题必须设计专门的修复程序。改进遗传算子策略则需要设计针对问题的表达方式以及专门的遗传算子来维持解的可行性。惩罚策略解的质量严重依赖于惩罚因子的选取，当惩罚因子不适当时，算法可能收敛于不可行解。

本文针对目前的约束处理方法中存在的问题，提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难，使得约束处理问题简单化。实例测试结果表明，该约束处理方法的有效性。

2约束处理方法描述

2.1单目标有约束优化问题一般形式

maxf(x)

s.t.gi(x)≤0; i=1,2,LL,m1

hi(x)=0; i=m1+1,L,m(=m1+m2) x∈X

nn

这里f;g1,g2,Lgm;hm1+1,hm1+2,L,hm都是定义在E上的实值函数。X是E上的

1

子集，x是n维实向量，其分量为x1,x2,L,xn。上述问题要求在变量x1,x2,L,xn满足约束的同时极大化函数f。函数f通常为目标函数。约束gi(x)≤0;称为不等式约束；约束hi(x)=0;称为等式约束。集合X通常为变量的上下界限定的区域。向量x∈X且满足所有

约束，则称之为问题的可行解。所有可行解构成可行域。否则,为问题的不可行解,所有不可行解构成不可行域。问题的目标是找到一个可行解x使得f(x)≤f(x)对于所有可行解x成立。那么，x为最优解[4]。

2.2算法描述

目前，最常采用的约束处理方法为惩罚函数法。但优化搜索的效率对惩罚因子的选择有

-1-

http://www.paper.edu.cn

明显的依赖性。同时，惩罚因子没有统一的选择标准，使得惩罚因子选择非常困难。

基于惩罚函数的方法，选择是对可行解与不可行解的混合种群进行的。若种群中只有可行解，则不会出现惩罚因子的问题。但若采用拒绝策略，完全拒绝不可行解则大大减少搜索范围，很难收敛到最优解。“既然我们的目标是找到可行的最优解，一定要用对不可行解进行惩罚的方法吗？”[5]正是根据这一思路，本文提出一种既要利用不可行解扩大搜索范围，又不引入惩罚因子的约束优化处理方法。

该方法引入两个种群：可行种群和不可行种群。遗传算法采用实数编码法，对两个种 群进行的交叉操作为：分别从可行种群popf和不可行种群popinf中随机选择一个个体

p1，p2为父代个体进行混合的算术交叉，生成两个新个体c1,c2。采用可行种群与不可行

种群个体进行交叉的目的是扩大搜索空间。对交叉、变异后生成的新个体进行判断，将其分为可行种群和不可行种群，分别对可行种群和不可行种群进行选择操作。

由于与惩罚函数法具有相同的原理，即两种方法都利用不可行解增加搜索范围，同时利用可行解与不可行解之间的交叉操作产生新的解。在现实中存在一大类约束优化问题，其最优解位于约束边界上或附近，及最优点处不等式约束全部或大部分取为等号。因此，采用一种称为凸交叉的算术交叉，算术交叉操作及参数选择如下[4]：

不可行区域D c1=λ1p1+λ1p2， c2=λ1p2+λ2p1，

A可行区域Cλ1+λ2=1， λ1>0,λ2>0

B如右图所示：可行区域的点A与不可行区域点C交叉时，生成的个体在A、C之间的连线上。该交叉方法可以搜索到约束边界附近的点。

如何从交叉和变异中产生的新种群以及交叉变异之前的新种群中找到最优解？这是选择操作要解决的问题。本文的方法是将原始种群分为可行种群和不可行种群，对两种群分别进行选择操作。选择操作实现对个体适应值的评估，通过优胜劣态的进化原理最终收敛到最优解。这种方法就避免了确定惩罚因子带来的困难。

2.3算法流程

step 0：初始化，设置变异概率pm 、可行种群大小和不可行种群大小，根据约束条件对

初始种群中的个体进行判断，将初始种群分为可行种群popf和不可行种群popinf； step 1：对可行种群popf与不可行种群popinf进行混合交叉、变异操作；

step 2：根据约束条件对交叉、变异后生成的新种群中个体进行判断，将种群分为可行种群

popf和不可行种群popinf；

step 3：采用 (µ+λ) 选择策略分别对不可行种群、可行种群进行选择操作；

step 4：判断算法终止条件是否满足？NO：转到step 1；YES：终止程序；

3问题测试及实验结果

数值测试例子

-2-

http://www.paper.edu.cn

问题1[6]

2

maxf(x)=−2x12+2x1x2−2x2+4x1+6x2 s.t. x1+x2≤2

x1+5x2≤5

x1≥0, x2≥0

问题2[4,7]

minf(x)=5.3578547x3+0.8356891x1x5+37.293239x1−40792.141 s.t. 0≤85.334407+0.0056868x2x5+0.00026x1x4−0.0022053x3x5≤92 90≤80.51249+0.0071317x2x5+0.0029955x1x2+0.0021813x3≤110 20≤9.300961+0.0047026x3x5+0.0012547x1x3+0.0019085x3x4≤25 78≤x1≤102

2

2

33≤x2≤45 27≤x3≤45

27≤x4≤45

27≤x5≤45

根据上文提出的约束处理方法，编写matlab程序进行实验，采用进化策略中的(µ+λ)选择方法，对问题1，2求解结果为：

问题1. 初始种群popsize大小为400，可行种群与不可行种群分别为初始种群大小的一半，迭代次数gen为150，变异概率pm为0.05，程序运行10次得到最好解f(x)=7.1611，对应的 变量值为（1.1287， 0.7742）。唐加福等采用混合遗传算法（HGA）得到的最优解7.16085[6]。问题2. 初始种群大小popsize为400，可行种群与不可行种群分别为初始种群大小的一半，迭代次数gen为100，变异概率pm为0.05，程序运行10次得到最好解f(x)=-3.0918e+004， 对应的变量值为（78.3002，33.8606，27.8735，44.8036，42.6653）。与Homaifar,Qi和Lai用基于惩罚策略的遗传算法得到解[8]以及广义简约梯度法（GRG）得到的结果有很大的提高，如下表所示。同时，李敏强、寇纪淞等基于遗传算法的直接比较—比例方法[1]得到结果最好解为-30665.539[9]。通过实验比较可知，该方法是一种很有效的约束处理方法。

表1 算法结果

项目

参考解

遗传算法基于遗传的

全局参考解

遗传算法基于遗传的局部参考解

GRG的解

本文的方法得到的解

f(x)

x1 x2 x3 x4 x5

-30665.5 78.00 33.00 29.995 45.00 36.776 -30175.804 80.61 34.21 31.34 42.05 34.85 -30182.269 81.49 34.09 31.24 42.20 34.37 -30373.950 78.62 33.44 31.07 44.18 35.22 -30918.0078.3002 33.8606 27.8735 44.8036 42.6653

4结论

利用遗传算法解决约束优化问题时，出现的问题是在进行交叉、变异操作时，会出现不可行解。可以按照处理不可行解的方法对约束优化问题处理方法进行分类。完全拒绝不可行解的方法就是拒绝策略，惩罚策略对不可行解的适应度值进行处理。本文的方法是引入可行种群和不可行种群两个种群进行混合交叉、变异操作来扩大搜索范围，增加种群的多样性，

-3-

http://www.paper.edu.cn

产生新的解；然后两个种群分别进行选择操作以提高种群的平均适应度值。通过几个常用的测试问题的求解以及与其它几种约束处理方法的比较表明：本文提出的约束处理方法具有很好的性能，且处理方法简单。

进一步的研究问题：各种约束处理方法的比较研究，特别是各种处理方法的效率的比较，遗传算法中种群大小、交叉概率、变异概率、迭代次数等参数的选取对算法的性能的影响的研究。同时，任何算法都有其适用范围，因此进一步研究本文算法对哪些问题效果好。

参考文献：

1． 林丹、李敏强、寇纪淞 基于遗传算法求解约束优化问题的一种算法 软件学报 Vol12.No4 2001 628-632 2． David E.Goldberg Genetic Algorithms in Search, Optimization & Machine Learning Addison-wesley

publishing company 1989

3． Michalewicz, Z., Dasgupta, D., Le Riche, R.G., and Schoenauer, M., Evolutionary Algorithms for

Constrained Engineering Problems, Computers & Industrial Engineering Journal, Vol.30, No.2, September 1996, pp.851-870

4． 玄光男,程润伟 北京: 遗传算法与工程设计 科学出版社 2000

5． Michalewicz, Z Evolutionary Algorithms for Constrained Optimization IWEC’2000 International Workshop

on Evolutionary Computation Wuhan pp.1—11

6． Tang Jiafu, Wang Dingwei, A.Ip, R.Y.K.Fung A hybrid genetic algorithm for a type of non-linear

programming problems, Computers and Mathematics with Applications, Vol.36, No.5. 1998 pp.11-21 7． Himmelblau, M., Applied Nonlinear Programming, McGraw-Hill, New York,1972

8． Homaifar, A.,C. Qi, and S. Lai, Constrained optimization via genetic algorithms, Simulation, Vol. 62, No.4,

pp.242-254,1994

9． 李敏强、寇纪淞、林丹、李全书 北京: 遗传算法的基本理论与应用 科学出版社 2002

A new handling constraint method based on the Genetic

Algorithms

Su Yongyan1，Wang Pan1，Fan zhun2

1 School of Automation,Wuhan university of technology

2 Danmark university of technology

Abstract

A new method to handle constrained optimization is proposed in this paper, to solve the disadvantages of the methods .This method searches the solution space of the problem though the admixture crossover of feasible and infeasible solutions, and does the selection operation on feasible and infeasible populations, respectively. It avoids the difficulty of selecting the penalty factor in penalty strategy and makes the handling constrain simplify. Numerical results show that it is a general effective method.

Keywords：Genetic Algorithm; Constraint handling; feasible solution; infeasible solution

-4-