带杂交、变异因子的自适应蚁群算法
在电力系统无功优化中的应用
陈敬宁 何桂贤
（1.中国南方电网公司，广东 广州 510620；
2. 华南理工大学电力学院，广东 广州 510640）
摘 要：蚁群算法是一种通用仿生算法，可求解传统方法难以解决的非凸、非线性非连续的优化问题。本文针对基本算法的缺点，结合遗传算法和自适应思想对其进行改进，并应用于电力系统无功优化问题。本文通过IEEE6结点算例和某地区一个实际配电网算例，验证了算法的有效性。
关键词：电力系统；无功优化；蚁群算法
0． 引言
电力系统中无功功率不足，将产生一系列问题：电压水平下降，损耗增加，稳定性下降，用户部分用电设备工作不正常等。因此在现代电力系统运行中不仅要重视有功功率的生产和平衡，而且要十分重视无功功率的平衡和配置。电力系统无功优化是指系统在一定运行方式下，要求解满足各种约束条件，达到有功网损最小等预定目标的优化问题，无功优化问题是一个动态、多目标、多约束、不确定性的非线性混合整数规划问题，其控制变量为离散变量。它涉及无功补偿地点的选择、无功补偿容量的确定、变压器分接头的调节和发电机机端电压的配合等，是一个多约束的非线性规划问题，也是电力系统分析中的一个难题。长期以来，国内外的许多专家，学者都对此进行了大量的研究和探索工作，根据简化措施的不同，提出了很多方法，主要有试验误差法、非线形规划、线性规划、动态规划等经典方法。
在 20世纪90年代，意大利学者M Dorlgo，V M aniezzo，A Colorni等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟进化算法：蚁群算法（ant colony algorithm）。ACO(Ant Colony Optimization) 算法是作为一种包含自从1991年M Dorlgo等人提出蚁群算法以来的许多相关算法的框架而被提出来的，并且它成功地运用于解决组合优化问题，如：TSP(Traveling Salesman Problem)，QAP(Quadratic Assignment Problem)，JSP(Jobshop Scheduling Problem)。
本文针对ACO算法的一些缺点，在其中引入遗传算法的思想对其进行改进并运用于电力系统无功优化问题。
1． 无功优化问题的数学模型
电力系统无功优化问题是一个动态、多目标、多约束、不确定性的非线性整数规划问题。电力系统无功优化控制的数学模型：
minf=f(x,u)
st:g(x,u)=0
(1)
h(x,u)≤0
式 （1）中，f为目标函数，通常是有功损耗最小；g为用于约束的潮流方程；h用于确定约束变量的可行域；U为控制变量即调度人员可以调整、控制的变量。一般常用的控制变量有：
（1）除平衡节点外，其它发电机的无功出力：
（2）所有发电机节点（包括平衡节点）及具有可调无功补偿设备节点的电压模值；
（3）可调变压器的变比；
（4）并联电抗器和／或电容器的成组投切；
X为状态变量即通过计算而确定的变量，一般常见的有：
（l）除平衡节点外其它所有节点的电压相角；
（2）除发电机节点以及具有可调无功补偿设备节点之外，其它所有节点的电压模值。
有的也采用发电机节点及具有可调无功补偿设备节点的无功出力作为控制变量，则它们相应的节点电压模值就要改作为状态变量。
无功优化问题的一般约束条件为：
（1）潮流方程约束：
（2）支路潮流限制；
（3）节点发电出力限制；
（4）节点电压限制；
（5）可调变压器变比的限制；
（6）并联电抗器和／或电容器的投切容量限制。
对于经典无功优化问题来说，并不一定包含上述所有控制变量和所有约束条件。其目标函数通常都是网损最小，还可以为电压水平最好，无功补偿容量最小等。
3． 蚁群算法及其改进
蚁群算法是一种通用仿生算法，可求解传统方法难以解决的非凸、非线性非连续的优化问题。它通过模拟蚂蚁群的行为来求解问题，本质上是一种基于群体的多代理算法。蚁群算法与其它模拟进化算法一样，通过候选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。
3．1 蚁群算法原理
蚁群算法通过模拟蚂蚁寻找食物并回到巢穴的方法来求解问题。研究表明，蚂蚁在前进途中会留下一种信息素(pheromone)。蚂蚁就是用这种物质来与其它蚂蚁交流、合作，以找到较短路径。经过某一路径的蚂蚁越多，路径上的这种信息素的强度就越大。蚂蚁选择路径时就偏向于选择信息素强度大的方向。这就是蚂蚁能找到回到巢穴或食物处的较短路径的原因。通过实验还表明，这种跟随信息素强度前进的行为会随着经过的蚂蚁的增多而加强。由于通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过这条较短路径上的点，这些点上的信息素的强度就会因蚂蚁经过它的次数更多而更强，这样就会有更多的蚂蚁选择这条路，这条路径上的信息素的强度就会越来越大，选择这条路径的蚂蚁也会越多。
3．2 基本算法
为了便于说明，我们采用n城市（0，1，…，I，…，j，…，n－1为城市编号）的TSP问题来解释基本蚁群算法。N城市TSP问题就是无重复经过n座城市时走过的路程最短的问题。
设m为蚁群数量，dij为城市i、j间距离，Tij为路径ij上残留信息素数量，
初始时各路径上信息素的量相等：Tkij =C（C为非零常数），蚂蚁k（k＝0，1，…，m）从城市i向城市j的概率
式中allowk＝{0，1，…，n-1}-tabuk，为蚂蚁k下一步允许选择的城市；a、B分别为T、η作用程度。人工蚂蚁和自然蚁群系统不同之处在于人工蚁群系统具有一定记忆力：tabuk用以记录蚂蚁k走过的城市，而且随着进化过程不断动态调整。
信息素随时间推移而减少经过n各时刻，蚂蚁完成一次循环后，各条路径上信息素根据下式调整：
式 （3）中△Tij为本次循环中留在路径ij上的总信息素量，有三种计算方法：
式中：Q为常数。这三种计算方法中，前一个利用整体信息，后两个利用局部信息，它们分别称为Ant-cycle System、Ant-quantity System及Ant-density System。
3．3 蚁群算法的不足之处以及本文改进算法的思路
由前面对蚁群算法的介绍可知，蚁群算法在运算过程中，蚁群的转移是由各条路径上留下的信息量的强度和城市之间的距离来引导的。蚁群运动的路径总是趋近于信息量最强的路径。通过对蚁群以及蚁群算法的研究表明，不论是真实蚁群系统还是人工蚁群系统，通常情况下，信息量最强的路径与所需要的最优路径比较接近。
然而，信息量最强的路径不是所需要的最优路径的情况仍然存在，而且在人工蚁群系统中，这种现象经常出现。这是由于在人工蚁群系统中，各路径上的初始信息量是相同的，蚁群创建的第一条路径所用到的信息就主要是城市之间的距离信息，这时，蚁群算法等价于贪婪算法，这一次，蚁群在所经过的路径上留下的信息就不一定能反映出最优路径的方向，特别是蚁群中个体数目较少或者所计算的路径的组合较多时，就更不能保证蚁群创建的第一条路径能引导蚁群走向全局最优路径。这一次循环中，蚁群留下的信息会因正反馈作用使这条不是最优，而且可能是离最优解相差很远的路径上的信息得到不应有的增强而阻碍以后的蚂蚁发现更好的全局最优解。
不仅是第一次循环所创建的路径可能对蚁群产生误导，任何一次循环，只要这次循环所利用的信息较平均地分布在各个方向上，这次循环所产生的路径就可能会对以后蚁群的选择产生误导。
蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合，这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度较慢，正反馈原理旨在强化性能较好的解，却容易出现停滞现象。这是造成蚁群算法的不足之处的根本原因。
当问题规模比较大时，由于信息量的挥发系数1-p的存在，使那些从未被搜索到的解上信息量会减小到接近于0，降低了算法的全局搜索能力，而且1-p过大时，当解的信息量增大时，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力。通过减小1-p虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低。
也就是说蚁群算法与遗传算法等模拟进化算法一样也存在着易于陷于局部最小值的缺陷。
因此，蚁群所找出的解需要通过一定的方法来增强，使蚁群所留下的信息尽可能地不对以后的蚁群产生误导而且能够克服计算时间较长的缺陷，从而提高蚁群算法的全局搜索能力，提高其搜索速度。
受到遗传算法中的杂交和变异算子的作用的启发，我们提出一种新的蚁群算法——具有杂交、变异特征的自适应蚁群算法。
改进算法主要在算法的基础上增加了杂交算子、变异因子和对挥发系数进行自适应变化。
3．3．1 杂交
在杂交之前需要选择父体蚂蚁。本文算法采用的是转盘式选择(Roulette Wheel Selection)。采用这种选择策略需要先计算第k只蚂蚁本次循环所产生的路径的长度，并根据这个长度按下式计算各只蚂蚁被选择的概率：
用这种方式选择，1/Lk较大的蚂蚁即(Lk较小的蚂蚁被选中的几率更大。选择蚂蚁杂交后，允许按一定的比例吸收略差的蚂蚁或只吸收比原解对应的路径长度小一定百分比的蚂蚁，对被吸收的蚂蚁执行全局更新规则具体见下面所列算法。
杂交过程为：先随机选择两个杂交点。然后交换两父体中、在所选杂交点之间的部分这个部分被称为杂交段。将父体1的杂交段位置不变地复制到后代2中，同样也将父体2的杂交段位置不变地复制到后代1中。父体1中的其他元素不变，用没有经过的部分按先后顺序代替父体1中与父体2 杂交段相同的元素。对父体2 进行同样的操作。计算杂交生成后代路径的长度，如果比父体路径要短则更新信息素、用后代取代父体位置，否则取消杂交。这样就完成一次杂交。
3．3．2 变异
如同遗传算法一样，我们使用小随机概率来决定每只蚂蚁是否发生变异，也就是说发生变异的蚂蚁是随机选定的。在本文中我们采用逆转变异方式。
设选定的某个个体所走过路径为：i0、i1、i2、…、i( n- 1 )，其中i0,i1,…,in-1∈{0，1，2，…，n- 1}。本文使用两个随机数来决定变异点，决定变异点后，将两个变异点之间的城市按与原来相反的顺序排列。重新计算这个个体所走过的路程，如果比原来短则保存变异并更新信息素，否则取消变异。这样就完成一次变异操作。
3．3．3 自适应
对于算法因为选择策略的缺点，我们从选择策略方面进行修改，我们采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态地调整作确定性选择的概率。当进化到一定代的数目后，进化方向已经基本确定，这时对路径上信息量作动态调整，缩小最好和最差路径上的信息量的差距，并且适当加大随机选择的概率，以利于对解空间的更完全搜索，从而可以有效地克服基本蚁群算法的两个不足。此算法按照下式确定蚂蚁ｋ由ｉ转多到的下一城市j：
式 （4）中，Po∈(0,1),r为(0,1)中均匀分布的随机数。当进化方向基本确定后用简单的放大(或缩小)方法调整每一路径上的信息量。
对于挥发系数1-ρ，本文方法自适应改变ρ的值。ρ初始值为1；当算法求得的最优值在N次循环内没有明显改进时，ρ减为：
式 （5）中ρmin为ρ的最小值。用于防止ρ过小而降低算法的收敛速度。
4． 算例
要将蚁群算法应用于电力系统无功优化中，只需要将系统中各个可调变压器变比、电容或电抗投切容量等量化分级作为“城市”让蚂蚁进行搜索，而目标函数为系统最小网损即可。在无功优化算例中，以外点发构造辅助函数，将平衡节点有功上下限等不便于计如可行域的约束变量以罚函数的形式计于目标函数中，以QG、 QC、V、T上下限界定可行域。
本文采用IEEE6节点系统和广州地区的一个23节点配电网作为算例以验证本文改进算法有效性。
算法中参数如下：蚁群蚂蚁数量m＝10；初始信息量＝1.0；T、η作用程度、a、β分别为1.0、2.0；残留信息素单位时间内蒸发度（初始值）1－ρ＝0.1。
