模擬退火算法

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

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

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

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

用newPop取代Pop}until(任何染色體得分超過Tf,或繁殖代數(shù)超過G)基本遺傳算法優(yōu)化下面的方法可優(yōu)化遺傳算法的性能。精英主義(ElitistStrategy)選擇：是基本遺傳算法的一種優(yōu)化。為了防止進化過程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封不動的復制到下一代中。插入操作：可在3個基本操作的基礎上增加一個插入操作。插入操作將染色體中的某個隨機的片段移位到另一個隨機的位置。五-使用AForge.Genetic解決TSP問題AForge.NET是一個C#實現(xiàn)的面向人工智能、計算機視覺等領域的開源架構。AForge.NET中包含有一個遺傳算法的類庫。AForge.NET主頁：/AForge.NET代碼下載：http://code.google.Com/p/aforge/介紹一下AForge的遺傳算法用法吧。AForge.Genetic的類結構如下: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寫個解決TSP問題的最簡單實例。測試數(shù)據(jù)集采用網(wǎng)上流傳的中國31個省會城市的坐標：13042312363913154177224437121399348815353326155632381229419610044312790438657030071970256217562788149123811676133269537151678391821794061237037802212367625784029283842632931342919083507236733942643343932012935324031403550254523572778282623702975操作過程：下載AForge.NET類庫，網(wǎng)址：http://code.google.eom/p/aforge/downloads/list創(chuàng)建C#空項目GenticTSPo然后在AForge目錄下找到AForge.dll和AForge.Genetic.dll，將其拷貝到TestTSP項目的bin/Debug目錄下。再通過“AddReference..."將這兩個DLL添加到工程。將31個城市坐標數(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]);//讀取城市坐標map[i,1]=int.Parse(temp[1]);}//createfitnessfunctionTSPFitnessFunctionfitnessFunction=newTSPFitnessFunction(map);intpopulationSize=1000;//種群最大規(guī)模/*0：EliteSelection算法1：RankSe