计 算 机 工 程 第 36 卷 第14期
Vol.36 No.14 Computer Engineering ·人工智能及识别技术·
文章编号：1000—3428(2010)14—0147—03
文献标识码：A
2010年7月
July 2010
中图分类号：TP301
一种求解约束优化问题的遗传算法
梁昔明，秦浩宇，龙 文
(中南大学信息科学与工程学院，长沙 410083)
摘 要：提出一种求解约束优化问题的遗传算法。通过可行解与不可行解算术交叉的方法对问题的决策空间进行搜索，对可行种群和不可行种群分别按照适应度和约束违反度进行选择。传统变异操作使得解往往偏离了约束区域，因此引入对可行解的边界变异和对不可行解的非均匀变异，并通过维变异方法保持种群的多样性。数值实验结果说明该算法的有效性。 关键词：约束优化问题；可行解；不可行解；遗传算法
Genetic Algorithm for Solving Constrained Optimization Problem
LIANG Xi-ming, QIN Hao-yu, LONG Wen
(School of Information Science and Engineering, Central South University, Changsha 410083)
【Abstract 】A genetic algorithm to handle constrained optimization problem is proposed. This method searches the decision space of a problemthrough the arithmetic crossover of feasible and infeasible solutions, and performs a selection on feasible and infeasible populations respectivelyaccording to fitness and constraint violation. It uses the boundary mutation on feasible solutions and the non-uniform mutation on infeasiblesolutions because the solutions usually deviate from the constraint domain after the traditional mutation operation. It maintains the populationdiversity through dimension mutation. Numerical results show that it is an effective algorithm.
【Key words】constrained optimization problem; feasible solution; infeasible solution; genetic algorithm
1 概述
在实际工程和科学研究中，约束优化问题是一类广泛存在但又较难求解的问题。一个有不等式和等式约束条件的约束优化问题可以写成如下的形式：
min f (x ) x =(x 1, x 2, ⋅⋅⋅, x n ) ∈ℜn
⎧g j (x ) ≤0 j =1,2, ⋅⋅⋅, l ⎪
s.t. ⎨h j (x ) =0 j =l +1, l +2, ⋅⋅⋅, p (1) ⎪
⎩l i ≤x i ≤u i i =1,2, ⋅⋅⋅, n
其中，x ∈Ω⊆S 为决策向量；Ω为可行域；S 为决策空间。一般的，S 为ℜn 中的n 维长方体。变量x i 在[l i , u i ]中取值；f (x ) 为目标函数；g j (x ) ≤0为第j 个不等式约束条件，h j (x ) =0为第j 个等式约束条件。一般来说，将等式约束条件转换为不等式约束条件进行处理，即
h (x ) −δ
≤0
(2)
其中，δ为等式约束条件的容忍值，一般取较小的正数，这样式(1)将包含p 个不等式约束条件。若x 满足p 个约束条件，则称其为一个可行解；若x 至少违反一个约束，则称其为一个不可行解。
由于约束优化问题的复杂性，传统算法往往不能够有效地解决，而全局优化算法的群体搜索策略和不依赖于梯度信息的计算方式使得其在处理约束优化问题上更为有效。遗传算法是文献[1]提出的一种并行的全局优化算法，最早用来处理无约束优化问题。如果能结合适当的约束处理技术，其在处理约束优化问题方面更具通用性[2]。因此，用遗传算法求解约束优化问题已成为国内外研究的热点。
从约束优化遗传算法=约束处理技术+遗传算法的研究框架出发，约束优化中最大的挑战就是如何同时处理约束和
优化目标函数。目前，遗传算法常用的约束处理方法有拒绝法、修复法、修改遗传算子法、惩罚函数法等。修改遗传算子法是针对问题设计特殊的算子，保证可行解变化后仍为可行解，即遗传操作在可行域上是封闭的，该方法对问题本身依赖性太大。惩罚函数法是对不可行解进行惩罚，进而将约束优化问题转化为无约束优化问题，但同时需要引入惩罚因子，增加了算法的计算量，而且惩罚因子选取是否合适也严重影响算法的性能。惩罚因子过小，部分个体仍有可能破坏约束；惩罚因子过大，有可能使个体差异不大而降低了个体之间的竞争力，从而降低了算法的运行效率。
本文针对目前约束处理方法上存在的问题，提出了一种新的约束处理方法，通过可行解与不可行解的混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作，这就避免了引入惩罚因子而造成的困难。同时，由于通过传统的变异操作后的解往往偏离了约束区域，针对这个问题，本文引入了边界变异和非均匀变异，很好地解决了上述问题，该操作更容易搜索到边界区域。另外，为了维持种群多样性，采用了维变异的思想。结合上述内容得到了一种新的处理约束优化问题的改进遗传算法。数值实验说明了该算法效果较好。
基金项目：国家自然科学基金资助项目“过程控制系统的一类设定点优化方法研究”(60874070)；高校博士点基金资助项目“生产过程操作优化全局寻优方法研究”([1**********])
作者简介：梁昔明(1967－) ，男，教授、博士、博士生导师，主研方向：过程控制及系统优化，进化计算；秦浩宇，硕士研究生；龙 文，博士研究生
收稿日期：2010-03-05 E-mail ：[email protected]
—147—
2 基于遗传算法的约束优化方法
2.1 新的约束处理方法
在现实中存在一大类约束优化问题，其最优解存在于约束边界上或附近，即最优点处不等式约束全部或大部分取为等号。目前，越来越多的研究者已经意识到了不可行解的重要性。文献[3]认为，在种群中保持一定比例的接近可行域边界的不可行解，对于找到全局最优解很有帮助，如图1所示。
可以看出，该选择方法不同于赌轮选择，省去了赌轮选
择中适应度定标的问题，且操作起来较为简单，提高了算法的效率。同时，对可行解和不可行解分别进行选择，避免了类似惩罚函数法引入惩罚因子所带来的计算困难。 2.5 变异操作
由于传统变异算子可能使得解偏离约束区域，因此对可行解和不可行解分别采用了边界变异和非均匀变异。
边界变异的具体操作如下[1]：
在由X=x1x 2···x k ···x l 向X ' =x1x 2···x ' k ···x l 进行边界变异操作时，若变异点x k 处的基因值取值范围为[U k min , U k max ]，则新的基因值x ' k 由下式确定：
k ⎧U min if random (0,1)=0⎪′=⎨x k (6) k
U if random (0,1)1 =⎪⎩max
2
图1 可行解与不可行解的算术交叉
对于靠近可行域边界的不可行解，在对其进行遗传操作
时，这些个体很容易穿越约束边界进入可行域，产生可行解或接近最优解的后代[2]。根据这一思想，本文提出了将可行解与不可行解进行算术交叉的方法，对问题的解空间进行搜索，对可行种群和不可行种群分别按照适应度和约束违反度进行选择，避免了如惩罚函数法引入惩罚因子而带来的不确定性问题。
2.2 适应度函数
可行解的适应度函数obj fea 取为优化问题的目标函数，即 obj fea (x ) =f (x ) (3) 文献[4]认为违反约束条件很小且具有较小目标函数值的不可行解依然有效。因此，采用约束违反度作为不可行解的适应度函数：
obj inf (x ) =∑max{0,g j (x )} 1≤j ≤l (4)
i =1l
当变量的取值范围特别宽，并且无其他约束条件时，边界变异会带来不好的作用。但它特别适用于最优点位于或接近可行区域边界时的一类问题，并且保证了可行解在进行边界变异后仍为可行解。同时，因为基因座的基因值受到其边界限制，以及约束条件带来的限制，使得该方法只能应用于对可行解的变异。
非均匀变异的具体操作如下[1]：
在由X=x1x 2···x k ···x l 向X ' =x1x 2···x ' k ···x l 进行非均匀变异操作时，若变异点x k 处的基因值取值范围为[U k min , U k max ]，则新的基因值x ' k 由下式确定：
k
⎧⎪x k +∆(t , U max −x k ) if random (0,1)=0′=⎨ (7) x k
k
−∆− =x (t , x U ) if random (0,1)1⎪k min ⎩k
∆(t , y ) =y ⋅(1−r (1−t /T ) b ) (8)
其中，obj inf 表示个体x 到可行域边界距离的一种度量，反映
了个体x 违反约束条件的程度。
2.3 交叉操作
在本文提出的约束处理方法中，采用可行解与不可行解进行算术交叉，即2个个体进行线性组合产生出2个新的个体，具体操作如下：
假设在2个个体X 、X 之间进行算术交叉，则交叉后产
t
A
t B
其中，r 为[0,1]范围内符合均匀概率分布的一个随机数；T 是最大进化代数；b 是一个系统参数，它决定了随机扰动对进化代数t 的依赖程度。
由式(7)、式(8)可以看出，在遗传算法进化初期，由于t 较小，非均匀变异进行均匀的随机搜索，而在后期由于t 的增大则进行局部搜索，使得对最优解的搜索过程更加集中在某一最有希望的重点区域中。
在变异过程中，为了不破坏当前最优解，使得变异向着最优的方向进行，采用了保护策略：
(1)可行解：变异后通过式(3)进行比较，只有变异后个体目标函数值小于原个体的，才进行替代。
(2)不可行解：变异后通过式(4)进行比较，只有该值小于原个体的，才进行替代。
2.6 种群多样性的保持
在约束优化问题中，有一部分问题包含很多的局部最优解。随着遗传算法的迭代，种群的多样性逐渐降低，这导致了算法的早熟，不能找到全局最优解。为了解决上述问题，本文采用如下方法，通过对种群多样性的衡量，引入维变异[5]。
种群多样性的衡量[6]：
diversity (P ) =
P −1P 2
⋅ (9)
P ⋅(P −1) ⋅L i =1j =i +生的2个个体为
⎧⎪X =αX +(1−α) X
(5) ⎨t +1t t
⎪⎩X B =αX A +(1−α) X B
t +1
A
t B
t A
其中，α为[0,1]之间的随机数。从图1中可以看出，在二维情况下，当点A 、B 进行算术交叉时，产生的子代一定位于两点的连线上，随着种群进化，交叉后的点将不断向边界靠近，十分有利于找到全局最优解。
2.4 选择操作
在本文算法中，由于在交叉操作中采用了可行解和不可行解的交叉，因此在种群中需要保持不可解的存在，设不可行解占种群的比例为ε。
设最大种群数为Popsize ，其中，可行解为N 1；不可行解为N 2。假设交叉后产生P 个个体，其中，可行解为P 1；不可行解为P 2。这时，将N 1和P 1合并，N 2和P 2合并，通过式(3)、式(4)分别进行选择，得到可行解为Q 1，不可行解为Q 2，Q 1和Q 2的总数为Popsize 。 ——148
其中，P 为种群；|P |为种群个数；n 为问题的维数；|L |搜索
空间S 的最长半径。p ik 和p jk 分别为种群中第i 个和第j 个个体的第k 个基因。
在此，定义一个种群多样性值div ，div 根据不同的问题来定义，当diversity (P ) 小于该值时，进行维变异，即随机对种群中的某一维重新初始化。
本文提出的算法其流程如图2所示。
不可行解比例ε=0.1。式(2)中的容忍值δ=0.000 1，式(8)中的b 取值为2~5，种群多样性值div 根据不同问题具体设定，每个测试函数独立运行30次。
表1给出了本文算法在上述设定参数时得到的实验结果，包括独立运行的最好值(Best)、平均值(Mean)、最差值(Worst)、解的标准方差(St.dev)。在对6个测试函数进行测试时，最大进化代数在500~4 000之间。从表1中可以看出，对测试函数g01、g03、g08、g11，本文算法和另2种算法均一致地找到了全局最优解。对测试函数g02，虽然本文在 30次实验中没有全部找到最优解，但4个状态的值均好于另2种算法，其中最好值更是达到了-0.803 617，更接近最优解。对测试函数g06，3种算法的最好值是一样的，但是在其他 3个状态下本文算法取得了较好的效果。整体来看，除测试函数g08外，本文算法获得的解的标准方差都远小于另外 2种算法，说明了本文算法有较好的鲁棒性。
4 结束语
本文提出了一种新的处理约束的方法，即将可行解和不可行解进行算术交叉，对可行种群和不可行种群分别按照适应度和约束违反度进行选择，避免了如惩罚函数法引入惩罚因子所带来的困难。同时，通过引入对可行解的边界变异，保证了可行解变异后仍为可行解，为算法的最终收敛提供了保障。另外，为了防止算法早熟，本文采用了通过维变异来保持种群多样性的方法。数值实验说明了该算法有很好的鲁棒性。
参考文献
[1] 周 明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出
PA 图2 算法流程
3 数值实验
为了评价本文算法的性能，从文献[7]的13个标准测试函数中选取g01、g02、g03、g06、g08、g11进行测试，测试函数表达式见文献[7]。将本文算法记为PA ，与RY [7]和SMES [8]提出的算法进行比较，实验结果如表1所示。
表1 6个测试函数的实验结果比较
测试函数
最优值
状态 Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev
方法RY -15.000-15.000 -15.000 0.0E+00 -0.803 515-0.781 975 -0.726 288 2.0E-02 -1.000-1.000 -1.000 1.9E-04 -6 961.814-6 875.940 -6 350.262 1.6E+02 -0.095 825-0.095 825 -0.095 825 2.6E-17 -0.750-0.750 -0.750 8.0E-05
SMES -15.000-15.000-15.000 -15.000-15.000 -15.000
0 0 -0.803 601-0.785 238 -0.751 322 1.7E-02 -1.000-1.000 -1.000 2.1E-04 -6 961.814-6 961.284 -6 952.482 1.9E+00 -0.095 825-0.095 825 -0.095 825 0 -0.75-0.75 -0.75 1.5E-04
-0.803 617-0.801 299-0.792 5831.3E-05-1.000-1.000 -1.000 2.0E-08-6 961.814-6 961.811-6 961.8031.0E-05-0.095 825-0.095 825-0.095 8243.2E-14-0.750-0.750 -0.750 3.9E-10
版社, 1999.
[2] Gen M, Cheng Runwei. Genetic Algorithms and Engineering
Design[M]. New York, USA: Wiley, 2000.
[3] 林 丹, 李敏强, 寇纪凇. 基于遗传算法求解约束优化问题的一
种算法[J]. 软件学报, 2001, 12(4): 628-632.
[4] Farmani R, Wright J A. Self-adaptive Fitness Formulation for
Constrained Optimization[J]. IEEE Trans. on Evolutionary Computation, 2003, 7(5): 445-455.
[5] 付国江, 王少梅, 刘舒燕, 等. 含维变异算子的粒子群算法[J].
武汉大学学报: 工学版, 2005, 38(4): 79-83.
[6] Lacevic B, Konjicija S, Avdagic Z. Population Diversity Measure
Based on Singular Values of the Distance Matrix[C]//Proc. of IEEE Congress on Evolutionary Computation. [S. l.]: IEEE Press, 2007: 1863-1869.
[7] Runarsson T P, Yao Xin. Stochastic Ranking for Constrained
Evolutionary Optimization[J]. IEEE Trans. on Evolutionary Computation, 2000, 4(3): 284-294.
[8] Mezura-Montes E, Coello C A C. A Simple Multimembered
Evolution Strategy to Solve Constrained Optimization Problems[J]. IEEE Trans. on Evolutionary Computation, 2005, 9(1): 1-17.
g01 -15.000
g02 -0.803 619
g03 -1.000
g06 -6 961.814
g08 -0.095 825
g11 0.750
本文的遗传算法采用实数编码。算法的参数均设定为：种群规模Popsize =200，交叉概率P c =0.7，变异概率P m =0.1，
编辑 顾逸斐
—149—
计 算 机 工 程 第 36 卷 第14期
Vol.36 No.14 Computer Engineering ·人工智能及识别技术·
文章编号：1000—3428(2010)14—0147—03
文献标识码：A
2010年7月
July 2010
中图分类号：TP301
一种求解约束优化问题的遗传算法
梁昔明，秦浩宇，龙 文
(中南大学信息科学与工程学院，长沙 410083)
摘 要：提出一种求解约束优化问题的遗传算法。通过可行解与不可行解算术交叉的方法对问题的决策空间进行搜索，对可行种群和不可行种群分别按照适应度和约束违反度进行选择。传统变异操作使得解往往偏离了约束区域，因此引入对可行解的边界变异和对不可行解的非均匀变异，并通过维变异方法保持种群的多样性。数值实验结果说明该算法的有效性。 关键词：约束优化问题；可行解；不可行解；遗传算法
Genetic Algorithm for Solving Constrained Optimization Problem
LIANG Xi-ming, QIN Hao-yu, LONG Wen
(School of Information Science and Engineering, Central South University, Changsha 410083)
【Abstract 】A genetic algorithm to handle constrained optimization problem is proposed. This method searches the decision space of a problemthrough the arithmetic crossover of feasible and infeasible solutions, and performs a selection on feasible and infeasible populations respectivelyaccording to fitness and constraint violation. It uses the boundary mutation on feasible solutions and the non-uniform mutation on infeasiblesolutions because the solutions usually deviate from the constraint domain after the traditional mutation operation. It maintains the populationdiversity through dimension mutation. Numerical results show that it is an effective algorithm.
【Key words】constrained optimization problem; feasible solution; infeasible solution; genetic algorithm
1 概述
在实际工程和科学研究中，约束优化问题是一类广泛存在但又较难求解的问题。一个有不等式和等式约束条件的约束优化问题可以写成如下的形式：
min f (x ) x =(x 1, x 2, ⋅⋅⋅, x n ) ∈ℜn
⎧g j (x ) ≤0 j =1,2, ⋅⋅⋅, l ⎪
s.t. ⎨h j (x ) =0 j =l +1, l +2, ⋅⋅⋅, p (1) ⎪
⎩l i ≤x i ≤u i i =1,2, ⋅⋅⋅, n
其中，x ∈Ω⊆S 为决策向量；Ω为可行域；S 为决策空间。一般的，S 为ℜn 中的n 维长方体。变量x i 在[l i , u i ]中取值；f (x ) 为目标函数；g j (x ) ≤0为第j 个不等式约束条件，h j (x ) =0为第j 个等式约束条件。一般来说，将等式约束条件转换为不等式约束条件进行处理，即
h (x ) −δ
≤0
(2)
其中，δ为等式约束条件的容忍值，一般取较小的正数，这样式(1)将包含p 个不等式约束条件。若x 满足p 个约束条件，则称其为一个可行解；若x 至少违反一个约束，则称其为一个不可行解。
由于约束优化问题的复杂性，传统算法往往不能够有效地解决，而全局优化算法的群体搜索策略和不依赖于梯度信息的计算方式使得其在处理约束优化问题上更为有效。遗传算法是文献[1]提出的一种并行的全局优化算法，最早用来处理无约束优化问题。如果能结合适当的约束处理技术，其在处理约束优化问题方面更具通用性[2]。因此，用遗传算法求解约束优化问题已成为国内外研究的热点。
从约束优化遗传算法=约束处理技术+遗传算法的研究框架出发，约束优化中最大的挑战就是如何同时处理约束和
优化目标函数。目前，遗传算法常用的约束处理方法有拒绝法、修复法、修改遗传算子法、惩罚函数法等。修改遗传算子法是针对问题设计特殊的算子，保证可行解变化后仍为可行解，即遗传操作在可行域上是封闭的，该方法对问题本身依赖性太大。惩罚函数法是对不可行解进行惩罚，进而将约束优化问题转化为无约束优化问题，但同时需要引入惩罚因子，增加了算法的计算量，而且惩罚因子选取是否合适也严重影响算法的性能。惩罚因子过小，部分个体仍有可能破坏约束；惩罚因子过大，有可能使个体差异不大而降低了个体之间的竞争力，从而降低了算法的运行效率。
本文针对目前约束处理方法上存在的问题，提出了一种新的约束处理方法，通过可行解与不可行解的混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作，这就避免了引入惩罚因子而造成的困难。同时，由于通过传统的变异操作后的解往往偏离了约束区域，针对这个问题，本文引入了边界变异和非均匀变异，很好地解决了上述问题，该操作更容易搜索到边界区域。另外，为了维持种群多样性，采用了维变异的思想。结合上述内容得到了一种新的处理约束优化问题的改进遗传算法。数值实验说明了该算法效果较好。
基金项目：国家自然科学基金资助项目“过程控制系统的一类设定点优化方法研究”(60874070)；高校博士点基金资助项目“生产过程操作优化全局寻优方法研究”([1**********])
作者简介：梁昔明(1967－) ，男，教授、博士、博士生导师，主研方向：过程控制及系统优化，进化计算；秦浩宇，硕士研究生；龙 文，博士研究生
收稿日期：2010-03-05 E-mail ：[email protected]
—147—
2 基于遗传算法的约束优化方法
2.1 新的约束处理方法
在现实中存在一大类约束优化问题，其最优解存在于约束边界上或附近，即最优点处不等式约束全部或大部分取为等号。目前，越来越多的研究者已经意识到了不可行解的重要性。文献[3]认为，在种群中保持一定比例的接近可行域边界的不可行解，对于找到全局最优解很有帮助，如图1所示。
可以看出，该选择方法不同于赌轮选择，省去了赌轮选
择中适应度定标的问题，且操作起来较为简单，提高了算法的效率。同时，对可行解和不可行解分别进行选择，避免了类似惩罚函数法引入惩罚因子所带来的计算困难。 2.5 变异操作
由于传统变异算子可能使得解偏离约束区域，因此对可行解和不可行解分别采用了边界变异和非均匀变异。
边界变异的具体操作如下[1]：
在由X=x1x 2···x k ···x l 向X ' =x1x 2···x ' k ···x l 进行边界变异操作时，若变异点x k 处的基因值取值范围为[U k min , U k max ]，则新的基因值x ' k 由下式确定：
k ⎧U min if random (0,1)=0⎪′=⎨x k (6) k
U if random (0,1)1 =⎪⎩max
2
图1 可行解与不可行解的算术交叉
对于靠近可行域边界的不可行解，在对其进行遗传操作
时，这些个体很容易穿越约束边界进入可行域，产生可行解或接近最优解的后代[2]。根据这一思想，本文提出了将可行解与不可行解进行算术交叉的方法，对问题的解空间进行搜索，对可行种群和不可行种群分别按照适应度和约束违反度进行选择，避免了如惩罚函数法引入惩罚因子而带来的不确定性问题。
2.2 适应度函数
可行解的适应度函数obj fea 取为优化问题的目标函数，即 obj fea (x ) =f (x ) (3) 文献[4]认为违反约束条件很小且具有较小目标函数值的不可行解依然有效。因此，采用约束违反度作为不可行解的适应度函数：
obj inf (x ) =∑max{0,g j (x )} 1≤j ≤l (4)
i =1l
当变量的取值范围特别宽，并且无其他约束条件时，边界变异会带来不好的作用。但它特别适用于最优点位于或接近可行区域边界时的一类问题，并且保证了可行解在进行边界变异后仍为可行解。同时，因为基因座的基因值受到其边界限制，以及约束条件带来的限制，使得该方法只能应用于对可行解的变异。
非均匀变异的具体操作如下[1]：
在由X=x1x 2···x k ···x l 向X ' =x1x 2···x ' k ···x l 进行非均匀变异操作时，若变异点x k 处的基因值取值范围为[U k min , U k max ]，则新的基因值x ' k 由下式确定：
k
⎧⎪x k +∆(t , U max −x k ) if random (0,1)=0′=⎨ (7) x k
k
−∆− =x (t , x U ) if random (0,1)1⎪k min ⎩k
∆(t , y ) =y ⋅(1−r (1−t /T ) b ) (8)
其中，obj inf 表示个体x 到可行域边界距离的一种度量，反映
了个体x 违反约束条件的程度。
2.3 交叉操作
在本文提出的约束处理方法中，采用可行解与不可行解进行算术交叉，即2个个体进行线性组合产生出2个新的个体，具体操作如下：
假设在2个个体X 、X 之间进行算术交叉，则交叉后产
t
A
t B
其中，r 为[0,1]范围内符合均匀概率分布的一个随机数；T 是最大进化代数；b 是一个系统参数，它决定了随机扰动对进化代数t 的依赖程度。
由式(7)、式(8)可以看出，在遗传算法进化初期，由于t 较小，非均匀变异进行均匀的随机搜索，而在后期由于t 的增大则进行局部搜索，使得对最优解的搜索过程更加集中在某一最有希望的重点区域中。
在变异过程中，为了不破坏当前最优解，使得变异向着最优的方向进行，采用了保护策略：
(1)可行解：变异后通过式(3)进行比较，只有变异后个体目标函数值小于原个体的，才进行替代。
(2)不可行解：变异后通过式(4)进行比较，只有该值小于原个体的，才进行替代。
2.6 种群多样性的保持
在约束优化问题中，有一部分问题包含很多的局部最优解。随着遗传算法的迭代，种群的多样性逐渐降低，这导致了算法的早熟，不能找到全局最优解。为了解决上述问题，本文采用如下方法，通过对种群多样性的衡量，引入维变异[5]。
种群多样性的衡量[6]：
diversity (P ) =
P −1P 2
⋅ (9)
P ⋅(P −1) ⋅L i =1j =i +生的2个个体为
⎧⎪X =αX +(1−α) X
(5) ⎨t +1t t
⎪⎩X B =αX A +(1−α) X B
t +1
A
t B
t A
其中，α为[0,1]之间的随机数。从图1中可以看出，在二维情况下，当点A 、B 进行算术交叉时，产生的子代一定位于两点的连线上，随着种群进化，交叉后的点将不断向边界靠近，十分有利于找到全局最优解。
2.4 选择操作
在本文算法中，由于在交叉操作中采用了可行解和不可行解的交叉，因此在种群中需要保持不可解的存在，设不可行解占种群的比例为ε。
设最大种群数为Popsize ，其中，可行解为N 1；不可行解为N 2。假设交叉后产生P 个个体，其中，可行解为P 1；不可行解为P 2。这时，将N 1和P 1合并，N 2和P 2合并，通过式(3)、式(4)分别进行选择，得到可行解为Q 1，不可行解为Q 2，Q 1和Q 2的总数为Popsize 。 ——148
其中，P 为种群；|P |为种群个数；n 为问题的维数；|L |搜索
空间S 的最长半径。p ik 和p jk 分别为种群中第i 个和第j 个个体的第k 个基因。
在此，定义一个种群多样性值div ，div 根据不同的问题来定义，当diversity (P ) 小于该值时，进行维变异，即随机对种群中的某一维重新初始化。
本文提出的算法其流程如图2所示。
不可行解比例ε=0.1。式(2)中的容忍值δ=0.000 1，式(8)中的b 取值为2~5，种群多样性值div 根据不同问题具体设定，每个测试函数独立运行30次。
表1给出了本文算法在上述设定参数时得到的实验结果，包括独立运行的最好值(Best)、平均值(Mean)、最差值(Worst)、解的标准方差(St.dev)。在对6个测试函数进行测试时，最大进化代数在500~4 000之间。从表1中可以看出，对测试函数g01、g03、g08、g11，本文算法和另2种算法均一致地找到了全局最优解。对测试函数g02，虽然本文在 30次实验中没有全部找到最优解，但4个状态的值均好于另2种算法，其中最好值更是达到了-0.803 617，更接近最优解。对测试函数g06，3种算法的最好值是一样的，但是在其他 3个状态下本文算法取得了较好的效果。整体来看，除测试函数g08外，本文算法获得的解的标准方差都远小于另外 2种算法，说明了本文算法有较好的鲁棒性。
4 结束语
本文提出了一种新的处理约束的方法，即将可行解和不可行解进行算术交叉，对可行种群和不可行种群分别按照适应度和约束违反度进行选择，避免了如惩罚函数法引入惩罚因子所带来的困难。同时，通过引入对可行解的边界变异，保证了可行解变异后仍为可行解，为算法的最终收敛提供了保障。另外，为了防止算法早熟，本文采用了通过维变异来保持种群多样性的方法。数值实验说明了该算法有很好的鲁棒性。
参考文献
[1] 周 明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出
PA 图2 算法流程
3 数值实验
为了评价本文算法的性能，从文献[7]的13个标准测试函数中选取g01、g02、g03、g06、g08、g11进行测试，测试函数表达式见文献[7]。将本文算法记为PA ，与RY [7]和SMES [8]提出的算法进行比较，实验结果如表1所示。
表1 6个测试函数的实验结果比较
测试函数
最优值
状态 Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev Best Mean Worst St.dev
方法RY -15.000-15.000 -15.000 0.0E+00 -0.803 515-0.781 975 -0.726 288 2.0E-02 -1.000-1.000 -1.000 1.9E-04 -6 961.814-6 875.940 -6 350.262 1.6E+02 -0.095 825-0.095 825 -0.095 825 2.6E-17 -0.750-0.750 -0.750 8.0E-05
SMES -15.000-15.000-15.000 -15.000-15.000 -15.000
0 0 -0.803 601-0.785 238 -0.751 322 1.7E-02 -1.000-1.000 -1.000 2.1E-04 -6 961.814-6 961.284 -6 952.482 1.9E+00 -0.095 825-0.095 825 -0.095 825 0 -0.75-0.75 -0.75 1.5E-04
-0.803 617-0.801 299-0.792 5831.3E-05-1.000-1.000 -1.000 2.0E-08-6 961.814-6 961.811-6 961.8031.0E-05-0.095 825-0.095 825-0.095 8243.2E-14-0.750-0.750 -0.750 3.9E-10
版社, 1999.
[2] Gen M, Cheng Runwei. Genetic Algorithms and Engineering
Design[M]. New York, USA: Wiley, 2000.
[3] 林 丹, 李敏强, 寇纪凇. 基于遗传算法求解约束优化问题的一
种算法[J]. 软件学报, 2001, 12(4): 628-632.
[4] Farmani R, Wright J A. Self-adaptive Fitness Formulation for
Constrained Optimization[J]. IEEE Trans. on Evolutionary Computation, 2003, 7(5): 445-455.
[5] 付国江, 王少梅, 刘舒燕, 等. 含维变异算子的粒子群算法[J].
武汉大学学报: 工学版, 2005, 38(4): 79-83.
[6] Lacevic B, Konjicija S, Avdagic Z. Population Diversity Measure
Based on Singular Values of the Distance Matrix[C]//Proc. of IEEE Congress on Evolutionary Computation. [S. l.]: IEEE Press, 2007: 1863-1869.
[7] Runarsson T P, Yao Xin. Stochastic Ranking for Constrained
Evolutionary Optimization[J]. IEEE Trans. on Evolutionary Computation, 2000, 4(3): 284-294.
[8] Mezura-Montes E, Coello C A C. A Simple Multimembered
Evolution Strategy to Solve Constrained Optimization Problems[J]. IEEE Trans. on Evolutionary Computation, 2005, 9(1): 1-17.
g01 -15.000
g02 -0.803 619
g03 -1.000
g06 -6 961.814
g08 -0.095 825
g11 0.750
本文的遗传算法采用实数编码。算法的参数均设定为：种群规模Popsize =200，交叉概率P c =0.7，变异概率P m =0.1，
编辑 顾逸斐
—149—