...线性规划问题的粒子群算法定稿 .doc

吴和海++熊高峰+袁晋蓉+秦跃杰

摘 要： 针对机组组合这一高维、非线性混合整数规划问题，提出一种结合修补策略的整数编码粒子群（ICPSO） 算法。用正负整数分别表示机组开停机的时间长度，有效减少待优化变量个数。基于机组组合问题的特点，采用修补策略处理不满足约束条件的个体，使算法只在可行解区域内搜索，有效提高收敛速度，通过切除冗余机组，提高解的质量。仿真算例表明，相比整型编码遗传（r?ICGA）算法、改进粒子群（IPSO）算法、社会演化（SEP）算法，提出的ICPSO算法能够更有效地处理大规模机组组合优化问题，执行时间较短、求解精度更高。

关键词： 机组组合； 粒子群算法； 整数编码； 修补策略

中图分类号： TN919?34； TP18 文献标识码： A 文章编号： 1004?373X（2017）11?0167?05

An modified integer?coded particle swarm optimization algorithm

for unit commitment optimization

WU Hehai， XIONG Gaofeng， YUAN Jinrong， QIN Yuejie

（College of Electrical and Information Engineering， Hunan University， Changsha 410082， China）

Abstract： Aiming at the high dimension and nonlinear mixed integer programming problems of unit commitment， an integer?coded particle swarm optimization （ICPSO） algorithm combined with repairing scheme is proposed. The positive and negative integers are used to represent the time length of unit startup and shutdown to reduce the quantity of variables under optimization effectively. On the basis of the characteristic of unit commitment， the repairing scheme is adopted to handle the individuals which can′t conform to the constraint conditions， so as to make it only search in the feasible solution region， and improve the convergence rate. The redundancy unit is cut out to improve the quality of solution. The simulation example results show that， in comparison with r?ICGA， IPSO algorithm and SEP algorithm， the ICPSO algorithm can handle the combinatorial optimization of large?scale units effectively， has shorter execution time and higher solving accuracy.

Keywords： unit commitment； particle swarm optimization； integer coding； repairing scheme

0 引 言

机组组合优化是电力系统经济调度中一个非常重要的问题，它的高维数、非凸、离散、非线性，使得理论上很难求取其最优解。但由于它能够带来显著的经济效益，许多国内外学者一直在积极研究，提出各种方法来解决这个问题，例如，动态规划法、拉格朗日松弛法、优先顺序法等确定方法以及遗传算法、蚁群算法、模拟退火等智能优化算法[1?2]。但到目前为止，以上方法均存在一定的缺陷，如面临“维数灾”、求解时间较长、精度不够高等，不适合实际机组组合的优化。

粒子群优化算法（PSO）是一种随机全局优化算法，该算法自提出以来，因为其具有简单、收敛速度快且效果显著等优点，在各个领域得到广泛的应用[3?6]。目前粒子群算法在求解机组组合问题时[7?8]，普遍采用二进制编码方式，用0?1表示发电机组的开停机状态；处理约束条件在适应度函数中加入惩罚项。对于大规模机组系统，这种编码方式会导致种群个体长度过长，影响算法搜索效率，浪费大量求解时间[9]；惩罚项的引入会使得计算时间的极大增加，同时惩罚乘子的调整也存在困难[10]。

针对上述问题，本文提出一种适用于大规模机组组合问题的整数编码粒子群算法。采用整数编码方式来表达机组组合问题，有效减少待优化变量个数；同时采用粒子修补策略处理不满足约束条件的粒子，以提高搜索速度和解的质量。算例仿真验证了文中所提出的算法能够有效求解电力系统大规模机组组合问题。

1 机组组合的数学模型

1.1 目标函数

电力系统机组组合问题是指在规定的时期内，在满足功率平衡等约束条件下，合理的安排机组的开停机顺序与出力，使得系统的总发电成本最小。机组组合问题的目标函数可表示为[11]：

（1）

式中：为系统总发电成本；代表机组台数；为时段总个数；为机组在时段内的输出功率；为机组在时段内的开停机状态，当时表示机组开机，时表示机组停机；表示机组在时段内的耗量成本，其中，为机组的运行成本参数；表示机组在时段内的启动成本，它与机组启动之前的连续停机时间长短有关。

1.2 约束条件

（1） 功率平衡约束：

（2）

（2） 最小开/停机时间约束：

（3）

（4）

（3） 机组出力上下限约束：

（5）

（4） 旋转备用约束：

（6）

（5） 机组爬坡约束：

（7）

（8）

（6） 最大开关机次数约束：

（9）

式中：表示调度时段内的系统负荷需求；表示机组开机后的最小开机时间；表示机组的最小停运时间；表示机组的最小出力；表示机组的最大出力；为时段内的旋转备用值；分别为机组的功率最大上调量、下调量；表示机组在调度周期内的开停机次数；为机组在调度周期内允许的最大开停机次数。

