一种求解最优潮流的组合算法

1、一种求解最优潮流的组合算法             一种求解最优潮流的组合算法丁晓莺, 王锡凡, 陈皓勇(西安交通大学电气工程学院，陕西 西安710049)    摘  要： 提出了一种基于现代内点(MIP)理论与退火选择遗传算法(AGA)的组合算法：将原问题去掉整数变量约束，形成一个非线性规划问题；通过赋予整数变量矢量不同的初值，形成一个非线性规划问题集合，将其看作是AGA的进化种群，以MIP求出每一个非线性规划问题的最优值作为它的适

2、应值；通过AGA试探，找出最优个体，该个体整数变量和连续变量的取值即为原问题最优解中各变量的值。 AGA与MIP二者取长补短既能精确处理整数变量，改善计算结果的质量，又保证了算法的计算速度; 对AGA的改进提高了算法的收敛性能，增强了逃脱局部极值的能力。    关键词： 最优潮流；现代内点算法；遗传算法；模拟退火1  引言    20世纪60年代初期, 法国学者Carpentier和Siroux首次探讨了OPF问题。随着研究的不断深入，OPF已形成一个复杂的混合整数非线性规划问题。目前，无论是节点实时电价的计算、辅助服务的定

3、价、还是输电网络的阻塞管理及可用输电容量的估计等领域，都可利用最优潮流作为研究工具。从计算复杂性而言，几乎所有的整数规划问题都属于“NP hard”问题，很少有严格精确的多项式算法。一般求解此类问题有3种途径： 确定性算法，这类算法（如割平面法、分支定界法、动态规划法）保证能找到问题的最优解，但是当问题变量超过3040时，算法的效率很低，其计算时间将随变量数目的增加成指数倍增长1。 近似算法，先放弃变量的整数性要求，解一个（非）线性规划问题，然后用“四舍五入”的办法得到整数解。我们称它为（非）线性规划松弛法。由于目前求解（非）线性规划方法的研究已十分成熟，计算速度快与收敛性能稳定是该方法的过人

4、之处，然而这种办法在整数变量取值范围很大时，会使“四舍五入”后的结果产生很大的偏移，失去了“最优”的意义。 启发式算法，采用在一个群体规模内随机寻优的策略，能有效地找到问题的最优或次优解。如模拟进化规划方法2，模拟退火方法3。然而，寻得最优解的代价是计算时间的大量耗费。    保证解的质量与节约计算时间是求解整数规划问题的关键。本文提出的算法是将现代内点(MIP)理论与基于退火选择的遗传算法(AGA)4相结合，用于求解OPF问题。利用现代内点算法快速的寻优过程，可靠的收敛特性，以及多项式的计算复杂性等优点，处理模型中的连续变量；同时采用准确定性退火选择策略，通过遗

5、传操作处理整数变量，克服了简单遗传算法(SGA)随计算规模的扩大而使收敛速度减慢、容易落入局部极值的缺陷，从而能以较大的概率求得全局最优。2  OPF的数学模型与组合算法思想    最优潮流是指在满足电力系统运行约束的条件下达到所选目标函数最小的一种稳定运行状态。本文采用的OPF数学模型为   （1）目标函数（系统总的发电费用最小）：；式中  为所有有功电源的集合。    目标函数还可根据计算目的的不同而具有不同的形式，如最小网损、最小甩负荷、最高电压水平及最小控制量、变化量等。 &#

6、160; （2）等式约束（系统功率平衡方程）：                      （ 所有节点的集合）   （3）不等式约束（系统正常运行时的各种可行性约束）    1）有功源有功出力的上下界约束   ( 有功电源的集合)；    2）无功源无功出力上下界约束   （ 无功电源的集合）；&#

7、160;   3）有载调压变压器抽头位置上下界约束   （ 有载调压变压器抽头集合）；    4）节点电压幅值上下界约束    （ 所有节点的集合，平衡节点除外）；    5）线路潮流约束  （，线路两端节点的集合）式中，为发电机的有功、无功出力；，为节点 的有功、无功负荷；为第个变压器抽头位置；，为节点的电压实部与虚部，为节点导纳矩阵第行第列元素的实部与虚部；,为第台发电机的耗量特性曲线参数；为节点，之间线路的有功潮流。   

