基于物种选择的遗传算法求解约束非线性规划问题

梁昔明¹，朱  灿^{1, 2}，颜东煌³

 ( 中南大学 信息科学与工程学院，湖南 长沙，410083；

2. 长沙理工大学 交通与运输工程学院，湖南 长沙，410076；

3. 长沙理工大学 桥梁与结构工程学院，湖南 长沙，410076)

摘  要：将信赖域思想和基于稳定进化策略思想相结合，提出一种基于物种选择的遗传算法。根据当前代最优点，采用稳定最优种群数目和收缩最优种群边界的方法将种群划分为最优种群和全局种群，并提出基于构造优化方向的一种新的交叉算子。研究结果表明：对这2种群按不同的策略协调进化，较好地平衡了种群的多样性和选择压力，兼顾了局部搜索和全局搜索；缺少合适的搜索方向是进化后阶段收敛速度慢的重要原因之一；本算法能有效地提高遗传算法的收敛速度，并具有比较好的鲁棒性。

关键词：遗传算法；种群划分；物种选择；交叉算子；非线性规划

中图分类号：TP242.6         文献标识码：A         文章编号：1672-7207(2009)01-0185-05

Novel genetic algorithm based on species selection for

solving constrained non-linear programming problems

LIANG Xi-ming¹, ZHU Can^{1, 2}, YAN Dong-huang³

 ( School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. College of Traffic and Transportation Engineering, Changsha University of Science and Technology,

 Changsha 410076, China;

3. School of Bridge and Structure Engineering, Changsha University of Science and Technology,

 Changsha 410076, China)

Abstract: A novel genetic algorithm based on species selection was proposed with combination of trust reign and evolutionary stable strategy. The population was divided into two parts based on the distances between individuals and the current optimal individual. One was the optimal population of current generation, and the other aggregated hypo-opt individuals. A new cross operator based on optimal vector was presented and some numerical tests were made. The results show that this new approach can enhance local searching by bounding constrained optimal population and could rise the population diversities by introducing self-adaptive mutation probability in hypo-opt population. Rational searching vector unreachable is one of the reasons for slow convergent speed. The algorithm is effective and robust.

Key words: genetic algorithms; population decomposition; species selection; cross operator; nonlinear constrained optimization

科学和工程领域中的许多优化问题最终可归结为求解一个带有约束条件的函数极值问题。问题描述如下：

。

s.t.

             (1)

其中：x为决策变量；f(x)为目标函数；g_i(x)≤0，h_j(x)=0分别为不等式约束条件和等式约束条件。

基于生物自然选择和遗传机理的优化算法——遗传算法，由于其对求解问题限制少，不要求目标函数连续，并具有内在的隐并行性和较强的鲁棒性，因而，在处理非线性问题时越来越受到重视。

尽管保留最优个体的遗传算法以概率为1收敛于最优解，但实际应用时，遗传算法局部搜索能力弱，容易出现早熟和后期收敛速度太慢等现象^[1]。很多研究者对遗传算法进行了改进。王秀坤等^[2-3]结合一些搜索技术来优化遗传算法，如模拟退火算法、梯度算法^[3]、混沌优化及结合神经网络优化^[4]、粒子优化等。但是很多搜索技术本身计算量大，对此，袁晓辉等^[5-8]提出了自适应思想并应用于遗传算法的各个环节，包括设计自适应适应度函数，自适应地改变种群数，自适应地改变交叉变异概率以及改进交叉和变异算子，引入小生境技术等等。对于非线性问题(1)，约束处理、设计合适的适应度函数也是遗传算法的难点之一。对于约束条件的处理，目前主要有可行解优先、惩罚函数法、增加修复算子、pareto强度比较法^[9]，结合多目标优化思想^[10]等方法。但是，很多研究者对遗传算法的改进只能针对特定问题有效，没有普适性。在此，本文作者提出一种基于物种选择的遗传算法来改善遗传算法，提出一种新的自适应惩罚策略和基于构造优化方向的一种新的交叉算子来处理约束问题，最后用常见的测试函数验证本方法的有效性。

1  信赖域思想与基于稳定进化策略思想的结合

