用GTS算法解决机组组合问题

1、用GTS算法解决机组组合问题概论概论机组组合问题 为了实现电力供需的平衡，并最合理的利用发电资源，预先对发电机组的启停和出力进行调度安排就是非常必要的。机组优化组合和优化启停就是要在满足约束条件的情况下，优化地选定各时段参加运行的机组，求出机组的最佳运行方案，实现发电成本最小。经济调度问题 在满足负载需求以及功率平衡方程和机组运行限制的前提下，以一种最优的分配方案分配机组的运行方案。遗传算法 从代表问题中可能存在的一个解集的一个种群开始逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。在本文

2、的UCP问题中，我们以机组运行状态的二进制编码作为问题的解集，以目标函数即成本以及引入约束的罚函数的和作为算法中的适应方程。本文的算法核心就是基于遗传算法。 禁忌搜索 Tabu搜索是一种强有力的优化搜索算法，核心在于对搜索过程进行短期记忆和中长期记忆。以令搜索具有广泛性和集中性，基本思想是搜索基本的解空间，在当解空间的领域中找到另一个更好的解时，更新解空间。但是为了跳出局部极值和避免循环，搜索中设置了禁止表，当搜索解在禁止表中时，则放弃该解。搜索过程可以灵活使用禁止表记录搜索过程，从而使搜索过程能够找到局部最优解，又能跳出局部极值找到更优的解。本文中主要用该算法构造种群中的新成员。模拟退火法

3、是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。当温度不断下降至0时，最终以概率为1稳定在其“能量”的全局最小点上。本文中用模拟退火法对由遗传算法得到的解集进行逐个实验，以更新算法解集进行下一轮迭代。2.模型的建立模型的建立Uit机组i在t时段的运行状态（ON=1，OFF=0）Vit机组i在t时段的开，关状态Pit机组i在t时段的

4、发电出力Fit(Pit)机组i在t时段的产出花费Sit机组i的启动成本Soi机组i的冷开机成本PDt系统在t时段内负载需求的峰值Rtt时段的旋转备用符号的约定Pmaxi Pmini机组i的最大，发电出力Toni Toffi机组i的运行与关闭时间Tupi Tdowni机组i的开机与关机时间idownioffiiiitiitiitiititTtNiitititititTETTDSoSCPBPAPFSVPFUF )/exp(1i)(t)(211启动成本的目标函数：机组函数：时段内产出花费的目标发电成本目标函数：调度时间内所有机组的目标函数tTTtTTtiUPPPUtRPDPUtPDPUupionid

5、ownioffiitiitiitNittiitNititit;:,;:;)(:;:maxmin1max1最小开关机时间约束运行约束旋转备用约束负载约束约束条件3.构造算法构造算法综述 本文用遗传算法(GA)，禁忌搜索(TS)和模拟退火法(SA)来解决UCP问题中的机组运行状态的组合优化问题。以二进制码来表示机组的状态变量Uit，再经由GTS算法，求解使得在满足发电约束同时成本最低的机组调度问题。 算法步骤如下: 随机选择一系列可行解(染色体)，定义其为初始种群(由若干个染色体串组成，每个串对应一个自变量值)。 以解决调度问题来求出每个染色体的数值。 根据适应函数，计算种群中每个染色体的适应度。

6、 用遗传算法(GA)构造新的种群: (1).挑选适应度最好的解决方案(染色体)，复制到新种群中。 (2).对现有的种群随机选取一部分方案用禁忌搜索(TS)在新的种群中构造新的成员。 (3).用交叉的操作来完成新种群中新成员的构造。 (4).用变异操作来对新种群进行完善。 用模拟退火法(SA)对新种群的成员进行测试。终止准则 我们将停止算法如果下面两个条件有一个满足:l 最好方案的执行迭代数大于预先设定的最大迭代数。l 最大允许的迭代次数已经达到算法流程图4.GTS算法中的算法中的GA算法算法解决方案的编码 UCP的解决方案可以由一个二进制矩阵来表示出来，我们的编码方法是用二进制数来对解决方案中

7、的十进制数进行转换。矩阵中每一个长度为T的列向量代表着机组在不同时间段下的运行状态，经过对这些列向量的二进制数的解码，我们可以得到N个十进制数U1，U2，.,UN。 范围从0到2N-1。下面给出一些图助于理解适应度函数 遗传算法在进化搜索过程中基本不利于外部信息，仅以适应度函数为依据。一般情况下适应度函数是由目标函数变换而成的。对目标函数的某种映射称为适应度的尺度转换。交叉 交叉操作是发生在染色体的十进制码中的，具体可以分为以下两个步骤。第一步是将新选择产生的匹配池中的染色体由轮盘赌规则两两随机进行匹配。 第二步则是进行交叉繁殖：通过父辈染色体的十进制码的串的交换产生出新的孩子。(串的选择规则

8、可以拟定)两个父辈染色体产生两个孩子染色体，种群中染色体数量不发生改变。变异 以一种很小的概率随机的选择一个染色体，选择的染色体被解码成二进制数，随机选择一个机组以及时间段，改变其二进制的值(由1变为0，由0变为1)。5.GTS算法中的算法中的TS算法算法TS算法在GTS算法的作用 用来对GA算法随机选中的种群的成员构造新的相邻成员。增加了算法的广泛性。TS算法的具体实现 UCP问题中的禁忌表(TL)被构造为一个Z*N维的矩阵，Z为TL的长度，N为机组的数量。每一个TL矩阵的列向量表示了一个机组的TL。列向量i的每一个十进制数记录了机组i的状态的搜寻方案。经由这种方式我们以最小的记忆需求记录了

9、所有的搜寻方案中机组的状态信息。算法流程图禁忌表与搜寻方案6.GTS算法中的算法中的SA算法算法SA算法步骤 给出SA算法的第k次迭代步骤 step(1):构造新的温度Cpk=Cp0()k,01。 step(2):在温度Cpk下对GA算法构成的种群成员一个一个的做退火实验。 step(3):退火实验:计算增量t=C(xj)-C(xi)，其中C(x)为评价函数 。 若t=U(0,1),使xi=xj。跳转到step(2)，其他，跳转step(2)。 其中xi是SA算法的现行方案，xj为GA算法的现行种群成员。 step(4):如果所有种群中的成员都经过了退火实验，跳转到主算法的下一个步骤。如果还有

10、成员没有实验，跳转到step(2)。 为了方便理解，下引入算法流程图来对算法进行进一步的解释。SA算法流程图7.例子例子为了体现出GTS算法的优越性，我们用三个例子以拉格朗日松弛算法，整数规划来对GTS算法进行比较，在调度的24小时时间内例子1和2包括了10个运行机组，例子3则有26个机组。比较例子的仿真图我们可以看出，GTS算法的优越性比较明显，GTS的参数选择具体如下：种群大小为50，交叉率为0.8，变异率 为0.3，精英复制 为2，最大种群成员数为1000, 禁忌表大小为7，初始温度为5000，=0.9。仿真图8.总结总结本文用到了一种新的算法(GTS)来解决机组组合问题，该算法结合了三种算法，在GA算法的基础上，引用TS算法来构造GA算法的种群中的新成员，用SA算法来加速GA算法的收敛速度。本文用的GTS算法与一般的GA算法的不同在于三点：第一：这种算法的解决方案用二进制与十进制混合编码表示