2 基于整数编码粒子群算法的机组组合问题

求解

2.1 整数编码

用正负整数分别表示机组开停机时间长度，机组开停机状态设计为矩阵： （10）

式中：为粒子种群中的第个个体；表示机组的状态阶段所持续的时间，正整数值代表机组连续开机的小时数，负整数值代表机组持续停机的小时数；表示机组开停机阶段数的上限（每台机组一般每天开停机次数不超过5次），一些重负荷机组的开停机阶段数不足时用数字0填充，从而保持粒子矩阵列数恒定。每行表示某机组在调度周期内的开停机安排，满足。第台机组所有时段的启停安排由一组正负相间的整数串来表示，构成矩阵的行向量。所有机组的整数串（行向量）组成整个调度周期全部机组的启停安排，即机组组合问题的解。

图1详细演示了如何通过一个10×5的整数编码矩阵表达10机组在24 h内的一个调度安排。若使用二进制编码，同样的调度所需的矩阵规模增大至10×24，计算量将大大增加。例如第六行向量 [-8，6，-5，4，-1]表示此机组在1～8时段内停机，9～14时段内开机，15～19时段内停机，20～23时段内开机，24时段内停机。该编码方式从特性上就限制了机组在一个调度周期内的启停状态次数最多不超过满足机组最大开停机次数的约束。

2.2 粒子种群的初始化

（1） 时，机组在第一个状态阶段持续的时间：

（11）

式中：表示机组在上一个调度周期最后一个状态阶段持续的时间，这样生成的能够保证机组延续前一个调度周期的状态且满足最小开停机时间约束。

（2） 时，考虑到机组需满足最小开停机时间约束，可按式（12）初始化：

（12）

式中：表示第个状态阶段后剩余的调度时段数。

（13）

（3） 即最后一个状态阶段，它所持续的时间初始化如下：

（14）

由于随机数的原因，若前个状态阶段的持续时间之和等于调度周期时段数则余下的状态阶段所持续的时间用0来补充，保证所有的粒子矩阵有相同的列数。根据式（11）～式（14）初始化得到的粒子種群，满足机组最小开停机时间约束。

2.3 粒子进化

粒子在寻优过程中，依据迄今为止找到的最优解和整个粒子群搜索到的最优解来调整粒子的进化速度和方向。

粒子的速度按照下式进行变化：

（15）

粒子位置的更新公式如下：

（16）

式中：为种群粒子个数；为第次迭代后粒子的速度；为第次迭代后粒子的位置；为粒子个体的历史最优位置；为种群最好位置；rand1，rand2为[0，1]之间的随机数；是加速度常数；为惯性权重；Int为取整符号。

2.4 修补粒子

在粒子群迭代优化过程中不可避免地会产生一些无效的粒子，在这些无效粒子中会有各个状态阶段的持续时间之和不等于调度周期时段数整数串不是正负相间的情况，从而导致该粒子无效。需要对粒子个体进行修补，按行向量的先后顺序进行。以个体中行为例，具体措施如下：

（1） 若保持前个状态阶段持续时间不变，其中满足且令段的值变为0，正负保持不变；

（2） 若，考虑到此种情况修补繁琐、耗时较多，则重新初始化该粒子；

（3） 若行不是正负相间的整数串，则保持的大小不变，依次调整它们的正负号以满足条件；

（4） 若有的情况，则交换两者的位置，否则不满足编码方式的特性。

2.5 约束条件处理

2.5.1 旋转备用约束处理

每个时段都应该对旋转备用约束进行检验，若违反约束，则应调整机组开停机状态。本文采用机组最小耗量与机组的最大出力之比作为指标，对机组进行优先排序[12]。当时段所有开机机组的最大输出功率之和小于系统负荷量和旋转备用时，对按照指标排列好的机组逐一检查其开停机状态，将状态为0的机组开启，直到满足旋转备用约束，转至时段继续检验。

2.5.2 最小开停机时间约束处理

违背最小开机时间约束通常出现在高峰负荷时段，因为峰值时间往往低于最小开机时间。类似地，因低负荷持续时间一般低于最短关机时间，最小关机约束的违背常出现于低负荷时段。在粒子群进化过程中，采用最小开停机时间修补策略对粒子编码矩阵进行修复[13]。

如图2所示，若检查是否满足最小开机时间约束，若不满足，则将变为1，机组继续开机；如图3所示，若检查～时刻机组是否都能满足最小停机时间约束，若不满足，则机组继续开机，变为1。

2.6 切除冗余机组

在求解过程中，由于缺少对机组运行实际特点的考虑，易出现小容量机组运行过多、机组备用容量过剩的情况，使得发电成本增加。因此有必要关闭多余备用机组，即切除冗余机组。

