一种求解约束优化问题基于混合遗传算子的遗传算法 A Genetic Algorithm Based on Hybrid Genetic Operators for Solving Constrained Optimization Problems

doi:10.12677/ORF.2014.41001

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Operations Research and Fuzziology 运筹与模糊学, 2014, 4, 1-6

http://dx.doi.org/10.12677/orf.2014.41001 Published Online February 2014 (http://www.hanspub.org/journal/orf.html)

A Genetic Algorithm Based on Hybrid Genetic

Operators for Solving Constrained Optimization

Problems

Jianni Wan, Hecheng Li

Departm ent of Mathematics, Qinghai Normal University, Xining, C hi na

Email: nanb eihuizi@1 26.com

Received: Nov. 5th, 2013; revised: Nov. 19th , 2013; accepted: Dec. 4th, 2013

which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accordance

Abstract: For the case that the optima of constrained optimization problems are often located on boundary of

the feasible region, a new genetic algorithm based on hybrid genetic operators is proposed in this paper. First,

in this algorithm, the crossover is executed according to feasible and infeasible individuals, respectively. A

feasible point is always combined with the best-known one found so far for cro ssover, whereas an infeasible

individual is selected according to the fitness for crossover with any feasible one. In addition, in order to

make infeasible solutions become feasible ones and make feasible points move toward the boundary of feasi-

ble region, a hybrid mutation operator is presented based on boundar y mutation a nd Gaussia n mutatio n. Nu-

merical experiments and comparison results show the efficiency of the method.

Keywords: Genetic Algor ithm; Constrained O ptimization; O ptimal Solution

一种求解约束优化问题基于混合遗传算子的遗传算法

万建妮，李和成

青海师范大学，西宁，中国

Email: nanbeihuizi@126 .c om

收稿日期：2013 年11月5日；修回日期：2013 年11 月19 日；录用日期：2013 年12 月4日

摘要：针对约束优化问题的最优解可能位于可行域边界的情况，提出了一种新的基于混合遗传算子

的遗传算法。首先，在该算法中，杂交过程按可行个体和不可行个体分别进行，可行个体与最好个体

杂交，不可行个体按照约束违反度的大小与可行个体杂交。其次，引入了一个基于边界变异和高斯变

异的混合变异算子，其目的是促使不可行解变为可行解，可行解向边界移动。数值实验和比较结果表

明了该方法的有效性。

关键词：遗传算法；约束优化；最优解

1. 引言

复杂约束优化问题在最优化领域一直是难以处理的问题，传统的优化方法求解这类问题时都是基于梯度的

信息，这只适用于目标函数和约束条件可微的情形，而且求得的解多为局部最优解[1]。为了避免对函数凸性、

可微性的要求，基于群体搜索的智能算法越来越受到人们的欢迎，其中进化算法是其中的典型代表之一。进化

OPEN ACCESS 1

万建妮，李和成 | 一种求解约束优化问题基于混合遗传算子的遗传算法

算法是一种模拟自然进化过程的全局优化方法，与传统的优化方法相比，进化算法更适合求解具有非凸不可微

函数的复杂约束优化问题[2]。

工程应用和科学研究中，许多问题都可以转化为求解一个带约束条件的函数优化问题。利用进化算法求解

约束优化问题时必须先处理好约束。许多学者对此进行了广泛的研究，也提出了大量的约束优化进化算法[2,3]。

Michalewicz 等将现有的约束优化算法分成 4类：惩罚函数法，多目标法，基于可行解优于不可行解思想的算法

和其他混合法[3]。惩罚函数法是处理约束最常用的方法，是对不可行解进行惩罚，进而将约束优化问题转化为

无约束优化问题[4-8]。但该方法需要引入罚因子，罚因子值的选取是否合适会直接影响算法的性能。罚因子值过

小，起不到惩罚不可行个体的作用。罚因子过大，有可能使部分靠近约束域边界不可行个体缺乏竞争力，而这

部分个体对搜索边界区域的最优解是非常有利的。因此会降低算法的搜索效率。多目标法将约束条件作为一个

或多个目标来处理，这样基于非劣解比较的方法可能会导致算法的计算量增大。基于可行解优于不可行解的算

法没有充分利用不可行解的信息，其情形与罚函数法中因子过大的情况类似。

在进化算法中，如果能结合适当的约束处理技术，那么在处理约束约束优化问题上更具通用性。因此，在

