模擬退火算法

.爬山算法(HillClimbing)介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。爬山算法實(shí)現(xiàn)很簡單，其主要缺點(diǎn)是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1所示：假設(shè)C點(diǎn)為當(dāng)前解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會停止搜索，因?yàn)樵贏點(diǎn)無論向那個(gè)方向小幅度移動都不能得到更優(yōu)的解。圖1二.模擬退火(SA,SimulatedAnnealing)思想爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會以一定的概率接受到E的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。模擬退火算法描述：若J(Y(i+1))>=J(Y(i))(即移動后得到更優(yōu)解)，則總是接受該移動若J(Y(i+1))<J(Y(i))(即移動后的解比當(dāng)前解要差)，則以一定的概率接

受移動，而且這個(gè)概率隨著時(shí)間推移逐漸降低(逐漸降低才能趨向穩(wěn)定)這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。根據(jù)熱力學(xué)的原理，在溫度為T時(shí)，出現(xiàn)能量差為dE的降溫的概率為P(dE)，表示為：P(dE)=exp(dE/(kT))其中k是一個(gè)常數(shù)，exp表示自然指數(shù)，且dE<0。這條公式說白了就是：溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE總是小于0(否則就不叫退火了)，因此dE/kT<0，所以P(dE)的函數(shù)取值范圍是(0,1)。隨著溫度T的降低，P(dE)會逐漸降低。我們將一次向較差解的移動看做一次溫度跳變過程，我們以概率P(dE)來接受這樣的移動。關(guān)于爬山算法與模擬退火，有一個(gè)有趣的比喻：爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠(yuǎn)處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。模擬退火：兔子喝醉了。它隨機(jī)地跳了很長時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。下面給出模擬退火的偽代碼表示。模擬退火算法偽代碼國日代碼/*J(y)：在狀態(tài)y時(shí)的評價(jià)函數(shù)值Y(i)：表示當(dāng)前狀態(tài)Y(i+1)：表示新的狀態(tài)r：用于控制降溫的快慢T：系統(tǒng)的溫度，系統(tǒng)初始應(yīng)該要處于一個(gè)高溫的狀態(tài)T_min:溫度的下限，若溫度T達(dá)到T_min，則停止搜索*/while(T>T_min)(dE=J(Y(i+1))-J(Y(i));if(dE>=0)//表達(dá)移動后得到更優(yōu)解，則總是接受移動Y(i+1)=Y(i);//接受從Y(i)到Y(jié)(i+1)的移動else(//函數(shù)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(jié)(i+1)的移動}T=r*T;//降溫退火，0<r<1。r越大，降溫越慢；r越小，降溫越快/**若r過大，則搜索到全局最優(yōu)解的可能會較高，但搜索的過程也就較長。若r過小，則搜索的過程會很快，但最終可能會達(dá)到一個(gè)局部最優(yōu)值*/i++;}使用模擬退火算法解決旅行商問題旅行商問題(TSP,TravelingSalesmanProblem):有N個(gè)城市，要求從其中某個(gè)問題出發(fā)，唯一遍歷所有城市，再回到出發(fā)的城市，求最短的路線。旅行商問題屬于所謂的NP完全問題，精確的解決TSP只能通過窮舉所有的路徑組合，其時(shí)間復(fù)雜度是O(N!)。使用模擬退火算法可以比較快的求出TSP的一條近似最優(yōu)路徑。(使用遺傳算法也是可以的，我將在下一篇文章中介紹)模擬退火解決TSP的思路：產(chǎn)生一條新的遍歷路徑P(i+1)，計(jì)算路徑P(i+1)的長度L(P(i+1))若L(P(i+1))<L(P(i))，則接受P(i+1)為新的路徑，否則以模擬退火的那個(gè)概率接受P(i+1)，然后降溫重復(fù)步驟1，2直到滿足退出條件產(chǎn)生新的遍歷路徑的方法有很多，下面列舉其中3種：隨機(jī)選擇2個(gè)節(jié)點(diǎn)，交換路徑中的這2個(gè)節(jié)點(diǎn)的順序。隨機(jī)選擇2個(gè)節(jié)點(diǎn)，將路徑中這2個(gè)節(jié)點(diǎn)間的節(jié)點(diǎn)順序逆轉(zhuǎn)。隨機(jī)選擇3個(gè)節(jié)點(diǎn)m，n，k，然后將節(jié)點(diǎn)m與n間的節(jié)點(diǎn)移位到節(jié)點(diǎn)k后面。算法評價(jià)模擬退火算法是一種隨機(jī)算法，并不一定能找到全局的最優(yōu)解，可以比較快的找到問題的近似最優(yōu)解。如果參數(shù)設(shè)置得當(dāng)，模擬退火算法搜索效率比窮舉法要高。Alice和她的同學(xué)Bob通過網(wǎng)上聊天商量明天早晨誰去教室打掃衛(wèi)生的事，Bob說：“我在桌上放了一枚硬幣，你猜一下，是正面朝上還是反面朝上？如果猜對了，我去掃地。如果猜錯(cuò)了，嘿嘿…?！盇lice顯然不會同意，擔(dān)心自己不論猜正面還是反面，Bob都說她錯(cuò)了。分析：看到這題，我的第一反應(yīng)是葛優(yōu)的“分歧終端機(jī)”。(/▽?最關(guān)鍵是要找到一種方法使得Alice給出她的猜測后Bob不能抵賴。一種參考答案如下：Bob與Alice商量選取一個(gè)哈希函數(shù)hash()，hash()的值域應(yīng)該盡可能大。Bob選擇一個(gè)大隨機(jī)數(shù)x，計(jì)算hash(x)；通過網(wǎng)絡(luò)告訴Alicehash(x)的值A(chǔ)lice告訴Bob對x的奇偶性猜測(偶數(shù)表示“正面”；奇數(shù)代表“背面”)Bob告訴Alicex的值A(chǔ)lice驗(yàn)證hash(x)但是這樣也不是100%能夠防止Bob作弊的。Bob如果想抵賴，那么他應(yīng)該事先找出兩個(gè)大整數(shù)，一奇一偶，而且哈希函數(shù)值相同。(抵賴的難度就取決于hash函數(shù)的選擇了)第2題Alice與Bob相愛了，他們想通過書信來商量私奔的事。暗戀Alice的郵遞員Chuck經(jīng)常利用職權(quán)之便偷看他們之間的通信。Alice與Bob各有一把鎖和只能打開自己那把鎖的鑰匙。另外Bob還有一個(gè)能夠上鎖的鐵盒子。問如何防止Chunk偷看他們之間的通信？分析：Bob將情書放進(jìn)鐵盒，用自己的鎖給盒子上鎖。Alice收到后給盒子加上自己的鎖，然后將盒子寄回給Bob。Bob收到后將自己的鎖取下，再將盒子寄給Alice。Alice收到盒子后取下自己的鎖就可以看信了。第3題某人第一天由A地去B地，第二天由B地沿原路返回A地。問：在什么條件下，可以保證途中至少存在一地，此人在兩天中的同一時(shí)間到達(dá)該地。分析：假如我們換一種想法，把第二天的返回改變成另一人在同一天由B去A，問題就化為在什么條件下，兩人至少在途中相遇一次，這樣結(jié)論就很容易得出了：只要其中一個(gè)人在另外一個(gè)人到達(dá)之前出發(fā)，則兩人必會在途中相遇。第4題一條長度為L的竹竿上分布著N個(gè)螞蟻，已知所有螞蟻的行進(jìn)速度都是v，兩只螞蟻碰頭后會掉頭走，給定初始時(shí)刻螞蟻的行進(jìn)方向。問如何計(jì)算所有螞蟻離開竹竿要多長時(shí)間？分析：最直接也是最笨的方法就是對每個(gè)螞蟻的行動進(jìn)行模擬。這樣誰都能想到的答案當(dāng)然不是出題者想要的了。換個(gè)角度想，2個(gè)螞蟻碰頭后掉頭走實(shí)質(zhì)上是等價(jià)于它們碰頭后擦肩而過繼續(xù)趕路。（如果你將所有螞蟻都看作一樣的話）好了，這樣一想，過程簡單多了。對于每個(gè)螞蟻，都假設(shè)竹竿上只有它一個(gè)螞蟻，然后計(jì)算出它離開竹竿的時(shí)間。所需時(shí)間最長的螞蟻所耗的時(shí)間就是題目的答案了。第5題一對情侶一起去買了一塊餅女生吃了3/7塊餅?zāi)猩缘羰Ｏ碌?/7塊餅?zāi)猩扰喑隽?.5元請問這塊餅多少元？分析：4.5元（有回答31.5的么？舉個(gè)手？）遺傳算法(GA,GeneticAlgorithm)，也稱進(jìn)化算法。遺傳算法是受達(dá)爾文的進(jìn)化論的啟發(fā)，借鑒生物進(jìn)化過程而提出的一種啟發(fā)式搜索算法。因此在介紹遺傳算法前有必要簡單的介紹生物進(jìn)化知識。進(jìn)化論知識作為遺傳算法生物背景的介紹，下面內(nèi)容了解即可：種群(Population)：生物的進(jìn)化以群體的形式進(jìn)行，這樣的一個(gè)群體稱為種群。個(gè)體：組成種群的單個(gè)生物。基因(Gene)：一個(gè)遺傳因子。染色體(Chromosome):包含一組的基因。生存競爭，適者生存：對環(huán)境適應(yīng)度高的、牛B的個(gè)體參與繁殖的機(jī)會比較多，后代就會越來越多。適應(yīng)度低的個(gè)體參與繁殖的機(jī)會比較少，后代就會越來越少。遺傳與變異：新個(gè)體會遺傳父母雙方各一部分的基因，同時(shí)有一定的概率發(fā)生基因變異。簡單說來就是：繁殖過程，會發(fā)生基因交叉(Crossover)，基因突變(Mutation)，適應(yīng)度(Fitness)低的個(gè)體會被逐步淘汰，而適應(yīng)度高的個(gè)體會越來越多。那么經(jīng)過N代的自然選擇后，保存下來的個(gè)體都是適應(yīng)度很高的，其中很可能包含史上產(chǎn)生的適應(yīng)度最高的那個(gè)個(gè)體。遺傳算法思想借鑒生物進(jìn)化論，遺傳算法將要解決的問題模擬成一個(gè)生物進(jìn)化的過程，通過復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解。這樣進(jìn)化N代后就很有可能會進(jìn)化出適應(yīng)度函數(shù)值很高的個(gè)體。舉個(gè)例子，使用遺傳算法解決“0-1背包問題”的思路：0-1背包的解可以編碼為一串0-1字符串(0：不取，1：取)；首先，隨機(jī)產(chǎn)生M個(gè)0-1字符串，然后評價(jià)這些0-1字符串作為0-1背包問題的解的優(yōu)劣；然后，隨機(jī)選擇一些字符串通過交叉、突變等操作產(chǎn)生下一代的M個(gè)字符串，而且較優(yōu)的解被選中的概率要比較高。這樣經(jīng)過G代的進(jìn)化后就可能會產(chǎn)生出0-1背包問題的一個(gè)“近似最優(yōu)解”。編碼：需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進(jìn)制編碼，即將問題的解編碼成二進(jìn)制位數(shù)組的形式。例如，問題的解是整數(shù)，那么可以將其編碼成二進(jìn)制位數(shù)組的形式。將0-1字符串作為0-1背包問題的解就屬于二進(jìn)制編碼。

遺傳算法有3個(gè)最基本的操作：選擇，交叉，變異。選擇：選擇一些染色體來產(chǎn)生下一代。一種常用的選擇策略是“比例選擇”，也就是個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。假設(shè)群體的個(gè)體總數(shù)是M，那么那么一個(gè)體Xi被選中的概率為f(Xi)/(f(X1)+f(X2)+ +f(Xn))。比例選擇實(shí)現(xiàn)算法就是所謂的“輪盤賭算法”(RouletteWheelSelection)，輪盤賭算法的一個(gè)簡單的實(shí)現(xiàn)如下：國日輪盤賭算法/**按設(shè)定的概率，隨機(jī)選中一個(gè)個(gè)體*P[i]表示第i個(gè)個(gè)體被選中的概率*/intRWS()(m=0;r=Random(0,1);//r為。至1的隨機(jī)數(shù)for(i=1;i<=N;i++)(/*產(chǎn)生的隨機(jī)數(shù)在m~m+P[i]間則認(rèn)為選中了i*因此i被選中的概率是P[i]*/m=m+P[i];if(r<=m)returni;}}交叉(Crossover)：2條染色體交換部分基因，來構(gòu)造下一代的2條新的染色體。例如：交叉前：00000|o11100000000|1OOOO11100|000001111110|00101交叉后：00000|000001111110|1000011100IO11100000000I00101染色體交叉是以一定的概率發(fā)生的，這個(gè)概率記為Pc。變異(Mutation)：在繁殖過程，新產(chǎn)生的染色體中的基因會以一定的概率出錯(cuò)，稱為變異。變異發(fā)生的概率記為Pm。例如：變異前：

000001110000000010000變異后：000001110000100010000適應(yīng)度函數(shù)(FitnessFunction):用于評價(jià)某個(gè)染色體的適應(yīng)度，用f(x)表示。有時(shí)需要區(qū)分染色體的適應(yīng)度函數(shù)與問題的目標(biāo)函數(shù)。例如：0-1背包問題的目標(biāo)函數(shù)是所取得物品價(jià)值，但將物品價(jià)值作為染色體的適應(yīng)度函數(shù)可能并不一定適合。適應(yīng)度函數(shù)與目標(biāo)函數(shù)是正相關(guān)的，可對目標(biāo)函數(shù)作一些變形來得到適應(yīng)度函數(shù)?；具z傳算法的偽代碼國日基本遺傳算法偽代碼/*Pc：交叉發(fā)生的概率Pm：變異發(fā)生的概率M：種群規(guī)模G：終止進(jìn)化的代數(shù)Tf：進(jìn)化產(chǎn)生的任何一個(gè)個(gè)體的適應(yīng)度函數(shù)超過Tf，則可以終止進(jìn)化過程*/初始化Pm，Pc，M，G，Tf等參數(shù)。隨機(jī)產(chǎn)生第一代種群Popdo(計(jì)算種群Pop中每一個(gè)體的適應(yīng)度F(i)。初始化空種群newPopdo(根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個(gè)個(gè)體if(random(0,1)<Pc)(對2個(gè)個(gè)體按交叉概率Pc執(zhí)行交叉操作}if(random(0,1)<Pm)(對2個(gè)個(gè)體按變異概率Pm執(zhí)行變異操作}將2個(gè)新個(gè)體加入種群newPop中}until(M個(gè)子代被創(chuàng)建)

用newPop取代Pop}until(任何染色體得分超過Tf,或繁殖代數(shù)超過G)基本遺傳算法優(yōu)化下面的方法可優(yōu)化遺傳算法的性能。精英主義(ElitistStrategy)選擇：是基本遺傳算法的一種優(yōu)化。為了防止進(jìn)化過程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封不動的復(fù)制到下一代中。插入操作：可在3個(gè)基本操作的基礎(chǔ)上增加一個(gè)插入操作。插入操作將染色體中的某個(gè)隨機(jī)的片段移位到另一個(gè)隨機(jī)的位置。五-使用AForge.Genetic解決TSP問題AForge.NET是一個(gè)C#實(shí)現(xiàn)的面向人工智能、計(jì)算機(jī)視覺等領(lǐng)域的開源架構(gòu)。AForge.NET中包含有一個(gè)遺傳算法的類庫。AForge.NET主頁：/AForge.NET代碼下載：http://code.google.Com/p/aforge/介紹一下AForge的遺傳算法用法吧。AForge.Genetic的類結(jié)構(gòu)如下:OptimizationFunctionlDOptimiza.tionFunction2DSymbolicRegressianFitnessTimeSeriesPredictwnFitness<<inlcrface?IFitncssFunction<<inierftice>>ISelectionMethod<<interffice>>IGPGcneEliteSelectionRuuI[?ttcWheelSelectionSimplcGcncFunctionBinaryChromosomeGEPChromosomcGHTreeChromosoroe<<inteifacc>?IChrotnosomcExtendedGeneFunctiOptimizationFunctionlDOptimiza.tionFunction2DSymbolicRegressianFitnessTimeSeriesPredictwnFitness<<inlcrface?IFitncssFunction<<inierftice>>ISelectionMethod<<interffice>>IGPGcneEliteSelectionRuuI[?ttcWheelSelectionSimplcGcncFunctionBinaryChromosomeGEPChromosomcGHTreeChromosoroe<<inteifacc>?IChrotnosomcExtendedGeneFunctionShortArrayChromosome圖1.AForge.Genetic的類圖下面用AForge.Genetic寫個(gè)解決TSP問題的最簡單實(shí)例。測試數(shù)據(jù)集采用網(wǎng)上流傳的中國31個(gè)省會城市的坐標(biāo)：13042312363913154177224437121399348815353326155632381229419610044312790438657030071970256217562788149123811676133269537151678391821794061237037802212367625784029283842632931342919083507236733942643343932012935324031403550254523572778282623702975操作過程：下載AForge.NET類庫，網(wǎng)址：http://code.google.eom/p/aforge/downloads/list創(chuàng)建C#空項(xiàng)目GenticTSPo然后在AForge目錄下找到AForge.dll和AForge.Genetic.dll，將其拷貝到TestTSP項(xiàng)目的bin/Debug目錄下。再通過“AddReference..."將這兩個(gè)DLL添加到工程。將31個(gè)城市坐標(biāo)數(shù)據(jù)保存為bin/Debug/Data.txt。添加TSPFitnessFunction.cs，加入如下代碼：

TSPFitnessFunction類usingSystem;usingAForge.Genetic;namespaceGenticTSP(///<summary>///FitnessfunctionforTSPtask(TravalingSalasmanProblem)///</summary>publicclassTSPFitnessFunction:IFitnessFunction(//mapprivateint[,]map=null;//ConstructorpublicTSPFitnessFunction(int[,]map)(this.map=map;}///<summary>///Evaluatechromosome-calculatesitsfitnessvalue///</summary>publicdoubleEvaluate(IChromosomechromosome)(return1/(PathLength(chromosome)+1);}///<summary>///Translategenotypetophenotype///</summary>publicobjectTranslate(IChromosomechromosome)(returnchromosome.ToString();}///<summary>///Calculatepathlengthrepresentedbythespecifiedchromosome///</summary>publicdoublePathLength(IChromosomechromosome)(//salesmanpathushort[]path=((PermutationChromosome)chromosome).Value;

//checkpathsizeif(path.Length!=map.GetLength(0))(thrownewArgumentException("Invalidpathspecified-notallcitiesarevisited");}//pathlengthintprev=path[0];intcurr=path[path.Length-1];//calculatedistancebetweenthelastandthefirstcitydoubledx=map[curr,0]-map[prev,0];doubledy=map[curr,1]-map[prev,1];doublepathLength=Math.Sqrt(dx*dx+dy*dy);//calculatethepathlengthfromthefirstcitytothelastfor(inti=1,n=path.Length;i<n;i++)(//getcurrentcitycurr=path[i];//calculatedistancedx=map[curr,0]-map[prev,0];dy=map[curr,1]-map[prev,1];pathLength+=Math.Sqrt(dx*dx+dy*dy);//putcurrentcityaspreviousprev=curr;}returnpathLength;}}}(5)添加GenticTSP.cs，加入如下代碼:田日GenticTSP類usingSystem;

usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.IO;usingAForge;usingAForge.Genetic;namespaceGenticTSP(classGenticTSP(staticvoidMain()(StreamReaderreader=newStreamReader("Data.txt");intcitiesCount=31;//城市數(shù)int[,]map=newint[citiesCount,2];for(inti=0;i<citiesCount;i++)(stringvalue=reader.ReadLine();string[]temp=value.Split('');map[i,0]=int.Parse(temp[0]);//讀取城市坐標(biāo)map[i,1]=int.Parse(temp[1]);}//createfitnessfunctionTSPFitnessFunctionfitnessFunction=newTSPFitnessFunction(map);intpopulationSize=1000;//種群最大規(guī)模/*0：EliteSelection算法1：RankSe