遗传算法的交叉算子和变异算子实际上都是针对自变量设计的，其“启发作用”具有局部性质。比如，实数编码启发式交叉算子计算公式一般设计为，其中，x₁的适应度比x₂的优。若x₁和x₂不在同一局部极小点附近，则这种交叉产生的新种子没有“启发”意义，反而破坏了2个父代种子的基因模式，其效果相当于变异。就好像自然界牛和马杂交不会产生出一个更优秀的动物一样。这一问题对于采用结合其他局部搜索技术来提高遗传算法的性能的综合法同样存在。同时，各种参数(如惩罚因子)的选取也应该有一个信赖域,不能因为一些随机的变异影响参数的取值。所以,有必要为整个种群设定一个“信赖域”。

苏小红等^[11]提出了一种基于生物学的“进化稳定策略(Evolutionary stable strategy)”的遗传算法，通过引入突变算子来实现种群的多样性。本文作者提出一种通过种群划分的方法将信赖域思想和基于稳定进化策略思想结合起来，将同一局部极小点附近的种子定义为一个物种。将种群划分成最优种群和种群仓库2部分。通过选定最优种子和稳定最优种子数目来界定信赖域以确定最优种群，而对信赖域外部的种子主要是通过变异来实现物种的多样化。通过不断缩小最优种群区域来提高遗传算法的局部搜索速度。同时，通过设定最优种群边界最小值，自适应地每隔一定代数调整最优种群和其他种群的种子个数来平衡种群多样性，较好地平衡了种群多样性和选择压力，兼顾了局部搜索和全局搜索。

2  一种新的约束处理策略

对于问题(1)，将适应度函数设计为：

惩罚因子λ按照惩罚项的平均增量不高于目标函数的平均增量来设计。假设种子分布图如图1所示。若全是可行点，则随意取值。若可行点比较多，即种子主要分布于区域Ⅰ，少量位于区域Ⅱ时，惩罚因子依据平均可行点与平均不可行点适应度相同的方法确定。这种处理实质是比较种子适应度时考虑2个不同区域。若没有可行点或可行点个数太少，即种子主要分布位于区域Ⅱ和Ⅲ时，则取不可行点函数值的标准差除以约束和的标准差。这种设计在一定程度上能使种群沿约束值减小的方向进化，避免修复算子比较大的计算，实现一定程度的自我修复。设种群个数为p，可行点个数为p₁，则不可行点个数为p-p₁，可行域标记为，标准差函数为std，则

图1  种群分布示意图

Fig.1  Sketch map of population distribution

由式(3)所得结果实际上是各个局部极小点附近λ计算的平均值。

3  基于物种选择的遗传算法

3.1  种群划分及协同进化策略

首先找出种群中最优种子，使得

根据种子到的距离，将余下种子分为种群1和种群2。用界限值L_k界定种群1，种子到的距离小于等于L_k的种子进入子种群1，距离大于L_k的种子进入种群2。希望的L_k领域只包含1个局部极小点，但由于无法确定2个局部极小点之间的距离，因此，用L_k来界定种群1的距离是不准确的。若L_k比实际距离大，也就是说，种群1里还有超过1个局部极小点的种子，则对种群1内的种子在该种群内部进化，随着进化的进行，L_k会逐渐减小，当L_k减小到某一精度值时，对种群1只保留当前最优点，实现最优种群规模自收缩来确保其他区域有比较大的搜索机会，每进化一代，将2个种群混合重组，重新划分成2个种群继续进化。固定2个种群的选择池大小，实际上也就是为了确定种群1里的种子数目，从而确保并稳定种群2有足够的种子来确保其多样性。当代最优解更新来源于种群2说明搜索范围在更换，种群2就像1个局部极小点仓库一样促使整个种群到一个更好的搜索范围内搜索。

种群1主要用于提高平均适应度，提高收敛速度，而种群2的主要作用是保持种群多样性，所以，种群1的进化以交叉为主，而种群2的进化以变异为主。其中，种群2里要避免重复种子出现。所以，种群1中的交叉变异率依常规遗传算法确定，种群2中的变异率根据重复种子个数来确定。在轮盘赌选择时，将进入种群2交配池的重复种子置于交配池的后部，统计重复种子个数，用交叉和变异算子产生相应个数的不同种子，替换种群2后部的重复种子。由于种群2里种子不同，所以，保证了整个种群的多样性。

本方法实质是通过设定一个自适应的距离来隔离一个随当前最优点变化的小生境，在小生境内部按常规遗传算法进化来稳定选择压力，在小生境外部再通过大概率的变异和交叉算子来实现种群的多样性。其最大优点是出现得比较晚的种子只要适应度不是太低，虽然其适应度比出现得比较早的种子的适应度低，但进入选择池的机会也是相当大，从而使新种子能继续繁衍，避免陷入局部最优解。