在调度周期内，依次检查每个时段内所有开机机组的最大出力之和是否超过系统负荷和旋转备用。若超过，则按优先表逆序关闭已开机组。再重新检测，直至该时段机组输出总功率不过量。

3 算例分析

本文采用经典算例对算法的性能进行检验，为了便于对比分析，不考虑爬坡约束，可以直接采用等微增率准则进行负荷经济分配。计算中粒子种群大小取20；最大迭代进化次数取100；均取2；权重系数从0.9～0.4线性递减，粒子最大速度为10。计算周期为一天，全天分为24个时段。机组开停机阶段数的上限考虑到粒子群算法的随机性，应用本文ICPSO算法进行20次独立迭代计算，取其中最好的解作为最终优化结果。

采用文献[8?9]中的10台机组参数和24 h的负荷数据以及旋转备用，并根据上述文献中的复制方法将系统规模扩大至20台、40台、60台、80台和100台，系统负荷和备用同时按比例增加。

表1给出ICPSO算法求得的10机组系统最优运行成本，系统总的运行成本为$563 937.7，其中启动总成本费用为$4 090，机组发电总成本为$559 847.7，最优调度表见表2。

表3为本文的ICPSO算法与其他优化算法[8?9，11]对10～100台机组系统求解结果的比较。可以看出，对于10机组系统，本文ICPSO算法和r?ICGA都能获得相同的总费用，优于SEP，IPSO算法；随着机组台数的增加，ICPSO的求解结果均优于其他三种方法，验证了本文算法求解大规模机组组合问题的有效性和高精度性。

图4给出了本文算法在不同机组规模下的执行时间曲线，随着机组台数的增加，执行时间近似线性增长，10机组时耗时约3.2 s，100机组时也只需要28.2 s左右。这是由于本文采用修复策略对不可行粒子进行修复，使算法只在可行解区域内搜索最优解，有效提高收敛速度；同时相比二进制编码，本文的整数编码方式能有效提高粒子群算法的搜索效率。因此本文提出的整数编码粒子群算法更适用于求解大规模机组组合问题。

图4 不同机组规模的执行时间曲线

4 结 语

本文采用整数编码粒子群算法来求解机组组合问题。通过整数编码方式，用正负整数分别表示机组开停机时间长度，相比于二进制编码它能有效减少待优化变量个数。求解过程中针对机组组合问题的特点，采用修补策略处理不满足约束条件的粒子，使算法只在可行解区域内搜索，通过切除冗余机组提高解的精度。仿真算例表明，相比r?ICGA，IPSO，SEP，本文提出的ICPSO算法求解大规模机组组合优化问题具有更高的精度，求解时间大幅度减少。

参考文献

[1] KAZARLIS S A， BAKIRTZIS A G， PETRIDIS V. A genetic algorithm solution to the unit commitment problem [J]. IEEE transactions on power systems， 1996， 11（1）： 83?92.

[2] 黎静华，兰飞.机组组合问题的模型及算法综述[J].现代电力，2011，28（6）：1?10.

[3] 李丹，高立群，王珂，等.电力系统机组组合问题的动态双种群粒子群算法[J].计算机应用，2008，28（1）：104?107.

[4] 张涛，史苏怡，徐雪琴.基于二进制量子粒子群算法的含分布式电源配电网重构[J].电力系统保护与控制，2016，44（4）：22?28.

[5] 方源，章桐，陈霏霏，等.電动车动力总成噪声品质粒子群?向量机预测模型[J].西安交通大学学报，2016，50（1）：41?46.

[6] 王春枝，张会丽，叶志伟，等.一种基于混沌粒子群算法和支持向量机的 P2P流量识别方法[J].计算机应用与软件，2015（8）：288?291.

[7] 耿晓军，王刚.粒子群算法应用于机组组合问题的优化[J].现代电子技术，2007，30（16）：111?113.

[8] 赵波，曹一家.电力系统机组组合问题的改进粒子群优化算法[J].电网技术，2004，28（21）：6?10.

[9] 张伟，赵进慧，王宁.带修复操作整型编码遗传算法求解大规模机组组合问题[J].化工学报，2012，63（9）：2972?2979.

[10] AMJADY N， SHIRZADI A. Unit commitment using a new integer coded genetic algorithm [J]. European transactions on electrical power， 2009， 19（8）： 1161?1176.

[11] 王喆，余贻鑫，张弘鹏.社会演化算法在机组组合中的应用[J].中国电机工程学报，2004，24（4）：12?17.

[12] 黎静华，韦化.求解机组组合问题的领域搜索法[J].中国电机工程学报，2008，28（13）：33?40.

[13] 蔡振华.考虑电价的机组组合问题研究[D].长沙：湖南大学，2013.