现代优化算法--课件

现代优化算法潘克家[e-mail]2011-8-82目录现在优化算法概论模拟退火算法(SA)遗传算法(GA)3Part1概论主要是说明现代优化算法的重要性。4现代优化算法现代优化算法遗传算法模拟退火算法禁忌搜索算法人工神经网络蚁群算法粒子群算法差分进化算法特点：•基于客观世界中的一些自然现象；•建立在计算机迭代计算的基础上；•具有普适性，可解决实际应用问题。5数学建模竞赛中的算法(1)93A非线性交调的频率设计:拟合、规划93B足球队排名次:矩阵论、图论、层次分析法、整数规划94A逢山开路:图论、插值、动态规划94B锁具装箱问题:图论、组合数学95A飞行管理问题:非线性规划、线性规划95B天车与冶炼炉的作业调度:非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法96A最优捕鱼策略：微分方程、积分、非线性规划696B节水洗衣机：非线性规划97A零件参数设计：微积分、非线性规划、随机模拟97B截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路98A投资收益与风险：线性规划、非线性规划98B灾情巡视：最小生成树、Hamilton圈、旅行商问题99A自动化车床：积分、概率分布、随机模拟、分布拟合度检验数学建模竞赛中的算法(2)799B钻井布局：几何变换、枚举、最大完全子图、混合整数规划00ADNA分类：神经网络、最小二乘拟合、统计分类00B管道订购：最短路、二次规划01A血管的三维重建：数据挖掘、曲面重建与拟合01B公交车调度：非线性规划02A车灯光源优化设计：最优化02B彩票中的数学：概率与优化数学建模竞赛中的算法(3)1497年A题用模拟退火算法00年B题用神经网络分类算法01年B题这种难题也可以使用神经网络美国89年A题也和BP算法有关系美国03年B题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。最优化理论的三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。19最优化问题(OptimizationProblem)最优化问题:1212()(,,,)(,,,)nnMinimizefxfxxxsubjecttoxxxxSX组合优化问题(CombinatorialOptimizationProblem):最优化问题中的解空间X或S由离散集合构成。其中很多问题是NP完全(NondeterministicPolynomialCompleteness)问题.20待解决的问题连续性问题，以微积分为基础，规模较小传统的优化方法理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性、收敛速度传统优化方法21现代优化算法现代优化算法又称智能优化算法或现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。22待解决的问题离散性、不确定性、大规模现代的优化方法启发式算法（heuristicalgorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法算法复杂性现代优化方法23现代优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。24全局优化(Rastrigin’sFunction)221212()2010(cos2cos2)Rasxxxxx全局最小点(0,0)现代优化算法特点：1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续的要求;容易实现，求解稳健。3)但收敛速度慢,能获得全局最优;适合于求解空间不知的情况。4)SA,GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题;求解速度和质量远超过常规方法。26常用的现代优化算法遗传算法GeneticAlgorithm，简称GA模拟退火算法SimulatedAnnealing，简称SA禁忌搜索算法TabuSearch，简称TS神经网络算法NeuralNetworkAlgorithm，简称NNA粒子群算法ParticleSwarmOptimization，简称PSO差分进化算法DifferentialEvolution，简称DE27搜索示例：三个孩子的年龄(1)两个多年未见的朋友相遇，聊了很多事情。…A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆祝生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们的情况。A：好的，我给你一些提示，他们三个年龄之积是36.B：很好，但我还需要更多提示。28三个孩子的年龄(2)A：我的大儿子的眼睛是蓝色的。B考虑了一下说，但是，我还有一点信息来解决你的这个难题。B：哦，够了，B给出了正确的答案，即三个小孩的年龄。A：他们三个年龄之和等于那幢房子的窗户个数。A指着对面的一幢房子说。29三个孩子的年龄(3)根据对话信息，用搜索的方法来解此问题。信息1:三个小孩年龄之积为36只有以下8种可能，搜索范围减少至8种情况:第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄1111212330三个孩子的年龄(4)信息2:三个小孩年龄之和等于窗户数第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123窗户数:3821161413131110如果窗户数为38、21、16、14、11、10即可得出答案B还需信息，即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色的得答案：(9、2、2)31典型问题——旅行商问题（Travelingsalesmanproblem,TSP）123412181032搜索示例：TSP问题给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。32典型问题——旅行商问题（Travelingsalesmanproblem,TSP）城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困难计算复杂度：指数灾难33Part2模拟退火法343536模拟退火算法及模型算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。物理退火过程算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。37什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。物理退火过程38模拟退火算法及模型等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。3940模拟退火算法及模型智能优化计算数学表述在温度T，分子停留在状态r满足Boltzmann概率分布物理退火过程DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)}({子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随41模拟退火算法及模型智能优化计算数学表述在同一个温度T，选定两个能量E1E2，有物理退火过程TkEETkETZEEPEEPBB12121exp1exp)(1}{}{10在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。42智能优化计算若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：1、当温度很高时，每个状态概率基本相同，接近平均值1/|D|；2、状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；3、当温度趋于0时，分子停在最低能量状态概率趋于1。模拟退火算法能量最低状态非能量最低状态TkrETZrEEPB)(exp)(1)}({数学表述43模拟退火算法及模型智能优化计算Metropolis准则（1953）——以概率接受新状态物理退火过程固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。44模拟退火算法及模型智能优化计算否则，以概率p=exp[-(Ej-Ei)/kBT]接受j为当前状态。物理退火过程Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j若EjEi，则接受j为当前状态；即：p大于[0,1)区间的随机数，则仍接受状态j为当前状态；否则保留状态i为当前状态。45模拟退火算法及模型智能优化计算Metropolis准则（1953）——以概率接受新状态p=exp[-(Ej-Ei)/kBT]物理退火过程在低温下，只接受与当前状态能量差较小的新状态。在高温下，可接受与当前状态能量差较大的新状态；46组合优化与物理退火的相似性智能优化计算相似性比较组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量47SA算法描述48案例讲解已知敌方100个目标的经度、纬度我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为1000公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。49问题分析50算法描述(解空间与目标函数)51算法描述一次迭代由三步组成52算法描述53案例讲解0102030405060700510152025303540Sum=41217.86454模拟退火算法及模型智能优化计算基本步骤给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。模拟退火算法的基本思想和步骤55模拟退火算法及模型智能优化计算影响优化结果的主要因素给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。模拟退火算法的基本思想和步骤三函数两准则初始温度59模拟退火算法关键参数和操作的设计智能优化计算原则(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。方法具体形式对算法影响不