模拟退火算法

模拟退火算法为一种现代优化算法，用来求解全局最小（最优）解

模拟退火法的核心原理：当材料从状态i进入状态j时，若E(j)<=E(i),状态会被转移（E(i)=E(j)）;若为其他情况，状态会以小概率被转移。也就是说，模拟退火法是一个不断寻找新解和缓慢降温交替的过程。具体实现：

1. 优化函数 f(x)。
2. 初始温度，初始解x0。
3. 根据初始温度，初始解，生成下一个解x2。
4. 判断f(x2)与f(x0)的关系，并根据核心原理进行判断、取值。
5. 根据规定的每一个温度结束的标志，判断是否需要降温
6. 返回第三步

算法流程

具体应用例子

求解TSP问题 例:有100个目标，需要找出巡航最优路径。

代码实现

	clc,clear
	
	%导入数据部分
	
	[~,~,raw] = xlsread('sj.xlsx','Sheet1','A2:H26');
	sj0 = reshape([raw{:}],size(raw)); %将raw{:}重构成原来尺寸的矩阵
	x = sj0(:,[1:2:8]);     %将数据中的经度部分存储在x矩阵中
	x = x(:);               %将x（四列）转为一列
	y = sj0(:,[2:2:8]);     %将数据中的纬度部分存储在y矩阵中
	y = y(:);               %将y（四列）转为一列
	
	%对数据进行处理的部分
	
	sj = [x y];             %将xy矩阵合成，sj中第一列为x；sj中第二列为y
	d1 = [70,40];           %将基地位置存储进去
	sj = [d1;sj;d1];        %将基地存储入数据中,都整合成两列
	sj = sj*pi/180;         %将角度转为弧度制（计算距离时，位置坐标被当作角度计算）
	
	%创建距离公式，距离存储矩阵（用于存储两个点之间的距离）
	
	d = zeros(102);         %创建距离矩阵
	for i = 1:101
	    for j = i+1:102
	        d(i,j) = 6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(i,2))*sin(sj(j,2)));
	    end
	end
	d =d +d';
	
	path = [];              %创建用于存储路径的矩阵
	long = inf;             %初始化距离变量（inf为正无穷）
	rand('state',sum(clock));           %初始化随机数发生器，这种写法的作用：是每一次初始值不同，避免出现相同数字
	
	%蒙特卡洛算法部分，为了得到更好的初始值，先用蒙特卡洛法求解相对较好的解
	
	for j=1:1000            %随机产生一千种解
	    path0 = [1,1+randperm(100),102];%解的情况
	    temp =0;
	    %求解每种情况对应的距离值
	
	    for i=1:101         %通过循环，解得该情况下的距离
	        temp = temp + d(path0(i)+path0(i+1));
	    end
	
	    %对每种情况进行比较，得到最优（小）解
	
	    if temp<long
	        path = path0;
	        long =temp;
	        long
	    end
	end
	
	%模拟退火法部分
	e = 0.1^30;     %结束条件
	L = 20000;      %迭代次数（解空间的大小）
	at = 0.999;     %执行一次的降温比例
	T = 1;          %初始温度
	for k =1:L
	    c = 2+floor(100*rand(1,2));
	    %另c取20000次大于2的值；其中c是一个一行二列的矩阵，rand产生一行二列的元素大于0小于1的随机数矩阵
	    c = sort(c);        %对c的元素进行升序排列
	    c1 = c(1);c2=c(2);
	    df = d(path(c1-1),path(c2))+d(path(c1),path(c2+1)) - d(path(c1-1),path(c1))-d(path(c2),path(c2+1));
	    %判断两组不相邻的两个点的具体是否小于两组相邻两个点之间的距离
	    if df<0
	        path = [path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long = long+df;
	        %如果新解距离小于原来解，则进行替换
	    elseif exp(-df/T) >= rand
	        path = [path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long = long+df;
	        %以这个极小的概率，进行替换
	    end
	    T = T*at;
	    if T<e
	        break;
	    end
	end
	
	%输出部分
	
	path;
	long;
	xx = sj(path,1);
	yy = sj(path,2);
	figure
	plot(xx,yy,'- *')
	legend('巡航最优路径')
	figure
	plot(xx,yy,'ro')
	legend('巡航点位置')

实现效果

模拟退火法模板

依据上述程序改动

	%模拟退火法部分
	e =   ;     %结束条件（到该温度终止）
	L =   ;     %迭代次数（解空间的大小）
	at =  ;     %执行一次的降温比例
	T =   ;     %初始温度
	for k =1:L
		%{

		计算新解的代价
		
		%}
	    
	    if %取新解的条件（新解的代价需要满足的条件）
	        
	    %{
		满足条件，进行替换
		%}

	    elseif exp(-df/T) >= rand	%不满足条件且被替换的概率
		
		%{
		发生这个概率的事件，进行替换
		}%
	    
	    end

	    T = T*at;	%每次进行降温
	    if T<e		%达到目标温度，结束模拟退火法
	        break;
	    end