基因编辑差分算法在多燃料经济调度中的应用

2018-08-01孟安波林艺城

计算机工程与应用 2018年15期

孟安波，林艺城

广东工业大学自动化学院，广州 510006

1 引言

在电力系统运行中，经济调度（Economic Dispatch，ED）是一项重要的优化任务，其主要目标为在满足出力—负荷平衡的等式约束和发电机出力等不等式约束条件的前提下，使得总发电成本最小，对电力系统的安全经济运行具有重要的意义[1]。传统ED优化问题中，发电机组进气阀突然开启所产生的拔丝现象——阀点效应往往被忽略不计，这降低了模型的求解精度[2]。同时，仅能利用单一燃料的传统发电机组已经不能满足经济和环境的需求，因此能使用多种燃料的发电机组成为目前火力发电的主流。本文ED模型中同时考虑了发电机组的阀点效应和多燃料。计及阀点效应给ED问题的寻优空间增加了大量的局部最优点，而考虑多燃料则使得ED的解空间不连续，因此该问题呈现出一系列高维、非凸、非线性、不连续的特点，进一步增加了问题的解决难度。随着系统工程理论研究的日趋成熟和现代计算机技术在计及阀点效应和多燃料经济调度领域的不断发展与应用，各种新方法和新技术也层出不穷。常见有传统的数学优化方法：如线性规划[3]、非线性规划[4]、动态规划[5]等，传统的优化方法过度依赖数学模型，并在求解时需将数学模型进行简化，且对初始解较为敏感，因此在处理此类计及阀点效应和多燃料的复杂DE优化问题时容易陷入局部最优点。近年来，智能优化算法得到了高速发展，因此，在解决多燃料DE问题上大量地采用启发式优化算法，如原始的启发式优化方法，主要有遗传算法（GA）[6]、粒子群算法（PSO）[6]、差分算法（DE）[7]、重力搜索算法（GSO）[8]、竞拍分布式算法（AA）[9]、布谷鸟搜索算法（CSA）[10]、禁忌搜索算法（TSA）[6]、生物优化算法（BBO）[11]、搜寻者优化算法（SOA）[12]等。相对于传统数学优化方法，这些原始启发式算法对所求问题的数学模型没有特殊限制，具有强大的适应性。然而，原始算法仍存在容易出现过早熟现象，收敛精度不高等缺陷。因此，更多的学者致力于研究其改进方法，如从算法结构上的改进，主要有改进遗传算法[7，13-14]、改进粒子群算法[7，15-20]、改进布谷鸟算法[21]、改进蛙跳算法[22]、扰动差分算法（SDE）[23]、全局最优和声搜索算法（GHS）[23]等，或结合两个及以上算法的混合，如混合遗传乘数更新算法[24]、混合分布式粒子群和禁忌搜索算法[25]等[7，19，23，26-27]，这些改进或混合算法比原始算法适应性更强，优化结果也更具优势，然而这些算法在面临不可微、不连续、非凸、非线性的大规模计及阀点效应的多燃料经济调度优化问题时，同样也存在一些缺陷，如种群多样性不足，容易陷入局部最优，收敛速度较慢等，因此，需要提出一种更高效的方法解决该优化问题。

差分进化（Differential Evolution，DE）算法[28]的基本思想是仿照生物进化机制，利用种群中个体间的差异产生新的个体，然后进行交叉、选择操作以实现种群的进化，并通过多次迭代搜索最终得到全局最优解。DE算法不但具备结构简单、控制参数少、易于实现、有较强的鲁棒性等优点，而且其固有的并行性有助于算法求解大规模系统模型。尤其是在低维单峰函数优化问题中具有明显的收敛速度快、寻优精度高等优势。然而在面临高维、多峰、非线性及不可微等复杂优化函数时，存在后期收敛速度慢，容易陷入局部最优等缺陷。针对这一问题，本文首次提出了基因编辑差分算法（Gene Editing Differential Evolution，GEDE），该算法在标准差分算法的基础上，通过融入最新研制的基因编辑操作，该操作能有效缓解DE算法后期收敛种群多样性不足导致陷入局部最优的现象，并且在收敛后期种群中个体严格满足等式约束情况下，每次基因编辑操作均为在可行域中搜索，这极大地降低了整个搜索空间，大幅度地提高算法搜索效率。此外，本文将通过10机组和40机组的多燃料电力系统的算例进行仿真分析，并与文献所提多种方法进行综合对比，验证所提算法在求解高维、非凸、不连续的计及阀点效应的多燃料经济调度优化问题时的有效性与优越性。

