模拟退火算法应用于最优排列问题和最优组合问题 之 排列篇

标签: 模拟退火 算法 应用 | 发表时间:2011-05-17 23:03 | 作者:左洸 团子小囧
出处:http://www.cnblogs.com/

一般学习模拟退火算法的时候,都是用全排列问题作为例子讲解,所谓全排列问题,就是说解的长度(或者步骤)是确定的,只不过排列顺序不同罢了,其中任何一种排列顺序都是问题的一个解,我们通过不断尝试不同的排列顺序,找到其中最优的一个。

 

TSP旅行商问题就是典型的全排列问题,所有的城市都是两两互联的,每个城市都要去一次(且只能去一次),先去那个后去那个,顺序不同只不过花费的代价不一样,但都是问题的一个解决方案。

 

注意:任何一种排列都是问题的一个解。这是一种很好的特性,这种情况下,可以直接应用典型的模拟退火算法。

 

模拟退火算法的核心就是对解的取舍。

 

第一步:首先生成一个初始解。

生成初始解的时候,你可以随机生成,也可以依照某种原则生成。无论怎样,反正就是一组排列。

当你把这组排列应用到问题域的时候, 会得到一个反馈的结果(也可以叫输出吧),比如说总花费、总路程之类的,一般我们希望这个结果越小(或者越大)越好。

这里,最优的输出值大概是多少,我们并不知道,甚至没有任何概念。

所以,应用这个初始解得到的输出,可能离目标很远,也可能离目标很近,哪怕他就在目的地门口,我们也一无所知。

 

第二步:变换解。

所谓变换解就是,我们把前一个解做一定的改变,具体怎么改变呢?

我要说取前一个解的领域,你可能会说我装逼(哈哈)。

其实想怎么变就怎么变,比如:将排列(即前一个解)中某两个元素的位置交换一下,再比如:将排列(即前一个解)从某个位置劈开,然后将两部分前后调换一下,再重新组合起来,等等。 

 

发挥你的想象,只要你每次都用同样的变换就行。另外,变换最起码要遵守问题描述,比如每个城市只能去一次,你不能变的去两次。

 

现在我们有了一个新的解。

如果把这个新的解应用的问题域上,同样也会得到一个反馈结果(输出),同样,我们还是不知道这个输出距离最终目标有多远。 

不管怎么样,我们至少可以确定一点,新解和旧解的输出肯定不同。

变换的核心思想就是:差之毫厘,谬之千里。

 

第三步:新解的取舍。 

现在我们有两个解和两个解的输出。虽然我们不知道最终目标输出是多少,但是哪个解的输出距离目标更近一点我们应该能看出来。

比如:旧解的输出是花费100元,新解的输出是花费80元。

如果像这样,新解比旧解“看上去”更好,我们就把新解作为当前解,回到第二步,用它再做新的变换。

注意:这里我用到一个“看上去”,确实是这样,只要看上去更好就行,你不用考虑更多,也许他可能要兜圈子。

 

如果新解比旧解看上去要差呢?扔了它?那就成了贪心算法了。模拟退火的核心就在这里,怎么取舍这个看上去差一点的解。

要说公式有点复杂,要说白了其实很简单,就是掷骰子。

骰子出大时候,我们就接受这个看上去差一点的解作为新的当前解,用它再做新的变换。

 

如果骰子出了小,那只有放弃他了,当前解不发生改变,还是前面的旧解,下一次变换只能

再次用他重新来一次。

当然这个骰子做了一点手脚,刚开始总是出大,后来大小出的差不多,再后来就总是出小了。具体原因大家自己看公式去吧。

 

这里想说一下,为什么我们要用一定的可能性来接受这个看上去差一点的解能?

因为这个解虽然差一点,但是也许只是看上去差一点, 作为下一个变换的起点,看上去差一点的解不见得比看上去好一点的解前途更差。

延安的共军和重庆的国军,你选哪个呢?身在其中,有时候骰子可能更靠谱一点。

 

第四步:循环。

现在,我们可能接受了变换解作为当前解;也可能放弃了变换解,当前解没发生变化,还是上一个解。 

不管怎么样,回到第二步,对当前解继续使用变换,取舍,循环下去。。。。。。。。

 

第五步:退出。

前面我们说过,一般情况下我们不知道最终目标是多少,如果知道的话,比如花费40元,如果某一个解的输出得到了这个花费40元,那么你的算法就可以退出了。这个解就是一个最优解(因为他的输出你确定是最优的)。

但是一般情况下我们不知道最终目标说多少,怎么办呢?

前面我们分析过,虽然有时候通过骰子,我们可能会接受一些看上去差一点的解,但是经过许多次循环以后,我们获得的当前解还是越来越好的

由于这样一个趋势,程序运行一段时间以后,我们无论再怎么变换出新解,也得不到更好的输出。

但是骰子还会让我们接受一些差解,那不就死循环了吗?

别忘了,骰子也有一个趋势,就是到后来就总是出小,即不再接受差解。

 

这样,找不出更好的解,也不再接受差解,如果当前解经过长时间都没发生改变,比如说100000次循环都没变,那么我们就可以认为当前解就是比较优秀的解了,可以退出了。

 

还有一种类似的方法是看输出。比如,初解的输出是100元,过了一会得到一个更好的值80元,再过一会又得到一个更好的值40元,然后经过长时间的运算也没找到更好的输出,那么40元输出对应的那个解就是比较优秀的解。

 

最后一个问题:是最优解吗?

回答:保证是比较优秀的解;很可能是最优解,但不能保证。哪怕你得到40元这个当前最好输出以后又运行了1年,没有找到更好的输出,也不能保证40元对应的解就是最优解(也许他真的就是)。

 

