模式识别九--模拟退火算法的设计与实现

2024-06-12 20:38

本文主要是介绍模式识别九--模拟退火算法的设计与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文转自:http://www.kancloud.cn/digest/prandmethod/102851

        本节的目的是记录以下学习和掌握模拟退火(Simulated Annealing,简称SA算法)过程。模拟退火算法是一种通用概率算法,用来在一个大的搜寻空间内寻找命题的最优解。这里分别使用随机模拟退火算法和确定性模拟退火算法,在MATLAB平台上进行编程,以寻找一个6-单元全连接网络的能量最小化模型。

参考书籍:Richard O. Duda, Peter E. Hart, David G. Stork 著《模式分类》

一、技术论述

1.随机方法

学习在构造模式分类器中起着中心的作用。一个通常的做法是先假设一个单参数或多参数的模型,然后根据训练样本来估计各参数的取值。当模型相当简单并且低维时,可以采用解析的方法,如求函数导数,来显式求解方程以获得最优参数。如果模型相对复杂一些,则可以通过计算局部的导数而采用梯度下降算法来解,如人工神经网络或其他一些最大似然方法。而对于更复杂的模型,经常会出现许多局部极值,上述方法的效果往往不尽人意。

如果一个问题越复杂,或者先验知识和训练样本越少,我们对能够自动搜索可行解的复杂搜索算法的依赖性就越强,如基于参数搜索的随即方法。一个通常的做法是使搜索朝着预期最优解的区域前进,同时允许一定程度的随机扰动,以发现更好的解。

2.随机搜索

这里主要研究在多个候选解中搜索最优解的方法。假设给定多个变量si,i=1,2,…,N,其中每个变量的数值都取两个离散值之一(如-1和1)。优化问题是这样描述的:确定N个si的合适取值,时下述能量函数(又称为代价函数)最小:

其中w_ij是一个实对称矩阵,取值可正可负,其中令到自身的反馈权为零(即w_ii=0),这是因为非零w_ii只是在能量函数E上增加一个与si无关的常数,不影响问题的本质。这个优化问题可以用网络和节点的方式表示,如下图所示,其中节点之间的链接对应每个权值w_ij。

3.贪心算法的局限性

如上所述,对于求解有N个变量si的能量E最小化问题,除非N的取值很小,否则往往无法直接求解,因为其构型数目高达N^2。如果使用贪心算法搜索最优的构型,需要先随机选取每个节点的起始状态,然后顺序考查每个节点从而计算与之相联系的si=1状态和si=-1状态的能量,最后选取能够降低能量的状态迁移。这种判断只用到了直接与之相连的具有非零权值的相邻节点。

这种贪心搜索算法成功找到最优解的可能性很小,因为系统常常会陷入局部能量最小值,或根本就不收敛,因此需要选择其他搜索方法。

4.模拟退火

在热力学中,固体的退火过程主要由以下三部分组成:

  1. 加温过程。其目的是增强粒子的热运动,使其偏离平衡位置。当温度足够高时,固体将熔解为液体,从而消除系统原先可能存在的非均匀态,使随后进行的冷却过程以某一平衡态为起点。熔解过程实际是系统的熵增过程,系统能量也随温度的升高而增大。
  2. 等温过程。物理学的知识告诉我们,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态。
  3. 冷却过程。其目的是使粒子的热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。

Metropolis等在1953年提出了重要性采样法,即以概率大小接受新状态。具体而言,在温度T时, 由当前状态i产生新状态j,两者的能量分别为Ei和Ej,若Ej小于Ei,则接受新状态j为当前状态;否则,计算概率p(∆E):

若p(∆E)大于[0,1]区间内的随机数,则仍旧接受新状态j为当前状态;若不成立则保留i为当前状态,其中k为玻尔兹曼常数,T为系统温度。上述重要性采样过程通常称为Metropolis准则:

  1. 在高温下可接受与当前状态能量差较大的新状态;
  2. 而在低温下基本只接受与当前能量差较小的新状态;
  3. 且当温度趋于零时,就不能接受比当前状态能量高的新状态。

1983年Kirkpatrick 等意识到组合优化与物理退火的相似性,并受到Metropolis 准则的启迪,提出了模拟退火算法。模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法,其出发点是基于物理退火过程与组合优化之间的相似性,模拟退火方法由某一较高初温开始,利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索,伴随温度的不断下降,重复抽样过程,最终得到问题的全局最优。对比贪心算法,模拟退火算法主要的优势在于它使系统有可能从局部最小处跳出。

对于一个优化问题:

把优化问题的求解过程与统计热力学的热平衡问题进行类比,通过模拟高温物体退火过程的方法,试图找到优化问题的全局最优或近似全局最优解;

