李桂鑫1迟福建1刘聪1
（1.国网天津市电力公司天津300010）
摘要：对遗传算法进行简单描述，根据其特点对遗传算法做出改进。在转移概率的改进中，本文实现了参数、与最大迭代次数Nmax的联动性；在信息素挥发因子的改进中，提出一种基于自适应的挥发因子；进而明确改进遗传算法的配电网网架优化步骤后，并经过仿真验证该方法的可行性和有效性。
前言
遗传算法是一种高效的、并行全局搜索方法，它能够在整个优化过程中自动搜索知识空间中的解，并能够自适应的控制整个搜索过程以求最优解空间。遗传算法通过优胜劣汰的生存原则，从潜在的优化方案中逐次产生最优解的方案。在遗传算法的迭代过程中，它会通过不断地复制、变异及交叉得到比初始染色体更好的适应度值，如同自然界中的不断进化，遗传算法的过程导致种群中个体的不断进化，并得到比原个体更加适应环境的新个体。
1遗传因子
1.1选择过程
选择过程又称为复制过程，是从群体中按照优胜劣汰原则选择或者复制优良个体组成新群体的操作。选择是建立在适应度值计算的基础之上，而个体适应度值是从目标函数转换得出。
轮盘赌方法又称为适应度比例法，是遗传算法中最为常用的选择方法。它是通过每个个体适应度的概率决定下一代个体存留的可能性。在每一轮的选择过程中会随机产生0到1之间的数值，并将该数值作为选择指针确定选择个体，因此，当个体适应度较大时，其被选择的概率就越大。这一概率值可以表示为1-1：
其中，Pi为个体i的选择概率；fi为个体i的适应度值；N为群体规模大小。根据式1-1可以看出，如果个体适应度值越大，则个体被选择的概率就越大。
1.2交叉过程
交叉过程是对自然界中生物进化中遗传基因重组变异的仿真，也是遗传操作中的核心部分，通过交叉过程，可以将父代两个个体间的部分结果分解重构，并生成新的个体。通过交叉操作得到的新个体能够更加适用于约束环境，加强算法的搜索能力，使算法性能得以提高。
均匀交叉的交叉过程更为广泛，染色体上面的每个基因编码都可作为潜在的交叉点。均匀交叉首先需要产生与染色体同长的掩码，然后明确掩码中的变量值是由哪个父代个体提供，再进行交叉操作，便可得到新的个体。
1.3变异过程
在自然界的基因遗传中，某些基因会在复制过程中出现错误，从而导致染色体上的某些基因发生变异。遗传算法中的变异过程是指对染色体上某些基因值作变动，从而产生新的个体。遗传算法的变异操作，能够改进算法的局限性，提高算法优化的能力，从而跳出局部最优现象的发生。遗传变异过程如下例所示：
个体a：11100101变异后得到新个体a，：11110101
由上例可以发现，个体的变异发生在第四个基因编码上。一般地，遗传变异操作发生的概率较小，结合选择过程和交叉过程，可以保证染色体的遗传过程中减少优秀信息的缺失，保证算法有效性。
2遗传算法的改进
2.1编码方式的改进
遗传算法中常用的编码为二进制编码，该编码方式简单易行，并且利于交叉、变异等操作的实现。但是，当遇到高维度、高精度的优化问题时，就不能很好的克服由函数高维映射造成的误差，导致算法局部搜索能力下降，并不能得到问题所求的最优解。针对此问题，人们提出格雷编码方式将该问题得以解决；格雷编码方式是二进制编码方式的变形；它将两个连续对应的编码值，让其码位中出了一个不同之外，其余的都相同。设现有二进制编码，则其对应的格雷编码为，他们之间的转换方式为：
其中，fmax为群体中最大适应度值；f为两个交叉个体中适应度值较大个体的适应度值；favg为群体平均适应度值；f为变异个体的适应度值；k1，k2，k3，k4为0到1之间的常数。
通过公式可以看出，交叉变异概率的自适应确定，如果是或者，则其概率是呈线性变化的，并且种群中最大适应度个体的交叉变异概率为0；反之，则概率值为固定常数不变。这就会导致如果在遗传过程的早期，其概率值是自适应的改变，但随着进化过程的加深，其概率值就会一成不变，这很容易导致算法陷入局部最优，使得算法过早收敛。因此，针对这一问题，可以按照以下方式进行改进。
其中，fmax为群体中最大适应度值；f为两个交叉个体中适应度值较大个体的适应度值；favg为群体平均适应度值；f’为变异个体的适应度值；k1,k2为0到1之间的常数；Pc1的取值为0.9或者1；Pc2为0.5到1之间的数值；Pm1取值0.1；Pm2为0.05到0.1之间的数值。通过这种方式的改进，可以提高种群中个体的交叉变异概率，也意味着群体中最大适应度个体的交叉变异概率也被提高，其概率值不再是0；这不但实现了算法交叉变异概率的自适应性，还提高算法的局部搜索能力，帮助算法达到全局最优。
3算例验证
遗传算法种群数量通常是通过主观经验进行确定，因此，为保证算法能够得
到最优值，本文将设置不同的种群数量进行运算得到最优解空间，并从中选取最
优值。
本文对改进遗传算法的基本设计如下：
（1）编码方式：采用格雷编码方式，容易解决网架优化中的高度非线性问
题。
（2）初始种群：以随机的方式生成初始种群。
基于以上分析，可设置改进遗传算法的运行参数，即设定种群数量NAGA=90，最大迭代次数Tmax=2000，算法收敛判断依据，交叉概率参数Pc1=0.5、Pc2=0.4、Pc3=0.3，变异概率参数Pm1=0.3、Pm2=0.2、Pm3=0.1运行算法程序，得出算法的最优迭代图如图1所示：
绿线代表遗传算法每次迭代的最优结果，蓝线代表算法每次迭代的初始值。从图中可以看出，绿线所代表的的最优结果呈平缓下降趋势，说明改进后的算法能够在每次迭代中找到最优值，算法的收敛速度较快，并且能够避免陷入局部最优的情况发生。蓝线代表的每次迭代的初始解基本上呈现递减的趋势，但其中出现了小的波动，这是因为我们在设定初始值时，是利用随机的方式选取的初始种群，从而造成每次迭代都会出现不同情况的初始值，但总体上还是能够与绿线重合，得到最优结果。
为进一步说明改进后遗传算法的优化效果，我们将其与基本遗传算法的优化
效果做出对比；首先设置一般遗传算法的基本参数，即设定种群数量NAGA=90，最大迭代次数T=2000，设定算法交叉概率为Pc=0.8，Pm=0.1。得到对比结果如表1所示。
从上表可以看出，改进遗传算法的迭代次数为320次，小于基本遗传算法，改进遗传算法能够较快的收敛并进行全局寻优。从最优结果来看，算法的最优值
1.271要小于基本遗传算法的最优值1.405；造成这种现象的出现是由于基本遗传算法在寻优过程中陷入了局部最优，算法过早的收敛，并没有达到全局最优；从一定程度上反映出对遗传算法的交叉概率和变异概率进行自适应改进能够明显的帮助遗传算法根据不同情况制定不同的概率值，从而避免算法过早收敛并跳出局部最优，使得算法能够达到全局最优。遗传算法与表中其他两种算法进行比较，从最优值上可以看出，遗传算法的优化能力要强于模拟退火法（SA）以及禁忌搜索法（TS）；尤其是改进遗传算法的最优值（1.213）与平均值（1.26）远远的优于其他两种算法；这正好体现出了遗传算法在解决配电网网架优化问题时的优越性能。
4总结
遗传算法（GA）是根据自然界生物进化理论演化而来的一种高性能优化算法；其强大的全局搜索能力以及良好的优化性能，自创建以来得到广泛的应用和发展。本文首先介绍遗传算法（GA）的基本理论，并详细的阐述了GA的三个基本算子：选择算子、交叉算子以及变异算子。其次，在基本遗传算法的基础之上，本文分别从遗传算法的编码方式、交叉概率Pc和变异概率Pm三个方面对其做出改进，并将其应用于配电网网架问题中去。在制定出详细的基于改进遗传算法的配电网网架优化步骤之后，本文还将改进遗传算法（IGA）与基本遗传算法以及其它算法的计算结果相比较，通过比较发现：遗传算法（GA）的优化性能要远远的高于模拟退火法（SA）和禁忌搜索法（TS）；而改进后的遗传算法（IGA）的优化结果要强于基本遗传算法（GA）；这是因为改进后的遗传算法（GA）能够避免算法过早的收敛并跳出局部最优，从而得到全局最优。最后，得到经改进遗传算法（IGA）优化后的配电网网架图；说明改进后的遗传算法在配电网网架优化的问题中具有良好的应用价值和前景。
参考文献
[1]梅念,石东源,杨增力,段献忠.一种实用的复杂配电网故障定位的矩阵算法[J].电力系统自动化,2007,31(10):66-70.
[2]刘健，倪建立，杜宇.配电网故障区段判断和隔离的统一矩阵算法[J].电力系统自动化，1999,23(1):31-33.
[3]许奎，张雪松，杨波.配电网故障定位的改进通用矩阵算法[[J].继电器,2007,35(3):6-8
[4]王飞，孙荣.配电网故障定位的改进矩阵算法[J].电力系统自动化，2003,27(24):45-46,49.
[5]陈鹏,滕欢,滕福生.故障信息不足时配电网故障定位的方法[J].电力系统自化,2003,27(10):71-72
[6]智秀霞.配电网行波故障测距的研究[D].华北电力大学硕士论文,2009
作者简介
李桂鑫（1981年9月—），男，汉族，高级工程师，研究生学历，祖籍天津市。主要从事电网规划管理，工作单位：国网天津市电力公司。