8、; 其等式约束与不等式约束也可根据应用范围的不同而增减，如应用于电力市场环境下就必须加入一些经济约束和表示市场参与者之间关系的约束5。    作为一个混合整数非线性规划问题，OPF模型中既有连续变量又有整数变量。因求解只含连续变量的OPF方法已十分成熟，且整数变量在该问题中所占比重不大，故可将问题中的连续变量与整数变量分离求解： 将原OPF问题去掉整数变量约束，形成一个非线性规划问题 ，以将连续变量与整数变量分离； 在算法的内层，采用计算速度快、收敛稳定的现代内点算法处理连续变量，从而确保整个算法的性能； 以随机寻优的遗传算法求解整数变量的最优配置，从而确保原问题

9、解的质量； 将两者求得的最优解组合，形成原OPF问题的最优解。    图1为基于以上思路所提组合算法的流程框图。图中， 为种群进化的代数，即算法迭代的次数； 为种群中染色体的序号； 为种群中染色体的数目；集合 = ， ， ； 为变压器抽头位置； 为抽头数；集合 = ， ，图1  组合算法流程框图    ， 为原OPF问题中的连续变量，包括有功源有功出力m个，无功源无功出力r个和节点电压实部与虚部2n个；非线性规划问题的集合 = ， ，调用MIP求出 的目标函数值作为它的适应值 ， ； 为退火选择遗传算法得到的最优个体， 与

10、组合构成原OPF问题的最优解；算法终止条件为：总迭代次数 >最大迭代次数，或连续一定的进化代内各染色体的适应值无变化。3  组合算法内层模块的实现    由图1可以看出，内层模块的主要功能是通过求解非线性规划问题 来确定连续变量的取值。由于每次迭代需要求解 个 ，因此求解问题 的方法的选择是决定组合算法计算速度的关键。MIP以其按牛顿下降方向寻优能可靠、快速地收敛及多项式的计算复杂度等优点成为求解 的最佳选择。    下面采用广义优化问题的模型简单介绍MIP的主要步骤。     

11、   obj              st      式中  ， 为等式约束的个数； ， ， 为不等式约束的个数； ,。    基于扰动（Karush Kuhn Tucker ，KKT)条件的现代内点算法由以下4个步骤组成    （1）用松弛变量将不等式约束化为等式约束       ，

12、式中  ； ； 。    （2）形成拉格朗日函数                 （3）导出扰动的KKT一阶最优条件    由于 ， （ 表示 ，以下形式同理）成立，原问题KKT条件转化为   ，   ， ,   ， ，   。    因不可直接求解以上方程组，所以将L

13、l和Lu经 扰动得到    ， 。式中  均为拉格朗日乘子, , ,； ；  ；  ； ； ; ; ;扰动因子 ； 为互补间隙, 为中心参数，一般取0.1。     （4）用牛顿法导出求解扰动KKT条件的修正方程为  式中  。    解上述方程得到第k次迭代的修正量，于是最优解的一个新的近似为                

14、        式中                  ,                           

15、;  i=1,2,r。     该求解、修正过程将重复进行, 直至m小于某一给定的计算精度为止，此时得到问题的最优解，计算停止。    从上述介绍可知，MIP的计算量主要在于形成和求解修正方程，因此，数据结构的优化和稀疏技术的应用将使该方法具有以下实用价值： 节点电压使用直角坐标表示形式，从而使海森矩阵中的元素为常数； 通过对问题变量的重组和矩阵的分块，可达到减少计算量、加快计算速度的目的； 采用一定的变量排列顺序，使修正方程的系数矩阵以 的块矩阵形式具有与节点导纳矩阵相同的结构，方便编程的同时可大量减少注入元的产

16、生，减少计算量、加快计算速度6。4  组合算法外层模块的实现4.1  SA与SGA的区别    组合算法的外层模块是希望通过随机寻优策略求取使 的目标函数最优的整数变量的取值。一旦寻到 ， 与 两者配合即为原问题的最优解。目前，常用的随机寻优方法主要有模拟退火（SA）和遗传算法（SGA）,二者间的区别为： SA的全局收敛性依赖于Boltzmann策略,即收敛性由参数A 控制，其中k为迭代次数, A 下降越慢, 结果越趋于最优；而SGA中没有这样的控制参数，因此，SGA存在着过早收敛的问题。 SGA同时对串解的每个个体进行搜索，能保留与前代相关的

