无约束条件的模拟退火算法

无约束条件的模拟退火算法.实验目的：使用模拟退火算法解决连续函数优化问题。使用C或C++语言编程环境实现模拟退火算法，并运行函数4得出函数的极值和极值点位置。maxf3,j,z)=50-(5x-2j)2+(%-7j2+2z)4二・模拟退火算法介绍:模拟退火算法是1982年,KirkPatrick将退火思想引入组合优化领域，提出的一种解大规模组合优化问题的算法，对NP完全组合优化问题尤其有效。它以优化问题的求解与物理系统的退火过程的相似性为基础，利用Metropolis算法并适当控制温度的下降过程式项模拟退火，从而达到求解全局优化问题的目的。模拟退火算法在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目标函数值变好的试探点，而且还能够以一定的概率接受使目标函数值变差的试探点，接受概率随着温度的下降逐渐减少。模拟退火算法的这种搜索策略有利于避免搜索过程因陷入局部最优解而无法自拔的弊病，有利于提高求得全局最优解的可靠性。无约束条件的模拟退火算法：给定初始解%0eRn和初始温度T0>0，给定产生随机向量的概率密度函数和控制温度下降过程的温度更新函数，给定常数 P>0。计算f(%)，置X0=%0，X.=%0，f.=f(%0)，k=0根据给定的概率密度函数产生一个随机向量Zk，利用当前迭代点Xk和随机向量Zk产生一个新的试探点，即Yk=Xk+Zk计算f(yk)产生一个在(0，1)上均匀分布的随机数门，计算在给定当前迭代点Xk和温度二下接受试探点Yk的概率P(yk|Xk,T)，即:pTkP(Yk|Xk,“)=min(1,exp(一'f()-f(")|))pTk如果n<P(yk|Xk,T)，则置Xk+1=yk,f(Xk+1)=f(yk)；否则置Xk+1=Xk,f(Xk+1)=f(Xk)。如果f(Xk+1)<f.,则置X.=Xk+1,f.=f(Xk+1)。如果满足迭代终止条件，则算法结束，Xmin就作为近似的全局最优解，fmin为相应的最优值；否则继续步骤6。根据给定的温度更新函数产生一个新的温度《,置k=k+1,转步骤2。核心问题：冷却参数表、领域结构和新解产生器、接受准则和随机数产生器(即Metropolis算法)为退火算法过程的三大支柱。冷却参数即&的选取，新解产生器即由司机函数产生下一个解的一个变换，接受准则即为概率接受准则和随机数产生器(Metropolis算法)，这里我们选取p=0.96;新解产生器为：x_next=x+-x*(rand()% 10000) /10100.00y_next=y+-y*(rand()% 10000) /10100.00z_next=z+-z*(rand()% 10000) /10100.00随机数产生器：r_rand=0.01*(rand()+500)/33000.00;接受准则为：P(YkIXk,T「=min(1,exp(-顷(X^.争宙)|))kr_rand<P时，接受下一个解，否则，继续寻找。程序流程图：

J、&E:\文档、陈鹏涛\shuxueshiyan\chenpengtao\moni\Debu...xy2®：2030-25hsz=-6-40136e+014x_next=9.61188Lnext=22.8891E_next=-4.72277hsz_next=-1.70431e+014r_i'and=0-00267667最大值为:-1.70431e+014皆职潺最大值时CK_niax=9.61188Lnax=22-8891z_niax=-4_?227?hsz=-1-70431e+014x_next=4-61941Lnext=17.463?z_next=-0.892183hsz_next=-2.05316e+013r_i'and=0-0026?667最大值为:-2-05316e+013

49.74070.002733880.0560898-0.00134393=49.99030.00111667最终结果:49.9903当取得最美值时七max=50,这时X_max(2.44036e-009,1・09176e-006,-3・95199e-010)最终结果:49.9903当取得最美值时七.实验心得：通过本次实验，了解了无约束模拟退火算法的思想，算法原理，结果流程，并实现了用所写的程序求解全局最优解，求得了实验函数的最大值。在编写程序的过程中，由于起初对算法有一定的误解，没能理解其实质，后来查资料，明白了其原理，经过认真地考虑，实现了算法。但是，由于原本的模拟退火算法有两层循环，在这里，我们简化了只有一层循环。在实验中，对参数的设置有较高的要求，需要经过多次的尝试，才能调到比较合适的结果。附录：(源程序)#include<iostream>#include<cmath>#include<ctime>#include<cstdlib>usingnamespacestd;constdoubleb=0.9;doubleu=0;doubleIfunc(doublex,doubley,doublez){doublehsz=0.0;hsz=50-pow(5*x-2*y,2)-pow(x-7*y*y+2*z*z,4);returnhsz;}doubleglfunc(doublew1,doublew2,doubleT){doublep;doubleu=0;doublew3=-1.00*abs(w1-w2);u=exp(w3/(b*T));if(u<1)p=u;elsep=1;returnp;}voidmain(){doublex=0,y=0,z=0,x_next=0,y_next=0,z_next=0,hsz=0,hsz_next=0,hsz_max=0;doublex_max,y_max,z_max;cout<<”请输入xyz值：";cin>>x>>y>>z;cout<<endl;doubleT=20000;hsz_max=Ifunc(x,y,z);do{hsz=Ifunc(x,y,z);cout<<"hsz="<<hsz<<endl;//计算初始值srand(static_cast<unsigned>(time(static_cast<time_t*>(NULL))));〃进彳亍y=x+z变换x_next=x+-x*(rand()%10000)/10100.00;

y_next=y+-y*(rand()%10000)/10100.00;z_next=z+-z*(rand()%10000)/10100.00;cout<<"x_next="<<x_next<<endl;cout<<"y_next="<<y_next<<endl;cout<<"z_next="<<z_next<<endl;hsz_next=Ifunc(x_next,y_next,z_next);cout<<"hsz_next="<<hsz_next<<endl;〃随机选取数r_randdoubler_rand=0.01*(rand()+500)/33000.00;cout<<"r_rand="<<r_rand<<endl;doublep=glfunc(hsz,hsz_next,T);///概率接受检验if(r_rand<=p){x=x_next;y=y_nextz=z_next;hsz=hsz_next;}else{x_next=x;y_next=y;z_next=z;hsz_next=hsz;}if(hsz_next>hsz_max){x_max=x_next;y_max=y_next;z_max=z_next;hsz_max=hsz_next;T=T*b;}cout