允许随着参数的调整,目标函数可以偶尔向能量增加的方向发展(对应于能量有时上升),以利于跳出局部极小的区域,随着假想温度的下降(对应于物体的退火),系统活动性降低,最终稳定在全局最小所在的区域。

5.两种模拟退火算法

两种模拟退火算法,即随机模拟退火和和确定性模拟退火算法的实现步骤如下所示:

随机模拟退火算法收敛很慢,部分原因在于其中搜索的全部的构型空间的离散本质,即构型空间是一个N维超立方体。每一次搜索轨迹都只能沿着超立方体的一条边,状态只能落在超立方体的顶点上,因此失去了完整的梯度信息。而梯度信息是可以用超立方体内部的连续状态值提供的。一种更快的方法就是以下的确定性模拟退火算法:

二、实验结果讨论

构造一个6-单元全连接网络,能量函数使用公式:

其中网络的连接权值矩阵如下:

设计步骤主要包括以下几个部分: 
编写程序[E, s_out] = RandomSimulatedAnnealing(T_max, time_max, c, s, w),实现以上算法1所述的随机模拟退火算法。这里需要设定以下参数: T_max=10,T(m+1) =c*T(m),c=0.9,进行实验,能量随温度下降次数的变化曲线如图2所示(由于模拟退火算法所得到的结果有一定的随机性,因此以下步骤均执行四次算法进行观察),四次所得到的最终构型s如图3所示。

改变参数:初始温度:T_max=5,T(m+1) =c*T(m),c=0.5,进行实验,能量随温度下降次数的变化曲线如图4所示,四次所得到的最终构型s如图5所示。

编写程序[E, s_out] = DeterministicAnnealing(T_max, time_max, c, s, w),实现以上算法2所述的确定性模拟退火算法。这里需要设定以下参数: T_max=10,T(m+1) =c*T(m),c=0.9,进行实验,能量随温度下降次数的变化曲线如图6所示,四次所得到的最终构型s如图7所示。

改变参数:初始温度:T_max=5,T(m+1) =c*T(m),c=0.5,进行实验,能量随温度下降次数的变化曲线如图8所示,四次所得到的最终构型s如图9所示。

结论:图2、3给出了多次随机模拟退火算法的运行结果,可以看到构型s不一定完全一样;能量函数E的波形在经过若干次逐渐递减的震荡后基本收敛到全局最小值-19。当改变T(1)=5,c=0.5时,从图4中可观察到能量函数E的波形极速下降,并达到较小的值,中间少了一个温度渐变和震荡调整的过程。

图6、7给出多次确定性模拟退火算法的运行结果,且每次得到的最终构型s均一致;能量函数E的波形在经过平缓递减后收敛到全局最小值-19,不出现随机模拟退火中剧烈震荡的情况。当改变T(1)=5,c=0.5时,从图8中可观察到能量函数E的波形同样呈现出极速下降的态势,并达到较小的值,中间少了一个温度渐变和调整的过程。

综合以上的实验结果,我们发现随机退火和确定性退火均能给出相似的最终解,但对于一些大规模的现实问题,随机模拟退火的运行速度很慢,而相比之下确定性退火算法要快很多,有时可以快2~3个数量级。

另外,初温T(1)和温度下降系数c的选择对算法性能也有很大影响。初温的确定应折衷考虑优化质量和优化效率,常用方法包括以下几种:

  • 均匀抽样一组状态,以各状态目标值的方差为初温;
  • 随机产生一组状态,确定两两状态间的最大目标值差|∆max|,然后依据差值,利用一定的函数确定初温。譬如T(1)=-∆/ln 
    p_r,其中p_r为初始接受概率;
  • 利用经验公式给出。

模拟退火算法设计中包括三个重要的函数:状态产生函数、状态接受函数、温度更新函数;同时在程序设计时,需遵循内循环终止准则、外循环终止准则。这些环节的设计将决定模拟退火算法的优化性能。

三、实验结果

