數(shù)學(xué)建?，F(xiàn)代優(yōu)化算法遺傳算法

1、數(shù)學(xué)建模現(xiàn)代優(yōu)化算法遺傳算法一般的優(yōu)化具有下面形式：minf (x1, x2, , xn)s.t. g(x) 0，xD其中x1, x2, , xn（即問題的可行域，代表問題參數(shù)的選擇范圍），即minf (X)，其中X（矢量形式）。f(x)是決策問題的數(shù)學(xué)模型，也是決策問題的目標函數(shù)目標函數(shù)，g(x) 0是決策問題的約束條件約束條件，D是決策問題的定義域（可行域可行域）。注：注：求問題的最大和最小是同一個問題，算法完全一樣。習慣上，將優(yōu)化算法分為兩類：局部優(yōu)化算局部優(yōu)化算法法和全局性優(yōu)化算法全局性優(yōu)化算法。前者可以稱為經(jīng)典優(yōu)經(jīng)典優(yōu)化算法化算法，已經(jīng)得到了人們廣泛深入的研究。線性規(guī)劃、整數(shù)規(guī)劃、0

2、1規(guī)劃、非線性規(guī)劃、排隊論、決策論。后者習慣上稱為現(xiàn)代優(yōu)化現(xiàn)代優(yōu)化算法算法，是20世紀80年代興起的新型全局性優(yōu)化算法，主要包括禁忌搜索禁忌搜索、模擬退火模擬退火、遺傳算法、神經(jīng)網(wǎng)絡(luò)等，其主要應(yīng)用對象是優(yōu)化問題中的難解問題難解問題，即NPhard問題 算法比喻 為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。 方案一：兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機落到了地球上的某些地方。他們不知道自己的使命是什么。但是，如果你過幾年就殺死一部分海拔低的兔子，多產(chǎn)的兔子們自己就會找到珠穆朗瑪峰。遺傳算法 方案二：兔子們朝著比現(xiàn)在高的地方跳去，它們找到了不遠處的最高山峰。但是這座山不一定是珠穆

3、朗瑪峰。其實，它們這種做法只是自己心理上認為找到了最高的山，并不能保證局部最優(yōu)值就是全局最優(yōu)值。局部搜索法 方案三：兔子們知道一個兔子的力量是渺小的。于是，它們互相轉(zhuǎn)告著，哪里的山已經(jīng)找過，并且找過的每一座山他們都留下一只兔子做記號。這樣，它們制定了下一步去哪里尋找的策略。禁忌搜索法 方案四：兔子們用酒將自己灌醉了。它們隨機地跳了很長時間。在這期間，它們可能走向高處，也可能踏入平地。但是，隨著時間的流逝，它們漸漸清醒了并朝最高方向跳去。模擬退火法 一一 遺傳算法遺傳算法遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學(xué)的Holland教

4、授提出，起源于60年代對自然和人工自適應(yīng)系統(tǒng)的研究。70年代De. Jong 基于遺傳算法的思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗。在一系列研究工作的基礎(chǔ)上。80年代由Goldberg進行總結(jié)，形成了遺傳算法的基本框架。一一 遺傳算法遺傳算法其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它的應(yīng)用范圍非常廣泛，尤其適合于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化，機器學(xué)習，自適應(yīng)控制，規(guī)劃設(shè)計和人工生命等領(lǐng)域，從而確立了它在21世紀的智能計算技術(shù)中的關(guān)鍵地位。 1 遺傳算法的基本步驟 遺傳算法流程圖如下：集團中個體適應(yīng)度的檢測評估選擇交叉

5、變異圖1 遺傳算法的基本流程編碼和初始集團生成一、編碼一、編碼 遺傳算法主要是通過遺傳操作對群體中具有某種結(jié)構(gòu)形式的個體施加結(jié)重組處理，從而不斷地搜索出群體中個體間結(jié)構(gòu)相似性，由此可見，遺傳算法不能直接處理問題空間參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個體。這一轉(zhuǎn)換操作就叫做編碼。編碼方法主要有：二進制編碼，Gray編碼，動態(tài)編碼，實數(shù)編碼，有序串編碼，多參數(shù)編碼，可變長編碼等。 （一）一維染色體編碼（二值編碼） 所謂一維染色體編碼是指搜索空間的參數(shù)轉(zhuǎn)換到遺傳空間過后，其相應(yīng)的基因呈一維排列構(gòu)成的染色體。具體地說，在遺傳空間中，用以表示個體的字符集中的要素構(gòu)成了字符串。

