现代(智能)优化算法

现代优化算法现代优化算法禁忌搜索算法模拟退火算法遗传算法人工神经网络蚁群算法粒子群算法混合算法……………特点：•基于客观世界中的一些自然现象；•建立在计算机迭代计算的基础上；•具有普适性，可解决实际应用问题。97年A题用模拟退火算法00年B题用神经网络分类算法01年B题这种难题也可以使用神经网络美国89年A题也和BP(ErrorBackPropagation)算法有关系美国03年B题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。最优化理论的三大非经典算法:模拟退火法(SA)、遗传算法(GA)、神经网络(NN)近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。最优化问题(OptimizationProblem)最优化问题:1212()(,,,)(,,,)nnMinimizefxfxxxsubjecttoxxxxSX组合优化问题(CombinatorialOptimizationProblem):最优化问题中的解空间X或S由离散集合构成。其中很多问题是NP完全(NondeterministicPolynomialCompleteness)问题.待解决的问题连续性问题，以微积分为基础，规模较小传统的优化方法理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性、收敛速度经典优化方法待解决的问题离散性、不确定性、大规模现代的优化方法启发式算法（heuristicalgorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法算法复杂性现代优化方法现代优化算法现代优化算法又称智能优化算法或现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。它们的共同特点：都是从任一解出发，按照某种机制,以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。全局优化Rastrigin’sFunction221212()2010(cos2cos2)Rasxxxxx全局最小点(0,0)模拟退火算法一、模拟退火算法基本原理模拟退火算法（SimalatedAnnealing，简称SA）属于一种通用的随机探索算法，1953年N.Metropolis(梅特罗波利斯)等人提出了模拟退火算法，其基本思想是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比试图通过模拟高温物体退火过程，来找到优化问题的全局最优解或近似全局最优解．一个物体（如金属）的退火过程大体如下：首先对该物体高温加热（熔化），显然物体内原子处于高速运行的高能状态．然而作为一个实际的物理系统，原子的运动又总是趋于最低的能量状态，在退火的初始状态，由于温度较高，物体处于高能状态，随着温度的逐渐降低，物体内部原子运动化学能趋于低能状态，这种由高能向低能逐渐降温的过程称为退火．当温度降至结晶温度后，物体由原子运动变为围绕晶体格点的微小振动，液体凝固成固体，退火过程结束．当我们把目标函数f(X)看成定义在可行集（解空间）上的能量曲面，而整个曲面f(X)凹凸不平，如果让一个光滑圆球在曲面上自由滚动，这个圆球十有八九会滚到最近的凹处停止运动，但该低谷并不一定是最深的一个凹谷，模拟退火方法就类似于沿水平方向给圆球一个水平方向作用力，若作用于小球的作用力足够大且小球所处的低谷并不很深．对于一个优化问题min()()0,1,2,,,..()0,1,2,,.ijfXgXilsthXjm小球受水平力作用会从该低谷流出，落入另一低谷，然后受水平力作用又滚出，如此不断滚动，如果作用小球的水平力掌握得适当，小球很有可能停留在最深的低谷之中，这个最深低谷就是优化问题的全局最优解或接近于全局最优解．作用于小球上的水平力相应于模拟退火中的温度T，水平作用力减小相应于温度降低，如图所示．二、模拟退火算法基本迭代步骤(1)给定初始温度及初始点X,计算该点的函数值f(X)．(2)随机产生扰动ΔS得新点计算新点X’=X+ΔX函数值f(X’)及函数值差Δf=f(X’)–f(X).(3)若Δf≤0,则接受新点,作为下一次模拟的初始点．(4)若Δf0则计算新点接受概率P(Δf)=exp(–Δf/(K–T)),在区间[0,1]上产生服从均匀分布的伪随机数r∈[0,1]．如果有P(Δf)≥r，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点．以上步骤，称为Metropolis过程．按照一定的退火方案逐渐降低温度，重复Metropolis过程，就构成模拟退火迭代法．当系统的温度足够低时，就认为达到了全局最优解．在模拟退火算法中，降温的方式对算法有很大的影响．如果温度下降过快，可能会丢失极值点，如果温度下降过慢，算法的收敛速度又大大降低，为了提高模拟退火算法的有效性，许多学者提出了多种退火方案，如(1)经典退火方案：降温公式为特点是温度下降很缓慢，因此，算法收敛程度很慢．0()ln(1)TTtt(2)快速退火方式：降温公式为0()1TTtt特点是在高温区温度下降比较快，而在低温区降温的速度较慢．这符合热力学分子运动理论，即分子在高温时，具有较低能量的概率要比在低温时小得多，因此寻优的重点应在低温区，其中参数α可以改善退火曲线的形态．组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量相似性比较三、模拟退火算法对应了一个马尔可夫链（略）模拟退火算法的优点质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。改进的可行方案（1）设计合适的状态产生函数；（2）设计高效的退火历程；（3）避免状态的迂回搜索；（4）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；（7）设计合适的算法终止准则。问题单机极小化总流水时间的排序问题四个工作：，求的最优顺序。四.计算举例15,5,18,84321PPPP41miniiF预备知识：按SPT准则，最优顺序为3-1-4-2四.计算举例11212312341234FPFPPFPPPFPPPP12344321453821511892FPPPP用SA求解这个问题状态表达：顺序编码邻域定义：两两换位定义为邻域移动解：设降温过程定义为初始解：i=1-4-2-3四.计算举例1000T60fT203kkkTTTTnT118if⑴①②③注释：1.①无条件转移；2.②③为有条件转移；3.在②③中，虽然目标值变坏，但搜索范围变大；4.是随机产生的四.计算举例100kT1324982043211190.81060.741442311320.87810.3991kkfTfTjfjfijjfjeijjfjeij⑵①②③注释：1.①有条件转移；2.②为无条件转移；3.在③中，停在4-3-1-2状态，目标值仍为109；四.计算举例8042131350.96320.341343121092643211190.88250.9286kkkfTfTTjfjeijjfjfijjfjeii(3)①②③注释：1.①②无条件转移；2.在③中，停在3-1-4-2状态，目标值仍为92；SA没有历史最优，不会终止在最优解，故算法一定要保持历史最优。四.计算举例6013429524314292321431310.52200.7105kkfTTjfjfijjfjfijjfjeiiSA终止在最优解上的条件：初始温度足够高热平衡时间足够长终止温度足够低降温过程足够慢以上条件实际中很难满足，所以只能记录历史最优解。四.计算举例30城市TSP问题TSPBenchmark问题4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450初始温度的计算fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。283591467283591467283591467281593467283419567235981467参数设定截止温度tf=0.01;退温系数alpha=0.90;内循环次数L=200*CityNum;运行过程运行过程运行过程运行过程运行过程SA算法结构示意图simulannealbndsimulannealsimulannealcommon.msaenginesolverData.running=ture?sacheckexit.msanewpoint.msaupdates.mgadsplot.m得到最优解NYSAT的使用只需要调用主函数simulannealbnd即可，函数simulannealbnd则调用函数simulanneal对模拟退火问题进行求解。函数simulanneal依次调用函数simulannealcommon和函数saengine，并最终得到最优解。在函数saengine中，SA进行迭代搜索，直到满足一定的条件才退出。在迭代过程中，函数sanewpoint和函数saupdates是关键函数。x1=-5:0.01:5;x2=-5:0.01:5;[x1,x2]=meshgrid(x1,x2);x3=20+x1^2+x2^2-10*(cos(2*pi*x1)+cos(2*pi*x2));surfc(x1,x2,x3)colormaphsvrf3=@(x,y)rastriginsfcn([x./10,y./10]);ezsurfc(rf3,[-3030])rng(1,'twister')[xfvalexitflag]=ga(@rastriginsfcn,2)遗传算法一、遗传算法基本原理遗传算法（GeneticAlgorithm，简称GA）是由美国Michigan大学的Holland教授于1975年首次提出，它的基本思想是基于Darwin的进化论和Mendel的遗传学．即生物的遗传，变异、选择在生物的进化过程起着重要作用，它使生物不仅能够保持自身固有特性，同时还能够不断改变自身以适应新的生存环境．遗传算法是一种基于群体进化的计算模型，它通过群体的个体之间繁殖、变异、竞争等方法进行的信息交换优胜劣汰，从而一步步地逼近问题最优解．对个体的遗传操作主要是通过选择（繁殖）交叉和变异（突变）这三个基本的遗传算子来实现．生物的进货是以群体的形式进行的，而群体的进化是通过个体的信息遗传与交叉来完成的．与之对应，遗传算法的运算对象也是群体，它由N个个体组成一个集合，通过对该集合进行遗传操作来模拟生物的进化过程，遗传算法中的个体就是模拟生物的染色体，称为人工染色体．为了完成对个体的遗传操作，需要将个体的表现型转换为基因型，