四、简单代码实现

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 随机模拟退火函数
% 输入参数:
%   T_max:初始温度
%   time_max:最大迭代次数
%   c:温度下降比率
%   s:初始构型
%   w:权值矩阵
% 输出参数:
%   E:能量变化矩阵
%   s_out:经过算法计算后的构型
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [E, s_out] = RandomSimulatedAnnealing(T_max, time_max, c, s, w)[x, y] = size(s);time = 1;        % 迭代次数
T(time) = T_max; % 初始温度设置while (time < (time_max + 1)) % (T(time) > T_min) for i = 1:1000num = ceil(rand(1) * y); % 选择产生一个1到y之间的随机数for j = 1:ye(j) = w(num, j) * s(num) * s(j);endEa(time) = -1 / 2 * sum(e);Eb(time) = -Ea(time);if Eb(time) < Ea(time)s(num) = -s(num);elseif (exp(-(Eb(time) - Ea(time)) / T(time)) > rand())s(num) = -s(num);elses(num) = s(num);endend% 计算能量EE(time) = 0;for it = 1:6for jt = 1:6E(time) = E(time) + w(it, jt) * s(it) * s(jt);endendE(time) = E(time) * (-0.5);s_out(time,:) = s;  % 每次形成的构型time = time + 1;T(time) = T(time - 1) * c;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 确定性模拟退火函数
% 输入参数:
%   T_max:初始温度
%   time_max:最大迭代次数
%   c:温度下降比率
%   s:初始构型
%   w:权值矩阵
% 中间函数:
%   tanh(l / T):响应函数,该函数有一个隐含的重新规格化的作用
% 输出参数:
%   E:能量变化矩阵
%   s_out:经过算法计算后的构型
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [E, s_out] = DeterministicAnnealing(T_max, time_max, c, s, w)[x, y] = size(s);time = 1;        % 迭代次数
T(time) = T_max; % 初始温度设置while (time < (time_max + 1))num = ceil(rand(1) * y); % 选择产生一个1到y之间的随机数for j = 1:ye(j) = w(num, j) * s(j);endl(time) = sum(e);s(num) = tanh(l(time) / T(time));% 计算能量EE(time) = 0;for it = 1:6for jt = 1:6E(time) = E(time) + w(it, jt) * s(it) * s(jt);endendE(time) = E(time) * (-0.5);s_out(time,:) = s; % 每次形成的构型time = time + 1;T(time) = T(time - 1) * c;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%模拟退火算法实验
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear;
close all;% 网络的连接权值矩阵
w = [ 0 5 -3 4 4 1;...5 0 -1 2 -3 1;...-3 -1 0 2 2 0;...4 2 2 0 3 -3;...4 -3 2 3 0 5;...1 1 0 -3 5 0];num = 6; % 总共产生6个数 
s_in = rand(1,num); % 生成1和-1的随机序列 
s_in(s_in > 0.5) = 1; 
s_in(s_in < 0.5) = -1;
disp(['初始构型S为:',num2str(s_in)]);% 以下是随机模拟退火算法
T_max = 10;        % 初始温度设置
time_max = 100;    % 最大迭代次数
c = 0.9;           % 温度变化比率
[E1, s_out1] = RandomSimulatedAnnealing(T_max, time_max, c, s_in, w);
subplot(221),plot(E1);grid on;
title(['T(1) = ',num2str(T_max),',c = ',num2str(c),',随机模拟退火算法能量变化曲线']);
disp(['T(1) = 10,c = 0.9,随机模拟退火算法最终构型S为:',num2str(s_out1(time_max,:))]);T_max = 5;         % 初始温度设置
time_max = 100;    % 最大迭代次数
c = 0.5;           % 温度变化比率
[E2, s_out2] = RandomSimulatedAnnealing(T_max, time_max, c, s_in, w);
subplot(222),plot(E2);grid on;
title(['T(1) = ',num2str(T_max),',c = ',num2str(c),',随机模拟退火算法能量变化曲线']);
disp(['T(1) = 5,c = 0.5,随机模拟退火算法最终构型S为:',num2str(s_out2(time_max,:))]);% 以下是确定性模拟退火算法
T_max = 10;        % 初始温度设置
time_max = 100;    % 最大迭代次数
c = 0.9;           % 温度变化比率
[E3, s_out3] = DeterministicAnnealing(T_max, time_max, c, s_in, w);
subplot(223),plot(E3);grid on;
title(['T(1) = ',num2str(T_max),',c = ',num2str(c),',确定性模拟退火算法能量变化曲线']);
disp(['T(1) = 10,c = 0.9,确定性模拟退火算法最终构型S为:',num2str(s_out3(time_max,:))]);T_max = 5;         % 初始温度设置
time_max = 100;    % 最大迭代次数
c = 0.5;           % 温度变化比率
[E4, s_out4] = DeterministicAnnealing(T_max, time_max, c, s_in, w);
subplot(224),plot(E4);grid on;
title(['T(1) = ',num2str(T_max),',c = ',num2str(c),',确定性模拟退火算法能量变化曲线']);
disp(['T(1) = 5,c = 0.5,确定性模拟退火算法最终构型S为:',num2str(s_out4(time_max,:))]);

参考链接:http://www.cnblogs.com/growing/archive/2010/12/16/1908255.html

这篇关于模式识别九--模拟退火算法的设计与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1055278

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo