计算机算法翻译

第六章模拟退火6.1退火和概率模拟退火(SA)是一种随机搜索技术全局优化的问题，并在模拟退火在材料加工过程中金属冷却时，遍地都在结冰到水品形体与最低的能量和更大的crys-tal大小，从而降低金属结构上的缺陷。这退火过程包括精心控制温度和冷却速度(常称为退火表附后)。应用模拟退火到优化柯克帕特里克开创的问题，Gelatt和维奇1983。从那时起，有广泛的研究。不像摘要现有基于梯度的方法和确定性搜索方法的缺点,有被困局部最小值，主要利用模拟退火就是它能避免陷入局部最小点。事实上，已经证明，模拟退火将逐渐融合给全球的最优性,如果足够多的随机性，用于com-bination非常缓慢冷却。比喻来说,这相当于下降一些弹跳球在一个景观，当球反弹和松散的能量，他们定居局部最小点。如果所有的球都是圆的允许足够多次的反弹和松散的能量慢得，一些球最终会落进了全球最低位置，因此全球最低到达。最基本的理念的模拟退火算法使用随机搜索,不仅接受变化改善系统的功能指标,而且还把一些变化这并非是理想的。在一个最小化问题，例如，任何更好的移动或者改变(或降低成本价值)的目标functionfwill被接受,然而,有些变化外，还将接受增加的probabilityp。这个概率p,也被称为“过渡概率，是由p=e6EkT(6.1)wherekis的玻尔兹曼常数，这是最tempera-ture控制退火工艺。6Eis改变的能量水平。这种转移概率为依据的玻尔兹曼分布的物理。最简单的方式，linkOEwithob-jective功能的变化6f是使用6E=y6f,(6.2)wherey是一个常数。为了简单而不失去共性，我们可以usek=1andy=1。因此，概率psimply成为p(Of,T)=e—6fTo(6.3)我们是否接受改变，我们通常使用一个随机的numberras一个门槛。因此,奖学金〉不锈钢p=e-6fT>r,(6.4)它被接受。6.2参数选择这里的选择是至关重要的各项合适的温度。对于一个给定的changeSf,如果是太高(T-8),然后63年6.2参数选择模拟退火算法开始目的functionf(x)、x=(x1,xp)T初始化初始温度丁0和初始guessx(0)最终temperatureT设置fiterationsN和最大数量的aT—冷却scheduleT7定义，(0<a<1)当(T>Tfandn<N)随机运动到新的地点:中国+1=+randn中国CalculateOf=fn+1(中国+1)—fn(中国)如果有更好的接受这个新的解决方案如果没有好转生成一个随机的numberr接受奖学金=经验［—Of/kT)>r结束更新bestx*和*虽然年底结束图6.1:模拟退火算法。p—1,这意味着几乎所有的变化将被接受。IfTis太低(T—0)，然后anyOf>0(更糟的是解决方案)很少被接受，因此asp—0so-lution的多样性是有限的，但Ofwill几乎总是有什么改进被接受。事实上，这个特殊的caseT—0对应摘要现有基于梯度的方法,因为只有更好的解决方案接受,而且系统本质上是攀登或降序在一座小山上。因此，ifTis太高,系统处于一个高能状态对拓扑的景观,min-ima不容易到达。如果是太低，系统可能被困在局部最小(不一定是全球各地最低),并没有足够的能量系统跳出局部极小探索其他潜在的全球最小点。所以适当的温度应该计算。另一个重要的问题是如何控制退火或冷却过程以便系统逐渐冷却下来更高的温度对最终向全球mini-mum冻结状态。有很多种方法可以控制冷却64年第六章。模拟退火利率或下降的温度。两种常用退火时间表（或冷却sched-ules）:线性和几何冷却。对于一个线性冷却过程中，我们在丁二T0-阳（6.5）和T-T-6T,那里的T0是初始温度,然后呢伪时间t是迭代。&is冷却速度，应该选在thatT等一0时的方式t-tf（最大数量的迭代），这通常会给。=T0/tf。几何冷却本质上降低了由一个冷却因素tempera-ture0<a<1thatTis取代aTorT（T）=T0at,t=1,2,…，tf。（6.6）第二种方法的优点是thatT――0whent°°,因此没有必要指定的最大数量iterationst的f。因为这个原因，我们将利用这个几何冷却时间表。冷却过程中应该慢得足以允许系统稳定容易。在实践中,a二0.70.9是常用。此外，对于一个给定的温度、多重评估对目标函数是必要的。如果太少的评估，有个危险是，传系统不稳定和sub-sequently将不收敛其全球最优。如果太许多评估,这是耗费时间的，系统会通常数收敛太慢的迭代可能是指数达到稳定问题的大小。因此，有一个平衡的数量的评估与解的质量。我们可以做许多评估一些温度水平或做一些评估在许多tem-perature水平。有两个主要的方式设置这个号码大数：固定或变化。第一次使用一个固定的号码在各温度的迭代，而第二所愿在增加在较低温度下的迭代局部极值，可以充分挖掘。6.3SA算法图6.2:轮廓的一个功能的香蕉担任位于索非亚安替全球minimumf*二0(1,1)。6.3SA算法利用模拟退火算法可以概括为一如图伪代码。6.1。为了找到一个合适的起始temperatureT0,我们可以使用任何信息的日标函数。如果我们知道最大的改变最大0f)的日标函数，我们可以用它来估计初始temperatureT吗0对于一个给定的probabilityp0。这是T—^0马克斯(Of)指定转接方式0。如果我们不知道的最大变化可能objec-tive函数，我们可以使用一个启发式算法。我们可以开始评估从很高的温度。(所以，几乎所有变化是接受，降低温度迅速)直到大约50%到60%的最糟的举动是接受，然后用这个温度作为新的初始temperatureT0适当的和相对缓慢冷却处理。最后的温度，就应该把注意力集中在理论没有更糟运动可以被接受。然而，如果T女一0时,多的不必要的评估是非常必要的。在具体实践图6.3:500评估在模拟退火。最后的“全球最好的标志。简单地选择一个很小的价值，说,Tf=10-1010-5,根据所要求的质量的方法和时间约束。6.4实施基于这个指南选择重要参与如冷却速度，最初与最后的温度，和平衡数量的发展过程中，我们可以实现既使用Matlab和模拟退火的八度音阶oMatlab程序的im-plemented下面给出音阶。一些相关的模拟测试功能作了说明在详细的例子。范例6.1:香蕉担任位于索非亚安替功能。的f(x,y)=(1-x)2+100(y-x2)2,我们知道它的全球minimumf*=0发生在(1,1)(见图6.2)。这是一个标准的测试功能和很艰难对于大多数算法。然而，使用该程序给出下面,我们可以找到这个全球最低容易，以及500年的评估在模拟退火如图。6.3o6.4■5-5图6.4:蛋箱功能全球最低f=0在(0,0)。最低%找到一个函数的通过模拟退火程序X%S杨(剑桥大学)％用法：sa_simpledemo(“模拟disp…要花一分钟左右！”);测试函数%担任位于索非亚安替f*=0(1,1)fstr='(1-x)“2+100*(y-x"2广2';%兑换成内联函数女二尽量以矢量为单位(嵌入的(fstr));%节日的地形对日标函数范围=[2];xgrid=范围(1):0.1:范围(2);ygrid=范围(3):0.1:范围(4);(x,y)=meshgrid(xgrid,ygrid);surfc(x,y,f(x,y));%初始化参数和设置T_init=1.0;%初始温度T_min=1e-10;最终停止温度。％(如。，T_min=1eT0)F_min=1e+100;%最小值的功能max_rej=500;%最大数量的排斥max_run=100;%最大数量的分max_accept=15;%最大数量的接受k=1;%玻尔兹曼常数0=0.9;%冷却因素Enorm=1e-5;%能源标准(如Enorm=1e-8)猜=[22];%初始猜测%初始化计数器我门等我二0,乔二0;接受=0;totaleval=0;%初始化不同的变量值T_initT=;E_init=f猜,猜(1)(2));E_old=E_init;E_new=E_old;最好的二猜测，最初猜到的价值观。模拟annealling%开始当(丁>T_min)和(]<=max_rej)和E_new>F_min)i=1+1;“如果马克斯编号的检查运行/接受被遇见如果我〉=max_run)|接受〉=max_accept)根据%冷却冷却时间表在T二阿尔法*T;totaleval=totaleval+我。％重置柜台i=1;接受二1;结束“在新的位置函数值ns=猜+兰特(1,2)*randn;E_new=f(nsns(1)、(2));%决定接受了新的途径DeltaE=E_new-E_old;%接受如果改善如果-DeltaE>Enorm)最好的二ns;E_old=E_new;接受二接受+1，乔=0;结束“有一个小的概率接受没有好转如果DeltaE<=Enorm和经验(-DeltaE/(k*T)>rand);最好的二ns;E_old=E_new;接受二接受+1;别的j=m+1;结束%更新估计的最优解f_opt=E_old;结束图6.5:粒子的路径在退火迭代。%显示最后的结果disp(strcat(“Obj功能：’，fstr));disp(strcat(的评价：“,num2str(totaleval)));disp(strcat(最好的位置：’，num2str(最好的)));disp(strcat(最好的估计:’，num2str(f_opt)));范例6.2:使用上述计划的同时，我们也可以模拟一个更复杂的功能，给出了常被称为蛋箱，其全球最小f*二0是(0,0)。日的两个变量函数f(x，y)=x2+y2+25[罪2+罪(x)2(y)，在域名(x，y)E[—5、5]X[—5、5]。蛋箱的景观功能。如图6.4，粒子的路径中，模拟退火如下所示在图6.5。值得指出的是我们用于随机genera-tor程序兰特(1，2)，＜1/2leads离散在几个主要的方向运动,这可能改善收敛为一类的功能。然而，日前担任位于索非亚安替测试函数,该离散ap-proach不工作。连续运动中的所有方向，简单地使用随机functionrand（1,2）在这个简单的程序演示了计划。它将需要大约2500为了得到一个准确的评估与三位小数。第七章和谐搜索7.1Music-Based算法和谐搜索（HS）是一种相对较新的启发式算法，这是第一次optimiza-tionz.w.Geem开发〉，《H。金正日在2001vLoganathan及g。自那以后，它已经被应用到解决许多优化问题,包括给出优化、供水管网、地下水造型、节能调度、桁亍架设计、车辆rout-ing等等。和谐搜索相结合的可能性与其他算法如粒子群优化（PSO）也被研究。搜索引擎是一个music-based和谐optimiza-tion准启发式算法。这是受观察的日标音乐是寻找一个完美的和谐状态。这音乐是类似于和谐找到最优的优化的过程。在优化搜索过程被比喻为这样一名音乐家即兴创作的过程。这per-fectly愉悦的和谐是由音频的审美标准。审美素质的本质上是一种乐器根据其音高（或频率），音质（或声音的质量），和振幅（或声音）。音色的主要是开创性的谐波含量依次确定通过波形图或调制的音频信号。图7.1:和谐与频率比两个音符书2:3及其波形。曾经，它能产生谐波的将在很大程度上依靠球场的特定频率范围的仪器。不同的音符有着不同的频率。例如，注：以上的中央C音（或者标准音乐会A4）从一个基本频率0=440赫兹。当速度在干燥的空气是声音aboutv=331+0.6whereTisTm/s温度接近0摄氏度。。所以在房间temper-atureT=20°C,A4注有wavelength尤v/f^00.7795米。当我们调整投球，实际上我们是在尝试改变频率。在音乐理论，pitchpinMIDI经常被描绘成一个数值量表（一个线性沥青空间）使用下列公式p=69+12日志2（f440赫兹），（7.1）或f=440X2（p-69）/12（7.2）这意味着有一个球场的A4笔记69号。在这个规模，倍频与12号的，semitone相对应大小1。此外，比两个音的频率这是一个八度与众不同的是2:1。因此，频率的一个了注1倍（减半）（降低）提出一个八度音阶。例如,A2110赫兹的频率是A5有而880赫兹的频率。7.2和谐搜索图7.2:随机的音符。当不同的测量方法，同时oc-curring和谐球，就像任何美学质量、点主观的。然而，它可能会使用一些标准的es-timation和谐。频率比、开创的古希腊数学家毕达哥拉斯，是一个好方法这样的估计。例如，八度的比率1:2当声音一起玩的愉快，所以纸币比例为2:3（见图7.1）。然而，这些都不太可能对任何如所示的随机笔记在7.2生产pleas-ant和谐。7.2和谐搜索搜索可以被解释成和谐做更详细的援助的讨论的一个mu-sician即兴创作过程。当一个音乐家即兴创作，他或她有三个可能的选择:（1）玩什么著名的音乐作品（一个系列球准确的和谐）从他/她的记忆；（2）演奏一些类似于一个已知的块（因此调整沥青略）；（3）或随机作曲的笔记。如果我们这三个选项固化优化，我们有三个相应的组成:和谐的使用内存，音高调整,并被随机分组。使用和谐的记忆是很重要的，因为这是simi-lar选择最适合个人遗传算法。这将确保最佳的和弦,将被保留下来新的和谐的记忆。为了使用这种记忆有效分配parameterr凸轮接受E[0,1],称为和谐或考虑记忆接受率。如果此汇率过低，只有少数选择最好的和声五月份可以吗74第七章。和谐搜索收敛速度太慢。如果这个比率极高（近1）,al-most所有和弦是用在和谐的记忆，然后其他不探索和声,导致潜在的错误的解决方案。因此，一般情况下,r接受二0.7〜0.95。调整沥青有轻微的第二部分，我们必须用一种方法能effi-ciently调整频率。在理论上，球场上可调的线性或non-linearly,但在实践中，使用线性调整。所以我们有p一个二plowerlimit+p范围*兰特,（7.3）wherep范围=pupperlimit—plowerlimit。Randis随机num-ber发电机在范围为0和1。音高调节相似的变异算子的遗传算法。我们pitch-adjusting能分配率（rpa以控制这个学位调整。Ifrpa过低,那么就没有什么改变。如果它太高了，然后可能不con-verge算法。因此，我们通常用户pa在大多数二0.1〜0.5模拟。第三个构件是随机化，即增加多样性的解决方案。虽然调整球场上有一个类似的角色，但它是局限于特定当地球调整，从而与局部搜索。使用随机试验可以驱动系统探讨不同不同的解决方法,以便找到全局最优。这三个组件在和谐中搜索可以作为阐述伪代码。如图7.3。在这个伪代码，我们可以看到，随机取样的可能性P随机-r=1接受（7.4）实际的可能性和俯仰调节P沥青二匕接受rpa。（7.5）此外,如遗传算法和粒子群op-timization、和谐搜索并不是一个摘要现有基于梯度搜索，所以它避免了大部分的陷阱中的任何摘要现有基于梯度搜索算法。因此，它有更少的数学要求,75年7.3实施和谐搜索开始目的functionf（x）、x=（x1,xp）T产生初始谐波（实数数组）定义俯仰调节率（rpa）和沥青限制定义接受率（r和谐记忆接受）当（t<最大数量的迭代）产生新的谐波接受最好的谐波调整球场，得到新的谐波（解决方案）如果（rand>raccept）,选择一个现有的谐波随机如果（rand>rpa其他），调整在一定范围内随机球场其他通过随机生成新的谐波结束接受新谐波（解决方案）如果更好虽然年底找到当前最佳估计结束图7.3:伪码搜索的和谐。随后，它可以用来处理复杂objec-tive是否连续或不连续函数、线性或非线性、或随机噪声。另一方面,搜索可能潜在的和谐比遗传算法更有效，因为和谐搜索不使用二进制编码和解码，但是它却有吗多重解向量。因此，他在每一次快迭代°HS算法的实施也比较容易。此外，有证据表明，他sen-sitive进行选参数少，这就意味着我们不这么做微调这些参数必须把质量的解决方案。7.3实施使用这三个组件描述在上面部分，我们和谐的搜索算法,可以实现在两个Matlab和八度音阶。功能的香蕉为担任位于索非亚安替图7.4:和弦的变化在和谐中搜索°f(x,y)=(1-x)2+100(y-x2)2(7.6)在(x,y)E[—10,10]X[—10,10],它有一个全球最低f在最小=0(1,1)。以下的Matlab/八度程序可以用来找到它的最优。％和谐搜索(简单的演示)的Matlab程序书面X%S杨(剑桥大学)%用法:hs_simple%或hs_simple("x"2+(y-5)“2',25000);功能的影响[解决方案,fbest]=hs_simple(funstr,MaxAttempt)disp(“这可能需要几分钟……”)；%MaxAttempt=25000;最大数量的尝试如果nargin<2,MaxAttempt=25000最后如果nargin<1,“香蕉的功能是担任位于索非亚安替“在全球fmin=0(1,1)。funstr='(1-x1广2+100*(x2-x1八2广2';结束%转换成内联函数女二尽量以矢量为单位(嵌入的(funstr));ndim=2,%数量的独立变量%范围的日标函数范围(1)=[-10];范围(2)=[-10];%投俯仰调节范围pa_range=[200];77年7.3实施%初始参数的设置HS_size=20;%长度的解决方案的向量HMacceptRate=0.95;%HM接受率PArate=0.7;%俯仰调节率%生成初始解向量因为我二1:HS_size,为j=1:ndim,x(j)二范围