2 经济调度模型

2.1 传统的经济调度目标函数

式中Fj为机组 j的燃料费用；N为发电机组数；aj、bj、cj为发电机组 j的燃料费用系数，Pj为发电机组 j的出力。

传统ED问题的主要目标是在满足电力系统安全运行的各种约束下，通过优化各发电机组有功出力使得所有发电机总燃料费用最小，其目标函数为：

2.2 计及阀点效应经济调度目标函数

在实际的经济调度中，通常还需考虑汽轮机进气阀突然开启所出现的拔丝现象，该现象会在机组的耗量特性曲线上叠加一个如图1的脉动效果——阀点效应，可表示为：

式中ej、fj为发电机组 j的阀点效应系数；Pminj为发电机组 j的最小技术出力。

图1 计及与忽略阀点效应的火电厂耗量特性曲线对比图

2.3 计及阀点效应和多燃料的经济调度目标函数

当发电机组同时考虑阀点效应和多燃料时，机组的耗量特性曲线将出现如图2所示的分段脉动效果，该数学模型可表示为：

式中ajK、bjK、cjK、ejK、fjK为机组 j的第K种类型燃料的费用系数，该分段函数共有K段；为机组 j的最大出力。

图2 同时考虑多燃料和阀点效应的机组油耗特性曲线

2.4 约束条件

（1）负荷平衡约束

式中，PD为系统负荷需求。

（2）机组出力约束

3 基因编辑差分优化算法

3.1 标准差分进化算法

与遗传算法相似，DE算法也包含交叉、变异和选择操作，不同的是，DE在随机选择的父代个体间差分矢量的基础上生成变异个体；其次，按一定的交叉概率对父代个体与变异个体执行交叉操作，生成试验个体；最后采用贪婪策略保留父代个体与试验个体之间适应值较好的个体。

3.1.1 变异操作

DE算法是在父代个体之间差分矢量的基础上执行变异操作的，每个差分矢量包含父代（如第g代）的两个不同个体。实际应用中DE有多种变异方案[29]，其变异个体的生成方式也各有差异。本文采用的变异操作具体如下：

式中，g 为当前代数；r1、r2、r3∈N(1,M)⋂r1≠r2≠r3≠i；为第g代变异个体i；、、为第g代种群中随机挑选的互不相同个体；G∈[0,2]为缩放比例因子，用于控制差分矢量-对个体的影响。

3.1.2 交叉操作

DE算法通过交叉操作以提高种群的多样性。该过程根据当前种群中个体和变异操作所产生的变异个体实施交叉操作，产生试验个体，具体交叉方式如下：

式中，rand为[0，1]之间服从均匀分布的随机数；pDE∈[0,1]为交叉概率；N为变量的维数。

3.1.3 选择操作

3.2 基因编辑差分算法

标准DE算法的性能主要取决于其全局搜索和局部探测能力，在一定意义上，这取决于该算法的种群大小、缩放比例因子、交叉概率等控制参数的设置，相比于其他的启发式算法而言，DE算法具备控制参数少、可操作性强、群体搜索、具有记忆个体最优和全局最优的保优功能等优点。然而，与其他诸如遗传算法、蚁群算法、粒子群算法等绝大多数启发式算法相似，DE算法由于自身固有利用差分向量进行突变产生新个体的搜索方式造成该算法在当迭代次数达进行到一定次数时，种群多样性的急剧下降，形成“聚集”现象，导致过早收敛的问题。

为增强DE算法的全局收敛能力，使算法在处理高维多峰复杂优化问题时，降低算法在某一局部最优点出现停滞的可能性，避免种群多样性过早丧失，协助其跳出局部最优。本文通过在上述标准DE算法的基础上融入最新研制的基因编辑技术操作，其实现过程如图3所示。

