代码编织梦想

目录

一、理论基础

二、核心程序

三、仿真结论


一、理论基础

        在日常的生产生活环节中发现很多复杂的函数以及其它复杂问题例如: 函数优化、JSP(生产调度)、TSP(旅行商)等,这些问题其中的NP完全问题本身所固有的计算复杂性,求其精确解的计算量往往随问题的规模呈现指数型增长,传统的最优解或者近似最优解方法(枚举法、启发式算法、搜索算法)很难寻找到最优解或者求解到最优解根本无法实现,而设计和现实一种能够解决复杂问题,并且求得最优解或者近似最优解效率高、通用性强的算法来解决这些问题很有必要,这样就为本课题的研究提供了一个需求。

        针对某一具体问题来设计和现实模拟退火算法,模拟退火算法是近年来提出的一种适合解决大规模组合优化问题,特别是NP问题的通用有效近似算法,具有描述简单,运用广泛,运行效率高和较少受初始条件限制的优点,运用模拟退火算法来实现复杂函数和复杂问题的最优化,并且通过多个函数和复杂问题来测试和检验所实现的模拟退火算法的求解性能。

       用最优算法如线性规划求NP完全问题的最优解,需要问题规模的指数阶时间,在问题规模增大时,往往由于计算时间的限制而丧失可行性。用近似算法如贪心法求解NP完全问题,在多项式界的时间里,只能给出近似最优解。模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。。

       模拟退火法(Simulated Annealing)是Kirkpatrick [2]等人在1983年提出并成功地应用在组合最佳化问题中,它是蒙地卡罗演算法的推广。退火是一种物理过程,一种金属物体再加热至一定的温度后,它的所有分子在状态空间中自由运\动。随着温度的下降,这些分子逐渐停留在不同的状态。在温度最低时,分子重新以一定的结构排列,而分子的分布也就是以前面所述的以波兹曼(Boltzamnn)概率分布。不同於上述所介绍的蒙地卡罗演算法,模拟退火法中的温度是随着退火的时候有所改变,因此如何对温度作有效的调整就变成整个模拟退火法最重要的一环。模拟退火算法是近年来在国内外都比较受关注的算法。它的思想最早在1953年由Metropolis提出,在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现,迅速引起了很多专家学者的兴趣,不断对其进行研究。

二、核心程序

function Best_tour_length= tspsiman(EUC_2D) 
flops(0) ;
t0= clock ;
xy= EUC_2D ; 
n_num= length(xy) ;
rand('state',sum(100*clock));
 
distance_matrix = zeros(n_num) ;
for n_num_x = 1: n_num,
     for n_num_y = 1:n_num_x
          x = xy(n_num_x, 1) ;
          y = xy(n_num_x, 2) ;
          xx = xy(n_num_y, 1) ;
          yy = xy(n_num_y, 2) ;
          distance_matrix(n_num_x, n_num_y)= ceil(sqrt((x - xx)^2 + (y - yy)^2)) ;
          distance_matrix(n_num_y, n_num_x)= distance_matrix(n_num_x, n_num_y) ;
 	end
end 


lenbestNN= inf ;
pbestNN= [] ;

   prand= randperm(n_num) ; 
		f=find(prand==1) ;
		prand(f)= prand(1) ;
 	p= [1 prand(2)] ;
	i= prand(3) ;
	count= 3 ;
	 
	while count <= n_num
     	NNdist= inf ;
     	pp= i ;
     	for j= 1: n_num
          	if (distance_matrix(i, j) < NNdist) & (j~=i) & ((j~=p) == ones(1,length(p)))%333??????????????????
                NNdist= distance_matrix(i, j) ; 
                pp= j ;
          	end           
     	end
     	p= [p pp] ; 
      i= pp ;
     	count= count + 1 ;
	end
	
	len= tourdist(p, distance_matrix) ;
 
	if len < lenbestNN
		lenbestNN= len ; 
		pbestNN= p ; 
	end 


solnn= [] ;
lenn= [] ; temp= [] ;
soln= 1 ;
% ========================
% A 2-Opt local search
% ========================
lencurr= lenbestNN; 
Best_tour_length= lenbestNN 
pcurr= pbestNN ; 
pbest= pbestNN ; 
 
% ========================
% Temperature control
% ========================
restart= 1 ;
Tstart= 30 ; % Start temperature
Tend= 1 ; % Stop temperature
Tred= 0.97 ;
T= Tstart ;
Nochange= 2 ; % If after Nochange neighborhood searches, no improvements or 
              %  changes in tour search, annealing complete, break search.
% ========================

lenn= [lenn lencurr] ;
temp= [temp T] ;
solnn= [solnn soln] ;

bb= 0 ;  

