《模拟退火算法》由会员分享，可在线阅读，更多相关《模拟退火算法（18页珍藏版）》请在金锄头文库上搜索。
1、一.爬山算法(Hill Climbing )介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法， 该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个 局部最优解。爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到 全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最 优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的 解。图1二.模拟退火(SA,Simulated Annealing)思想爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此 只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，
2、但是它的搜索过程 引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因 此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火 算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几 次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。模拟退火算法描述：若J( Y(i + 1) )= J( Y(i)(即移动后得到更优解)，则总是接受该移动 若J( Y(i + 1) ) T_min )dE= J( Y(i+1)- J( Y(i);if ( dE= 0 )/表达移动后得到更优解，则总是接受移动Y(i + 1)= Y(i) ;/接受从 Y
3、(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 ;/降温退火，0r1。r越大，降温越慢；r越小，降温越快/*若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程 会很快，但最终可能会达到一个局部最优值*/i+ ;四. 使用模拟退火算法解决旅行商问题旅行商问题(TSP , Traveling Salesman Problem ):有
4、N 个城市，要 求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。旅行商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有 的路径组合，其时间复杂度是0(N!)。使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。(使用遗传 算法也是可以的，我将在下一篇文章中介绍)模拟退火解决TSP的思路：1. 产生一条新的遍历路径P(i + 1)，计算路径P(i + 1)的长度L( P(i + 1)2. 若L(P(i+1) L(P(i)，贝U接受P(i + 1)为新的路径，否则以模拟退火的那 个概率接受P(i+1)，然后降温3. 重复步骤1, 2直到满足退出条件产生新的
5、遍历路径的方法有很多，下面列举其中3种：1. 随机选择2个节点，交换路径中的这2个节点的顺序。2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。3. 随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后 面。五. 算法评价模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快 的找到问题的近似最优解。如果参数设置得当，模拟退火算法搜索效率比穷举 法要咼。Alice和她的同学Bob通过网上聊天商量明天早晨谁去教室打扫卫生的事， Bob说：“我在桌上放了一枚硬币，你猜一下，是正面朝上还是反面朝上？如果 猜对了，我去扫地。如果猜错了，嘿嘿。”Alice显然不会同意
6、，担心自己不论猜正面还是反面，Bob都说她错了。分析：看到这题，我的第一反应是葛优的“分歧终端机”。(丿最关键是要找到一种方法使得Alice给出她的猜测后Bob不能抵赖。一种参考 答案如下：1. Bob与Alice商量选取一个哈希函数hash(), hash()的值域应该尽可能大。2. Bob选择一个大随机数x,计算hash(x)；通过网络告诉Alice hash(x)的 值3. Alice告诉Bob对x的奇偶性猜测(偶数表示“正面”；奇数代表“背面”)4. Bob告诉Alice x的值5. Alice 验证 hash(x)但是这样也不是100%能够防止Bob作弊的。Bob如果想抵赖，那么他应
7、该事 先找出两个大整数，一奇一偶,而且哈希函数值相同。(抵赖的难度就取决于hash 函数的选择了)第2题Alice与Bob相爱了，他们想通过书信来商量私奔的事。暗恋Alice的 邮递员Chuck经常利用职权之便偷看他们之间的通信。Alice与Bob各有一把 锁和只能打开自己那把锁的钥匙。另外Bob还有一个能够上锁的铁盒子。问如 何防止Chunk偷看他们之间的通信？分析：Bob将情书放进铁盒，用自己的锁给盒子上锁。Alice收到后给盒子加 上自己的锁，然后将盒子寄回给Bob。Bob收到后将自己的锁取下，再将盒子 寄给Alice。Alice收到盒子后取下自己的锁就可以看信了。第3题某人第一天由A地
8、去B地，第二天由B地沿原路返回A地。问：在什么条件 下，可以保证途中至少存在一地，此人在两天中的同一时间到达该地。分析：假如我们换一种想法，把第二天的返回改变成另一人在同一天由B去A,问题 就化为在什么条件下，两人至少在途中相遇一次，这样结论就很容易得出了：只 要其中一个人在另外一个人到达之前出发，则两人必会在途中相遇。第4题一条长度为L的竹竿上分布着N个蚂蚁，已知所有蚂蚁的行进速度都是 V,两只蚂蚁碰头后会掉头走，给定初始时刻蚂蚁的行进方向。问如何计算所有 蚂蚁离开竹竿要多长时间？分析：最直接也是最笨的方法就是对每个蚂蚁的行动进行模拟。这样谁都能想 到的答案当然不是出题者想要的了。换个角度想
9、，2个蚂蚁碰头后掉头走实质上是等价于它们碰头后擦肩而 过继续赶路。（如果你将所有蚂蚁都看作一样的话）好了，这样一想，过程简单多了。对于每个蚂蚁，都假设竹竿上只有它 一个蚂蚁，然后计算出它离开竹竿的时间。所需时间最长的蚂蚁所耗的时间就是 题目的答案了。第5题一对情侣一起去买了一块饼女生吃了 3/7块饼男生吃掉剩下的4/7块饼男生比女生多出了 4.5元请问这块饼多少元？分析：4.5元（有回答31.5的么？举个手？）遗传算法(GA , Genetic Algorithm )，也称进化算法。遗传算法是受 达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此 在介绍遗传算法前有必要简单
10、的介绍生物进化知识。一进化论知识作为遗传算法生物背景的介绍，下面内容了解即可：种群(Population)：生物的进化以群体的形式进行，这样的一个群体称 为种群。个体：组成种群的单个生物。基因(Gene )： 一个遗传因子。染色体(Chromosome ):包含一组的基因。生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比 较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越 来越少。遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发 生基因变异。简单说来就是：繁殖过程，会发生基因交叉(Crossover )，基因突变 (Mutation )，适
11、应度(Fitness )低的个体会被逐步淘汰，而适应度高的个体 会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的, 其中很可能包含史上产生的适应度最高的那个个体。二遗传算法思想借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通 过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解, 增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值 很高的个体。举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编 码为一串0-1字符串(0：不取，1：取)；首先，随机产生M个0-1字符串， 然后评价这些0-1字符串作为0
12、-1背包问题的解的优劣；然后，随机选择一些字 符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的 概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近 似最优解”。编码：需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一 种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。例如，问 题的解是整数，那么可以将其编码成二进制位数组的形式。将0-1字符串作为0-1 背包问题的解就属于二进制编码。遗传算法有3个最基本的操作：选择，交叉，变异。选择：选择一些染色体来产生下一代。一种常用的选择策略是“比例选择”, 也就是个体被选中的概率与其适应度函
13、数值成正比。假设群体的个体总数是M， 那么那么一个体 Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + +f(Xn)。比例选择实现算法就是所谓的“轮盘赌算法”(Roulette Wheel Selection )，轮盘赌算法的一个简单的实现如下：田日轮盘赌算法/*按设定的概率，随机选中一个个体* Pi表示第i个个体被选中的概率*/int RWS()m= 0;r=Random(0,1); /r 为0至 1 的随机数for(i=1;i=N; i+)/*产生的随机数在mm+Pi间则认为选中了 i *因此i被选中的概率是Pi*/m= m+ Pi;if(r=m)return i;交叉(Crossover)： 2条染色体交换部分基因，来构造下一代的2条新的染色体。 例如： 交叉前：OOOOO|oiiioooooooo|1OOOO11100|00000111111