在数值实验中，对2个种群里的种子进行交叉，并对比更新最优解的来源，发现最优种子来源于种群1的相对较多，来源于种群2的也有一部分，但是，来源于种群1和种群2的种子交叉的情况非常小。所以，没必要对2个种群进行交叉计算。

3.2  选择算子

采用2个适应度函数来选择种子，按适应度函数F₁选择种子进入2个种群pop1和pop2，按适应度函数F₂将种群种子排序。记norm为欧氏距离函数，ε为计算精度，popsize，popsize1，popsize2分别为总种群大小、种群1大小、种群2大小，k为进化代数。

式(6)表示选择进入种群1的种子个数为略小于总的种群数目的一半。

3.3  交配池大小的确定

2个种群里的种子按式(2)排序后，分别按轮盘赌方法进入交配池，轮盘赌选择概率计算公式为：

种群2实际上是保存距离当前代最优种子比较远而适应度函数值不一定比种群1中的种子适应度函数值高的种子，当L_k≤ε时，种群1退化为1个种子。故将种群2并入种群1。

3.4  一种新的交叉算子设计

多父辈交叉有利于提高遗传算法的性能^[12]，但是，多父辈交叉遗传算法的性能依赖于测试函数和交叉操作的父辈数量。本文作者提出一种新的交叉算子，与算术交叉、启发式交叉算子配合使用。交叉算子和变异算子设计要尽量按目标函数和约束条件同时更好的方向变化。称该方向为Pareto强度可行方向，有关Pareto强度定义见文献[9]，设为当前局部最优点，x₁和x₂为交叉父体，则x₁和x₂的位置关系如图2所示。

图2  种子位置关系示意图

Fig.2  Sketch map of positional relation between two parents

当x₂位于区域Ⅰ时，x₂→x₁为可行搜索方向；当x₂位于区域Ⅱ时，x₁→x₂为可行搜索方向；当x₂位于区域Ⅲ和Ⅳ时，x₁和x₂不存在Pareto强度关系。采取将x₁，x₂和 3点交叉方式，将交叉算子设计如下：

3.5  算法描述

步骤1  确定种群规模，初始化种群。

步骤2  根据式(3)求出惩罚因子；求出最优可行点为当前最优种子，并计算其他种子到当前最优种子的欧氏距离。

步骤3  按式(5)计算距离，并划分种群；

步骤4  对种群1和种群2分别按式(3)计算惩罚因子，形成新的适应度。

步骤5  按式(8)计算交配池规模，并用轮盘赌方法产生种子进入1个或2个交配池；对于种群2，将重复种子置于交配池的后部，统计重复种子个数。

步骤6  对2种群或1种群分别进行交叉和变异运算。

步骤7  检验是否进化结束，若是则结束。否则将种群1和种群2混合，返回步骤2。

4  数值实验

取文献[13]中的4个测试函数来检验新算法，它们都是高维带约束条件的函数优化问题。

种群规模取80，独立运行20次，将平均最优解计算结果与Chootinan等^[13]提出的基于惩罚和修复策略的方法比较，结果如表1所示，其中，文献结果取修补参数为20。从表1可以看出，本文提出的算法明显比文献提出的算法要好，同时，本文算法简单，计算量远比修复算法要少，具有比较强的稳定性。

表1  数值计算结果比较分析

Table1  Results of two methods on several test functions

5  结  论

a. 提出了一种基于物种选择的遗传算法，根据种子到当前最优点距离将种群分成2个子种群并分别按照不同的进化策略协同进化重组的方法。

b. 通过固定2种群交配池大小来实现稳定最优种群数，通过缩小最优种群约束边界来提高局部搜索速度。

c. 在次优种群进化计算里，通过避免出现重复种子次数，增强了种群多样性。

d. 分析了精确惩罚因子的局部性质，提出了一种新的惩罚因子计算法，并通过采用两次计算惩罚因子的办法来处理约束条件。

e. 指出没有合理的搜索方向是遗传算法后阶段收敛速度太慢的原因，并提出了一种新的交叉算子来改善搜索。数值实验结果表明，本算法是非常有效的。

参考文献：

[1] 车 明, 孙晓华, 韩倩倩. 遗传算法与生物界进化相比存在的不足及改进[J]. 微处理机, 2006(2): 56-59.
CHE Ming, SUN Xiao-hua, HAN Qian-qian. Disadvantages of the genetic algorithm compared with biologic evolution and improvement[J]. Microprocessors, 2006(2): 56-59.

