模拟退火算法解析.ppt

1 研究背景 UC问题 * 负荷调度的二次规划问题 混合整数非线性规划问题----取决于发电机启停机组的开、关状态 为了满足负荷的要求，系统内联合运行的机组规模不断扩大，而众多的发电机组具有不同的燃料转换特性，某些机组具有较高的发电效率，而某些次之。如果仅靠改变机组出力而不改变启停机组的数目，在已开机机组的容量范围内往往难以通过调节满足负荷的这种变化。为了实现电力供需的平衡，并最合理地利用发电资源，预先对发电机组的启停和出力进行调度安排就是非常必要的,UC问题从属于经济调度问题。 机组组合(UC)问题 * 1 研究背景 经济负荷调度(ELD)问题 运用模拟退火算法解决优化机组组合与经济调度问题 SA的由来、目的、原理........... 依赖于组合约束条件，例如：时间间隔、爬坡速率，还需协调整个调度周期的发电机出力 SA由来？ * 1 研究背景 SA的主要目的？ Kirkpatrick,、Gelatt和Vecchi 提出模拟退火算法(SA)，其原理是将成本最小化函数的优化问题与金属冷却做类比，金属冷却达到“冰点”值等同于成本达到最小值SA算法基于Metropolis准则，它模拟了在给定温度下在平衡态过渡原子的状态。 解决无特定结构的组合优化问题 SA的缺点？ 由于算法收敛性的需要，导致迭代次数增加，使得需要更长的运算时间 传统的模拟退火算法 * 1 研究背景 解决机组组合(UC)问题时，忽略爬坡速率的约束条件 改进的模拟退火算法 基础 结合动态经济调度(DED)的方法，解决含有爬坡速率约束约束条件的UC问题 注：?对SA控制参数的调优 ?在三种可供选择的机制下，产生可行性实验解 ?对应每个温度下的局部优化技术，已达到减少运算时间 目标函数 * 2 UC问题 目标函数 目标函数 燃料成本 开机成本 ? ? (1). 发电机总功率 * 2 UC问题 约束条件 (4). 单台机组最小发电出力 (3). 热备用 (2). 单台机组发电要求 (5). 爬坡速率 (6). 最小启停时间 物理模拟退火算法 * 3 模拟退火算法(SA) 算法的初设温度 原理及模型 ?加温过程。当温度足够高时，固体熔为液体，增强粒子热运动，使其偏离平衡位置。 ?等温过程。与周围环境交换热量而温度不变，系统达到平衡态。 ?冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。 物理模拟退火算法 ?加温过程。当温度足够高时，固体熔为液体，增强粒子热运动，使其偏离平衡位置。 ?等温过程。与周围环境交换热量而温度不变，系统达到平衡态。 Metropolis抽样过程 控制参数的下降 能量的变化就是目标函数，要得到最优解就是能量的最低态，Metropolis准则是SA算法收敛于全局最优的关键，M准则以一定概率接受恶化解，这样使算法跳离局部最优的陷阱。 * 3 模拟退火算法(SA) 原理及模型 Metropolis criterion： 在算法的每一步中, 让原子作微小的随机移动, 并计算系统的能量变化 则接受这个移动, 并用移动后的系统状态作为算法下一步的起始点 Boltzmann分布： 接受新状态, 并作为下一步算法的起始点 T 的取值不同, 退火过程也不同, 致使系统状态变化不一样。T 越高, 系统接受 o 的状态的能力就越强, 这样, 系统陷人局部最优解的可能性也就愈小。为避免在局部最小值陷入最优，冷却进度也需要缓慢。 由于每一个过程都满足于前一个过程，用数学表达----马尔科夫链 足够长 足够高 足够缓慢 * 3 模拟退火算法(SA) 步骤 初始解 初始温度 新的随机实验解 成本差 依概率接受新解 马尔科夫链 通过一个迭代过程 通过迭代步骤，考虑机组最小启停时间约束和热备用等约束。但是收敛性不会被初始解影响 马尔科夫链的长度依赖于变量的数量，SA算法的长度在上限和变量数量之间 物理退火过程 * 3 模拟退火算法(SA) 步骤 跳出局部最优 三个有效机制为SA算法提供了新的实验解，这种机制的提供了在解空间内的二维探索和确保仅仅只有可行解会在算法运行过程中被检查出来，除此之外，这个机制精确了算法的收敛性并且减少执行所需时间。 * 3 模拟退火算法(SA) 产生实验解的方法 用“奖励”过程来组合三种机制，“奖励”过程检查在SA算法先前状态下特殊机制的选择是否会产生一个新的实验解(符合Metropolis criterion) ?作为机制的奖励，相同的机制会产生新的实验解