6、如a,b,c,d或1,2,3,4。 一維染色體編碼中最常用的符號集是二進制符號0,1，基于此符號集的個體呈二值碼串。二值編碼的一般方法是： (1)根據(jù)所需要的精度確定參數(shù)的串長； (2)解碼，由二值串轉(zhuǎn)化成實數(shù)； 例如：x=13,可被表示為01101。（二）多映射編碼（多參數(shù)） 在優(yōu)化問題求解中常常會遇見多參數(shù)優(yōu)化問題。其基本思路是將每一個參數(shù)進行二值編碼得到子串，每個子串對應(yīng)各自的編碼參數(shù)，然后將子串構(gòu)成一個完整的染色體串。 二、二、 初始群體的生成初始群體的生成 遺傳操作是對于多個體同時進行的。這眾多的個體組成了群體。在遺傳算法處理流程中，繼編碼設(shè)計后的任務(wù)是初始群體的設(shè)定，并以此為起點一

7、代代進化直到按某種進化停止準則終止進化過程，由此得到最后一代（或群體）。其中需要考慮到兩個因素：初始群體的設(shè)定；進化過程中各代（群體）的規(guī)模如何維持？它和交叉概率變異概率等參數(shù)一樣，對于遺傳算法效能的發(fā)揮是有影響的。初始群體的設(shè)定可采取如下策略： (1) 根據(jù)問題固有的知識，設(shè)法確定最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。 (2) 先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體當中去。這種過程不斷迭代，直到初始群體中個數(shù)達到了預(yù)先確定的規(guī)模。 三、適應(yīng)度函數(shù)三、適應(yīng)度函數(shù) 適應(yīng)度函數(shù)表明個體或解的優(yōu)劣性。不同的問題，適應(yīng)性函數(shù)的定義方式也不同。

8、這一操作是借用了達爾文的自然選擇原則，即個體適應(yīng)度越高，其被選擇的個體越多。 遺傳算法在進化搜索中基本上不用外部信息，僅用目標函數(shù)即適應(yīng)度函數(shù)為依據(jù)。遺傳函數(shù)的目標函數(shù)不受連續(xù)可微的約束且定義域可以為任意組合。對目標函數(shù)的唯一要求是，針對輸入可計算出能加以比較的非負結(jié)果，這一特點使得遺傳算法運用很廣。在具體的應(yīng)用中適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而定，要強調(diào)的是，適應(yīng)度函數(shù)評估是選擇操作的依據(jù)，適應(yīng)度函數(shù)的設(shè)計直接影響到遺傳算法的性能。目標函數(shù)映射成適應(yīng)度函數(shù) 在許多問題求解中，其目標函數(shù)是求取費用函數(shù)（代價函數(shù)）g（x）的最小值，而不是求效能函數(shù)或者利潤函數(shù)的最大值。由于遺傳算法中，