求解约束优化问题方面，以遗传算法为代表的进化算法已成为国内外研究的热点[4-8]。

本文针对目前约束处理方法上存在的问题，提出了一种新的约束处理方法。首先，利用可行域对种群进行

分类，将种群个体划分为可行解集和不可行解集。其次，保留每代可行解集中的最好个体。最后，在杂交运算

中，对可行解集和不可行解集中的个体分别用两种不同的杂交方式进行杂交，使得不可行解趋于可行解，可行

解趋于边界。

2．问题及相关概念

讨论的约束优化问题模型如下：

( )

()

min

s.t. g0,1,2,,

0,1, ,

,1, 2,,

iii

hjp m

lx uin



≤=



== +



≤≤ =





(1)

其中，

∈xR

，

( )

称为目标函数，

( )

g≤x

称为(1)的不等式约束，

( )

h=x

称为(1)的等式约束。给出集合

( )( )

{ }

:,0,0,1,2, ,,1, ,

nij

Eghipj pm=∈ ≤===+xx Rxx

为问题(1)的可行域，可行域中的点称为可行解。

用遗传算法求解上述问题时，如何在可行域中找到最优解，主要取决于算法设计，包括杂交和变异算子设

计及约束处理方法。鉴于此，本文设计了一种新的混合杂交算子。该方法利用当前种群中较好个体的信息来产

生后代，从可行域和不可行域两个方向进行搜索，从而提高算法的搜索能力。

3. 算法设计

3.1. 初始种群的产生

设

和

分别为变量

的上下限。基于变量的上下界，随机产生

个个体。判断这

个个体的可行性，若

至少包含一个可行个体，则记包含这

个个体的集合为初始种群，否则，利用随机生成的方法继续产生个体，

直到找到一个可行解为止。

3.2. 种群个体分类及排序

设

( )

为第

代种群，种群规模为

，将种群分为可行解和不可行解，分别记为：

{ }

12 1

,,,

B=xx x

，

{ }

12 2

,,,

L=yy y

，其中

12nn N+=

。

令：

OPEN ACCESS

万建妮，李和成 | 一种求解约束优化问题基于混合遗传算子的遗传算法

( )()

Ff=xx

(2)

为适应度函数。构造罚函数如下[8]：

( )( )

{ }

( )

max 0,,1

g ip

php im

≤≤



=+≤≤





(3)

( )

表示个体

在第

个约束的违反度，令罚函数

( )( )

∑

，表示个体

违反约束的程度。

对于 B中的点，考察

( )

的值，对于 L中的点考察

( )

的值。根据

( )

的函数值找 B中函数值最小的

个体，并记下这个最好个体。由于约束优化问题的最优解大部分位于可行域的边界上或附近[9-13]，所以在算法执

行中保留一部分约束违反值较小的个体有利于找到最优解。

3.3. 杂交算子

对可行个体和不可行个体分别执行两种不同的杂交方式。

对于可行个体(B 中的点)

，令目前的最好个体为

，执行如下杂交：

()()

*= ++∗−cpR1p p

，其中 c

为杂交后代。

是服从

维标准正态分布的随机向量，即：

( )( )( )

( )

22 2

0,0,, ,0,

σσ σ

∼=N

。

对于不可行个体(L中的点)，按

( )

的大小，以赌轮选择选出与 L同等数量的个体参与杂交。对于杂交个

体

，任取 B中的点

，执行如下杂交：

()

t=+∗−cp pp

，其中

( )

0,1t∈

，是一个动态选取的值。首先给一

个初始值

，

0.5t=

。按照该杂交方法，杂交后代不是可行个体或约束违反超过预先设定的阈值

，则将取

为

0.5 t∗

，逐步向可行域逼近，最终会使杂交后代落入可行域或满足约束违反的阈值

。

3.4. 变异算子

对种群中的两类个体各自进行不同的变异。对可行解集中的个体采取边界变异[4]，该算子描述如下：令

( )

12 n

xx x= ⋅⋅⋅m

为变异父代个体，变异后代记为：

′

，其分量按如下方式选取：

( )

min

max

ifrandom 0,10.5

<



′=>





(4)

其中，

min max





为

的上下界。

对于不可行解集中的个体为

，对其进行高斯变异[11]。记

为变异后代，则：

= +mp R

