2. 华东交通大学 电气与电子工程学院, 南昌 330013
提出了一种基于正交交叉算子的元胞差分进化算法.进化初期采用反学习初始化方法获得初始候选种群，利用元胞结构的局部搜索方法替代控制参数调节差分进化算法的选择压力，从而平衡差分进化算法的探索能力和开发能力，利用元胞自动机的并行演化机制保持种群的多样性，从而避免陷入局部最优.该算法利用无交叉因子的正交交叉算子，通过多元素重复试验加速种群收敛速度.对多个典型测试函数的仿真实验结果表明，所提出的算法相较于多个差分进化改进算法具有更快的收敛速度和更好的计算精度.
2. School of Electrical and Electronic Engineering, East China Jiaotong University, Nanchang 330013, China
A cellular differential evolution (cDE)algorithm based on orthogonal crossover is presented. The opposition-based learning initialization is used to search better solution in the initial stage, the local search within cellular neighbourhood structure is presented to tune the selection pressure instead of the control parameters. And the parallel evolution mechanism of cellular automata is given to ensure the diversity of the evolution population. In addition, the orthogonal crossover is adopted to accelerate the convergence speed with multi-element repeated trials. The performance of the cDE algorithm is evaluated on a suite of classic benchmark functions and compared favorably with the canonical DE and several DE variants. Simulation shows the proposed algorithm has better convergence performance and higher calculation accuracy.
差分进化算法(DE，differential evolution)是一种基于种群的并行迭代优化算法[1]，其性能主要由变异尺度因子、交叉概率因子和种群规模等控制参数决定，具有结构简单、收敛迅速、鲁棒性强等优点.然而，差分进化算法也存在早熟收敛和搜索停滞等缺陷，限制了其优化能力和应用范围，迫切需要加以研究和改进[2-3].
近来一些研究表明，具有空间群体结构的进化算法易于实现并行计算，从而获得较好质量的解[4].元胞进化算法是一类基于空间结构群体离散的进化算法[5-7]，元胞自动机所固有的并联设计赋予了元胞进化算法并行执行的优越性能，同时因进化种群分布在一个2维空间网格中，个体间的交互操作如变异、交叉等被限制在临近的个体之间进行，是一种新的进化算法模式. Noman等[8]提出线性和紧密型邻居结构的元胞差分进化算法，但都未考虑种群进化的动态过程.
为了更为真实地模拟自然界状况，通过元胞自动机对生命现象的模拟，将元胞自动机演化嵌入差分进化算法中，提出了一种新型元胞差分进化算法.该算法利用元胞自动机并行演化的特点平衡差分进化算法的探索能力与开发能力，通过反学习方法初始化种群[9]以及正交交叉算子[10]选择多个子代中的优胜者进入下一代进化，从而实现提高进化算法的全局收敛速度并保持种群的多样性.
1 标准差分进化算法差分进化是一种基于种群的并行迭代优化算法，整体演化过程包含2个阶段：初始化阶段和迭代进化阶段.在初始化阶段，种群个体在整个搜索空间进行随机分布；在进化阶段，每个个体经过变异、交叉和选择的迭代过程，并利用适应度函数对个体进行评估和更新，最终在满足进化停止条件时，输出最优个体.
1) 初始化
设差分进化种群为
|
(1) |
其中：Pg(X)代表第g代种群，Xig代表第g代种群中的第i个个体，Np为种群中的个体总数.代数g从0开始记录，即以P0(X)代表初始种群, gmax为最大进化代数.
2) 变异
差分进化和遗传算法最大的区别就是变异方式不同.遗传算法一般采用随机变异，变异个体和其他个体不发生关联.而差分进化个体的变异结果则由其他个体向量之间的差值决定.对于个体Xig，其变异向量可通过下式得到
|
(2) |
其中：Xr1g、Xr2g和Xr3g为在种群中随机选取的不同于Xig的个体，Fk为收缩因子，k为差分向量个数.
3) 交叉
在标准差分进化中，交叉一般采用二项式交叉策略，随机地从变异个体和原种群个体中抽取元素组成新的个体.元素抽取的数学模型为
|
(3) |
其中：uijg为交叉生成的新个体Uig中的一个元素，vijg为变异个体Vig中的一个元素，xijg为原种群个体Xig的对应元素，Cr称为交叉因子，决定了从变异个体中抽取元素的比例，从而最终决定了对原种群个体的扰动程度.
4) 选择
差分进化的选择采用一对一的竞争策略.通过交叉生成的个体Uig与原种群个体Xig按适应度进行竞争，如果Uig的适应度高于Xig，则在下一代种群中Xig的位置由Uig代替；否则，在原种群中保留Xig.
标准差分进化采用的选择策略模型为
|
(4) |
按照变异和交叉策略的不同，差分进化可以表示为DE(x, y, z).其中，x代表参与变异个体的选择方式，一般有随机选择(rand)和应用最优个体(best)两种；y代表变异中应用的差分向量个数，在实用中，一般不大于2；z代表交叉方式，bin代表二项式交叉，exp代表指数交叉.
2 基于元胞自动机的差分进化算法2.1 元胞自动机演化机理元胞自动机(CA, cellular automata)源于Von Neumann提出的一种极度并行的计算模型，其基本组成为元胞、元胞空间、邻居及规则4部分.一般CA是一个四元组A=(Ld, S, M, f), 其中：A代表一个CA系统；Ld表示元胞空间，d是一个正整数，S表示元胞的有限的、离散的状态集合；M表示所有领域内元胞的集合，包括n个不同元胞状态的一个空间矢量，记为M=(s1, s2, …, sn)，其中si∈S, i∈{1, 2, …, n}; f为局部映射或者局部规则.
常见的邻居结构有4种，如图 1所示.其中性能最优是C9结构(Moore结构)[8].
|
图 1 元胞差分进化算法的邻居结构 |
基本的演化规则如下
|
(5) |
|
(6) |
其中：St和St+1分别表示第t和t+1步进化后的元胞状态，S1表示“活”元胞保持其状态所需要的“活”邻居元胞的数目，S2表示“死”元胞复活需要的“活”邻居元胞的数目.不同的演化规则所获得的元胞生存密度不同. C9邻居结构分别采用下面3种规则可模拟生命系统的稳定、周期和复杂3种状态[6].
|
(7) |
|
(8) |
|
(9) |
首先采用随机生成的方式产生初始种群(见式(10a))，然后对Np个初始种群的向量求解对应的反向解(式(10b))，并加入初始种群中，最后选择Np个适应度高的向量构成新的初始种群.
|
(10a) |
|
(10b) |
其中kj、lj分别为第j维的上限和下限.
2.3 正交交叉操作交叉操作的目的是将染色体中性能优良的组块遗传到下一代染色体中，使之具有父辈染色体的优良性能.但是经典差分进化算法中采用的是一点交叉运算，使得大多情况下无法达到上述目的，而采用多点交叉运算可以避免这个问题.但多点交叉运算因交叉组合存在多种可能，因此组合方式将呈现爆炸式增长.为解决这个问题，对于低维函数可使用正交表Lq(2m)安排多点交叉运算，以保证交叉运算后能够获得优良的染色体.而对于高维函数的正交表则由多个低维正交表并排组合而成.
2.4 cDE的算法步骤种群规模和元胞个数都设置为Np，1个元胞对应1个个体的“活”、“死”状态.元胞差分进化算法(cDE，cellular differential evolution)的整体算法步骤如下.
步骤1 初始化
步骤1.1 设置种群规模Np，初始化收缩因子F值，确定算法停止条件;
步骤1.2 在搜索空间随机初始化Np个个体Xi0；采用反学习方法获取Np个反向解；根据目标函数评估所有个体获取Np个较优解；
步骤1.3 元胞自动机中各元胞状态随机初始化，分别对应每个个体的生存状态；
步骤1.4 产生正交交叉表；
步骤2 对“活”的个体进行迭代进化.若无“活”的个体，则跳至步骤3；
步骤2.1 按照事先选择的元胞邻居结构，个体从中选择候选个体参与下面步骤的变异操作；
步骤2.2 自适应调整收缩因子F并进行变异；
步骤2.3 按照正交交叉表执行交叉运算；
步骤2.4 按照适应度函数评估个体，并更新下一代；
步骤3 按照演化规则对元胞自动机进行演化，确定元胞的新一代生存状况；
步骤4 如果达到停止条件，输出最终结果；否则跳转到步骤2.
3 实验步骤为了测试所提出的改进元胞差分进化算法的性能，选取文献[3]中Griewank函数、Schwefel函数以及Com_func1函数这3个具有典型特点的标准测试函数集进行仿真实验. 表 1分别给出3个测试函数的名称、维数、搜索空间范围及最优解.种群规模设置225；缩放因子F采用文献[3]中的自适应方式；当测试函数为10维时正交交叉表使用L12(211)的前10列，当测试函数为30维时则采用3个10维正交交叉表并列组成.
|
表 1 3个标准测试函数说明 |
表 1所示为3个独立测试函数的维数、搜素空间及最优值的说明，其中包括2个一般测试函数(f1, f2)和1个组合函数(f3)，3个函数都为多峰函数.
3.2 寻优结果的精确性比较为了对元胞差分进化算法与经典差分进化算法及4种变种算法的精确性比较，分别对元胞差分进化算法与经典差分进化算法及4种变种算法进行25次独立运行后得出了各自算法最优值、各次结果的平均值及标准误差值，如表 2、表 3所示.其中每种测试函数各算法比较后的最优解使用黑体标示.
|
|
表 2 10维时各算法适应值的最优解、均值及标准差 |
|
|
表 3 30维时各算法适应值的最优解、均值及标准差 |
从表 2和表 3可以看出，元胞差分进化算法的表现要优于经典差分进化算法和4种变种算法.特别是在低维(10维)测试函数时元胞差分进化算法的性能表现得更为出色，3个测试函数都找到理论最优解.在高维(30维)测试函数时，元胞差分进化算法获得了2个测试函数的最优解，另外1个测试函数的结果元胞差分进化算法表现也是最优的.
3.3 收敛性分析收敛性是进化寻优算法性能比较重要的指标.经典差分进化算法和4种变种算法与元胞差分进化算法作用于3种测试函数所得到的收敛性能如图 2和图 3所示.其中横坐标表示进化代数；纵坐标采用对数坐标，表示最优值.
|
图 2 不同算法作用于不同测试函数的收敛速度(10维) |
|
图 3 不同算法作用于不同测试函数的收敛速度(30维) |
从图 2、图 3可以看出，相对于其他几种算法，由于采用反学习初始化方法，所提出的cDE算法在初始阶段能获得较好的初始适应值; 在对3种测试函数测试过程中，相对于其他5种差分进化变种算法，cDE算法不仅收敛速度较快，而且大多数都能获得测试函数的理论最优值.分析其原因主要有两点：第一，提出的算法通过基于元胞邻居结构的局部搜索机制代替控制参数调节进化算法的选择压力，同时采用元胞自动机并行进化机制保证进化过程中种群的多样性，从而使算法搜索到更优解的几率增大，为避免陷入局部最优解提供了可能；第二，相对于二项式交叉算法，正交交叉算子提供高维多元素的重复实验，使所提出的cDE算法更易于找到最优的后代，从而有利于提供算法的收敛速度.
4 结束语差分进化算法是一种简单且有效的寻优算法，已被用于多个场合下的最优值求解.但同时差分进化算法也存在早熟收敛和搜索停滞等缺陷，限制了其优化能力和应用范围.笔者将元胞自动机与差分进化算法相结合，利用元胞自动机并行演化和多目标处理机制的特点平衡差分进化算法的探索能力与开发能力；引入反学习方法作为初始化种群的工具；利用正交交叉算子代替经典差分进化算法中的二项式交叉算子，从多个子代中选择优胜者进入下一代进化，从而使元胞差分进化算法在保持种群多样性的同时实现了较快寻优收敛.通过多个典型测试函数的仿真实验结果表明，该算法相较于经典差分进化算法和4种变种算法具有更好的保持种群多样性的能力，从而有效避免陷入局部最优解，并具有更快的收敛速度.未来将进一步研究元胞差分进化算法在多目标优化及动态优化中的进化机理.
| [1] | Das S, Suganthan P N. Differential evolution: a survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation, 2011, 15(1): 4–31. doi: 10.1109/TEVC.2010.2059031 |
| [2] |
毕晓君, 刘国安. 基于云差分进化算法的约束多目标优化实现[J]. 哈尔滨工程大学学报, 2012, 33(8): 1022–1031.
Bi Xiaojun, Liu Guoan. A cloud differential evolutionary algorithm for constrained multi-objective optimization[J].Journal of Harbin Engineering University, 2012, 33(8): 1022–1031. |
| [3] | Jia Dongli, Zheng Guoxin, Khan M K. An effective memetic differential evolution algorithm based on chaotic local search[J].Information Sciences, 2011, 181(15): 3175–3187. doi: 10.1016/j.ins.2011.03.018 |
| [4] | Alba E, Tomassini M. Parallelism and evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation, 2002, 6(5): 443–462. doi: 10.1109/TEVC.2002.800880 |
| [5] | Alba E, Dorronsoro B. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms[J].IEEE Transactions on Evolutionary Computation, 2005, 9(2): 126–142. doi: 10.1109/TEVC.2005.843751 |
| [6] |
鲁宇明, 黎明, 李凌. 一种具有演化规则的元胞遗传算法[J]. 电子学报, 2010, 38(7): 1603–1607.
Lu Yuming, Li Ming, Li Ling. The cellular genetic algorithm with evolutionary rule[J].Acta Electronica Sinica, 2010, 38(7): 1603–1607. |
| [7] | Dorronsoro B, Bouvry P. Cellular genetic algorithms without additional parameters[J].Journal of Supercomputing, 2013, 63(3): 816–835. doi: 10.1007/s11227-012-0773-y |
| [8] | Noman N, Vatanutanon J, Iba H. Tuning selection pressure in differential evolution using local selection[C]//2010 2nd World Congress on Nature and Biologically Inspired Computing (NaBIC2010). Kitakyushu: IEEE Computer Society, 2010: 66-71. |
| [9] | Rahnamayan S, Tizhoosh H R, Salama M M A. Opposition-based differential evolution[J].IEEE Transactions on Evolutionary Computation, 2008, 12(1): 64–79. doi: 10.1109/TEVC.2007.894200 |
| [10] | Leung Y, Wang Yuping. An orthogonal genetic algorithm with quantization for global numberical optimization[J].IEEE Transactions on Evolutionary Computation, 2001, 5(1): 41–53. doi: 10.1109/4235.910464 |