9、適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。由此可見，在不少場合，將目標函數(shù)映射成最大值形式且函數(shù)值非負的適應(yīng)度函數(shù)是很有必要的。在通常情況下，要把一個最小化函數(shù)轉(zhuǎn)化為最大化問題，只需要簡單的把費用函數(shù)乘以-1，即以下兩種基本方法：（1）如目標函數(shù)為最大化問題：（2）如目標函數(shù)為最小化問題： 但這對遺傳算法而言，這種方法還不足以保證在各種情況下的非負值。對此可以采用以下的方法進行轉(zhuǎn)換：（3） 其中 可以采用目前g(x)出現(xiàn)過的最大值或者當前群體當中出現(xiàn)過的最大值，但最好與群體無關(guān)。maxmax( ),( )( )0,Cg xg xCf x當其他情況maxC( (

10、)( )Fit f xf x( ( )( )Fit f xf x 當求解問題的目標函數(shù)采用利潤函數(shù)形式時，為了保證其非負性，可用如下變換式： （4） 式中系數(shù) 可以式適合的輸入值，或是當前一代或者前面幾代中的g（x）的最小值，也可以是群體的方差。 第三、四兩種方法是對第一、二兩種方法的改進，但有時存在界限值預(yù)先估計困難，不可能精確的問題，為此有下面兩種改進的方法：minmin,0( )0,CCf xu(x)當u(x)+其他情況minC(5) 若目標函數(shù)為最小問題: (6) 若目標函數(shù)為最大問題： 1( ( )1( )Fit f xcf x 0,( ) 0cc f x1( ( )1( )Fit

11、f xcf x 0,( ) 0cc f x 四、遺傳操作四、遺傳操作 遺傳操作是模擬生物基因遺傳的操作。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個體按照他們對環(huán)境適應(yīng)的程度（適應(yīng)度評估）施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程，從優(yōu)化搜索的角度而言，遺傳操作可以使問題的解，一代又一代地優(yōu)化，并逼近最優(yōu)解。遺傳算法的基本操作包括以下三個基本算子：選擇，交叉,變異。 （一）選擇（一）選擇：選擇的目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。進行選擇的原則是適應(yīng)性強的個體為下一代貢獻一個或多個后代的概率大。以下介紹目前幾種常用的選擇算子：（1）

12、適應(yīng)度比例方法(fitness proportional model) 適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法，他也叫賭輪或蒙特卡羅（monte carlo）選擇。該方法中各個個體的選擇概率和其適應(yīng)度成比例。其描述如下：設(shè)群體的大小為n，其中個體i的適應(yīng)度值為 ,則i被選擇的概率為 顯然，概率 反映個體i的適應(yīng)度在總和中所占的比例，個體的適應(yīng)度越大，其被選擇的概率就越高，反之亦然，計算出群體中各個個體的選擇概率后，就可以決定那些個體可以被選出。if1niijjpffip（2）最佳個體保存方法（elitise model） 該方法的思想是把群體中適應(yīng)度最高的個體不進行配對而直接

13、復(fù)制到下一代中，此種選擇操作又稱復(fù)制（copy）。其定義如下： 設(shè)到時刻t（第t代），群體A(t)中為最佳個體。又設(shè)A(t+1)為新一代群體，若A(t+1)中不存在，則把作為A(t+1)中的第n+1個個體（其中，n為群體大?。?。此方法的優(yōu)點是，進化過程中某一代的最優(yōu)解可不被交叉和變異操作所破壞。這也隱含了一種危機，即局部最優(yōu)個體的基因會急速增加而使進化有可能限于局部解，也就是說該方法全局搜索能力差，它更適合單峰性質(zhì)的搜索空間搜索，而不是多峰性質(zhì)的空間搜索。所以此方法都與其他選擇方法結(jié)合使用。 *()a t*()a t*()a t（二）交叉（二）交叉：交換操作是遺傳算法中最主要的遺傳操作。在遺傳

14、算法中使用交叉算子來產(chǎn)生新的個體。對于占主流地位的二進制編碼而言，各種交叉算子都包括兩個基本容：1）從有選擇操作形成的配對庫（mating pool）中，對個體隨機配對，并按預(yù)先設(shè)定的交叉概率來決定每對是否需要進行交叉操作； 2）設(shè)定配對個體的交叉點（cross site），并對這些點前后的配對個體的部分結(jié)構(gòu)（或基因）進行相互交換。 基本交叉算子如下：單點交叉（one-point crossover），它是指在個體編碼串中只隨機設(shè)置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體。雙點交叉（twopoint crossover）是指在個體編碼串中隨機設(shè)置了二交叉點，然后再進行部分基因交換

15、。雙點交叉了的具體操作過程是：在相互配對的兩個個體編碼串中隨機設(shè)置兩個交叉點；交換兩個個體在所設(shè)定的兩個交叉點之間的部分染色體。 （三）變異（三）變異：變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個串的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.0010.01之間。遺傳算法導(dǎo)入變異的目的有兩個：一是使遺傳算法具有局部的隨機搜索能力。二是使遺傳算法可維持群體的多樣性，以預(yù)防出現(xiàn)群體未成熟收斂現(xiàn)象。變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。就基因字符0,1的二進制碼串而言，變異操作就是把某些基因座上的基因值取反，一般來說

16、具有以下兩個步驟：在群體中所有個體的碼串范圍內(nèi)隨機的確定基因座；以事先設(shè)定的變異概率來對這些基因座的基因值進行變異。1基本變異算子基本變異算子是指對群體中的個體碼串隨機挑選一個或者多個基因座，并對這些基因座的基因值做變動（以變異率做變動），0，1二進制碼串中的基本變異操作如下：2逆轉(zhuǎn)變異算子（inversion operator） 逆轉(zhuǎn)變異算子是變異算子的一種特殊形式。它的基本操作內(nèi)容是，在個體碼串中隨機挑選兩個逆轉(zhuǎn)點，然后將兩個逆轉(zhuǎn)點基因值以逆轉(zhuǎn)概率逆向排序。0,1二值碼串的逆轉(zhuǎn)操作如下： mP11011110111010 變 異iP1000100110100101 01 逆 轉(zhuǎn)2 遺傳算法

17、的模擬計算示例遺傳算法的模擬計算示例 下面解釋用遺傳算法求函數(shù) 的最大值的一些重要步驟.這里只介紹第一代群體的生成過程與結(jié)果.(1)編碼編碼 由于在該例中 ,因此將變量 編碼為5位長的二進制形式.如 可表示為 .(2)初始群體的生成初始群體的生成 隨機產(chǎn)生初始群體的每個個體,群體的大小為4(如下表). 2( ),0,31f xx x0,31xx13x 01101個體號初始群體 的值適應(yīng)度選擇概率適應(yīng)度期望值實際次數(shù)配對 交叉位置新一代群體的值適應(yīng)度101101131690.140.581240110012144211000245760.491.9721411001256253010008640

18、.060.220421101127729410011193610.311.231321000016256適應(yīng)度總和11701.004.0041754平均適應(yīng)度2930.251.001439最大適應(yīng)度5760.491.972729xx(3)適應(yīng)度計算適應(yīng)度計算 將每個個體 的函數(shù)值 作為該個體的適應(yīng)度.如個體01101的適應(yīng)度為 .(4)選擇選擇 計算每個個體的適應(yīng)度所占的比例 ,并以此作為相應(yīng)的選擇概率.表的第5列給出了每個個體的選擇概率.由此概率可計算出每個個體選擇的次數(shù).也可采用輪盤賭方式來決定每個個體的選擇份數(shù).賭輪按每個個體適應(yīng)度的比例分配,轉(zhuǎn)動賭輪4次,就可決定各自的選擇份數(shù).如表中

19、第7列.結(jié)果反映出,優(yōu)秀個體2獲得了最多的生存繁殖機會,最差個體3被淘汰.每次選擇都對個體進行一次復(fù)制,由此得到的4份復(fù)制送到配對庫,以備配對繁殖.x( )f x2(13)13169fijff(5)交叉與變異交叉與變異 這里采用簡單交叉操作:首先對配對庫中的個體進行隨機配對;其次,在配對個體中隨機設(shè)定交叉處,配對個體彼此交換部分信息(如表).于是得到4個新個體,這4個新個體就形成了新一代群體.比較新舊群體,不難發(fā)現(xiàn)新群體中個體適應(yīng)度的平均值和最大值都有明顯的提高.由此可見,新群體中的個體的確是朝著期望的方向進化了. 一般而言,變異概率都取得很小.在這里取 由于群體中共有 位基因可以變異,這就意

20、味著群體中通常沒有一位基因可變異. 20 0.0010.020.001,mp 二二 模擬退火算法模擬退火算法一、一、模擬退火算法簡介 從物理學(xué)的有關(guān)知識知道，固體在恒定的溫度下達到熱平衡的過程可以用Monte Carlo方法進行模擬Monte Carlo方法的算法簡單，但必須大量采樣才能得到比較精確的結(jié)果因而計算量大。基于物理系統(tǒng)在自由狀態(tài)下有向能量較低狀態(tài)轉(zhuǎn)移的趨勢，而熱運動又妨礙它準確落人最低狀態(tài)的考慮,Metropolis于1953年提出對有重要貢獻的狀態(tài)進行采樣，從而較快地達到比較理想的結(jié)果，其方法可以描述如下： 先給定以粒子相對位置表征的初始狀態(tài) ，作為固體的當前狀態(tài)，該狀態(tài)的能量為

21、 。然后用攝動裝置使隨機選取的某個粒子的位移產(chǎn)生一微小變化，得到一個新狀態(tài) ，新狀態(tài)的能量是 。如果 ，則該新狀態(tài)就可作為“重要”狀態(tài)，如果 ，則考慮到熱運動的影響，該新狀態(tài)是否為“重要” 狀態(tài)需要根據(jù)固體處于該狀態(tài)的概率來判斷。設(shè)固體處于狀態(tài) 與狀態(tài) 的概率比值為r，r是一個小于1的數(shù)，用隨機數(shù)產(chǎn)生器產(chǎn)生一個 區(qū)間的隨機數(shù) 。若 ，則新狀態(tài)作為重要狀態(tài)，否則舍去。 ijiEjEjiEEjiEEjir0,1 若新狀態(tài) 是重要狀態(tài),就 以取代 成為當前狀態(tài)，否則仍以 為當前狀態(tài)，再重復(fù)以上新狀態(tài)的產(chǎn)生過程，在固體狀態(tài)經(jīng)過大量變換（常稱之為遷移）后，系統(tǒng)趨于能量較低的平衡狀態(tài)。上述接受新狀態(tài)的準則

22、稱為Metropolis準則，相應(yīng)的算法稱為Metropolis算法。研究表明一般情況下 Metropolis算法計算量明顯少于 Monte Carlo算法。通過對固體退火過程的研究可知，高溫狀態(tài)下的物質(zhì)降溫時其內(nèi)能隨之下降，如果降溫過程充分緩慢，則在降溫過程中物質(zhì)體系始終處于平衡狀態(tài)。從而降到某一低溫時其內(nèi)能可達最小，稱這種降溫為退火過程。模擬退火過程的尋優(yōu)方法稱為模擬退火（Simulated anneating，SA）算法。 jiji(1) 模擬退火算法模擬退火算法（SA） 設(shè) 為所有可能的組合狀態(tài)，C： 為非負目標函數(shù)，即 ，反映了取狀態(tài) 為解的代價，則組合優(yōu)化問題可以形式地描述為尋找

23、，使 將狀態(tài) 看成是某一物質(zhì)體系的微觀狀態(tài)，而將 看成該物質(zhì)體系在狀態(tài) 下的能量，并用控制參數(shù) 表示為讓溫度 從一個足夠高的值慢慢下降，對每一 用Metropolis采樣法模擬該體系在此 下的熱平衡狀態(tài)，即對當前狀態(tài) 做隨機擾動以產(chǎn)生一個新的狀態(tài) ，計算增量：12, , ,kSS SSSR 0iC S iS*SSiSSCSCSi min*iS iC SiSTTTTSS并以概率 接受 作為新的狀態(tài)，當這樣的隨機擾動重復(fù)的次數(shù)足夠多后，系統(tǒng)將達到該溫度下的平衡狀態(tài)，且服從Boltzmann分布。這里b即為Boltzmann常數(shù)。上述Metropolis采樣過程與退火過程可通過下列步驟來實現(xiàn)。 ex

24、pCbTS（2）退火過程實現(xiàn)算法（）退火過程實現(xiàn)算法（AP） 1) 任選一初始狀態(tài) 作為初始解 ，并設(shè)初始溫度為 ，令 ； 2) 令 ，以 和 調(diào)用Metropolis采樣算法，然后返回到當前解 ； 3) 按一定的方式將 降溫，即另令 4) 檢查退火過程是否結(jié)束，否則轉(zhuǎn)到 2)； 5) 以當前解 作為最優(yōu)解輸出。0S 00SS0T0iiT TiSTiSST11,1;iiiT T TT i i iS（3）Metropolis采樣算法（采樣算法（M法）法） 用AP算法調(diào)用當前解 和 的過程如下： 1) 令 時的當前解為 ，而在溫度 下進行以下步驟； 2) 按某一規(guī)定方式根據(jù)當前解 所處的狀態(tài) ，產(chǎn)