细胞核（种群）中染色体（个体）的所有基因（维）进行两两不重复配对，并依据编辑概率 pc判断配对基因是否执行基因编辑操作，若rand＞pc则执行基因编辑操作，假定染色体i中的d1、d2维基因分别为 x(i,d1)和x(i,d2)，则对它们进行基因编辑操作产生修复的d1、d2维基因可表示如下：

（1）基因定点剪切、供体重组

式中，L(d1)、L(d2)为基因保守序列（分别为第d1、d2维元素对应的下限）；gd为所提取的基因供体。

图3 基因编辑技术操作的实现示意图

（2）基因供体随机剪切

式中，gs1、gs2分别为剪切后的基因供体片段。

（3）定点基因片段替换

式中，gr(i,d1)、gr(i,d2)分别为染色体i修复后的第d1、d2维基因。

基因检测与鉴定：若 gr(i,d1)≤U(d1)且 gr(i,d2)≤U(d2)，则基因编辑成功，转至判断下一配对基因是否执行基因编辑操作；若否，则转至步骤（2）重新进行基因供体随机剪切，直至基因编辑成功。

与DE算法的选择操作相同，执行完基因编辑技术操作的染色体需与父代染色体进行比较，择优保留进入下一次迭代。

本文所提GEDE算法在DE算法的研究基础上，融合了基因编辑技术操作，该操作通过采用一个编辑概率pc控制当前细胞核内所有染色体参与编辑的基因规模，这有利于协助部分维摆脱维局部最优的同时避免破坏正常维，有效地避免算法过早熟收敛。其次，由上述基因编辑技术操作过程不难发现，该操作并不会发生基因漂移，即基因编辑技术操作后配对维之和保持不变。因此，随着搜索的逐步深入，当出现细胞核中染色体上所有基因之和严格满足如式（4）中等式约束时，此时所执行的每次基因编辑技术操作将同样严格满足等式约束，对于上述计及阀点效应的多燃料经济调度更是同时满足等式约束和不等式约束，即每一次基因编辑技术操作均在可行域上搜索全局最优解，这极大提高了算法的计算效率，此过程可由图4所示。

图4 基因编辑技术操作搜索范围变化示意图

4 GEDE算法基本步骤

步骤1设定种群大小M、最大迭代次数maxgen、交叉概率pDE、编辑概率 pc，在解空间中随机初始化种群，并计算每个个体的适应度值。

步骤2对种群中所有个体执行变异、交叉和选择操作，更新种群。

步骤3对步骤2所产生子代种群执行基因编辑技术操作，更新种群。

步骤4判断是否达到最大迭代次数maxgen，若是，则输出适应度值最好的解作为最终优化结果，否则，转至步骤2继续迭代搜索。

GEDE算法的流程图如图5所示。

图5 GEDE算法流程图

5 GEDE算法在计及阀点效应的多燃料经济调度中的应用

应用GEDE算法解决计及阀点效应的多燃料经济调度优化问题的实现过程如下：

（1）初始化

设置种群（细胞核）大小M、最大迭代次数maxgen、交叉概率 pDE、编辑概率 pc，并根据式（12）在解空间中随机生成初始种群。

式中i∈(1,M)，j∈(1,N)。

种群中每个个体表示一个解，针对包含D台发电机组的计及阀点效应的多燃料经济调度优化问题，其第i个个体可表示：

式中，X(i)为种群中第i个个体；Xi,1为个体i中第一个控制变量；Pi,1为个体i第1台发电机组的出力。

（2）计算个体适应度

在计算个体适应度前，首先根据式（14）进行约束越限处理：

对调整后的个体，由式（15）计算其适应度值：

（3）执行变异、交叉及选择操作

根据式（6）～（7）执行变异、交叉操作产生试验个体，并由式（14）进行违约处理，随后根据式（15）计算试验个体的适应度，其次由式（8）进行选择操作，只有适应度值更好的个体能保留下来，参与基因编辑技术操作。

（4）执行基因编辑技术操作

细胞核（种群）中染色体（个体）所有基因（维），进行随机两两不重复配对，并依据编辑概率 pc判断配对基因是否执行基因编辑技术操作，若执行，则由式（9）～（11）执行基因编辑技术操作中的基因定点剪切、供体重组、基因供体随机剪切、定点基因片段替换和基因检测

