模拟退火算法和遗传算法

10.1模拟退火算法模拟退火算法（SimulatedAnnealingAlgorithm，简记为SAA）是受金属热加工技术的启迪而发展起来的一种随机搜索算法。模拟退火算法及模型算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。物理退火过程模拟退火算法及模型物理退火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，达到某种稳定状态。物理退火过程模拟退火算法及模型物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。物理退火过程10.1.1模拟退火算法的基本原理DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)}({子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随数学表述在温度T，分子停留在状态r满足Boltzmann概率分布物理退火过程10.1.1模拟退火算法的基本原理TkEETkETZEEPEEPBB12121exp1exp)(1}{}{数学表述在同一个温度T，选定两个能量E1E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。10.1.1模拟退火算法的基本原理数学表述若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。10.1.1模拟退火算法的基本原理Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j若EjEi，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。01-(Ej-Ei)/kTp10.1.1模拟退火算法的基本原理模拟退火算法的基本思想将一个优化问题比拟成一个金属物体，将优化问题的目标函数比拟成物体的能量，问题的解比拟成物体的状态，问题的最优解比拟成能量最低的状态，然后模拟金属物体的退火过程，从一个足够高的温度开始，逐渐降低温度，使物体分子从高能量状态缓慢的过渡到低能量状态，直至获得能量最小的理想状态为止，从而得到优化问题的全局最优解。10.1.2组合优化(,).,()(),,()(),optoptoptoptoptSfSfiSfifiiSiSfifiiSi组合优化的一个实例，其中是解空间，是目标函数在求最小值时，要求找出一个解使得在求最大值时，要求找到一个解使得无论是求最大值还是最小值，都称为全局最优解。10.1.2组合优化(,).()()min(),(,)iSfNiSfifjjSifiiSSfNiSiNiN设是组合优化问题的一个实例，是一个邻域结构，如果对所有的成立，则称是最小化问题的局部最优解.设是组合优化问题的一个实例，是一个邻域结构，如果对每一个，只要是关于为局部最优的，就有也一定是整体最优的，则称是恰当的.10.1.2组合优化组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量相似性比较10.1.3模拟退火算法的计算步骤及收敛性基本步骤给定初温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算法终止准则满足；输出算法搜索结果。10.1.3模拟退火算法的计算步骤及收敛性定义})1()(Pr{})1(,,)1(,)0()(Pr{)}({)(},,{1021inXjnXinXiXiXjnXZnkXkkXss，满足称为马尔可夫链，若随机序列时刻状态变量的取值。为间，为所有状态构成的解空令10.1.3模拟退火算法的计算步骤及收敛性})0()(Pr{)(,iXjnXpnji定义一步转移概率：n步转移概率：若解空间有限，称马尔可夫链为有限状态；若，称马尔可夫链为时齐的。马尔科夫链})1()(Pr{)1(,inXjnXnpji)1()(,,,npnpZnjiji10.1.3模拟退火算法的计算步骤及收敛性模拟退火算法对应了一个马尔可夫链模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。分析收敛性10.1.3模拟退火算法的计算步骤及收敛性模拟退火过程是从一个状态（解）到另一个状态（解）不断地随机游动，我们称这种游动为变换。从邻域Si中选出某个解j的方法称为解的产生机制.从当前解变换到下一个解的过程称为转移，它由产生机制的应用和接受准则的应用两部分组成。10.1.3模拟退火算法的计算步骤及收敛性(,).,()(),()()1()(),()().kijkijkijijkilkilklSliijkijkSfTijSGTATijpkpTGTATijGTijAT设是组合优化问题的一个实例在模拟退火算法中，当温度为一确定值时，两个解的转移概率定义为当当其中，称为从到的产生概率，称为接受概率10.1.3模拟退火算法的计算步骤及收敛性1010,0(,)().,1,,,...,,,0,0,1,2,...,1(),limlim()1,kkijijppllToptoptTkSfpkGijSplllSliljGkpqTPXkSSS设是组合优化问题的一个实例,是模拟退火算法对应的马尔科夫链的一步转移概率如果产生概率满足以下条件：对任意的，存在且使得那么，由此模拟退火过程所定义的马尔科夫链存在一平稳分布且有.为全局最优解集合10.1.4模拟退火算法实现的技术问题冷却进度表控制参数值Tf的选取马尔科夫链长度Lk的选取控制参数衰减函数的选取10.1.4模拟退火算法实现的技术问题原则(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。方法具体形式对算法影响不大一般采用min[1,exp(-∆C/t)]10.1.4模拟退火算法实现的技术问题方法（1）均匀抽样一组状态，以各状态目标值得方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。初温10.1.4模拟退火算法实现的技术问题0tKkKtk时齐算法的温度下降函数（1），α越接近1温度下降越慢，且其大小可以不断变化；（2），其中t0为起始温度，K为算法温度下降的总次数。温度更新函数10,0,1kttkk10.1.4模拟退火算法实现的技术问题非时齐模拟退火算法每个温度下只产生一个或少量候选解时齐算法——常用的Metropolis抽样稳定准则（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。内循环终止准则10.1.4模拟退火算法实现的技术问题模拟退火算法的优点质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。模拟退火算法的优缺点模拟退火算法的实现与应用给给给给给给给给给给给给给Si给给给给给Sj给给给给给给给s*给给给给给给给给给给给给min{1,exp[-(C(sj)-C(si))/tk]}=random[0,1]给给给给给给给给给给给给给给给给k=0Metropolis给给给给给给给给给给tk+1=update(tk)给k=k+1给Si给Sj，给给给给给给给给s*给给给给给给给给YNYNYN算法流程30城市TSP问题模拟退火算法的实现与应用运行过程30城市TSP问题模拟退火算法的实现与应用运行过程30城市TSP问题模拟退火算法的实现与应用运行过程30城市TSP问题10.2遗传算法遗传算法（GeneticAlgorithm，简称GA）是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与种群内部染色体的随机交换机制相结合的随机化搜索算法。10.2遗传算法达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。生物进化理论和遗传学的基本知识10.2遗传算法遗传学基本概念与术语基因座（locus）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；遗传算法的基本原理和特点10.2遗传算法遗传学基本概念与术语进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;遗传算法的基本原理和特点10.2遗传算法遗传学基本概念与术语选择（selection）：指决定以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;遗传算法的基本原理和特点10.2遗传算法遗传学基本概念与术语变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。遗传算法的基本原理和特点10.2遗传算法遗传算法的基本思路遗传算法实现的技术问题10.2遗传算法遗传算法实现的技术问题遗传算法的工作步骤1..2.0.3.ifthenGAgotocmiiiNppNttttfft选择问题的一个编码；给定种群规模、杂交概率和变异概率的值，给定终止条件随机产生由个字符串（长度相等）组成的种群pop()；令对pop()中每个个体pop()计算它的适应度（pop()).4.满足终止条件选择最佳个体作为的结果，输出结果，6else10.2遗传算法遗传