2．上海交通大学电子信息与电气工程学院，上海市200030）机组最优投入问题（optimalUnitCommitment，UC）是寻求1个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用为最小。该问题是一个高维数、非凸的、离散的、非线性的优化问题，很难找出理论上的最优解，但由于它能带来显著的经济效益，所以受到了国内外很多学者的广泛关注。作者尝试采用一种新型的模拟进化优化算法——蚁群优化算法(ACO)来求解该问题。首先，利用状态、决策及作者提出的路径概念把UC设计成类似于旅行商（TSP）问题的模式，从而可以方便地利用ACO来求解。其次，由于ACO处理的是无约束优化问题，对于UC这一约束优化问题，提出了不同的方法来处理各种约束。用tabu表限制不满足旋转备用约束和机组最小启/停时间约束的状态；通过附加惩罚项来处理线路N安全性约束。数值算例验证了此算法的可行性和有效性。
关键词：机组最优投入；蚁群优化算法；tabu表；转移概率；经济调度1引言
机组最优投入问题是寻求1个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用为最小，它是一个高维数、非凸的、离散的、非线性的优化问题，很难找出理论上的最优解，但由于它能带来显著的经济效益，国内外很多学者一直在积极研究，提出各种方法来解决该问题，如优先顺序法[1]、动态规划法[1~2]、整数规划和混合整数规划法[2]、分支定界法、拉格朗日松弛法[2,3]等。其中，优先顺序法简单实用，易于进行人工调整，但由于是逐次优化，可能会错过一些更好的方案；动态规划法根据选取变量方法的不同可以构成几种不同的算法，如①并列机组经济组合的动态规划算法可以给出各种负荷下的最优运行状态和运行耗量，但不便考虑启动耗量和时间段的关联；②多时段动态规划算法可以考虑时变的启动耗量，但由于状态和可选的路径较多，使得动态规划算法难以实用，为此很多学者提出各种措施来限制状态和路径数；③分解式动态规划算法等。近年来，遗传算法[3~5]、神经网络[6,7]法、模拟退火法[6,8]等在解决该问题上也取得了一些成果。
蚁群优化算法（AntcolonyOptimalalgorithm，ACO）是由意大利学者M﹒Dorigo近年来提出的一种新型的模拟进化优化算法[9]。该算法即是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法。它采用有记忆的人工蚂蚁，通过个体之间的信息交流与相互协作来找到从蚁穴到食物源的最短路径。目前蚁群算法在求解旅行商（TSP）、指派（assignmentproblem）、job-shop调度等优化问题中，得到了一系列较好的应用。值得一提的是基本ACO模型就是以TSP为例进行描述的，即ACO在求解TSP问题时具有明显的优势。本文利用机组最优投入问题与TSP问题之间的相似性，尝试把机组最优投入问题设计成类似于TSP问题的模式，并灵活的处理各种约束，从而可以用ACO算法来求解。ACO算法的引入为这一优化问题的有效解决提供了一种崭新的、有效的途径。
2蚁群优化算法的基本原理
蚁群优化算法模拟了真实的蚂蚁行为。众所周知，真实的蚂蚁能够在没有任何视觉线索的情况下找到从食物源到蚁穴的最短路径，并且能够适应环境的改变，比如在旧的路径上放置一障碍物，此时蚂蚁能够很快找到一条新的最短路径。生物学家的研究揭示了蚂蚁的这种能力是借助于一种叫做“信息素”的物质，蚂蚁个体利用该物质进行信息交流从而决定选择哪一条路径。蚂蚁在运动过程中，能够在它经过的路径上沉积一定的“信息素”，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径经过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流来搜索食物的。
蚁群优化算法本身也是一种迭代算法，但它并不是简单的迭代，当前的迭代总是利用以前迭代的信息，即模拟了信息正反馈原理。蚂蚁从某城市出发，按照状态转移规则选择下一个城市，该规则也被称为“随机比率规则”，式(1)给出了蚂蚁从城市i转移到j的转移概率[9]。
式中τij(t)表示τ时刻在路径ij上的信息量，ηij为路径长度的倒数，表示由城市i转移到城市j的期望程度，τij(t)ηij表示该路径单位长度的信息量，a为权重因子。路径的信息量越大，则该路径的转移概率越大，蚂蚁选择该路径的概率越大。蚂蚁按照上述转移概率规则选择城市并最终形成一条封闭路径，当所有的蚂蚁完成了它们的闭合路径后，则一次迭代结束，利用全局信息素更新规则来更新路径的信息量，再开始下一次迭代直到达到最大迭代次数或最大停滞次数。
ACO的全局信息更新规则如式(2)～(4)所示。
式中Q是常数，Lk表示第k只蚂蚁在本次循环中所走过的路径长度，在初始时刻，△τij(k)=0。参数Q,a,ρ可以用实验方法确定其最优组合。
3机组最优投入问题的数学模型
机组最优投入问题的目标函数中主要包括以下两个基本部分：①机组的发电费用，②机组的起动费用。同时，还必须满足一定的约束条件。机组最优投入问题在数学上可以描述为[1,5,11～12]
2）旋转备用约束
5）线路N安全性约束
式(5)～(11)中、Fsi(t)分别为第i台发电机的发电费用函数及起动费用函数；n为发电机台数，T为时段数，NL为线路数；为第i台机组在第t时段的出力；为全网负荷，为网损；
目标函数中，机组启动费用是停机时间的函数[11]，即
式中Fsi(t)为机组i在时段t的启动费用；为机组i在时段t的停运持续时间。
从该模型中可以看出机组最优投入问题是0-1变量和连续变量的混合非线性优化问题。假如有n台机组，每小时为1段，1天分为24段，机组间各种可能的组合数将达到（2n-1）24，即使n不大也是一个天文数字的量级，求解是十分困难的。因此，必须采用适当的办法对组合加以限制，达到可以接受的程度，才能更有效的求解该问题。
4蚁群优化算法在机组最优投入问题中的应用
4.1机组最优投入问题的蚁群算法模式
机组最优投入问题实际是一个多阶段最优决策问题，在每个时段机组有不同的组合方式；而蚁群优化算法求解TSP时也是一个求解多阶段最优决策问题，每个阶段选择一个未曾经过的城市[1][2][3]下一页