while T >= Tend  
	big= n_num - 1 ; 
	while big >= 3   
		small= big - 2 ;
		while small >= 1
		 
			curropt= distance_matrix(pcurr(big),pcurr(big+1)) + distance_matrix(pcurr(small),pcurr(small+1)) ;  
	 		swap2= distance_matrix(pcurr(small),pcurr(big)) + distance_matrix(pcurr(small+1),pcurr(big+1)) ; 
  
 			soln= soln + 1 ;
	 	
			if swap2 < curropt
 				order2= 1: n_num ;  
 				order2=[1:small big:-1:small+1 big+1:n_num] ; 
 
	 			pcurr= pcurr(order2) ;
				lencurr= tourdist(pcurr, distance_matrix) ;
				 
				lenn= [lenn lencurr] ; 
				temp= [temp T] ; 
				solnn= [solnn soln] ; 
 
 		 		if lencurr < Best_tour_length
				  	Best_tour_length= lencurr       
					pbest= pcurr ;  
					Temperature_of_best_tour_length= T
					Solution_count= soln  
					T= Tred * T ; 
					if T <= 3
						T= 50 ;
					end
 				end
				Tcurr= T ;      
   			bb= 0 ;
				big= n_num - 1 ; 
				small= big - 1 ;
				if T <= 3
					T= 10 ;
				end
 
				if T <= Tend ;
					big= 2.9 ; 
					break
 				end	
		
			elseif swap2 > curropt
            %r= abs(randn) ;
            r= rand; % where r ranges from 0.0 to 1.0 
            diff= swap2 - curropt ;
            %if r < exp(-(diff) / T)
        		if r <= exp(-(diff) / T)
					order2= 1: n_num ;
					order2=[1:small big:-1:small+1 big+1:n_num] ; 
 					pcurr= pcurr(order2) ;
           			lencurr= tourdist(pcurr, distance_matrix) ;
					
					T= Tred * T ; 
  					bb= 0 ;  
 	
				end
		 	end
     		small= small - 1 ;
		end
		big= big - 1 ;   
	end
	bb= bb + 1 ;   
 	if T <= Tend | bb > Nochange ;
 	
		clc
		Best_tour_length
		besttour= [pbest -pbest(1)]  
		Temperature_of_best_tour_length
		Solution_count
		Search_stop_temperature= T  
		Elapsed_time= etime(clock, t0) % In seconds
      Solutions_generated= soln 
      Floating_point_operations = flops
	 	if bb > Nochange
			No_change= bb
		end
		disp('Press ENTER to display plot') 
 		pause
		
		clc
		plot(temp, lenn)
		title('Simulated Annealing w/ 2-Opt local search')
		xlabel('Temperature (not scaled)')
		ylabel('Tour Lengths')
		grid
 	 	
		disp('Press ENTER to display plot') 
 		pause

		clc
		plot(solnn, lenn)
		title('Simulated Annealing w/ 2-Opt local search')
		xlabel('Number of Solutions')
		ylabel('Tour Lengths/Costs')
		grid

		disp('Press ENTER to restart search (if var restart > 0) or Ctrl^C to end search.')
		pause
	 	if restart > 0
 
			clc
			T= Tstart ; bb= 0 ;  
			solnn= []; lenn= []; temp= [] ;
			
		 	% =======================================================
			% This time randomly generate tours and restart annealing
			% =======================================================
			prand= randperm(n_num) ;
				f=find(prand==1) ;
				prand(f)= prand(1) ; prand(1)= 1 ;

		   lencurr= Best_tour_length 
         pcurr= pbest ;
         % =======================================================

 		end 
 	end
end	
% End of local search
A06-02

三、仿真结论

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ccsss22/article/details/129825184

基于Matlab的遗传算法程序设计及优化问题求解-爱代码爱编程

遗传算法(Genetic Algorithm)是模拟自然界生物进化机制的一种算法即遵循适者生存、优胜劣汰的法则也就是寻优过程中有用的保留无用的则去除. 在科学和生产实践中表现为在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法即找出一个最优解. 这种算法是1960年由Holland提出来的其最初的目的是研究自然系统的自适应行为并设计具有自适应功能

【BP-预测】基于模拟退火算法改进遗传算法优化BP神经网络预测matlab源码-爱代码爱编程

一、模拟退火算法 固体退火原理:当固体温度较高时,物质内能较大,固体内部分子运动剧烈;当温度逐渐降低时,物体内能也随之降低,分子运动趋于平稳;当固体温度降到常温时,固体内部分子运动最终平稳。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e^(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。 1.1、

模拟退火算法--matlab实现简单问题_面壁十年忘何图的博客-爱代码爱编程

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火算法属于启发式搜索算法的一种。本文主要借鉴B站数学建模清风的视频,文章仅做笔记使用,侵权立删。 目录 爬山法寻找函数最大值 爬山法的算法搜索流程: 模拟退火的算法搜索流程: Ct的设置: 题目1:求一个给定函

基于sa模拟退火优化的tsp路径规划算法matlab仿真-爱代码爱编程

目录 1.算法仿真效果 2.MATLAB核心程序 3.算法涉及理论知识概要 4.完整MATLAB 1.算法仿真效果 matlab2022a仿真结果如下: 2.MATLAB核心程序 ....................................................... graphNo = 1; [ gr

《matlab智能算法30个案例》:第20章 基于遗传模拟退火算法的聚类算法-爱代码爱编程

《MATLAB智能算法30个案例》:第20章 基于遗传模拟退火算法的聚类算法 1. 前言 2. MATLAB 仿真示例 3. 小结 1. 前言 《MATLAB智能算法30个案例分析