，

是服从

维

标准正态分布的随机向量，即：

( )( )( )

( )

22 2

00,,,0,

σσ σ

∼=N, R

。

3.5. 选择

采用精英保留策略[6]。从杂交后代和变异后代中选出最好个体与上代中的最好个体进行适应度的比较，保

留最好的一个个体到下一代。再从剩下的个体中选择

1N−

个个体构成下一代种群。

4. 基于混合遗传算子的遗传算法

基于算法设计中的各个策略，提出求解约束优化问题的新算法(genetic algorithm based on hybrid genetic op-

erators, GAHGO)。算法步骤如下：

1) 种群初始化

OPEN ACCESS 3

万建妮，李和成 | 一种求解约束优化问题基于混合遗传算子的遗传算法

设定参数值，并在给定区间内产生初始种群。对初始种群按照适应度进行评估后，再分类为可行解集和不

可行解集，找到可行个体的最好点。

2) 杂交

以杂交概率

从种群

( )

中的可行集和不可行集中选取参加杂交的个体，按设计的混合杂交算子杂交，

产生杂交后代集，记为

( )

。

3) 变异

以变异概率

从种群

( )

中的可行集和不可行集中选取变异个体，按变异算子执行变异运算，产生变异

后代集，记为

( )

。

4) 选择

保留

( )( )( )

Pk CkMk

中的最好个体到下一代，再从剩余个体中选出

1N−

个后代作为下一代种群

( 1)Pk+

。

5) 终止条件判断

判断是否满足终止条件，若满足，输出当前种群

中的最好解，否则，令

1kk= +

，分类个体，返回步骤 2。

5. 数值模拟

5.1. 测试函数与结果

为了测试提出算法的性能，从文献中选取了如下测试函数对该算法进行测试。

例1[7]：

( )()()()

( )

22 2

12 34

6 24

5676767

24 2

1123 45

2123 45

312 67

22 2

41 212367

min10512311

107410 8

.. 12723450,

282 73100,

196 2380,

4325 110,

fx xxxx

xxxxxxx

stg xxxxxx

gxxxxxx

gxx xxx

g xxxxxxxx

=−+ −++ −

++ +−− −

=− +++++≤

=−++ ++−≤

=−+++− ≤

= +−+ +−≤

−≤

( )

101,, 7.









≤=



例2[8]：

( )()

( )

min 1

.. 0,

11, 11.

fx xx

sth xxx

=+−



=−=



−≤≤−≤≤





例3[8]：

( )()

( )

()

1 12

2 21

min 1

.. 0,

20,

1010, 1010.

fx xx

stg xxx

gxx x

=+−



= −<

= −−<



−≤≤−≤≤



例4[14]：

( )

[ ]

min 43

. 2360,

3230,

240,

0,2 ,1,2.

fxx x

st x x

=−−

+ −≤



− +−≤



+ −≤



∈=



OPEN ACCESS

万建妮，李和成 | 一种求解约束优化问题基于混合遗传算子的遗传算法

例5[8]：

( )() ()

( )

312

11 2

2 12

sin 2πsin 2π

min

.10,

1(4) 0,

0 10,010.

fx xxx

st gxx

g xx

= −

+



=− +≤



=−+ −≤



≤≤≤≤



5.2. 结果与比较

对于以上测试函数，用

Matlab

在计算机上对其进行仿真实验，参数取值为：种群规模

200N=

，最大代数

500T=

，杂交概率

0.8

，变异概率

0.2

。对每一个测试函数独立运行 10 次，记录 10 次运算的最好值

和最差值，并计算了 10 次运算目标函数值的平均值、方差，及 10 次运算的平均 CPU 时间等。计算结果如表 1。

从表 1的结果可以看出，本文算法 GAHGO 找到了已知最优解，表明算法有较强的搜索能力。从最差结果

和标准差来看，最差解接近最好解，且标准差较小，因此算法比较稳定。

对算例 4，与文献[14]中的几种算法对比，比较结果见表 2。从最好解、最差解和平均值的比较结果来看，

本文算法对算例 1，算例2和算例 5的计算结果对比文献[5]的算法，比较结果见表 3。本文的计算结果与文献中

的方法几乎一致。

Table 1. Algorithm calculation resul t s

表1. 本文算法计算结果

序号最好解平均值最差解标准差已知最优解平均 CPU 时间/s

