【正文】 67 8638 ADCLBIQFTMEPRGSOJHKN 第三 39 9902 ANKDHIOJSGRPEMTFQBLC 最差 1 5794 AQFTMEPRGSJOIBLCDHKN 遺傳算法 ? 達(dá)爾文進(jìn)化論：“物競(jìng)天擇、適者生存” ? 70年代由美國(guó)的密執(zhí)根大學(xué)的 Holland教授首先提出 ? 近年來，遺傳算法作為一種有效的工具，已廣泛地應(yīng)用于最優(yōu)化問題求解之中。則次最優(yōu)解是除了局部最優(yōu)解以外接受概率最大的，其接受概率為： tffe01 ??? 如果該概率值小于平均值 1/N時(shí)，即： 可以認(rèn)為從局部最優(yōu)解跳出的可能性已經(jīng)很小了，因此可以終止算法。 算法的終止原則 （ 3） ? 無變化控制法 如果在相鄰的 n個(gè)溫度中，得到的解的指標(biāo)函數(shù)值無任何變化，則說明算法已經(jīng)收斂。如果接受率達(dá)到了 R， 則停止該溫度下的迭代，轉(zhuǎn)入下一個(gè)溫度。如果溫度每次下降的幅度比較小的話，則相鄰溫度下的平穩(wěn)分布應(yīng)該變化不大，也就是說，對(duì)于任意一個(gè)狀態(tài) i， 相鄰溫度下的平穩(wěn)分布應(yīng)滿足： ???????1)()(111iPiPkktt? 一個(gè)充分條件是： ????????11)()(kmkmtfiftfifee1)()()1( ??????? kmkmtfiftfifee ?? 兩邊取對(duì)數(shù)，并整理得： ? 用 代替 可得溫度的衰減函數(shù)： mkkkfifttt?????)()1ln (11 ?kt?3 mfif ?)(ktkkk ttt??3)1ln (11 ????每一溫度下的停止準(zhǔn)則（ 1） ? 固定長(zhǎng)度方法 ? 在每一個(gè)溫度下，都使用相同的 Lk。(),(139。 起始溫度的選?。?1） ? 一個(gè)合適的初始溫度，應(yīng)保證平穩(wěn)分布中每一個(gè)狀態(tài)的概率基本相等，也就是接受概率 P0近似等于 1。對(duì)于任意兩個(gè)狀態(tài) i和 j， 我們用 Pt(i, j)表示溫度 t下，從狀態(tài)i轉(zhuǎn)移到狀態(tài) j的一步轉(zhuǎn)移概率，則有： ? 其中： Gt(i,j) 是產(chǎn)生概率，表示從狀態(tài) i產(chǎn)生狀態(tài) j的概率。 11， 轉(zhuǎn) （ 4） 12， End 13， tk+1=Drop(tk)， k=k+1。 5， Begin 6， 從 i的鄰域 N(i)中隨機(jī)選擇一個(gè)解 j。 達(dá)到最小能量狀態(tài)的三個(gè)條件 ? （ 1） 初始溫度必須足夠高； ? （ 2） 在每個(gè)溫度下 ， 狀態(tài)的交換必須足夠充分； ? （ 3） 溫度 T的下降必須足夠緩慢 。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(tǒng)會(huì)趨向于落入較低能量的狀態(tài)。上式分子、分母同乘以 ? ??????????????????????????SjKTjEKTiETiTeeTP)()(00lim)(limKTmEe? ???????????????????????????????????????????????????????????????????????????????????????????????mmmSjKTEjEKTEiETSjKTEjESjKTEjEKTEiETSjKTEjEKTEiETiTSiSiSeeeeeeeTPmmmmmmmmmm如果如果01limlimlim)(lim)()(0)()()(0)()(00? 當(dāng)溫度趨近于 0時(shí)，系統(tǒng)以等概率趨近于幾個(gè)能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為 0。 ? ?TKTiEi ZeTP)(??????SjKTjET eZ)(? 考察一下式（ 6）隨溫度 T的變化情況： – 同一溫度下，兩個(gè)能量不同的狀態(tài) – 高溫下的情況 – 低溫下的情況 – 當(dāng)溫度下降時(shí)的情況 ? 在給定的溫度 T下，設(shè)有 i、 j兩個(gè)狀態(tài)，E(i)＜ E(j) ： ? 即在任何溫度 T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運(yùn)動(dòng)又妨礙了系統(tǒng)準(zhǔn)確落入低能狀態(tài)。 ? 退火過程： 隨著溫度的下降，粒子的熱運(yùn)動(dòng)逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時(shí)，粒子重新以一定的結(jié)構(gòu)排列。 5， 如果陷入了局部極小 ， 既交換了所有的皇后 后 ， 沖突數(shù)仍然不能下降 ， 則轉(zhuǎn) 1。 8， End 9， k = k+1 10， 如果 k達(dá)到了指定的次數(shù) ， 則從 k個(gè)結(jié)果中選 擇一個(gè)最好的結(jié)果輸出 ， 否則轉(zhuǎn) （ 2） 11， 輸出結(jié)果 12，結(jié)束 多種方法的集成 ? 以上幾種解決方法可以結(jié)合在一起使用，比如第一、第二種方法的結(jié)合，就產(chǎn)生了我們將在后面介紹的模擬退火方法。 局部搜索算法 3（ Local Search 3） 1， k = 0 2， 隨機(jī)的選擇一個(gè)初始的可能解 x0∈ D， xb=x0， P=N(xb) 3， 如果不滿足結(jié)束條件 ， 則 4， Begin 5， 選擇 P的一個(gè)子集 P39。中的最優(yōu)解 5， 如果 f(xn) f(xb)， 則 xb ＝ xn 6， 按照某種策略改變步長(zhǎng) ， 計(jì)算 P = N(xb)， 轉(zhuǎn) 2 7， 否則 P = P – P39。 第一次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, c, b, d, e), f(xn) = 42, f(xn) f(xb), P = P – {xn} = {(a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第二次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(xb), P = P – {xn} = {(a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第三次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, e, c, d, b), f(xn) = 44, f(xn) f(xb), P = P – {xn} = {(a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第四次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, d, c, e), f(xn) = 44, f(xn) f(xb), P = P – {xn} = {(a, b, e, d, c), (a, b, c, e, d)} 第五次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, e, d, c), f(xn) = 34, f(xn) f(xb), xb = (a, b, e, d, c), P = {(a, e, b, d, c), (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第六次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, e, b, d, c), f(xn) = 44, f(xn) f(xb), P = P – {xn} = {(a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第七次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, d, e, b, c), f(xn) = 39, f(xn) f(xb), P = P – {xn} = {(a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第八次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, c, e, d, b), f(xn) = 38, f(xn) f(xb), P = P – {xn} = {(a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第九次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, d, e, c), f(xn) = 38, f(xn) f(xb), P = P – {xn} = {(a, b, c, d, e), (a, b, e, c, d)} 第十次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, c, d, e), f(xn) = 38, f(xn) f(xb), P = P – {xn} = {(a, b, e, c, d)} 第十一次循環(huán) 從 P中選擇一個(gè)元素 ， 假設(shè) xn = (a, b, e, c, d), f(xn) = 41, f(xn) f(xb), P = P – {xn} = {} P等于空 ， 算法結(jié)束 ， 得到結(jié)果為 xb = (a, b, e, d, c), f(xb) = 34。中的最優(yōu)解 5， 如果 f(xn) f(xb)， 則 xb ＝ xn， P = N(xb)， 轉(zhuǎn) 2； f(x)為指標(biāo)函數(shù) 。 ? 目標(biāo)可以是最大值，也可以是最小值。 ? 通過交換兩個(gè)城市的位置獲取 S