25、生一個鄰近子集 ，由 隨機產(chǎn)生一個新的狀態(tài) 以作為一個當前解的候選解，并計算 3)若 ，則接受 作為下一個當前解；若 ，則按概率 接受 作為下一個當前解； 4)若 被接受，則令 。否則令 ；TS0k 0SST S kS N S k N S kS CC SC S k0C0CSexp/C bTS S1S kS1( )S kS k 5) 令 ，判斷是否滿足收斂準則，否則回到 2)； 6) 將當前解 返回調(diào)用它的AP算法。二、幾種典型問題的模擬退火算法幾種典型問題的模擬退火算法 模擬退火算法是依據(jù)Metropolis準則接受新解，因此除接受優(yōu)化解外，還在一個限定范圍內(nèi)接受劣解，這正是模擬退火算法與局部

26、搜索算法的本質(zhì)區(qū)別。由于開始時較大，可能接受一些較差的劣解。隨著的減小，只能接受較好的可行解。最后在趨于0時，就只接受較優(yōu)的可行解了，這就使模擬退火有可能從局部最優(yōu)的“陷阱”中跳出來，從而求得整體最優(yōu)解。研究表明，對大多數(shù)組合優(yōu)化問題而言，模擬退火算法要優(yōu)于局部搜索算法。下面僅對幾個典型問題給出一個用迭代方法實現(xiàn)的算法描述，以揭示其建立數(shù)學(xué)模型和新解產(chǎn)生的基本求解方法。 1k k S k1、貨郎擔問題（、貨郎擔問題（TSP） 設(shè)有n個城市和距離矩陣D= ，其中 表示城市 到城市 的距離，則問題是要找遍訪每個城市恰好一次的一條回路，且其路徑長度為最短。求解的模擬退火算法描述如下： （1）解空間

