2018, Vol. 50
2. 智能康复装置与检测技术教育部工程研究中心 天津 300130
2. Engineering Research Center of Intelligent Rehabilitation Device and Detecting Technology of Ministry of Education, Tianjin 300130, China
遗传算法(genetic algorithm，GA)由美国Holland教授于1975年提出，是一种智能优化算法.由于遗传算法不依赖于问题具体的信息，且具有很强的全局搜索能力，所以广泛应用于函数优化、故障诊断、车间调度、旅行商问题等众多领域[1-7]，但其具有易陷入局部最优解的缺陷.针对传统遗传算法的不足，各种改进算法相继被提出，其中文献[2-10]通过结合聚类、量子理论、生物免疫概念、小生境技术或其他进化算法等思想对遗传算法进行了改进.例如，文献[9]提出了基于聚类划分子种群的多种群遗传算法，将满足约束条件的个体根据其特征划分到不同种群中，避免所有子群陷入局部最优; 文献[10]通过带精英策略的快速非支配排序遗传算法在多目标无功优化中的应用，保留了父代中的优良个体.而文献[11-14]通过设计交叉、变异操作对遗传算法进行改进.例如，文献[14]采用自适应交叉变异，最大限度地保留了父代的优良特性，增强了算法的寻优能力.
本文提出了程序性细胞死亡进化算法(programmed cell death evolutionary algorithm，PCDA).首先，程序性细胞算子ced-3和ced-4协同完成选择操作，程序性细胞算子ced-9执行精英策略，目的是引导种群中的个体朝着最优解方向进化; 其次，经过自适应交叉、变异操作[14]，算法运行到一定代数后，结合聚类思想将种群划分为多个子种群; 最后，求解多峰值函数优化问题及经典TSP问题，结果表明了该算法的有效性.
1 程序性细胞死亡进化算法 1.1 程序性细胞死亡原理文献[15]描述了程序性细胞死亡原理：程序性细胞死亡是一个具有遗传性和程序性特征的过程，在生物体中能保持细胞的生死动态平衡.目前最新的研究进展是ced-4激活ced-3的机制，该机制是清华大学施一公实验室发现的，即ced-4以八聚体的形式存在，与两个ced-3结合激活ced-4的功能，而ced-4的功能又和ced-9有关联，这样就形成一个精确的调控系统[16].
在发育过程中，细胞只有在正确的时间发生正确的分化，才能产生正确的细胞类型.人体内的所有细胞根据特征的区别形成各种各样的组织和器官，如肌肉、血液、心脏和神经系统.细胞在正确的时间才发生分化对遗传算法的启发是：在进化过程中，个体只有到特定的代数才能正确地对种群进行划分，产生具有相同特征的子种群.本文结合程序性细胞死亡原理改进遗传算法，设计了程序性细胞死亡进化算法.该算法在遗传算法操作的基础上添加3个算子参加运算：算子ced-3和ced-4参与遗传算法的选择过程，而算子ced-9参与精英策略.
1.2 多种群协同进化构建了一个多种群协同进化模型.首先采用随机法产生初始群体P，进行遗传操作，直到特定的代数; 然后将种群通过对所有个体聚类的方法分解为n个子种群(P1，P2，…，Pn)，在进化过程中所有子种群协同进化，在各自种群的内部单独完成选择、交叉和变异操作，在各个子种群中选择有限的优良个体作为精英个体组成优良种群PP，子种群可以从优良种群中获取其他种群的精英个体，以改善本种群的品质，子种群和优良种群的关系如图 1所示，这种种群结构既增加了种群多样性，又提高了算法的收敛速度.
|
图 1 子种群和优良种群的关系 Figure 1 The relationship between sub populations and good populations |
模拟2个ced-3结合激活ced-4功能的生理过程，在PCDA算法的选择过程中，ced-3算子根据轮盘赌选择分别对子种群中的个体进行2次标记，每次标记的结果都是将适应度高的个体标记为“1”，适应度低的个体标记为“0”.2次ced-3算子标记过后，ced-4算子将标记为“00”的个体淘汰，标记为“11”的优秀个体采用ced-9算子保存，标记为“01”或“10”的大部分个体保留在原子种群中便于后续的进化操作，ced-4共有3种状态：
| $ {\rm{ced}} - 4({R_i}) = \left\{ \begin{array}{l} 0, \;\;\;\;\;\;\;{\rm{ced}} - 3 - 1({R_i}) \ne {\rm{ced}} - 3 - 2({R_i}), \\ 1, \;\;\;\;\;\;\;\;{\rm{ced}} - 3 - 1({R_i}) = {\rm{ced}} - 3 - 2({R_i}) = 1, \\ - 1, \;\;\;\;\;\;{\rm{ced}} - 3 - 1({R_i}) = {\rm{ced}} - 3 - 2({R_i}) = 0, \end{array} \right. $ | (1) |
式中：Ri是子种群中的第i个个体; ced-3-1(Ri)是对Ri执行第1次选择; ced-3-2(Ri)是对Ri执行第2次选择; ced-4=0时，不对个体进行任何操作; ced-4=1时，ced-9被激活执行精英保留操作; ced-4=-1时，删除个体Ri.
1.3.2 交叉遗传算法中起核心作用的是遗传操作的交叉算子.标准遗传算法采用的是一个恒定的交叉概率，而恒定不变的交叉概率存在自身缺陷，即经过几代的进化后，在算法运行后期种群内部的个体绝大多数是适应度高的个体，所以适应度高的个体作为父代的概率要大，从而被破坏的概率变大.针对恒定的交叉概率带来的不足，本文采用自适应交叉概率[17]，即在进化的过程中使交叉概率随着适应度值的变动自动调整，在进化后期避免了破坏种群中的优秀个体.自适应交叉概率的调整公式[18]为
| $ {P_c} = \left\{ \begin{array}{l} {P_{c1}} - \frac{{{P_{c1}} - {P_{c2}}}}{{{f_{{\rm{max}}}} - {f_{{\rm{avg}}}}}}\cdot(f - {f_{{\rm{avg}}}}), \;\;\;f \ge {f_{{\rm{avg}}}}, \\ {P_{c1}}, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f < {f_{{\rm{avg}}}}, \end{array} \right. $ | (2) |
式中：fmax为群体中最大的适应度值; favg为每代群体的平均适应度值; f表示交叉的两个个体中较大的适应度值.本文将Pc1设置为0.9.
1.3.3 变异变异操作使遗传算法具有局部的随机搜索能力.如果变异概率很大，那么整个搜索过程就退化为一个随机搜索过程.本文采用的自适应变异可以提供一个适度的变异概率，自适应变异概率的调整公式[18]为
| $ {P_m} = \left\{ \begin{array}{l} {P_{m1}} - \frac{{{P_{m1}} - {P_{m2}}}}{{{f_{{\rm{max}}}} - {f_{{\rm{avg}}}}}}\cdot(f\prime - {f_{avg}}), \;\;\;f\prime \ge {f_{{\rm{avg}}}}, \\ {P_{m1}}, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f\prime < {f_{{\rm{avg}}}}, \end{array} \right. $ | (3) |
式中：fmax为群体中最大的适应度值; favg为每代群体的平均适应度值; f′是即将变异的个体的适应度值.本文将Pm1设置为0.1.
引入的自适应交叉和自适应变异策略都与适应度值有关，两者的结合能够解决进化过程中因交叉和变异概率固定不变所导致的收敛速度缓慢的问题，克服种群早熟化的固有弊端，改善算法的收敛速度[18].
1.4 算法流程算法具体流程如下：
Step 1 初始化.采用二进制编码得到的初始种群P包含N个个体，个体染色体的长度设置为L; 对初始种群进行遗传操作，直到特定的代数G，才将种群分解为n个子种群，每个子种群含有的个体数没有必要一定相同;
Step 2 根据目标函数计算适应值函数f;
Step 3 执行选择操作.两次轮盘赌操作的结果由ced-3算子标记，由ced-4算子执行，由ced-9算子精英保留到优良种群中;
Step 4 执行自适应交叉、变异操作;
Step 5 为了实现子种群之间的共享，从优良种群中获取优良个体;
Step 6 判断是否到达最大遗传代数.如满足，算法运行结束，输出结果; 如不满足，则返回Step 2.
2 实例验证 2.1 测试函数实验分析用文献[19]中Rosenbrock函数和文献[20-21]中的三维Shubert函数测试算法性能，并与其他算法进行了对比.
2.1.1 Rosenbrock函数Rosenbrock函数为
| $ f({x_1}, {x_2}) = 100{(x_1^2 - {x_2})^2} + {(1 - {x_1})^2}, {x_1}, {x_2} \in \left[{-2.048, 2.048} \right]. $ | (4) |
函数的描述如式(4)所示，该函数是求解Rosenbrock函数的全局最大值.它有两个局部极大点，分别是：f(2.048，-2.048)=3 897.734 227和f(-2.048，-2.048)=3 905.926 227，其中Rosenbrock函数的图形如图 2所示.
|
图 2 Rosenbrock函数的图形 Figure 2 The figure of Rosenbrock function |
采用标准遗传算法(SGA)和本文的PCDA算法对Rosenbrock函数求解最优，结果如图 3所示.由图 3(a)可知，SGA算法在140代左右稳定在得到的最优解处，此时得到的最优解为3 897.725，即算法陷入了局部最优解; 由图 3(b)可知，大概进化到4代时，种群根据个体的特征划分为多种群，使大概在54代时PCDA算法得到了两个稳定的解，实线是PCDA算法得到的最优解(3 905.926)，虚线是PCDA算法得到的次优解(3 897.731).由此可得：PCDA算法收敛速度快，能同时得到全局最优解和次优解，有利于全局分析.
|
图 3 2种算法对Rosenbrock函数的进化过程 Figure 3 The evolution process of two algorithms to Rosenbrock function |
Shubert函数为
| $ f\left( {x, y} \right) = \sum\limits_{i = 1}^5 {i{\rm{cos}}\left[{\left( {i + 1} \right)\cdot x + i} \right]} \cdot\sum\limits_{i = 1}^5 {i{\rm{cos}}\left[{\left( {i + 1} \right)\cdot y + i} \right]}, x, y \in \left[{-10, 10} \right]. $ | (5) |
Shubert函数是多峰值函数，用(5)式求解该多峰值函数的全局最小点，全局最小点共有18个，全局最小点为fmin=-186.731，其中Shubert函数的图形如图 4所示.
|
图 4 Shubert函数的图形 Figure 4 The figure of Shubert function |
为了证明程序性细胞死亡进化算法的优越性，将它与改进的小生境算法(INGA)[20]、自适应遗传算法(AGA)、改进的自适应遗传算法(IAGA)[21]和标准遗传算法(SGA)进行了对比.涉及到的实验部分参数为：种群规模N=40，最大进化代数为50，共进行500次实验.表 1是5种算法进程中3个算子操作的设计.
|
表 1 3个算子操作的设计 Table 1 The design of three operators |
由于篇幅所限，各个算法的进化图不能全部展示.图 5(a)、(b)分别是SGA算法和PCDA算法对Shubert函数进行全局寻优的进化图，达到最大代数，进化终止.由图 5可以看出，PCDA算法确实收敛速度快并且能够搜索到最优点.
|
图 5 2种算法对Shubert函数的进化过程 Figure 5 The evolution process of two algorithms to Shubert function |
表 2列出了PCDA算法和其他4种算法的平均进化代数以及5种算法搜索到最优解的成功率.
|
|
表 2 5种算法的运算结果 Table 2 Operation results of five algorithms |
由表 2可知，在求解多峰值Shubert函数最优解的进程中，最差的SGA算法收敛到最小点处的成功率只有72%，而PCDA算法却每次都能搜到全局最优解，说明了PCDA算法在求解多峰值函数问题中的收敛率高于其他4种算法.
对比以上5种算法的数据可以看出，PCDA算法在求解复杂的多峰值寻优问题时不仅搜索到全局最优解，而且提高了算法的收敛率和收敛速度.
2.2 TSP问题的求解为验证本文算法的有效性，将该算法应用于典型的TSP问题.选用TSPLIB测试库中的经典案例eil51进行了测试.
取种群数N=100，迭代次数为600，个体长度M=51，交叉率Pc=0.9，Pc1=0.9，Pc2=0.6，变异率Pm=0.05，Pm1=0.05，Pm2=0.001，随机运行10次.PCDA算法运行结果的最优解为429.118，次优解为438.012，而文献[22]中GA算法得到最优解为433.443. PCDA算法运行到222代就得到了最优路径(见图 6)，比GA算法的300代提前了很多. PCDA算法和GA算法的进化过程如图 7所示.
|
图 6 最优路径 Figure 6 The optimal path |
|
图 7 进化过程 Figure 7 Evolutionary process |
针对遗传算法易陷入早熟收敛的缺陷，提出了一种程序性细胞死亡进化算法(PCDA).为了验证该算法的可行性，分别在Rosenbrock函数和Shubert函数上进行了性能测试，且与标准遗传算法(SGA)和其他改进的遗传算法进行了比较.从实验结果可以看出，对于多峰值函数寻优，PCDA算法表现出了良好的搜索性能，从而验证了PCDA算法的有效性和可行性.
在PCDA算法进化过程中，得到的次优解是潜在的最优解.当算法陷入到局部最优时, 有必要考虑新的可能解，使之跳出局部最优，从而为决策者对实际问题的解决提供多种方案.该算法对于多峰值函数寻优问题具有很好的优势，它能使多峰值函数得到全局最优解.TSP问题的实验结果表明该算法可以解决工程中非线性、多极值的问题.
| [1] |
马超, 邓超, 熊尧, 等. 一种基于混合遗传和粒子群的智能优化算法[J]. 计算机研究与发展, 2013, 50(11): 2278-2286. DOI:10.7544/issn1000-1239.2013.20111484 (  0) |
| [2] |
万建臣, 靳宗信. 多峰值函数优化问题的免疫遗传算法求解[J]. 电子科技大学学报, 2013, 42(5): 769-772. ( 0) |
| [3] |
刘占生, 窦唯, 王东华, 等. 基于遗传算法的旋转机械故障诊断方法融合[J]. 机械工程学报, 2007, 43(10): 227-233. DOI:10.3321/j.issn:0577-6686.2007.10.043 ( 0) |
| [4] |
刘晓冰, 焦璇, 宁涛, 等. 基于双链量子遗传算法的柔性作业车间调度[J]. 计算机集成制造系统, 2015, 21(2): 495-502. ( 0) |
| [5] |
张鑫龙, 陈秀万, 肖汉, 等. 一种求解旅行商问题的新型帝国竞争算法[J]. 控制与决策, 2016, 31(4): 586-592. ( 0) |
| [6] |
TOMINAGA Y, OKAMOTO Y, WAKAO S, et al. Binary-based topology optimization of magnetostatic shielding by a hybrid evolutionary algorithm combining genetic algorithm and extended compact genetic algorithm[J]. IEEE transactions on magnetics, 2013, 49(5): 2093-2096. DOI:10.1109/TMAG.2013.2240282 ( 0) |
| [7] |
HOU Y, WU N Q, ZHOU M C, et al. Pareto-optimization for scheduling of crude oil operations in refinery via genetic algorithm[J]. IEEE transactions on systems man and cybernetics, 2017, 47(3): 517-530. DOI:10.1109/TSMC.2015.2507161 ( 0) |
| [8] |
GUNTER R. Convergence analysis of canonical genetic algorithms[J]. IEEE transactions on neural networks, 1994, 5(1): 96-101. DOI:10.1109/72.265964 ( 0) |
| [9] |
丁若冰, 邹书蓉. 基于聚类划分子种群的多种群遗传算法[J]. 四川理工学院学报(自然科学版), 2014, 27(3): 46-49. DOI:10.11863/j.suse.2014.03.11 ( 0) |
| [10] |
冯士刚, 艾芊. 带精英策略的快速非支配排序遗传算法在多目标无功优化中的应用[J]. 电工技术学报, 2007, 22(12): 146-151. DOI:10.3321/j.issn:1000-6753.2007.12.024 ( 0) |
| [11] |
蔡良伟, 李霞. 遗传算法交叉操作的改进[J]. 系统工程与电子技术, 2006, 28(6): 925-928. ( 0) |
| [12] |
钟国坤, 曾碧, 余永权. 基于异位交叉的遗传算法的研究[J]. 控制与决策, 2003, 18(3): 361-363. ( 0) |
| [13] |
杨新武, 杨丽军. 基于交叉模型的改进遗传算法[J]. 控制与决策, 2016, 31(10): 1837-1844. ( 0) |
| [14] |
徐克林, 朱伟, 李艳冰. 配装-运输集成决策模型及其遗传算法[J]. 浙江大学学报(工学版), 2011, 45(9): 1630-1635. ( 0) |
| [15] |
ACEHAN D, JIANG X, MORGAN D G, et al. Three-dimensional structure of the apoptosome: implications for assembly, procaspase-9 binding, and activation[J]. Molecular cell, 2002, 9(2): 423-432. DOI:10.1016/S1097-2765(02)00442-2 ( 0) |
| [16] |
施一公, 孙兵法. 细胞凋亡的结构生物学研究进展[J]. 生命科学, 2010, 22(3): 224-228. ( 0) |
| [17] |
SRINIVAS M, PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE transactions on systems man and cybernetics, 2002, 24(4): 656-667. ( 0) |
| [18] |
刘爱军, 杨育, 程文明, 等. 复杂制造环境下的改进非支配排序遗传算法[J]. 计算机集成制造系统, 2012, 18(11): 2446-2458. ( 0) |
| [19] |
李纯莲, 王希诚, 赵金城, 等. 一种基于信息熵的多种群遗传算法[J]. 大连理工大学学报, 2004, 44(4): 589-593. ( 0) |
| [20] |
黄聪明, 陈湘秀. 小生境遗传算法的改进[J]. 北京理工大学学报, 2004, 24(8): 675-678. ( 0) |
| [21] |
陈明杰, 刘胜. 改进自适应遗传算法在函数优化中的应用研究[J]. 哈尔滨工程大学学报, 2007, 28(8): 875-879. ( 0) |
| [22] |
郁磊. MATLAB智能算法30个案例分析[M]. 北京: 北京航空航天大学出版社, 2015.
( 0) |