1 680.6300 680.6374 680.6606 0 .0111 680.6300 16.95

2 0.75 0 .7 5 0.75 0 0.7500 10.31

3 0 0 0 0 0 10.29

4 −9.0 −9.0 −9.0 1.1e − 005 −9.0 10.03

5 −0.0958 −0.0958 −0.0958 4.2e − 017 −0.0958 9.79

Table 2. Co mp aring the calculation res u lts o f [14]

表2. 与文[14]计算结果的比较

问题算法 bPSO PSO-CA MSMHCO GAHGO

P4 最好解 −8.999 −8.9999 −9.0000 −9.0

平均值 −8.999 −8.9998 −8.9999 −9.0

Table 3. Comparing with the algorithm in [5]

表3. 与文[5]中算法的比较

问题已知最好解解的类型 SMES GAHGO

P1 680.63

最好解

平均值

最差解

标准差

680.632

680.643

680.719

1.6E − 02

680.6300

680.6374

680.6606

0.0111

P2 0.7500

最好解

平均值

最差解

标准差

0.75

1.5E − 04

0.7500

p5 -0.0958

最好解

平均值

最差解

标准差

−0.0958

OPEN ACCESS 5

万建妮，李和成 | 一种求解约束优化问题基于混合遗传算子的遗传算法

6. 结束语

针对约束优化问题的最优解大部分在可行域边界上或可行域边界附近的特点，本文提出了一种基于混合杂

交算子的遗传算法。使得求解过程不断修正不可行个体，并促使种群可行个体向边界移动。数值实验表明，新

设计的算法具有较强的搜索能力。

致谢

本工作受国家自然科学基金项目(61065009)和青海省自然科学基金项目(2013-z-937Q)资助。

参考文献 (References)

[1] Runarsson H. P. and Yao X. (2000) Stoc hastic rankin g for constrained evolutionary optimization. IEEE Transactions on Evolutionary Compu-

tation, 4, 284-294.

[2] Venkatraman, S. and Yen, G.G. (2005) A generic framework for constrained optimization using genetic algorithms. IEEE Transactions on

Evolutionary Computation, 9, 424 -435.

[3] Michalewicz, Z. and Schoenauer, M. (1996) Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Comm-

putation, 4, 1-32.

[4] 梁昔明, 秦浩宇, 龙文 (2010) 一种求解约束优化问题的遗传算法.

计算机工程

, 14, 147-149.

[5] 梁昔明, 龙文, 秦浩宇等 (2010) 基于种群个体可行性的约束优化进化算法.

控制与决策

, 8, 1129-1138.

[6] Farmani, R. and Wright, J.A. (2003) Self-adaptive fitness formulation for constrained optimization. IEEE Transactions on Evolutionary Com-

putation, 5, 445-455.

[7] 范小勤, 汪小红, 尹洁 (2010) 约束优化问题的改进混合遗传算法.

过程控制

, 7, 13-16.

[8] 刘大莲, 徐尚文 (2012) 求解约束优化问题的内外交叉遗传算法.

系统工程与实践

, 1, 189-195.

[9] Mezura-Montes, E. and Coello Coello, C.A. (2005) A simple multimembered evolution strategy to solve constrained optimization problems.

IEEE Transactions on Evolutionary Computation, 9, 1-17.

[10] Kelner, V., Capitanescu, F., Leonardand, O., et al. (2008) A hybrid optimization technique coupling an evolutionary and a local search algo-

rithm. Journal of Computational and Applied Mathematics, 215, 448-456.

[11] Wang, Y., Cai, Z.X., Zh ou, Y.R., et al. (2008) An adaptive trade-off Model for const rained evolutionary optimization. IEEE Transaction s on

Evol utionary C omp ut atio n, 12, 80-92.

[12] Deb, K. (2005) A popu lati on algori thm genert or for rea l-pa ra met er op t imization. Soft computing—A fou ndations. Meth odologies and Applica-

tions, 9, 236-253.

[13] Rouarsson, T.P. and Yao, X. (2005) Search biases in constrained evolutionary optimization. IEEE Transactions on System, Man and Cybernet-

ics, 35, 233 -243.

[14] 张创业, 何登旭, 莫愿斌 (2010)多群多层协同进化算法的约束优化求解及应用.

计算机应用研究

, 5, 1638-1647.

OPEN ACCESS