《高等运筹学第精选PPT.ppt》由会员分享，可在线阅读，更多相关《高等运筹学第精选PPT.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于高等运筹学第1现在学习的是第1页，共21页25.1 固体退火过程和Metropolis准则 固体物质退火是先将固体加热至熔化，再徐徐冷却使之凝固体物质退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程固成规整晶体的热力学过程.固体物质的退火过程由三部分组成：加温过程：增强粒子的热运动；系统能量随之增大加温过程：增强粒子的热运动；系统能量随之增大 等温过程：系统达到该温度下能量最小状态，即平衡态等温过程：系统达到该温度下能量最小状态，即平衡态 冷却过程：使粒子的热运动减弱并逐渐有序化冷却过程：使粒子的热运动减弱并逐渐有序化对于固体在恒定温度下达到热平衡的过程模拟，对于固体在恒
2、定温度下达到热平衡的过程模拟，MetropolisMetropolis等人在等人在19531953年提出了“重要性采样法”，即以概率接受新状态若E Ej E Ei i，要依据概率，要依据概率 来确定来确定现在学习的是第2页，共21页35.2 模拟退火算法的基本思想和步骤 1.固体退火与组合优化之间的相似性 固体退火概念与优化问题的对应关系固体退火概念与优化问题的对应关系 固体退火 组合优化问题 状态i 系统能量Ei 能量最低状态 加温熔化 等温过程 冷却过程 解xi 目标函数f(xi)最优解 设定初温t0 产生新解、判断、接受/舍弃 控制参数t的变化 现在学习的是第3页，共21页42.算法思想
3、和步骤 MetropolisMetropolis算法：从某一初始状态出发，通过计算系统的算法：从某一初始状态出发，通过计算系统的时间演化过程，求出系统最终达到的状态时间演化过程，求出系统最终达到的状态SA：从某个初始解出发，经过大量解的变换后，求得给从某个初始解出发，经过大量解的变换后，求得给定控制参数值定控制参数值t时优化问题的相对最优解然后，减少t t的值，重复执行MetropolisMetropolis算法，就可以在算法，就可以在t t趋于零趋于零时，求得优化问题的全局最优解时，求得优化问题的全局最优解 SASA由与由与Metropolis准则对应的转移概率P Pt确定是否接受从当前解x
4、 xi到新解到新解xj j的转移，即 现在学习的是第4页，共21页5Procedure Simulated_Annealing;Procedure Simulated_Annealing;BeginBegin 任任选选一一个个初初始始解解x x0 0；确确定定初初始始温温度度t t0 0和和每每一一个个t t值值下下进进行行迭迭代代的的次次数数L L；x xi i:=x x0 0;（置初始解为当前解）（置初始解为当前解）k k :=0;=0;（温度变化计数器置（温度变化计数器置0 0）RepeatRepeat l l :=0;=0;（迭代次数计数器）（迭代次数计数器）RepeatRepeat
5、从邻域从邻域N N(x xi i)中随机选一中随机选一x xj j；计算计算f f=f f(x xj j)-)-f f(x xi i)；if(if(f f0)then 0)then x xi i:=x xj j;else if else if expexp(-(-f f/t tk k)random 0,1 then)random 0,1 then x xi i:=x xj j;l l :=l l+1;+1;until until l l=L L;k k :=k k+1;+1;t tk k :=t t(k k););until until 满足终止条件；满足终止条件；End;End;现在学习的是
6、第5页，共21页63.模拟退火算法的特点分析 SA依据依据MetropolisMetropolis准则接受新解，因此除接受优化解外，准则接受新解，因此除接受优化解外，还在一定范围内接受恶化解，这正是还在一定范围内接受恶化解，这正是SASA与局部搜索算法的本质区别所在 SASA具有如下特点：(1)优于局部搜索算法 (2)若在每个t值都达到平衡分布，且所构造的邻域结构能值都达到平衡分布，且所构造的邻域结构能使解空间中的任何两个状态可达，则使解空间中的任何两个状态可达，则SA渐近收敛于全局渐近收敛于全局最优解最优解(3)(3)随着控制参数t值的减小，算法返回某个全局最优解的概率单调增大.现在学习的是
7、第6页，共21页7与局部搜索算法相比，SASA的性能可概括为高效、健壮、通用和灵活 (1)(1)高效性SA可在较短时间里求得更好的最终解 (2)(2)健壮性（鲁棒性，健壮性（鲁棒性，robust）即算法的最终解并不十分依赖初始解的选取 (3)通用性和灵活性通用性和灵活性SA能应用于求解多种组合优化问题，为一个问题编制的程序可以有效地用于其它问题 现在学习的是第7页，共21页85.3 SA关键参数及其操作设计 SA主要包括主要包括“三函数两准则”：解产生函数（邻域结构）、解接受函数、温度更新函数、内循环终止准则和外循环终止准则 1.解产生函数（邻域结构）通常选择当前解经简单变换即可产生新解的方法
8、尽可能保证产生的候选解遍布整个解空间尽可能保证产生的候选解遍布整个解空间应能使解空间中的任何两个状态可达2.解接受函数 判断新解是否被接受的依据是Metropolis准则：现在学习的是第8页，共21页93.初始温度 从理论上说，初始温度从理论上说，初始温度t t0 0应使平稳分布中每一状态被接应使平稳分布中每一状态被接受的概率相等，也就是使受的概率相等，也就是使 若取若取P P0.9，则在f f =100时，时，t0949 在实际应用中可用以下方法进行简单地估计：在实际应用中可用以下方法进行简单地估计：(1)f f=(目标函数值的上界)(目标函数值的下界)(2)(2)随机产生若干个解，求所有解
9、对间的目标函数差，然随机产生若干个解，求所有解对间的目标函数差，然后取其中的最大者作为后取其中的最大者作为f 现在学习的是第9页，共21页104.温度更新函数 表示温度下降的方式并控制温度下降的速度表示温度下降的方式并控制温度下降的速度常用的温度更新函数是常用的温度更新函数是tk+1=ttk，01，通常=0.750.99 5.内循环终止准则 用于决定在各温度下产生候选解的数目，即每一个用于决定在各温度下产生候选解的数目，即每一个tk k值下进行迭代的次数L L L L往往只能取一个近似的足够大的数，如L=100=100n n300n，其中n n为问题的规模 还可用如下的抽样稳定准则来判断L是否
10、足够大：是否足够大：(1)目标函数的均值是否稳定(2)连续若干步的目标值变化较小连续若干步的目标值变化较小 现在学习的是第10页，共21页116.外循环终止准则 用于决定用于决定SASA何时结束常用的终止准则有：何时结束常用的终止准则有：(1)设定终止温度在实际应用中，可以给定一个足够小的正数，当温度，当温度t tk k时，算法终止(2)(2)给定一个确定的外循环总迭代次数(3)(3)给定当前的最好解保持不变的最大连续迭代次数 7.冷却进度表 初始温度初始温度t0，温度更新函数t tk+1 1=ttk k，每一个tk k值下进行值下进行迭代的次数迭代的次数L和和外循环终止准则称为模拟退火过程的
11、冷却进度表，是SASA应用的关键参数这些参数之间存在相互影响这些参数之间存在相互影响 现在学习的是第11页，共21页125.4 模拟退火算法实现与应用 讨论如何在SA所提供的通用算法框架下，针对具体问题予以实现对问题的简明描述：解空间解空间：指问题的所有可能解的集合，它限定了初始解：指问题的所有可能解的集合，它限定了初始解选取和新解产生时的范围选取和新解产生时的范围 目标函数：通常表述为若干优化目标的一个和式目标：通常表述为若干优化目标的一个和式目标函数值不一定就是问题的优化目标值，但其对应关系应是函数值不一定就是问题的优化目标值，但其对应关系应是明显的此外，目标函数式应当是易于计算的明显的此
12、外，目标函数式应当是易于计算的 初始解初始解：可以考虑随机生成 现在学习的是第12页，共21页131.旅行商问题 设有n个城市和距离矩阵D=(dij ij)，其中其中dij ij表示城市表示城市i i到城到城市市j j的距离的距离问题是要找遍访每个城市恰好一次的一条回路，且其路径长度为最短 求解求解TSPTSP的模拟退火算法描述如下：解空间：可表示为 1,2,1,2,n n 的所有循环排列的集合，的所有循环排列的集合，即即S S=(1 1,2 2,n n)|()|(1 1,2,n)为1,2,1,2,n n的循环排列 i i=j j表示在第i i个次序访问城市个次序访问城市j j，并约定n n+
13、1=1 1 初始解：可选为（1,2,n）目标函数：访问所有城市的一个回路的长度 现在学习的是第13页，共21页14新解的产生：设用以下方法产生（分别或交替使用）新解的产生：设用以下方法产生（分别或交替使用）2-交换任选访问的序号u和和v（设（设u uv），逆转u u和v及及其之间的访问顺序其之间的访问顺序当前当前解：1 u u-1 u u u u+1 v-1-1 v v v+1 n 新解：新解：1u u-1-1 v vv v-1-1 u+1+1uv+1 n 3-3-交换任选序号u、v和和w w（设（设uvwuvw），将），将u u和v v之间的子路径插到w w之后访问当前当前解：1 1 u u
14、-1 u u v v v v+1+1 w w w w+1+1 n新解：1 1u-1-1 v+1+1 w u v v w w+1+1 n目标函数差（目标函数差（2-2-交换）交换）现在学习的是第14页，共21页15当距离矩阵D D=（dij ij）为对称矩阵时，因为为对称矩阵时，因为d dij ij=dji ji，上式可，上式可简化为简化为 目标函数差（目标函数差（-交换）现在学习的是第15页，共21页162.01背包问题（Zero-one Knapsack Problem）给定一个装载量为给定一个装载量为M的背包及n件物品，物品件物品，物品i的重量和价的重量和价值分别为值分别为wi i和ci
15、i，i=1,2,=1,2,n要求选择若干件物品装入要求选择若干件物品装入背包，使其价值之和为最大背包，使其价值之和为最大 设设则问题的数学模型为则问题的数学模型为 x xi0,1,i i=1,2,n 现在学习的是第16页，共21页17求解求解0-10-1背包问题的模拟退火算法描述如下：的模拟退火算法描述如下：解空间 S=(=(x1,x2 2,xn)|)|w1 x1 1+w wn x xn nMM,xi0,10,1 目标函数 f(x1 1,x2 2,x xn)=)=c1 1 x1+c2 2 x x2+c cn n x xn n max max新解的产生 随机选取物品i，执行下列三种操作之一：执行
16、下列三种操作之一：若若i不在背包中，则将其装入背包不在背包中，则将其装入背包 若i不在背包中，则将其装入背包，同时从背包中随机取出另一物品j 若若i i已在背包中，则将其取出，并同时随机装入另一物品已在背包中，则将其取出，并同时随机装入另一物品j 归纳：x xi:=1x xi i，且（或）xj j:=1:=1xj j，i ij 现在学习的是第17页，共21页18背包价值差（目标函数差）及重量差背包价值差（目标函数差）及重量差 根据产生新解的三种可能，相应的背包价值差为根据产生新解的三种可能，相应的背包价值差为 为判定解的可行性，求出对应的背包重量差为 其中m为当前背包重量m的增量的增量 现在学
17、习的是第18页，共21页19接受准则：是增加了可行性测定的MetropolisMetropolis准则准则 现在学习的是第19页，共21页205.5 模拟退火算法的改进 SASA的的主要不足:返回一个高质量的最终解要花费较长的返回一个高质量的最终解要花费较长的时间时间 提高搜索效率是主要的改进内容，可能的途径：(1)选择适当的邻域结构和随机数序列选择适当的邻域结构和随机数序列 (2)选择合理的冷却进度表 (3)(3)SASA执行过程是一系列执行过程是一系列“产生新解、判断、接受产生新解、判断、接受/舍弃”的迭代过程，提高各个环节的时效可以缩减运算时间 (4)改变算法进程的各种变异方法，如有记忆的改变算法进程的各种变异方法，如有记忆的SA、回火退火法、加温退火法等 (5)(5)大规模并行计算大规模并行计算 现在学习的是第20页，共21页01.05.2023感感谢谢大大家家观观看看现在学习的是第21页，共21页