27、解空間 可表為 的所有循環(huán)排列的集合，即 其中每一個循環(huán)排列表示遍訪n個城市的一條回路，初始解可選為 。ijdijdijS1 ,2, ,n 的循環(huán)排列，為nkkkkkSnn21,|,1211,2,n （2）目標函數(shù) 此時目標函數(shù)即為訪問所有城市的路徑長度或代價函數(shù)的極小值，即 其中 。而一次迭代步驟由下列三步構(gòu)成。 (3) 新解的產(chǎn)生 新解可通過分別或交替使用以下兩種方法來產(chǎn)生。 1) 2變換法 任選序號 。交換 與 之間的訪問順序，此時新路徑為（不妨設(shè) ）： （*）nikkniidkkf111,min11nkk, u vvuuv11111 v vvuunukkkkkkk k 2) 3變換法

28、任選序號 和 ，將 和 之間的路徑插到 之后訪問，對應(yīng)的新路徑為（設(shè) ）： （*） 在實際中經(jīng)常將上述兩種方法綜合交替使用。 （4）代價函數(shù)差 相應(yīng)于新解（*）和（*）式的代價函數(shù)的差分別滿足： （ ）, u vwwvuu v w 1111uvwwnuvkkkk kkkk11111111uvu vi iuuv viinnk kk kkkk kkkk ki ui ufdddddd 和 特別地，當問題對稱即距離矩陣D= 為對稱矩陣時，（ ）式可簡化為： （5）接受準則 根據(jù)以上的分析，即可寫出相應(yīng)的算法。 111111uvw uv wuuv vw wk kk kk kk kk kk kfdddddd ijd 1111uvu vuuv vkkk kkkk kfdddd 否則f/T),exp(0f, 0p2、最大截問題（、最大截問題（MCP） 給定帶權(quán)圖 ，權(quán)矩陣為 。要將 劃分為子集 和 ，使 中所有頂點分屬 和 的邊的權(quán)之和最大。 模擬退火算法描述為： （1）解空間 解空間可表示為集 的所有劃分為兩個子集 和 的分劃 的集合，即 其中分劃 （ ；