最优解有时候就像本拉登,天天在你身边,你也不一定认得出来。 

 

//==========================================

作者: 左洸 发表于 2011-05-17 23:03 原文链接

评论: 2 查看评论 发表评论


最新新闻:
· 口碑网首推手机LBS+团购(2011-05-18 16:54)
· 联通正式引入2款黑莓手机 BIS业务月费60元(2011-05-18 16:51)
· 程序员的本质(2011-05-18 16:43)
· 盛大员工办问答网站米饭PK创新工场旗下知乎(2011-05-18 16:39)
· 凤凰视频启动凤鸣计划:主推视频媒体模式(2011-05-18 16:32)

编辑推荐:Scrum之成败——从自身案例说起,仅供参考

网站导航:博客园首页  我的园子  新闻  闪存  小组  博问  知识库

相关 [模拟退火 算法 应用] 推荐:

模拟退火算法应用于最优排列问题和最优组合问题 之 排列篇

- 团子小囧 - 博客园-首页原创精华区
一般学习模拟退火算法的时候,都是用全排列问题作为例子讲解,所谓全排列问题,就是说解的长度(或者步骤)是确定的,只不过排列顺序不同罢了,其中任何一种排列顺序都是问题的一个解,我们通过不断尝试不同的排列顺序,找到其中最优的一个. 象TSP旅行商问题就是典型的全排列问题,所有的城市都是两两互联的,每个城市都要去一次(且只能去一次),先去那个后去那个,顺序不同只不过花费的代价不一样,但都是问题的一个解决方案.

Chandy Lamport算法及其应用(exactly once)

- - Blog of Kami Wan
Chandy lamport算法简介. 先普及个概念(取自维基百科):. 今天讨论的chandy and larmport算法也是分布式快照算法的一种,用于在分布式系统中记录一个全局一致的快照. 原始论文可以参考 Distributed Snapshots: Determining Global States of Distributed System.

Simhash算法原理和网页查重应用

- - 互联网旁观者
传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法. 产生的两个签名,如果相等,说明原始内容在一定概率下是相等的;如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大. 从这个意义上来说,要设计一个hash算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签名值除了提供原始内容是否相等的信息外,还能额外提供不相等的原始内容的差异程度的信息.

电子商务推荐算法工业应用总结

- - 冰火岛
电子商务推荐算法工业应用总结. 谨以此文纪念阅读推荐算法论文,设计开发推荐算法,不断踩雷,加班的日子. 推荐系统就是要恰当的时间合适的地方,采用适用的方法给正确的人推荐满足需求的商品. 即 when where who what how. 本文关注的是其中的一个方面,电子商务推荐算法(即how). 开发满足实际工程应用的算法,推荐算法人员具备的能力:以工程化的方法,产品设计者的思维来设计和开发算法.

常见算法在实际项目中的应用

- - 博客 - 伯乐在线
近日Emanuele Viola在Stackexchange上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求:. 使用这些算法的软件或者硬件应该是被广泛应用的;. 例子需要具体,并给出确切的系统、算法的引用地址;.

序列特征在推荐算法中的应用

- - 掘金 后端
**简介:**行为序列特征在推荐,广告等领域中有着广泛应用,最近几年涌现了很多有关行为序列的研究论文,讲解如何将行为序列应用到实际场景中. 但是论文中的实际思想距离落地还有一段距离,因此本文先介绍一些论文中的序列特征的用法,然后介绍一下在大规模分布式推荐系统框架 EasyRec 中如何将序列特征快速落地,提升实际场景效果.

一致性哈希算法及其在分布式系统中的应用

- BeerBubble - 博客园-EricZhang's Technology Blog
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用. 首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接下来会对这个算法进行相对详细的描述,并讨论一些如虚拟节点等与此算法应用相关的话题.

苹果7月修改应用排行算法:首次参考用户评级

- - 博客园_新闻
研究机构 Fiksu 日前发布报告显示,苹果在 7 月底悄悄修改了应用商店(App Store)和 iTunes 中应用排行的算法,而新算法首次将用户对应用评级纳入排行时参考的因素. 根据 Fiksu,在 7 月份前,苹果应用排行的算法一般只参考应用的“下载数量”和“下载速度”. 但是在 7 月底,Fiksu 研究员发现,部分应用的排名出现令人意外的上升和下降,而这些应用在“下载数量”和“下载速度”方面却没有呈现相应的变化.

图片占用内存的算法和自定义应用堆内存

- - 移动开发 - ITeye博客
android中处理图片的基础类是Bitmap,顾名思义,就是位图. 图片的width*height*Config. 如果Config设置为ARGB_8888,那么上面的Config就是4. 一张480*320的图片占用的内存就是480*320*4 byte. 前面有人说了一下8M的概念,其实是在默认情况下android进程的内存占用量为16M,因为Bitmap他除了java中持有数据外,底层C++的 skia图形库还会持有一个SKBitmap对象,因此一般图片占用内存推荐大小应该不超过8M.

算法在社区氛围的应用(三): 机器学习在答非所问识别上的运用

- - 知乎每日精选
现在,瓦力可直接识别并处理该题中的答非所问内容. 我们鼓励认真、专业的分享,期待每一次讨论都能碰撞出更多有价值的信息,并希望每一个用心的回答都能够得到好的展示,为他人带来更多帮助. 但是,我们也发现在社区中出现了答非所问类的内容,影响知友们获取有价值内容的效率. 为了更好地识别答非所问类内容,我们采用了多种模型,包括传统的机器学习模型和比较新的深度学习模型.