机组优化组合问题的随机tabu搜索算法
吴金华，吴耀武，熊信艮, 钟德惠
（华中科技大学电气工程学院，湖北省 武汉市 430074）
摘 要：针对机组组合问题的特点，作者对tabu搜索策略和模拟退火算法（SA）的组合算法-随机tabu搜索策略的编码方式、移动规则和tabu表的构造等作了适应性的改进，并对实际机组组合算例进行了求解。仿真结果表明，tabu－SA组合算法有效地结合了SA算法的大规模寻优特性和tabu搜索的局部搜索能力强的特点，能快速搜索到高质量的系统优化解。而且随机tabu搜索算法具有框架性算法不易陷入局部最优的特点，易于与其他算法结合来构造新的高效组合算法。
关键词：机组组合；Tabu搜索；模拟退火算法；随机搜索
1 引言
机组组合是电力系统短期经济调度的一项重要任务。在数学规划上，机组组合问题属于NP完备（NP-Complete）问题，当系统规模较大时，几乎无法找出理论上的最优解。但由于它能够带来显著的经济效益，人们一直在积极研究和开发了各种算法来解决这个问题。例如：优先顺序法简单且计算速度快，但难于找到全局最优解；动态规划法、分支定界法理论上能找到最优解，但易陷入“维数灾”；拉格朗日松弛法运用灵活且成功地解决了大系统的机组组合问题，避免了“维数灾”，但需模型连续可导且具有凸性，等等。近年来，随着计算机、人工智能技术的发展和仿生优化算法的出现，一些新的优化算法迅速发展并在机组组合问题领域内取得了富有成效的应用，如遗传算法[1,2]、模拟退火法[3]、tabu搜索[4]和人工神经网络法[5]等。但由于各算法都各具优点和不足，如遗传算法对大规模系统寻优效果较差；模拟退火算法计算相当费时；tabu搜索的大规模寻优特性稍弱；而人工神经网络则对计算初值依赖较强等。如何对各算法进行改进，对它们的确良优缺点进行有效的取舍便成了今后各算法应用研究的热点。
针对机组组合问题的混合离散优化等特点，本文对tabu搜索和SA算法的组合算法——随机tabu搜索策略的数据编码、移动规则和tabu表作了适应性的构造，并运用其对机组组合问题进行求解，取得了很好的效果。算例仿真证明了其有效性。
2 随机tabu搜索的基本原理
Tabu搜索的基本思想是由F.Glover在20世纪60年代末提出来的，近年来逐步形成为一套系统的优化理论。Tabu搜索策略本质上是各类局部搜索法和启发式迭代法的一般框架，其主要特征是适应记忆（adaptive memory）和响应探索（responsive exploration），并因此而具备了智能特色。由于其构造实施的多样性和在许多最优化问题中的成功应用，研究结果表明，在解的优劣程度相当的条件下，tabu搜索的速度一般快于SA和遗传算法（GA），使之成为离散优化领域内又一研究热点。
Tabu搜索主要由移动（move）、tabu表（tabu list）和释放水平（aspiration level）构成。首先利用随机方法或与问题有关的启发式方法产生一个当前解X（即初始解，n维向量）之后，按一定的规则，采用一组“移动”对X进行操作，产生一组试验解。选择其中的最好解令为当前解，重复迭代，求出系统最优解。为了防止搜索过程返回到已经访问过的局部最优点，tabu搜索采用了适应记忆策略。将最近若干次所实现的移动的反方向记录到tabu表中，凡是tabu表中的移动一般不可作为下一步的搜索方向，从而防止产生循环，避免了局部最优。同时，为了尽可能不错过产生最优解的“移动”，tabu搜索对tabu表中的“移动”都赋予一个释放准则，当其达到了释放准则，则该“移动”将从tabu表中释放出来而不再被限制。
模拟退火算法（SA）也是一种适合于求解大型组合优化问题的技术，其核心在于模拟热力学中液体的冻结与结晶或金属溶液的冷却与退火过程。模拟退火算法是将Metropoplis接受准则引入到局部迭代改进算法中，一定程度上具有了脱离局部最优“陷阱”的能力。随机tabu搜索策略则是将SA算法的Metropolis接受准则嵌入到一般tabu搜索框架中，即在tabu搜索的每步局部迭代中，除采用tabu表来限制下一步的搜索方向，还通过Metropolis接受准则来决定局部优化解的接受。因此，与普通tabu搜索策略相比，它具备更高的全局寻优能力；与模拟退火算法相比，随机tabu搜索策略的解生成过程由于其搜索的方向性和搜索范围的不断调整而更有效。文献[6]对随机tabu搜索的全局收敛性进行了分析与证明。
3 随机tabu搜索在机组组合中的应用
3.1 机组组合问题的数学模型 设系统调度期间的时段数为H，系统中机组或等效机组数为G，各时段系统总负荷为PDt，则目标函数和主要约束条件的数学描述如下
式中 Fit (Pit)为t时段i机组的运行费用；STi和SDi为i机组的启停费用，一般视为常数或为启停时间的函数；Uit为i机组在时段t的状态，Uit=1或0分别表示为运行或停运状态；Pit为机组i在时段t的出力。约束条件中，Ct为时段t系统的网损；PDt为时段t系统总负荷；k为备用系数；Mi为i机组在计算周期内允许启停次数；Pimax和Pimin为i机组的上、下限出力；RURi和RDRi分别为机组i的升、降功率速度约束；MUi，MDi则为机组i的最小运行和最小停运时间。
机组的运行费用模型采用发电功率的函数表示，即
网损可作常数处理，即按总负荷的一定比例（7%）考虑。更详细的模型应包括线路潮流限制、分区功率平衡、机组的燃料限制和随机停运的影响等。
3.2 优化目标函数的建立与数据编码 对于除机组容量约束外的其他约束，采用罚函数法处理，以构成系统优化目标函数
式中 Cf为罚参数；R为约束形式，
常规求解机组组合问题时，一般将其分为机组组合和负荷经济分配两个子问题，即在每一运算步上，首先确定各机组在各时段的组合运行状态，然后再进行负荷经济分配运算，这使得计算量相当大，十分费时。为此本文采用了一种新的二进制与浮点数混合编码方式，即以串X={U11,
3.3 移动设计、tabu表与释放准则
tabu搜索的搜索过程由“移动”来实现。本文由于采用了二进制与浮点数混合编码策略，因此对码串中的U，P分量构造了不同的移动方式。
（1）对U分量，随机选取码串的某一位或几位U分量进行取反操作。
（2）对P分量，随机选取码串中P分量的一位或几位根据式
为保证搜索均在可行解中进行，算法对每组“移动”操作所产生的试验解群作如下检验和修正：
tabu表是tabu搜索策略的关键。在一般tabu算法实现中，tabu表中记录的是最近若干代迭代过程中的所实现的移动的反方向。本文将最近若干次迭代过程中所得局部优化解的码串记录到tabu表中。凡是处于