17、所有有用信息；而SA只保留了状态空间内的一个解，它所涉及的仅是前一个解邻域内的一个可行解。 SA按照一定概率接受比原来解差的解，能使搜索跳出局部极值而达到全局最优；而SGA一般只接受比原解好的解，因此可能会引起基因损失，导致搜索失败。如果将SGA和SA的长处结合起来, 取长补短, 可得到令人满意的效果。4.2  SA与SGA的结合    为了同时得到SA和SGA的优点，其方法之一是将退火因子引入选择操作中，成为整体退火选择。整体退火选择是从种群Tk中随机独立地选择一定数量的个体作为新的父本种群 ， ，被选中的概率为 其中, 表示适应值函数，ATk表示逐渐

18、趋于0的退火温度。可以证明，在整体退火选择准则下，遗传算法收敛的充要条件是允许其父代参加竞争。因此把允许其父代参加竞争的这类遗传算法称为退火选择遗传算法4。4.3  改进措施    在实际数值实验中发现，退火选择遗传算法的收敛速度和全局优化能力表现不太稳定，影响了算法的性能。为克服这一缺点，应采用以下改进措施：   （1）准确定性退火选择标准    在简单遗传算法的比例选择准则中，选入父代的个体数目是按适应值函数大小比例随机分配的，而整体退火选择准则在这点上没有改变，仅仅是根据退火温度对比例大小进行适当修

19、正而已。由于取随机数按比例分配，受随机数影响很大，可能选入父代的个体效果不理想。所以采用一种确定性退火选择标准4，即如果新的父本种群中个体ti(k)的数目期望值为 ，为减小随机的影响，在选择父本种群个体时，可大致按上述关系式计算所得的结果进行确定数目的选择   （2）多种遗传操作混合使用    该算法设计了多种杂交、变异算子，可将其根据不同效果分配使用，例如，将个体每一位在其约束上下界之间随机取值的随机变异算子；将个体每一位根据该个体与当前最优个体之间适应值之差的大小变异，差值越小，变异时随机取值范围越窄的自适应变异算子。随机变异算子使用于迭代

20、之初，以保证种群多样性；自适应变异算子使用于迭代后期，以利于解的改进。将多种杂交和变异算子交叉使用，有时会带来较好的效果。  （3）父本种群与变异群体共同组成新子代种群    我们发现，如果子代完全采用父本个体变异之后的新群体，可能导致原最好个体的丢失而增加算法迭代次数，耗费计算时间。但如果对父代与子代中个体按适应值排序后，选择其中好的个体组成新群体，将会减少种群中的多样性而出现过早收敛和停滞现象。为权衡利弊，我们将被选入父本种群的个体无变异进入子代，构成新群体的半数，然后由父本变异之后的个体组成另外半数。这样既保证了种群的多样性，使算法能以较大的概率寻

21、到全局最优解，又逐代记录下最优个体，并随迭代次数的增加最优个体逐渐增加，以保证算法的效率。    改进后的AGA克服了SGA随计算规模的扩大而使收敛速度减慢，容易落入局部极值的缺陷，从而能以较大的概率求得全局最优。因此，改进的AGA成为求解整数变量最优取值的比较合适的方法。5   组合算法流程    总结组合算法的详细流程步骤如下：   （1） ，初始化 = ， ， ，其中，t 表示变压器抽头位置，j=1,2,l，l ³ 20,  为种群数。即将 ( r = 1,2,K, K

22、为抽头数)在其约束范围内随机取值，取 ；   （2）如果 ，转到步骤（5），否则到步骤（3）；   （3）按 固定原问题中整数变量的取值，修正节点导纳矩阵。此时，问题中只含连续变量，形成非线性规划问题 ；   （4）调用MIP程序，求出 的目标函数值，将它作为第 个染色体的适应值 ， ,转到步骤（2）;   （5）如果满足终止条件：总迭代次数 >500或连续50代内各染色体的适应值无变化，则停止计算。将最优个体 中的 与 组成原问题的最优解；否则到步骤（6）；   （6） ，用退火温度修正各染色体的适应值，计算各染色体进入父本种群的数目期望值 ， ；   （7）如果 ，转到步骤（11），否则到步骤（8）；   （8）按期望值 选择两父体，并记录其编号；   （9）使用不同杂交算子按杂交概率 对两父体杂交，形成两个新个体；   （10）使用不同变异算子按变异概率 对新个体进行变异； ,转到步骤（7）；