[2] 王秀坤, 赫 然, 张晓峰. 一种改进的最优保存遗传算法[J]. 小型微型计算机系统, 2005, 26(4): 833-836.
WANG Xiu-kun, HE Ran, ZHANG Xiao-feng. Improvement of genetic algorithm with best elitist preserved method[J]. Mini-Micro System, 2005, 26(4): 833-836.

[3] 何新贵, 梁久祯. 利用目标函数梯度的遗传算法[J]. 软件学报, 2001, 12(7): 981-984.
HE Xin-gui, LIANG Jiu-zhen. Genetic algorithms using gradients of object functions[J]. Journal of Software, 2001, 12(7): 981-984.

[4] 洪 露, 穆志纯, 王岗罡. 一种改进型混合遗传算法的分析[J]. 工业仪表与自动化装置, 2005(3): 36-39.
HONG Lu, MU Zhi-chun, WANG Gang-ga. An analysis of a kind of improved hybrid genetic algorithm[J]. Industrial Instrumentation & Automation, 2005(3): 36-39.

[5] 袁晓辉, 袁艳斌, 王 乘, 等. 一种新型的自适应混沌遗传算法[J]. 电子学报, 2006, 34(4): 709-712.
YUAN Xiao-hui, YUAN Yan-bin, WANG Cheng, et al. A novel self-adaptive chaotic genetic algorithm[J]. Acta Electronica Sinica Acta Electronica Sinica, 2006, 34(4): 709-712.

[6] Jang W H. Gentic/quadratic search algorithm for plant economic optimizations using a process simulator[J]. Computers & Chemical Engineering, 2005, 30(2): 285-294.

[7] 胡妙娟, 胡 春, 钱 锋. 遗传算法中选择策略的分析[J]. 计算机与数字工程, 2006, 34(3): 1-4.
HU Miao-juan, HU Chun, QIAN Feng. General analysis of selection strategy in genetic algorithm[J]. Computer and Digital Engineering, 2006, 34(3): 1-4.

[8] 史 亮, 李海鹰, 杨俊安, 等. 基于主动进化的遗传算法[J]. 小型微型计算机系统, 2004, 25(5): 791-794.
SHI Liang, LI Hai-ying, YANG Jun-an, et al. Active evolution based genetic algorithm[J]. Mini-Micro System, 2004, 25(5): 791-794.

[9] 周育人, 李元香, 王 勇, 等. Pareto强度值演化算法求解约束优化问题[J]. 软件学报, 2003, 14(7): 1243-1249.
ZHOU Yu-ren, LI Yuan-xiang, WANG Yong, et al. A pareto strength evolutionary algorithm for constrained optimization[J]. Journal of Software, 2003, 14(7): 1243-1249.

[10] 王 勇, 蔡自兴, 曾 威, 等. 求解约束优化问题的一种新的进化算法[J]. 中南大学学报: 自然科学版, 2006, 37(1): 119-123.
WANG Yong, CAI Zi-xing, ZENG Wei, et al. A new evolutionary algorithm for solving constrained optimization problems[J]. J Cent South Univ: Science and Technology, 2006, 37(1): 119-123.

[11] 苏小红, 杨 博, 王亚东. 基于进化稳定策略的遗传算法[J]. 软件学报, 2003, 14(11): 1863-1867.
SU Xiao-hong, YANG Bo, WANG Ya-dong. A genetic algorithm based on evolutionarily stable strategy[J]. Journal of Software, 2003, 14(11): 1863-1867.

[12] 陈子仪, 康立山, 等. 多父体杂交演化算法求解约束优化问题[J]. 武汉大学学报: 信息科学版, 2006, 31(5): 440-443.
CHEN Zi-yi, KANG Li-shan. Multi-parent crossover evolutionary algorithm for constrained optimization[J]. Geomatics and Information Science of Wuhan University, 2006, 31(5): 440-443.

[13] Chootinan P, Chen A. Constraint handling in genetic algorithms using a gradient-based repair method[J]. Computers and Operations Research, 2006, 33: 2263-2281.

收稿日期：2008-04-17；修回日期：2008-09-13

基金项目：国家重点基础研究发展规划(973)项目(2002CB312203)；高等学校博士学科点专项科研基金资助项目(20070533131)

通信作者：梁昔明(1967-)，男，博士，教授，博士生导师，从事过程控制与系统优化、进化计算与人工生命研究；电话：0731-8830940；E-mail: ananxml@126.com