看出当该项趋于0时，与鉴定，产生新的染色体（个体）基因对，其次，由式（15）计算所有基因编辑操作后所产生新染色体的适应度，同理，根据式（8）执行选择操作，择优保留适应度值较好的染色体进入下一次迭代。

（5）停止条件

判断是否达到最大迭代次数maxgen，若否，则转至（3）执行执行变异、交叉及选择操作，继续迭代，若达到最大迭代次数，则输出适应度最好的值所对应的解作为最终优化结果。

6 算例分析

6.1 算例描述及算法参数设置

为验证本文所提GEDE算法求解具有高维、非凸、非线性、不连续特性的计及阀点效应和多燃料经济调度优化问题的有效性与优越性，本文分别采用经典10机组及40机组的计及阀点效应和多燃料电力系统经济调度算例进行仿真分析。其中40机组为10机组电力系统扩大4倍，相应负荷需求也扩大4倍，10机组系统具体参数见文献[30]。10机组算例种群规模设置为100，迭代次数设为300，惩罚系数λ=0.53，交叉概率 pDE设为0.4，编辑概率 pc设为0.5。同时，为保证仿真结果的公正与合理，40机组仿真中，DE算法和GEDE算法均采用相同初始种群及算法最优参数设置，大量实验表明，40机组系统最优交叉概率为0.3，其次该迭代次数设为2 000，其余设置与10机组相同。求解时采用MATLAB R2010 b进行程序语言编写；计算机运行环境为Inter®CPU G5400、2.49 GHz、内存为3.40 GB，操作系统为Windows XP Professional。

6.2 优化结果分析

通过前面所述GEDE优化算法，对10机组系统和40机组系统的计及阀点效应的多燃料经济调度算例进行优化求解，可得表1、2优化结果、表3、4分别列举了GEDE算法应用于10机组及40机组系统独立运行100次所得最优解的最小值、平均值、最大值及CUP平均运行时间并分别与其他各种算法的优化结果进行对比，图6、7分别描绘了不同算法应用在两个系统时的收敛曲线。由表1、2及文献[30]所给出的机组参数可以看出，无论是各机组的出力还是系统总出力均分别严格满足机组出力限制和系统功率平衡约束，这种优化结果表明了前面所述的约束处理方法能有效处理各种复杂的计及阀点效应的多燃料经济调度安全运行约束问题，同时不至于干扰GEDE算法本身所固有的动态进化过程。由表3、4不难发现，在10机组测试系统中，采用GEDE算法取得的最小燃料费用为623.822 33$/h，平均费用为623.822 7$/h，最大费用为623.839 5$/h，标准差为0.037 1，CPU平均运行时间为4.74 s。虽然，GEDE算法引入基因编辑技术操作使得平均CPU运行时间相比于GE算法增加了3.33 s。然而，由图6收敛曲线可见，GEDE算

表1 10系统机组出力、燃料类型及总出力

表2 40机组系统出力、燃料类型、总出力和总费用

表3 10机组系统不同算法优化结果对比

法仅需148次迭代便收敛至比其他启发式算法更优的解。因此，与DE算法及其他算法相比，GEDE算法在求解计及阀点效应的多燃料经济调度优化问题时能在相对合理的时间内取得更优的解，并能有效避免出现过早收敛现象，可见算法具有较强的全局收敛性。同时，由表3结合文献[30]对表3中带*号算法最优解的纠正，不难发现，GEDE算法所取得的优化结果无论是对比于表中所列举的原始启发式算法、改进启发式算法还是混合启发式算法均具有明显的优势，甚至GEDE算法的最大值比诸如 PSO[25]、DE[19]、AA[9]、GA[6]、RCGA[13]、ARCGA[14]、IGA_MU[24]等32种算法所得最小费用还小。由表4可以看出，与DE算法相比，GEDE算法在相同初始种群、种群大小和迭代次数下，不管是最小值，平均值、最大值还是标准差均取得明显优势。显然，GEDE算法的优化结果在40机组系统中较其他算法同样保持明显优势。这一系列优势表明GEDE算法具有较好的适应性、鲁棒性和全局收敛性。