- 浏览: 533090 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (231)
- 一个操作系统的实现 (20)
- 汇编(NASM) (12)
- Linux编程 (11)
- 项目管理 (4)
- 计算机网络 (8)
- 设计模式(抽象&封装) (17)
- 数据结构和算法 (32)
- java基础 (6)
- UML细节 (2)
- C/C++ (31)
- Windows (2)
- 乱七八糟 (13)
- MyLaB (6)
- 系统程序员-成长计划 (8)
- POJ部分题目 (10)
- 数学 (6)
- 分布式 & 云计算 (2)
- python (13)
- 面试 (1)
- 链接、装载与库 (11)
- java并行编程 (3)
- 数据库 (0)
- 体系结构 (3)
- C++ template / STL (4)
- Linux环境和脚本 (6)
最新评论
-
chuanwang66:
默默水塘 写道typedef void(*Fun)(void) ...
C++虚函数表(转) -
默默水塘:
typedef void(*Fun)(void);
C++虚函数表(转) -
lishaoqingmn:
写的很好,例子简单明了,将观察者模式都表达了出来。
这里是ja ...
观察者模式——Observer
引用:http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html
一. 爬山算法 ( Hill Climbing )
介绍模拟退火前,先介绍爬山算法。爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。
爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。如图1所示:假设C点为当前解,爬山算法搜索到A点这个局部最优解就会停止搜索,因为在A点无论向那个方向小幅度移动都不能得到更优的解。
二. 模拟退火(SA,Simulated Annealing)思想
爬山法是完完全全的贪心法,每次都鼠目寸光的选择一个当前最优解,因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。以图1为例,模拟退火算法在搜索到局部最优解A后,会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点,于是就跳出了局部最大值A。
模拟退火算法描述:
若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解),则总是接受该移动
若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)
这里的“一定的概率”的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。
根据热力学的原理,在温度为T时,出现能量差为dE的降温的概率为P(dE),表示为:
P(dE) = exp( dE/(kT) )
其中k是一个常数,exp表示自然指数,且dE<0。这条公式说白了就是:温度越高,出现一次能量差为dE的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于dE总是小于0(否则就不叫退火了),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。
随着温度T的降低,P(dE)会逐渐降低。
我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(dE)来接受这样的移动。
关于爬山算法与模拟退火,有一个有趣的比喻:
爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。
模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
下面给出模拟退火的伪代码表示
/* * J(y):在状态y时的评价函数值 * Y(i):表示当前状态 * Y(i+1):表示新的状态 * r: 用于控制降温的快慢(0<r<1,越小降温越快) * T: 系统的温度,系统初始应该要处于一个高温的状态 * T_min :温度的下限,若温度T达到T_min,则停止搜索 */ while( T > T_min ) { dE = J( Y(i+1) ) - J( Y(i) ) ; if ( dE >= 0 ) //表达移动后得到更优解,则总是接受移动 Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动 else { // 函数exp( dE/T )的取值范围是(0,1) ,dE/T越大,则exp( dE/T )也 if ( exp( dE/T ) > random( 0 , 1 ) ) Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动 } T = r * T ; //降温退火 ,0<r<1 。r越大,降温越慢;r越小,降温越快 /* * 若r过大,则搜索到全局最优解的可能会较高,但搜索的过程也就较长。若r过小,则搜索的过程会很快,但最终可能会达到一个局部最优值 */ i ++ ; }
三. 使用模拟退火算法解决旅行商问题
(TSP)
旅行商问题 ( TSP , Traveling Salesman Problem ) :有N个城市,要求从其中某个问题出发,唯一遍历所有城市,再回到出发的城市,求最短的路线。
旅行商问题属于所谓的NP完全问题,精确的解决TSP只能通过穷举所有的路径组合,其时间复杂度是O(N!) 。
使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。(使用遗传算法也是可以的,我将在下一篇文章中介绍)模拟退火解决TSP的思路:
1. 产生一条新的遍历路径P(i+1),计算路径P(i+1)的长度L( P(i+1) )
2. 若L(P(i+1)) < L(P(i)),则接受P(i+1)为新的路径,否则以模拟退火的那个概率接受P(i+1) ,然后降温
3. 重复步骤1,2直到满足退出条件
产生新的遍历路径的方法有很多,下面列举其中3种:
1. 随机选择2个节点,交换路径中的这2个节点的顺序。
2. 随机选择2个节点,将路径中这2个节点间的节点顺序逆转。
3. 随机选择3个节点m,n,k,然后将节点m与n间的节点移位到节点k后面。
这个实现参考了这里: http://www.codeproject.com/Articles/26758/Simulated-Annealing-Solving-the-Travelling-Salesma
原始代码采用c#实现,我用C++重写了一遍。但不知为何(???)
模拟退火代码有3个关键点,引用以上原文中的描述:
- Configuration setting : This is the permutation of the cities from 1 to N, given in all orders. Selecting an optimal one between these permutations is our aim.
- Rearrangement strategy : The strategy that we will follow here is replacing sections of the path, and replacing them with random ones to retest if this modified one is optimal or not.
- The objective function (which is the aim of the minimization): This is the sum of the distances between all the cities for a specific order.
TSP求解代码
/* 模拟退火(simulated annealing)求解TSP, C++实现 */ #include <iostream> #include <fstream> #include <sstream> #include <vector> #include <cstdlib> #include <string> #include <cmath> using namespace std; const int MAX_LINE_LENGTH=1000; const int MAX=100; double map[MAX][MAX]; vector<int> curOrder; vector<int> nextOrder; double shortestDist=1<<29; double temperature=10000.0; double deltaDist=0; double coolingRate=0.9999; double absoluteTemperature=0.00001; //当前TSP路线的长度 double getDist(vector<int> order){ double dist=0; for(int i=0;i<=order.size()-2;i++){ dist+=map[order[i]][order[i+1]]; } if(order.size()>1){ dist+=map[order[order.size()-1]][order[0]]; } return dist; } //状态转移:交换当前TSP回路上的任意两个点,范围[0, order.size-1] vector<int> getNextState(vector<int> order){ vector<int> newOrder; for(int i=0;i<order.size();i++){ newOrder.push_back(order[i]); } int i=rand()%order.size(); //rand()产生0~RAND_MAX间任意数,需要引入<cstdlib>,即使原来的<stdlib.h> int j=rand()%order.size(); int tmp=newOrder[i]; newOrder[i]=newOrder[j]; newOrder[j]=tmp; return newOrder; } int main(){ //1. 读取地图 ifstream in("..\\TSP\\Cities.txt"); char line[MAX_LINE_LENGTH]; int line_no=0; while(in.getline(line,MAX_LINE_LENGTH)){ //C++: 按行读取文件 //C++: char[] / string 的split操作 string str_line(line); stringstream ss(str_line); string buf; int col_no=0; while(ss>>buf){ double f=atof(buf.data()); //C++: char*转... (analogy to atoi() ) map[line_no][col_no]=f; col_no++; } line_no++; } //2. 模拟退火求解TSP //init configuration(state) for(int i=0;i<line_no;i++){ curOrder.push_back(i); } int iteration=0; //simulated annealing while(temperature>absoluteTemperature){ nextOrder=getNextState(curOrder); deltaDist=getDist(nextOrder)-shortestDist; if( deltaDist<0 || exp(-deltaDist/temperature)> (rand()/double(RAND_MAX)) ){ //C++: 产生随机数double∈[0,1] for(int i=0;i<nextOrder.size();i++){ curOrder[i]=nextOrder[i]; } shortestDist=shortestDist+deltaDist; } temperature*=coolingRate; iteration++; } cout<<iteration<<endl; cout<<"shortest distance is "<<shortestDist<<endl; cout<<"the order is: "; for(int i=0;i<curOrder.size();i++){ cout<<curOrder[i]<<"\t"; } return 0; }
测试数据Cities.txt
0.0 5.0 5.0 6.0 7.0 2.0 5.0 2.0 1.0 5.0 5.0 1.0 2.0 7.1 5.0 5.0 0.0 5.0 5.0 5.0 2.0 5.0 1.0 5.0 6.0 6.0 6.0 6.0 1.0 7.1 5.0 5.0 0.0 6.0 1.0 6.0 5.0 5.0 1.0 6.0 5.0 7.0 1.0 5.0 6.0 6.0 5.0 6.0 0.0 5.0 2.0 1.0 6.0 5.0 6.0 2.0 1.0 2.0 1.0 5.0 7.0 5.0 1.0 5.0 0.0 7.0 1.0 1.0 2.0 1.0 5.0 6.0 2.0 2.0 5.0 2.0 2.0 6.0 2.0 7.0 0.0 5.0 5.0 6.0 5.0 2.0 5.0 1.0 2.0 5.0 5.0 5.0 5.0 1.0 1.0 5.0 0.0 2.0 6.0 1.0 5.0 7.0 5.0 1.0 6.0 2.0 1.0 5.0 6.0 1.0 5.0 2.0 0.0 7.0 6.0 2.0 1.0 1.0 5.0 2.0 1.0 5.0 1.0 5.0 2.0 6.0 6.0 7.0 0.0 5.0 5.0 5.0 1.0 6.0 6.0 5.0 6.0 6.0 6.0 1.0 5.0 1.0 6.0 5.0 0.0 7.0 1.0 2.0 5.0 2.0 5.0 6.0 5.0 2.0 5.0 2.0 5.0 2.0 5.0 7.0 0.0 2.0 1.0 2.0 1.0 1.0 6.0 7.0 1.0 6.0 5.0 7.0 1.0 5.0 1.0 2.0 0.0 5.0 6.0 5.0 2.0 6.0 1.0 2.0 2.0 1.0 5.0 1.0 1.0 2.0 1.0 5.0 0.0 7.0 6.0 7.0 1.0 5.0 1.0 2.0 2.0 1.0 5.0 6.0 5.0 2.0 6.0 7.0 0.0 5.0 5.0 7.0 6.0 5.0 5.0 5.0 6.0 2.0 6.0 2.0 1.0 5.0 6.0 5.0 0.0
四. POJ例题
POJ 1379 Run Away
解题思路:
其实看程序就比较好理解启发式算法的思想了,但是我找了很多解题报告,发现都没有出现概率性选择并不是最优解的解决办法,有的利用了同时产生好几个点,利 用并发性,这也不能算是概率性选择,还是搞不太明白怎么办。但是就这道题说还是比较简单的,确定步长,减小速度为0.9,因为精度比较低,所以就比较好办 了。保存一个当前最优解集,利用随机性,步长和最优解集产生新的最优解集,最后得到的解有很大程度上不是最优解,但是对于这道题这个精度来说还是可以做到的。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<ctime> #include<cstdlib> using namespace std; const int NUM=20; const int RAD=1000; struct point { double x,y,val; point(){} point(double _x,double _y) { x=_x; y=_y; } }; point p[10001],May[NUM],e1,e2; int n; double X,Y; double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double judge(point t)//评价函数,得到点t的评价值val { double len=dis(t,p[0]); for(int i=1;i<n;i++) len=min(len,dis(t,p[i])); return len; } double Rand(){return rand()%(RAD+1)/(1.0*RAD);}//随机产生0-1的浮点数 point Rand_point(point a,point b)//在a,b框定的四边形内随机生成点 { double xx=a.x+(b.x-a.x)*Rand(); double yy=a.y+(b.y-a.y)*Rand(); point tmp=point(xx,yy); tmp.val=judge(tmp); return tmp; } void solve(double D) { May[0]=point(0,0); May[1]=point(X,Y); May[2]=point(0,Y); May[3]=point(X,0); May[0].val=judge(May[0]); May[1].val=judge(May[1]); May[2].val=judge(May[2]); May[3].val=judge(May[3]); //4个顶点的可能行较大,所以特殊构造 for(int i=4;i<NUM;i++) May[i]=Rand_point(May[0],May[1]);//步骤2 int iteration=0; while(D>0.01)//步骤 3 { for(int i=0;i<NUM;i++) for(int j=0;j<NUM;j++) { point tmp=Rand_point( point(max(0.0,May[i].x-D),max(0.0,May[i].y-D)), point(min(X,May[i].x+D),min(Y,May[i].y+D)) ); if(tmp.val>May[i].val) { May[i]=tmp; } } D*=0.9; iteration++; } //cout<<"iteration="<<iteration<<endl; point ans; ans.val=0; for(int i=0;i<NUM;i++){ //cout<<"("<<May[i].x<<", "<<May[i].y<<") val="<<May[i].val<<endl; if(May[i].val>ans.val) ans=May[i]; } printf("The safest point is (%.1f, %.1f).\n",ans.x,ans.y); } int main() { srand(time(0)); e2=point(0,0); int Case; int i; scanf("%d",&Case); while(Case--) { scanf("%lf%lf%d",&X,&Y,&n); for(i=0;i<n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } solve(max(Y,X)); } system("pause"); return 0; }
五. 算法评价
模拟退火算法是一种随机算法,并不一定能找到全局的最优解,可以比较快的找到问题的近似最优解。 如果参数设置得当,模拟退火算法搜索效率比穷举法要高。
发表评论
-
快排备忘
2013-10-26 11:27 547http://hi.baidu.com/pluto455988 ... -
LRU简单实现C++
2013-10-17 10:52 3970页面置换算法: 在地址映射过程中,若在页面中发现所要访问的页 ... -
二叉树相关
2013-10-04 17:40 690本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针 ... -
双指针策略(《编程之美》3.5 最短摘要生成)
2013-03-26 15:17 2221本文源自《编程之美》3.5 最短摘要生成一课。 ... -
K-MEDOIDS聚类算法
2012-12-04 21:18 1935k-medoids聚类算法 (wiki上讲得很清楚啊:) ) ... -
搜索(三)——回溯
2012-11-23 15:23 1023一、回溯 和 深度搜索 ... -
哈希Hash
2012-11-21 14:42 974要点一:哈希表长度 的确定是个两难的问题:太短则容 ... -
状态压缩DP
2012-11-14 20:27 729引例、 例1、 例2、 例3、 ... -
计算几何(一)——基础算法
2012-07-12 21:07 1903待续 《计算几何资料》为提纲 1. (1) 有向线段 ... -
计算几何(二)——平面最近点对
2012-07-12 10:54 885参考资料: 为何这个问题采用分治法 http://blog ... -
气泡滚大——剔除线性数据中的杂质
2012-06-18 09:43 940这是一道Java的面试题,但是我总结了除了一种自称为“ ... -
深入理解二分查找(二、二分答案)
2012-04-29 16:24 7180二分答案 如果已知候选答案的范围[min,max ... -
P问题、NP问题和NPC问题
2012-04-25 16:36 1046这篇文章转自这里 ... -
RMQ(Range Minimum/Maximum Query)区间最值查询
2012-04-18 20:47 1544一、RMQ问题描述 和 几种解题思路 RMQ问题 (Rang ... -
后缀数组
2012-04-16 09:49 1492一、后缀数组 及其对应的名次数组 举例:S=&quo ... -
大整数运算(部分转载)
2012-04-12 21:36 1170待补充:“浮点数高精度运算” 参见这里==> ... -
单向链表相关
2012-04-10 16:42 953单向链表是微软笔试常考的,参考这里:http://www.c ... -
关键路径(AOE)
2012-04-10 08:05 1648前面这段话是引用别人的,后面代码是自己写的,有待完善: ... -
搜索(二)——双向BFS
2012-03-24 17:18 2999参考这篇文章,以下前 ... -
搜索(一)——剪枝
2012-03-24 11:46 1534参考文档:《搜索方法 ...
相关推荐
模拟退火算法(Simulate Anneal,SA)是一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明...
MATLAB模拟退火算法求解VRPTW带时间窗的车辆路径规划问题。还有改进模拟退火算法,禁忌搜索蚁群算法等,以及各种算法的改进,数据可以更改,文章已经写好,需要可以联系我,可以直接用。 MATLAB模拟退火算法求解...
Matlab的模拟退火算法工具箱,可供修改使用
Matlab的模拟退火算法工具箱11111
模拟退火算法解决置换流水车间调度问题(python实现) Use Simulated Annealing Algorithm for the basic Job Shop Scheduling Problem With Python 作业车间调度问题(JSP)是计算机科学和运筹学中的一个热门优化问题...
该代码采用python编写模拟退火算法,整个过程中可以根据更改代码求解最大值与最小值。 1. 模拟退火算法的原理: 输入:温度T、退火控制参数k、初始点x0 输出:最优的自变量值、最大/最小值 (1)给定初始值温度T,...
模拟退火算法(SA)能有效的解决局部最优解问题。压缩包内含模拟退火模型、Matlab程序和测试数据。简单的模型,自学更改参数。
基于遗传算法和模拟退火算法改进的混合模拟退火算法(解决求函数极值问题,MATLAB代码已实现)混合模拟退火算法时遗传算法和模拟退火算法的结合,在混合模拟退火算法中使用了大量的样本作为问题的可能解决方案而不是...
模拟退火算法源于固体的退火过程,当把一个固体的加热使其升温,其内部分子出现无序状态,内能增大 而降温时,所有粒子趋于有序,冷却到最低温度时内能达到最少。当某一状态下系统内能减少,则完全 接受这一新的...
利用模拟退火算法实现VRP问题,此算法结果较为优良,对了解模拟退火算法有一定的借鉴意义
在 Python 中解决旅行商问题的模拟退火算法 使用模拟退火元启发式求解旅行商问题,并将结果可视化。 首先使用贪心算法(最近邻)来构建初始解决方案。 一个简单的实现,提供了不错的结果。 在具有 100 个节点的 ...
智能优化算法————》模拟退火算法————》C++实现
模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火算法
模拟退火算法组合优化-模拟退火.rar 模拟退火算法主要用于解决组和优化问题,它是模拟物理中晶体物质的退火过程而开发的一种优化算法。在对固体物质进行模拟退火处理时,通常先将它加温熔化,使其中的粒子可自由...
针对2011年全国大学生数学建模竞赛B题的0-1规划应用场景,用python编程复现了模拟退火算法(解决较大规模0-1问题),还用Lingo求解了较小规模的0-1规划问题。资料中附了当年的题目,数据,和原创的复现代码(因为...
解决车辆路径问题,改进的模拟退火和遗传算法,全面详细,适用于解决VRP问题和物流车辆规划
模拟退火模拟退火模拟退火模拟退火代码模拟退火代码
模拟退火法的MATLAB程序Generalsimulatedannealingalgorithm-anneal.m 模拟退火法的MATLAB程序General simulated annealing algorithm 附件所在帖子地址:https://www.ilovematlab.cn/thread-3129-1-1.html ...
平台 vs2015 基于模拟退火算法寻找最优布图解