經(jīng)典-智能優(yōu)化方法課件PPT-東北大學(xué)+王俊偉

智能優(yōu)化方法

AI-BasedOptimizationMethodsByWangJunweiPhDNortheasternUniversityChina20071課程進度No.1 導(dǎo)言、偽隨機數(shù)的產(chǎn)生方法No.2 遺傳算法(GA)No.3 遺傳算法(GA)No.4 遺傳算法(GA)No.5 禁忌搜索(TS)2課程進度No.6模擬退火(SA)No.7新發(fā)展起來的算法蟻群優(yōu)化(ACO)，粒子群優(yōu)化(PSO)

捕食搜索（PS）,群落選址算法（CLA）No.8考試3教材《智能優(yōu)化方法》汪定偉王俊偉王洪峰張瑞友郭哲編著高等教育出版社中英文文獻4第一章 導(dǎo)言5第一章導(dǎo)言〇.最優(yōu)化的重要性一.傳統(tǒng)優(yōu)化方法的基本步驟——三步曲二.傳統(tǒng)優(yōu)化方法的局限性三.實際問題中對最優(yōu)化方法的要求四.智能優(yōu)化算法的產(chǎn)生與發(fā)展五.應(yīng)用前景局限性和研究方向、注意事項6人類的一切活動都是認(rèn)識世界和改造世界的過程

即：認(rèn)識世界→ 改造世界

↓ ↓

(建模)(優(yōu)化)

〇.最優(yōu)化的重要性（1）7一切學(xué)科都是建模與優(yōu)化在某個特定領(lǐng)域中的應(yīng)用 概念模型(定性)→結(jié)構(gòu)模型(圖)→ →數(shù)學(xué)模型→智能模型

〇.最優(yōu)化的重要性（2）8最優(yōu)化理論的發(fā)展極值理論；運籌學(xué)的興起(OperationResearch)；數(shù)學(xué)規(guī)劃：線性規(guī)劃(LP)；非線性規(guī)劃(NLP)；動態(tài)規(guī)劃(PP)；馬爾托夫規(guī)劃(MDP)；排隊輪；決策論；存儲論。最優(yōu)化理論在國民經(jīng)濟中的廣泛應(yīng)用

〇.最優(yōu)化的重要性（3）9如下面框圖所示選一個初始解LP:大M，二階段法NLP:任意點或一個內(nèi)點

一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（1）10停止判據(jù)——停止規(guī)則最優(yōu)性檢驗LP:檢驗數(shù) 當(dāng)∏≥0時有可能減小NLP:一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（2）11向改進方向移動——改進解LP:轉(zhuǎn)軸變換(進基、退基)NLP:向負(fù)梯度方向移動(共軛梯度方向、牛頓方向) 一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（3）12停機選擇一個初始解停止準(zhǔn)則向改進方向移動啟動YN一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（4）13對問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求——有顯式表達，線性、連續(xù)、可微，且高階可微;2. 只從一個初始點出發(fā)，難以進行并行、網(wǎng)絡(luò)計算，難以提高計算效率；

二.傳統(tǒng)優(yōu)化方法的局限性（1）14最優(yōu)性達到的條件太苛刻——問題的函數(shù)為凸，可行域為凸；在非雙凸條件下，沒有跳出局部最優(yōu)解的能力。

二.傳統(tǒng)優(yōu)化方法的局限性（2）15對問題的描述要寬松(目標(biāo)和約束函數(shù))——

可以用一段程序來描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式；并不苛求最優(yōu)解——通常滿意解、理想解就可以了；三.實際問題中對最優(yōu)化方法的要求（1）16計算快速、高效,可隨時終止(根據(jù)時間定解的質(zhì)量)；能夠處理數(shù)據(jù)、信息的不確定性(如數(shù)據(jù)的模糊性，事件的隨機性)。三.實際問題中對最優(yōu)化方法的要求（2）171975年holland提出遺傳算法

(GeneticAlgorithm)1977年Glouer提出禁忌搜索算法

(TabnSearch) 四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（1）181982年Kirkpatrick提出模擬退火算法

(SimulatedAnnealing)人工神經(jīng)元網(wǎng)絡(luò)1995年Dorigo提出蟻群算法

(AntColonyOptimization)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（2）191995年Kennedy&Eherhart提出粒子群優(yōu)化(ParticleSwarmOptimization)其它文化算法(CulturalAlgorithm)人工生命算法(Artificial-LifeAlgorithm)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（3）20我們統(tǒng)稱以上算法為人工生命計算(ArtificialLifeComputation)人工生命計算+模糊邏輯(FuzzyLogic)=

軟計算(SoftComputation)人工生命計算+進化編程=

進化算法(Evolutionarycomputation)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（4）21應(yīng)用前景十分廣闊——國民經(jīng)濟的各個領(lǐng)域局限性——不能保證最優(yōu)解，理論上不完備五.應(yīng)用前景局限性和研究方向、注意事項（1）22研究方向及注意事項以應(yīng)用為主，擴大面向新問題的應(yīng)用；不要刻意做理論研究，若碰上也不拒絕;算法改進表現(xiàn)在以下幾個方面：問題的描述、編碼方法、算法構(gòu)造及可行性修復(fù)策略;要進行大量的上機計算；五.應(yīng)用前景局限性和研究方向、注意事項（2）23算例的選取，以下算例的說服力降序排列：網(wǎng)上的測試用例、文獻中的例子、實際例子、隨機產(chǎn)生的例子、自己編的例子;如何檢驗算法的好壞：比較計算速度、可解規(guī)模、(從不同的隨機種子出發(fā))達優(yōu)率。五.應(yīng)用前景局限性和研究方向、注意事項（3）24第二章 偽隨機數(shù)的產(chǎn)生25第二章偽隨機數(shù)的產(chǎn)生一.偽隨機數(shù)產(chǎn)生的意義二.產(chǎn)生U(0,1)的乘同余法三.正態(tài)分布N(0,1)的產(chǎn)生四.逆變法與其它分布隨機數(shù)的產(chǎn)生26在GA,SA,TS中都要用到；在計算機中的固有偽隨機數(shù)發(fā)生器只有U(0,1) 且可重復(fù)性不好，沒有其他分布；自己設(shè)計的發(fā)生器，可控型好、可重復(fù)性好，便于仿真比較。

一.偽隨機數(shù)產(chǎn)生的意義27乘同余法的計算公式

可產(chǎn)生隨機數(shù)序列。問題：怎樣設(shè)定和可以使隨機數(shù)序列最長？

二.產(chǎn)生U(0,1)的乘同余法（1）序列滿足以下關(guān)系式：常數(shù)取模(除以M后的余數(shù))或取整28乘同余法的方法： 若的整數(shù)，當(dāng){x}滿足以下條件時，可以達到最大周期(序列長度)

為3(Mod8)或5(Mod8)的數(shù)；為奇數(shù)，一般取為1。二.產(chǎn)生U(0,1)的乘同余法（2）29乘同余法舉例說明：

==16=3=1,3,9,11,1,3,9,11=5=1,5,9,13,1,5,9,13=3=2,6,2,6…可得整數(shù)序列，要想獲得U(0,1)，見下面二.產(chǎn)生U(0,1)的乘同余法（3）30產(chǎn)生U(0,1)步驟：；令 。

二.產(chǎn)生U(0,1)的乘同余法（4）31產(chǎn)生U(0,1)舉例說明：==16=3，x0=1=1/16,3/16,9/16,11/16,1/16,3/16,9/16,11/16…=3，x0=2=2/16,6/16,2/16,6/16…

二.產(chǎn)生U(0,1)的乘同余法（5）32優(yōu)秀編程舉例：IF(NR·(T·0))NR=NR+M(M對應(yīng)于計算機中最大整數(shù))

二.產(chǎn)生U(0,1)的乘同余法（6）33三.正態(tài)分布N(0,1)的產(chǎn)生（1）98.70正態(tài)分布可以用多個U(0,1)來近似，若是獨立同分布，較大，則近似正態(tài)分布，且滿足及 則

34令：一般n取12則：其中：

（詳見下頁）三.正態(tài)分布N(0,1)的產(chǎn)生（2）35注：三.正態(tài)分布N(0,1)的產(chǎn)生（3）36逆變法四.逆變法與其它分布隨機數(shù)的產(chǎn)生（1）101分布函數(shù)101密度函數(shù)=1,0≤x≤10,其它37

是分布函數(shù)，，如何產(chǎn)生？設(shè)，是隨機變量 產(chǎn)生，是分布函數(shù)逆變法的目的：產(chǎn)生分布的隨機數(shù)四.逆變法與其它分布隨機數(shù)的產(chǎn)生（2）38逆變法的步驟：已知，或由求即，令推導(dǎo)產(chǎn)生用得到四.逆變法與其它分布隨機數(shù)的產(chǎn)生（3）39負(fù)指數(shù)分布的產(chǎn)生

負(fù)指數(shù)函數(shù)的密度函數(shù)：四.逆變法與其它分布隨機數(shù)的產(chǎn)生（4）40負(fù)指數(shù)函數(shù)的分布函數(shù)的產(chǎn)生過程：①

令②③ 產(chǎn)生 則

④ 即四.逆變法與其它分布隨機數(shù)的產(chǎn)生（5）41產(chǎn)生 是負(fù)指數(shù)分布的。四.逆變法與其它分布隨機數(shù)的產(chǎn)生（6）42第三章 遺傳算法43第三章 遺傳算法一.導(dǎo)言二.Holland的基本GA三.計算舉例四.Holland的結(jié)構(gòu)理論五.GA的各種變形六.應(yīng)用七.學(xué)習(xí)GA的幾點體會44遺傳算法(GA)的產(chǎn)生

1975年，Holland提出GA

著名的書：

AdaptationinNaturalandArtificialSystems(中文名稱：自然與人工系統(tǒng)的自適應(yīng)性)

后來，DeJong和Goldberg做了大量工作，使GA更加完善。一.導(dǎo)言（1）45遺傳算法(GA)的來源： 生物的進化：自然選擇、適者生存生物的遺傳和變異

(GA)缺點：無人的主動性； 解決方法有以下三個：定向培育隨機算法網(wǎng)格法一.導(dǎo)言（2）46定向培育 過程如下： 第一：一個種群，大量的生物個體； 第二：選擇具有需要特性的若干個體； 第三：進行繁殖； 第四：重復(fù)第二，直到滿意為止。

一.導(dǎo)言（3）47隨機算法：在解空間隨機產(chǎn)生多個解，選擇最好的網(wǎng)格法：根據(jù)最好解的幾何分布，來不斷的縮小搜索范圍。一.導(dǎo)言（4）48遺傳算法的基本思想根據(jù)問題的目標(biāo)函數(shù)構(gòu)造適值函數(shù)(FitnessFunction)；產(chǎn)生一個初始種群(100-1000)；根據(jù)適值函數(shù)的好壞，不斷選擇繁殖；若干代后得到適值函數(shù)最好的個體即最優(yōu)解。一.導(dǎo)言（5）49遺傳算法的構(gòu)成要素種群(Population),種群大小(Pop-size)基因表達法——編碼方法

(EncodingScheme;GeneRepresentation)一.導(dǎo)言（6）50遺傳算子(GeneticOperator)： 交叉(Crossover)，變異(Mutation)選擇策略:一般為正比選擇停止準(zhǔn)則(StoppingRule/Criterion):

一般是指定最大代數(shù)一.導(dǎo)言（7）51算法框架與步驟 見下頁

二.Holland的基本GA（1）52二.Holland的基本GA（2）產(chǎn)生初始種群開始判斷停止條件輸出計算適值函數(shù)選擇遺傳運算更新種群停止YN評估(在解空間做)向改進方向移動(在編碼空間做)53解空間與編碼空間的轉(zhuǎn)換 遺傳運算是對編碼空間操作的，所以要進行兩個空間的轉(zhuǎn)換。 見下頁示意圖

二.Holland的基本GA（3）54二.Holland的基本GA（4）解空間編碼編碼空間011001100011110011遺傳運算后代011000000011110001解空間選擇解碼計算適值，評估適值55各個步驟的實現(xiàn)初始種群的產(chǎn)生編碼方法適值函數(shù)遺傳運算選擇策略停止準(zhǔn)則

二.Holland的基本GA（5）56初始種群的產(chǎn)生 隨機產(chǎn)生(依賴于編碼方法)；種群的大小(依賴于計算機的計算能力和計算復(fù)雜度)。例：0,1編碼產(chǎn)生，>0.5，=1；

<0.5，=0

二.Holland的基本GA（6）57編碼方法——二進制編碼二進制編碼，用0，1字符串表達。 例：0110010，適用以下三種情況背包問題：

1，背；0，不背二.Holland的基本GA（7）58實優(yōu)化：精度高時編碼長，一般不采用此法而用實值函數(shù)。指派問題二進制編碼缺點：編碼長不利于計算；二進制編碼優(yōu)點：便于位值計算，包括的實數(shù)范圍大

二.Holland的基本GA（8）59適值函數(shù)——根據(jù)目標(biāo)函數(shù)設(shè)計 用適值函數(shù)標(biāo)定(Scaling)目標(biāo)函數(shù) 采用方法或 。 遺傳運算(遺傳算法的精髓)——交叉和變異 下面我們就介紹一下交叉和變異

二.Holland的基本GA（9）60交叉(Crossover)單切點交叉隨機產(chǎn)生一個斷點(CuttingPoint)［1，n-1］例：

二.Holland的基本GA（10）011|0011101|

0110011|0110101|

0011單切點交叉61雙切點交叉(交換中間段)

例：不是所有點都交叉，設(shè)定一個交叉概率，一般為0.9二.Holland的基本GA（11）011|00|11101|

01|10011|01|

11101|

00|

10雙切點交叉62變異(Mutation)初始種群中沒有需要的基因，在種群中按變異概率 任選若干位基因改變位值0→1或1→0，有意想不到的結(jié)果，一般設(shè)定得比較小，在5%以下。

二.Holland的基本GA（12）63選擇策略 最常用的正比選擇(ProportionalSelection)對于個體，適值，選擇概率如下式可計算NP—NumberofPopulation

二.Holland的基本GA（13）64得到選擇概率后，我們采用旋輪法(RouletteWheel)令，隨機產(chǎn)生當(dāng)，選擇個體

二.Holland的基本GA（14）轉(zhuǎn)輪NP次NP*次做交叉；NP*次做變異；NP*(1--)

不變65如下圖所示:注：優(yōu)良種得到較多的繁殖機會，后代很像；而很可能失去繁殖的機會。

二.Holland的基本GA（15）66停止準(zhǔn)則指定最大代數(shù)(NG—NumberofMaxGeneration)

很少用，麻煩二.Holland的基本GA（16）67例1：，，NP=5簡單分析：編碼為五位的0，1編碼，推導(dǎo)如下設(shè)編碼長度L，取決于

，即編碼精度若要求編碼精度為1，則由C<=1可推得L>=5三.計算舉例（1）68②

，最大值 ，最小值三.計算舉例（2）1001030410069步驟：產(chǎn)生初始種群NG=10,t=0判斷停止準(zhǔn)則計算適值用旋輪法正比選擇三.計算舉例（3）70計算生成的列表：三.計算舉例（4）表1表2編碼交叉點子串編碼1100111923990.2060.20612410011192399200101532250.2770.48353201010104100311010265160.0440.527523011011338574101012118010.1550.682421101012118015011101436840.3170.999254001004280471觀察結(jié)果⑴ 整個種群在改善：23252992⑵ 模板0????較好，而1????較差⑶ “好壞”數(shù)量的變化 ：23；：32三.計算舉例（5）72結(jié)果(3)數(shù)量變化可由表1中的數(shù)據(jù)推導(dǎo)出：同理：

=0.9=0.02三.計算舉例（6）73雙親的選擇方法：隨機選： 產(chǎn)生，比例選:

產(chǎn)生，當(dāng)，選擇個體父親優(yōu)選，母親隨機選： 選，三.計算舉例（7）74又稱概形理論(SchemaTheory)1.模板的概念：若干位確定，若干位不確定的一類個體的總稱，用表示，如0????和1????。四.Holland的結(jié)構(gòu)理論（1）75模板的長度：模板第一個確定位與最后一個確定位之間的長度。模板的階數(shù)：模板中確定位的個數(shù)。例如：——?1?1?0??，=4，=3四.Holland的結(jié)構(gòu)理論（2）76常識：n位編碼總長n-1;階數(shù)為的概型，中的個體總數(shù)為;對于一個n位二進制表達，染色體長度為n

模板度>個體數(shù)(>)，即分類方法數(shù)>個體總數(shù)。因模板因子、個體因子分別為(0，1，?

)、(0，1)。四.Holland的結(jié)構(gòu)理論（3）77模板理論引理1：在正比選擇下，模板在第代的期望個體數(shù)為：其中是第代模板中所有個體的適值均值與種群中所有個體的適值均值的比，是第代的個體數(shù)。如例1中：0????

，

=1.4858，=2，=3四.Holland的結(jié)構(gòu)理論（4）78證明：四.Holland的結(jié)構(gòu)理論（5）79注釋:種群的適值和為：， 則選擇概率為：為中的個體總數(shù)，且下標(biāo)隨遺傳的進行而變化；四.Holland的結(jié)構(gòu)理論（6）80為模板中所有個體的適值均值;

為種群的適值均值只要均值>1，則好的種群的個體會越來越多。問題：以上證明沒有考慮交叉變異，那么交叉變異會不會破壞種群模板？概率有多大？四.Holland的結(jié)構(gòu)理論（7）81引理2：第代以概率做交叉，對長度為的概型，則在第代中個體數(shù)為概型的概率下界為：其中為第代個體為的概率。四.Holland的結(jié)構(gòu)理論（8）82引理2的證明證明：交叉破壞的條件做了交叉：交叉點在內(nèi):配偶不在中：則不被破壞的概率：四.Holland的結(jié)構(gòu)理論（9）83思考：若不屬于概型，是否能產(chǎn)生后代為概型？ 答案：可以四.Holland的結(jié)構(gòu)理論（10）84引理3：若第代以做變異，對于一個階數(shù)為的模板,則在第代仍為的概率的下界為：證明： 對于，當(dāng)=1，不破壞的概率為 當(dāng)>1，不破壞的概率為取其泰勒展開式的第一項：四.Holland的結(jié)構(gòu)理論（11）85主定理(概型定理)：第代以概率和做交叉和變異時，長度為，階數(shù)為，適值均值比為的概型在第代的期望個體數(shù)的下界為：當(dāng)時，隨代數(shù)的增加而增加。四.Holland的結(jié)構(gòu)理論（12）交叉破壞變異破壞86其它編碼方法順序編碼：用1到N的自然數(shù)的不同順序來編碼，此種編碼不允許重復(fù)，即且，又稱自然數(shù)編碼。該法適應(yīng)范圍很廣：指派、旅行商問題，單機調(diào)度。合法性問題：是否符合采用的編碼規(guī)則的問題五.GA的各種變形（1）87實數(shù)編碼特征：方便運算簡單，但反映不出基因的特征整數(shù)編碼 應(yīng)用于新產(chǎn)品投入，時間優(yōu)化，伙伴挑選例：3212345對順序編碼來說是不合法的，而對整數(shù)編碼來說是合法的；010200不合法的01編碼；五.GA的各種變形（2）88練習(xí)（1）對于編碼長度為7的0－1編碼，判斷以下編碼的合法性(1)[1020110],(2)[101100],(3)[0110010],(4)[0000000],(5)[2134576].

89練習(xí)（2）對于編碼長度為7的順序編碼，判斷以下編碼的合法性(1)[7120435],(2)[136247],(3)[2135476],(4)[8143257],(5)[2132576].

90練習(xí)（3）對于編碼長度為7的實數(shù)編碼，判斷以下編碼的合法性(1)[3.51.9271.81.70],(2)[89.054.78214.36.9],(3)[0110010],(4)[0000000],(5)[2134576].

91遺傳運算中的問題 在順序編碼遺傳運算的過程中會遇見不合法的編碼，應(yīng)戰(zhàn)的策略有二:拒絕或修復(fù)。例如：經(jīng)交叉后，后代編碼不合法

21|345|6721|125|6743|125|7643|345|76我們采用下面的修復(fù)策略使以上的編碼合法。五.GA的各種變形（3）92順序編碼的合法性修復(fù)：交叉修復(fù)策略 它分為以下幾種部分映射交叉順序交叉循環(huán)交叉五.GA的各種變形（4）93部分映射交叉(PMX) (PartiallyMappedCrossover)PMX步驟：⑴選切點X,Y；⑵交換中間部分；⑶確定映射關(guān)系；⑷將未換部分按映射關(guān)系恢復(fù)合法性。五.GA的各種變形（5）94PMX例題：五.GA的各種變形（6）映射關(guān)系：3-1，4-2，5-5則：43|125|6721|345|76

21|345|67|125|

43|125|76|345|

XY95順序交叉(OX

)OrderCrossoverOX步驟：⑴選切點X,Y；⑵交換中間部分；⑶從切點Y后第一個基因起列出原序，去掉已有基因；⑷Y后第一個位置起填入。五.GA的各種變形（7）96OX例題：五.GA的各種變形（8）列出基因：67213457643125則：34|125|6712|345|76

21|345|67|125|

43|125|76|345|

XY97OX的特點：較好的保留了相鄰關(guān)系、先后關(guān)系滿足了TSP問題的需要，但不保留位值特征。五.GA的各種變形（9）98循環(huán)交叉(CX)CycleCrossover基本思想：子串位置上的值必須與父母的相同位置上的位值相等。CX步驟：⑴選的第一個元素作為的第一位， 選的第一個元素作為的第一位；五.GA的各種變形（10）99⑵到中找的第一個元素賦給的相對位置…，重復(fù)此過程，直到上得到的第一個元素為止，稱為一個循環(huán)；⑶對最前的基因按、基因輪替原則重復(fù)以上過程；⑷重復(fù)以上過程，直到所有位都完成。五.GA的各種變形（11）100CX例題：五.GA的各種變形（12）245389617236

398654271362

32，94，58，71629346

34692295384671

348659217101CX的特點：與OX的特點不同的是，CX較好的保留了位值特征，適合指派問題；而OX較好的保留了相鄰關(guān)系、先后關(guān)系滿足了TSP問題的需要。五.GA的各種變形（13）102練習(xí)P1：［6128｜9547｜103］P2：［10741｜3628｜59］PMX：C1：C2：OX：C1：C2:103練習(xí)（2）P1：［61289547103］P2：［10741362859］CX：C1：C2：104變異的修復(fù)策略換位變異(最常用)

例：

43125674512367

移位變異：任選一位移到最前例：

43125675431267五.GA的各種變形（14）105實數(shù)編碼的合法性修復(fù)

交叉單切點交叉五.GA的各種變形（15）切點106雙切點交叉(與單切點交叉類似)

該方法最大的問題：如何在實優(yōu)化中保持可行性。五.GA的各種變形（16）107凸組合交叉約束是個凸集，可行性可以保持，問題是分散性太差，向中間匯集的問題需要解決。五.GA的各種變形（17）108變異位值變異： 任選一位加Δ， 例：五.GA的各種變形（18）109向梯度方向變異缺點：只能用于目標(biāo)函數(shù)可微的問題 例:五.GA的各種變形（19）110適值函數(shù)的標(biāo)定(Scaling)五.GA的各種變形（20）選擇壓力小，差別小，選優(yōu)功能弱化了選擇壓力大，差別放大，選優(yōu)功能強化了標(biāo)定111標(biāo)定的目的： 使適值函數(shù)不會太大，有一定差別選擇壓力的概念： 選擇壓力是種群好、壞個體被選中的概率之差，差大稱為選擇壓力大。五.GA的各種變形（21）112局部搜索、廣域搜索與選擇壓力的關(guān)系局部搜索與廣域搜索是GA中的一對矛盾，好的算法要將以上二者綜合考慮。算法開始重廣域搜索，選擇壓力??；隨迭代進行，逐步偏重于局部搜索，選擇壓力大。五.GA的各種變形（22）113適值的標(biāo)定方法線性標(biāo)定：函數(shù)表達式,

為目標(biāo)函數(shù)，為適值函數(shù)五.GA的各種變形（23）114對，

=1，=， 函數(shù)表達式： +ξ，對，

=-1，=,

函數(shù)表達式： +ξ，五.GA的各種變形（24）115動態(tài)線性標(biāo)定(最常用) 優(yōu)點：計算容易不占用時間函數(shù)表達式：，為迭代指標(biāo)最常用極大化：

=1,函數(shù)表達式：五.GA的各種變形（25）116加入的意義： 加入使最壞個體仍有繁殖的可能，隨而減小的取值： ，，， 調(diào)節(jié)和，從而來調(diào)節(jié)五.GA的各種變形（26）117引入目標(biāo)的目的： 調(diào)節(jié)選擇壓力，即好壞個體選擇概率的差，使廣域搜索范圍寬保持種群的多樣性，而局域搜索細保持收斂性。如下圖表示： 開始：希望選擇壓力小 后來：希望選擇壓力大五.GA的各種變形（27）NP118冪律標(biāo)定： 函數(shù)表達式： 的取值，>1時選擇壓力加大

<1時選擇壓力減小對數(shù)標(biāo)定： 函數(shù)表達式： 對數(shù)標(biāo)定的作用：縮小差別五.GA的各種變形（28）119指數(shù)標(biāo)定： 函數(shù)表達式： 指數(shù)標(biāo)定的作用：擴大差別窗口技術(shù)： 函數(shù)表達式： 為前W代中的最小目標(biāo)值，它考慮了各代

的波動，這樣具有記憶性五.GA的各種變形（29）120正規(guī)化技術(shù)： 函數(shù)表達式： 正規(guī)化技術(shù)的作用： 將映射到(0,1)區(qū)間，抑制超級染色體 正規(guī)化技術(shù)的實質(zhì)：特殊的動態(tài)標(biāo)定 即 其中：五.GA的各種變形（30）121選擇策略 傳統(tǒng)的GA選擇和遺傳是一起進行的，即使后代不如父代，卻無法糾正。下面介紹的選擇策略都是先遺傳后選擇。這樣，樣本空間擴大了，可供選擇的個體增多了。五.GA的各種變形（31）122截斷選擇： 選擇最好的前T個個體，讓每一個有1/T的選擇概率，平均得到NP/T個繁殖機會。例：NP=100,T=50 即100名學(xué)生，成績前50名的選出。每人的選擇概率為1／50，有平均2個機會。這種方法計算量在排序上。五.GA的各種變形（32）123順序選擇：步驟：⑴從好到壞排序所有個體⑵定義最好個體的選擇概率為,則第個個體的選擇概率為：五.GA的各種變形（33）124⑶ 由于 有限時要歸一化，則有下面的兩個公式：順序選擇的缺點： 把選擇概率固化了，選擇壓力不可調(diào)五.GA的各種變形（34）125舉例:

且：采用旋輪法，隨機產(chǎn)生當(dāng)，選擇個體五.GA的各種變形（35）126正比選擇： 令： ，用動態(tài)標(biāo)定來調(diào)節(jié)選擇壓力，采用旋輪法來共同完成種群的選擇。

五.GA的各種變形（36）127停止準(zhǔn)則指定最大代數(shù)檢查種群中適值的一致性，保持歷史上最好的個體。計算公式： 或第二種方法因很難實現(xiàn)，所以很少使用。五.GA的各種變形（37）128背包問題 個物品，對物品，價值為，重量為，背包容量是。如何選取物品裝入背包，使背包中的價值最大。

六.應(yīng)用（1）129模型:

，裝入物品 ，不裝入物品

六.應(yīng)用（2）130如何處理約束來保持可行性拒絕策略：可行解不易達到時，很難達到一個初始種群修復(fù)策略：將不可行解修復(fù)為可行的，但將失去多樣性。六.應(yīng)用（3）131懲罰策略： 設(shè)計懲罰函數(shù)，但設(shè)計不好會掩蓋目標(biāo)函數(shù)的優(yōu)化。 下面，我們將分別采用懲罰策略及優(yōu)先適合啟發(fā)式來處理上面的背包問題。

六.應(yīng)用（4）132罰函數(shù)法令適值函數(shù) ，其中是目標(biāo)函數(shù)令 ，其中

注： 與 是 的兩個端點六.應(yīng)用（5）133函數(shù)式的意義：⑴ 的作用是使 ，保證⑵可行也罰，只有當(dāng) 不罰。⑶罰函數(shù)法目的：把解拉向邊界，盡量裝滿。六.應(yīng)用（6）134解碼法——FirstFitHeuristic(優(yōu)先適合啟發(fā)式)解碼法是修復(fù)程序(修復(fù)可行性的方法)⑴步驟：將選上物品按降序排列；選前個物品，使 ；⑵解碼法的關(guān)鍵：如何在GA中解決可行性問題⑶編碼方法：采用順序編碼

六.應(yīng)用（7）135例：=7

用順序(3251467)表示選擇物品的順序用優(yōu)先適合啟發(fā)式保留前K位，使解可行即：

=3， (325)問題：編碼長度是可變的，如何做交叉和變異

六.應(yīng)用（8）136⑷變長順序編碼的遺傳算法插入式交叉算法在上選一個隨機的斷點；在上隨機選一個基因片斷插入的斷點處；去掉上的重復(fù)基因；按優(yōu)先適合啟發(fā)式得到可行解見下頁例題六.應(yīng)用（9）137例題：

六.應(yīng)用（10）去掉重復(fù)基因：32|46|15可行嗎？選5時背包裝不下，去掉5

32461

32|15432|46|154

12|46|35X138最小生成樹問題(MinimumSpanningTree)問題的提出難點：對于下面的紅色的圖形，如何設(shè)計一個合適的編碼方法？

六.應(yīng)用（11）12345612435768910139傳統(tǒng)的編碼方法：節(jié)點表示法： 無法避免回路，很難做遺傳運算，如：

{(1,2),(2,3),(2,5),(2,6),(4,6)} 六.應(yīng)用（12）12345612435768910140邊編碼法： 無法保證是樹無法保證可行性

{1,2,4,5,10}缺點：麻煩，無法做遺傳運算，無法保持合法性 六.應(yīng)用（13）12345612435768910141 為解決以上問題，人們提出了最小生成樹的(Pr?fer數(shù))的編碼方法。最小生成樹的定義： 用n-2位自然數(shù)唯一的表達出一棵n個節(jié)點的生成樹，而且交叉變異仍是一棵生成樹。六.應(yīng)用（14）142葉子：樹中度數(shù)為1的節(jié)點例如：1，3，4，5最小生成樹應(yīng)用條件：覆蓋所有頂點連通的沒有回路

六.應(yīng)用（15）123456143編碼步驟設(shè)節(jié)點i是標(biāo)號最小的葉子令j是編碼中的第一個數(shù)字，若i與j相連刪去邊(i,j)轉(zhuǎn)Ⅰ,直到剩下一條邊為止

六.應(yīng)用（16）123456144圖解：i=1,(i,j)=(1,2),j=2 ;i=3,(i,j)=(3,2) ,j=2 i=4,(i,j)=(4,6),j=6

;i=5,(i,j)=(5,2),j=2編碼：（2262）

六.應(yīng)用（17）12345623456245625626145解碼步驟令Pr?fer數(shù)中的節(jié)點集為,不包含在中的節(jié)點集為；若i為中最小標(biāo)號的節(jié)點，j為上最左邊數(shù)字連接邊(i,j)，并從中去掉i，從中去掉j，若j不再在中，將j加入中。

六.應(yīng)用（18）146重復(fù)Ⅱ，直到中沒有節(jié)點(即為空)，中剩下(s,r)連接(s,r)圖解過程見下頁

六.應(yīng)用（19）147例： =[2，2，6，2]，=[1，3，4，5] (1,2) =[2，6，2]， =[3，4，5] (3,2) =[6，2]， =[4，5] (4,6) =[2]， =[5，6] (5,2) =[Ф]， =[2，6] 六.應(yīng)用（20）123456123456123456123456123456123456148最小生成樹的的優(yōu)點：對于一個個節(jié)點的Pr?fer數(shù)的個數(shù)為，生成樹的個數(shù)也是。最小生成樹實現(xiàn)了解空間和編碼空間的一一對應(yīng)，交叉變異不破壞合法性。一個好的編碼方法對遺傳算法至關(guān)重要。

六.應(yīng)用（21）1491765234[23244]練習(xí):150175[63244]P=[157]4236練習(xí):151二次指派問題——機器布置問題(QAP)

機器布置問題FacilityLayout—QuadraticAssignmentProblem

六.應(yīng)用（22）152問題的提出：臺機器，要布置在個地方，機器i與k之間的物流量為，位置j與L之間的距離為，如何布置使費用最小。設(shè)： 表示機器i布置在位置j； 其它。同理對。

六.應(yīng)用（23）153數(shù)學(xué)模型： 二次0-1規(guī)劃

六.應(yīng)用（24）154用GA求解編碼——順序編碼 表示機器放在位置i，是1到n中的數(shù)如：[4,3,1,2,5]

機器4放在位置1； 機器3放在位置2； 機器1放在位置3；

…；

六.應(yīng)用（25）155該編碼的優(yōu)點：沒有重復(fù)，保證了編碼的合法性

六.應(yīng)用（26）156函數(shù)表達式變?yōu)椋簝?yōu)點：使其更加簡潔，便于計算。缺點：變量出現(xiàn)在下標(biāo)，任何數(shù)學(xué)規(guī)劃不可用解決方法：遺傳算法(GA) 六.應(yīng)用（27）157用GA求解的設(shè)定編碼方法：順序編碼適值公式：動態(tài)線性標(biāo)定：其它：用CX做交叉；換位變異；正比選擇，就可以解決該問題。

六.應(yīng)用（28）158編碼是成功的關(guān)鍵(如最小樹問題)最好能使編碼空間與解空間一一對應(yīng)減少編碼冗余，編碼應(yīng)盡可能短便于遺傳運算——有利于保持合法性、可行性實在沒有辦法保持，要設(shè)計合理的修復(fù)程序，盡可能保持父輩的特征。七.學(xué)習(xí)GA的幾點體會（1）159遺傳算子的設(shè)計有最大的創(chuàng)新空間選擇壓力的調(diào)整使多樣性和收斂性得到合適的分配。開始時多樣性重要，重廣域搜索；剛要結(jié)束時收斂性重要，重局域搜索。調(diào)整方法：適值函數(shù)的構(gòu)造；合適的標(biāo)定方法七.學(xué)習(xí)GA的幾點體會（2）160在GA的研究中我們要做一些什么擴大GA的應(yīng)用,GA應(yīng)用面廣，適應(yīng)性最好算法改進方向的研究理論研究算法開發(fā)中的幾個技術(shù)(見下頁)七.學(xué)習(xí)GA的幾點體會（3）161參數(shù)整定：經(jīng)驗加反復(fù)試驗(Tuning)如：， ，NG，NP幾種參數(shù)的選定判斷好壞算法的辦法：⑴ 快⑵ 能解的問題大⑶ 達優(yōu)率高，大問題50%的達優(yōu)率七.學(xué)習(xí)GA的幾點體會（4）162算例的選擇：⑴自己編的——沒有說服力，但可以解釋算法⑵隨機產(chǎn)生的——適合沒有前例的例子⑶文獻的例子——面較大⑷網(wǎng)上的例子——典型問題QAP,TSP七.學(xué)習(xí)GA的幾點體會（5）163智能優(yōu)化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina2004164第四章 禁忌搜索165第四章禁忌搜索（TabuSearch

）一.導(dǎo)言二.TS的基本原理及步驟三.TS的算法步驟四.TS可以克服局優(yōu)的分析五.TS舉例六.TS的中、長期表的使用七.TS表的應(yīng)用舉例八.學(xué)習(xí)TS的幾點體會166TS的提出

1977年F.Glover提出TS

，90年代初得到廣泛重視

一.導(dǎo)言（1）167TS的基本思想——避免在搜索過程中的循環(huán)只進不退的原則——用Tabu表鎖住退路不以局部最優(yōu)作為停止準(zhǔn)則鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能——找過的地方都記下來，不再找第二次一.導(dǎo)言（2）168TS的要素構(gòu)成禁忌表(TabuList)渴望水平函數(shù)(AspirationLevelFunction)移動規(guī)則——鄰域選優(yōu)選優(yōu)規(guī)則——保持歷史上的最優(yōu)解停止準(zhǔn)則——與GA相似一.導(dǎo)言（3）169問題的描述及鄰域的概念

TS僅用于離散優(yōu)化，排斥實優(yōu)化

二.TS的基本原理及步驟（1）170

二.TS的基本原理及步驟（2）171鄰域舉例：

X=[0,1,0,0,1,0,0] u=1, d=[0,0,1,0,0,0,0]注意：移動的意義是靈活的，目的是便于搜索。如：排序問題中一次換位可稱為一次移動，還可以定義為選一個切點，兩部分作交叉運算。二.TS的基本原理及步驟（3）172練習(xí)定義鄰域移動為位值加1或減1,對整數(shù)編碼[22353]，以下染色體是否在其鄰域內(nèi)：

[23353]，[23253]，[22355]，

[22343]，[22253]，[22344]，

是否是否否是173練習(xí)（2）定義鄰域移動為兩兩換位,對順序編碼[42351]，以下染色體是否在其鄰域內(nèi)：

[43251]，[43512]，[43351]，

[52341]，[12354]，[34251]，

是否是否否是174禁忌表的概念禁忌表的作用：防止搜索出現(xiàn)循環(huán)記錄前若干步走過的點、方向或目標(biāo)值，禁止返回表是動態(tài)更新的——把最新的解記入，最老的解從表中釋放(解禁)。表的長度稱為Tabu-Size，一般取5、7、11，表長越大分散性越好。二.TS的基本原理及步驟（4）175鄰域搜索規(guī)則每一步移動到不在T表中的鄰域中的最優(yōu)解，即若 ，則令則本次移動到最優(yōu)解鄰域搜索規(guī)則的作用：保證TS的優(yōu)良局部搜索功能二.TS的基本原理及步驟（5）176渴望水平函數(shù) 是一個取決于和的值，若有則是不受T表限制。即使，仍可取渴望水平，一般為歷史上曾經(jīng)達到的最好目標(biāo)值。二.TS的基本原理及步驟（6）177步驟：選一個初始點， ，令 ， ，迭代指標(biāo) ；若 停止，否則令 ，若

(其中NG為最大迭代數(shù))停止；注： 表示非正常終止，造成的原因：鄰域小，T表長。正常設(shè)置為(T表長度<鄰域大小)。步驟②的作用是設(shè)置循環(huán)體出口。三.TS的算法步驟（1）178若 ，令 ,更新 (當(dāng)前鄰域最優(yōu)目標(biāo)函數(shù)值)；注：步驟③的作用鄰域選優(yōu)若 ， 且 ，令

,更新C(x)；注：步驟④的作用破禁檢查三.TS的算法步驟（2）179三.TS的算法步驟（3）若 ，令，注：步驟⑤的作用選優(yōu)并記錄歷史最好點,更新渴望水平)更新T表，轉(zhuǎn)步2(存入T表中的第一個位置)180失敗出口(避免)破禁檢查初始開始更新T表停止YN停止YN若令若輸出終止出口step2step3step4step5step1鄰域移動擇優(yōu)規(guī)則181從鄰域搜索的方法看移向 中最好的解，但不與當(dāng)前解比較 是 中的最優(yōu)點，但 可能劣于四.TS可以克服局優(yōu)的分析（1）182選優(yōu)規(guī)則看始終保持歷史上的最優(yōu)解，不以當(dāng)前解為最優(yōu)從停止規(guī)則上看不以最優(yōu)判據(jù)為停止規(guī)則，而是指定最大迭代步數(shù)為停止條件，這樣不能保證最優(yōu)性。四.TS可以克服局優(yōu)的分析（2）183問題的提出由7層不同的絕緣材料構(gòu)成的一種絕緣體，應(yīng)如何排列順序，可獲得最好的絕緣性能。五.TS舉例（1）184 編碼方式：順序編碼 初始編碼：2-5-7-3-4-6-1

目標(biāo)值：極大化目標(biāo)值。鄰域定義：兩兩交換是一個鄰域移動鄰域大小：TabuSize：3 NG：5五.TS舉例（2）185初始表初始編碼：2-5-7-3-4-6-1結(jié)論：交換4和5五.TS舉例（3）移動5，467，443，622，304，1-1…………T表123186迭代1

編碼：2-4-7-3-5-6-1 ==16結(jié)論：交換1和3五.TS舉例（4）移動3，122，313，4-17，1-26，1-4…………T表14，523187迭代2

編碼：2-4-7-1-5-6-3 ==18結(jié)論：因交換1和3已在禁忌表中，故只能交換2和4五.TS舉例（5）移動1，3-22，4-47，6-64，5-75，3-9…………T表11，324，53若選擇這項 =16，渴望水平不能發(fā)生作用188迭代3

編碼：4-2-7-1-5-6-3 =14， =18結(jié)論：因渴望水平發(fā)揮作用，交換在破禁表中的4,5五.TS舉例（6）移動4，565，327，101，3-32，6-6…………T表12，421，334，5因 =20大于渴望水平=18此時渴望水平發(fā)生作用，破禁。交換4和5。 189迭代4

編碼：5-2-7-1-4-6-3 = =20結(jié)論：交換7和1五.TS舉例（7）移動7，104，3-36，3-55，4-62，6-8…………T表14，522，431，3190迭代5

編碼：5-2-1-7-4-6-3 = =20結(jié)論：迭代已到5次，得到最優(yōu)解

5-2-7-1-4-6-3和5-2-1-7-4-6-3 = =20五.TS舉例（8）191引入中長期表的目的改善TS的廣域搜索能力，TS的局域搜索能力很好，鄰域選優(yōu)快，但廣域搜索能力較差。搜索能力是TS的關(guān)鍵，采用中長期表可改善TS的廣域搜索能力。六.TS的中、長期表的使用（1）192中期表——頻數(shù)表頻數(shù)表的作用頻數(shù)表是用來記憶不同方向的移動次數(shù)，從而加以懲罰(比如兩兩交換，記錄每對交換的發(fā)生次數(shù))以提高搜索方向的多樣性。六.TS的中、長期表的使用（2）193在鄰域選優(yōu)公式中，令注：懲罰因子的取值一般應(yīng)遠小于目標(biāo)值(1%目標(biāo)值或1‰目標(biāo)值)，越大分散性越好，廣域搜索能力強，但會損壞鄰域搜索。六.TS的中、長期表的使用（3）194頻數(shù)表的記錄方法建立n×n的數(shù)組，對上半部分每做一步搜索將所有>0的數(shù)減1；對數(shù)組上半部分，給新發(fā)生的移動所對應(yīng)的數(shù)組元加上Tabu-Size;T表的下半部分，用來記頻數(shù)，每次(i,j)交換(i<j)，對應(yīng)的((j,i)+1)來記憶頻數(shù)。六.TS的中、長期表的使用（4）195頻數(shù)表的優(yōu)點：同一數(shù)組作為T表和頻數(shù)表共同使用，方便操作又節(jié)省了時間。六.TS的中、長期表的使用（5）196頻數(shù)表：Tabu-Size=7六.TS的中、長期表的使用（6）T表13，421，735，643，752，664，571，3197長期表的使用——多階段TS算法長期表的作用 長期表用來記錄每個階段的初始解，在下一階段產(chǎn)生初始解時，使之盡可能與已有的初始解有較大的距離。六.TS的中、長期表的使用（7）198圖示六.TS的中、長期表的使用（8）199函數(shù)表達式長期表的TS有很好的性能。六.TS的中、長期表的使用（9）200問題的來源1994年Icmell發(fā)表的論文，C&ORV21,No.8ComputerandOperationsResearch問題：帶有折扣資金流的約束網(wǎng)絡(luò)計劃問題(資源受限)例題見下頁七.TS表的應(yīng)用舉例（1）201n個工作組成的項目,求極小化折扣資金流的計劃七.TS表的應(yīng)用舉例（2）202H={(1,3),(1,4),(2,5),(2,6),(3,7),(5,7),(4,8),(6,8)}解：變量定義：七.TS表的應(yīng)用舉例（3）SE12687345203問題模型：

①式 ②式 ③式 ④式

⑤式脫期罰項n是最后完成的工作脫期懲罰因子204數(shù)學(xué)模型的解釋：①式折扣資金；②式每個工作只能完成1次;③式資源約束；④式工作i沒做完不允許做工作j仔細思考，以上數(shù)學(xué)表達式的下標(biāo)設(shè)計是非常精妙的尤其是③式資源約束。七.TS表的應(yīng)用舉例（5）205將以上模型簡化七.TS表的應(yīng)用舉例（6）206該式表示i在j之前這一項表示條件取和注：對于條件取和、，常規(guī)的優(yōu)化方法不能計算，但可用TS求解。207編碼方式：自然數(shù)編碼狀態(tài)：鄰域定義：鄰域大?。?n七.TS表的應(yīng)用舉例（8）208鄰域搜索規(guī)則： 中有可行解時，取可行解中目標(biāo)值最小 的鄰域解； 中無可行解時，取約束違反量最小的鄰域解七.TS表的應(yīng)用舉例（9）209TS的記憶功能——短、中、長期表要靈活使用TS相對于GA,SA是更快的算法，局域搜索能力強，但全局搜索能力較弱；改善TS的全局搜索能力，提高TS的分散性的方法用長期表八.學(xué)習(xí)TS的幾點體會（1）210加大TabuSize加大對頻數(shù)的懲罰，即增大TS仍是一種啟發(fā)式，不能保證最優(yōu)性TS的理論工作較少八.學(xué)習(xí)TS的幾點體會（2）211智能優(yōu)化方法

AI-BasedOptimizationMethodsByJunweiWangPhDNortheasternUniversityChina2007212第五章 模擬退火213第五章模擬退火一.導(dǎo)言二.退火過程和Bolzman方程三.SA的算法構(gòu)造及步驟四.計算舉例五.SA的收斂性分析六.SA的應(yīng)用舉例214模擬退火的產(chǎn)生(SA)1953年Metropolis提出原始的SA算法，未引 起反響1982年Kirkpatrick提出現(xiàn)代的SA算法，得到廣泛的應(yīng)用

一.導(dǎo)言（1）215基本思想模擬熱力學(xué)當(dāng)中的退火過程退火過程： 物體：高溫 低溫 高能狀態(tài) 低能狀態(tài)一.導(dǎo)言（2）緩慢下降216淬火：快速冷卻，使金屬處于高能狀態(tài)，較硬易斷退火：緩慢冷卻，使金屬處于低能狀態(tài)，較為柔韌

一.導(dǎo)言（3）217模擬退火在SA中的應(yīng)用在SA中將目標(biāo)函數(shù)作為能量函數(shù)模擬：初始高溫 溫度緩慢下降 終止在低溫這時能量函數(shù)達到極小，目標(biāo)函數(shù)最小一.導(dǎo)言（4）218熱力學(xué)中的退火過程 變溫物體緩慢降溫從而達到分子之間能量最低的狀態(tài)

二.退火過程和Bolzman方程（1）219二.退火過程和Bolzman方程（2）220Bolzman方程二.退火過程和Bolzman方程（3）221溫度對的影響當(dāng)很大時， ，各狀態(tài)的概率幾乎相等SA開始做廣域搜索，隨著溫度的下降 差別擴大二.退火過程和Bolzman方程（4）222當(dāng) 時，與的小差別帶來和的巨大差別例如：=90， =100，二.退火過程和Bolzman方程（5）223當(dāng) =100時二.退火過程和Bolzman方程（6）224當(dāng)=1時此時結(jié)論:

時，以概率1趨于最小能量狀態(tài)二.退火過程和Bolzman方程（7）225能量越低越穩(wěn)定?。?！

——真理物理現(xiàn)象人的生命現(xiàn)象自然科學(xué)哲學(xué)自然語言數(shù)學(xué)語言二.退火過程和Bolzman方程（8）226SA的模擬要求初始溫度足夠高降溫過程足夠慢終止溫度足夠低

三.SA的算法構(gòu)造及步驟（1）227問題的描述及要素

三.SA的算法構(gòu)造及步驟（2）228SA的計算步驟初始化,任選初始解,,給定初始溫度，終止溫度，令迭代指標(biāo) 。

注：選擇時，要足夠高，使隨機產(chǎn)生一個鄰域解， 計算目標(biāo)值增量三.SA的算法構(gòu)造及步驟（3）229若 轉(zhuǎn)步④(j比i好無條件轉(zhuǎn)移)；否則產(chǎn)生

(j比i好，有條件轉(zhuǎn)移)。

注： 高時，廣域搜索；低時，局域搜索若達到熱平衡(內(nèi)循環(huán)次數(shù)大于)轉(zhuǎn)步⑤，否則轉(zhuǎn)步②。

三.SA的算法構(gòu)造及步驟（4）230降低，若停止，否則轉(zhuǎn)步②。

注：降低的方法有以下兩種流程框圖見下頁

三.SA的算法構(gòu)造及步驟（5）231內(nèi)循環(huán)產(chǎn)生開始停止YNYN，降溫外循環(huán)設(shè)定產(chǎn)生計算YYNN232問題的提出單機極小化總流水時間的排序問題四個工作： ，求的最優(yōu)順序。

四.計算舉例（1）233預(yù)備知識：按SPT準(zhǔn)則，最優(yōu)順序為3-1-4-2四.計算舉例（2）234用SA求解這個問題狀態(tài)表達：順序編碼鄰域定義：兩兩換位定義為鄰域移動解：設(shè) 降溫過程定義為初始解：i=1-4-2-3四.計算舉例（3）235⑴

①②③注釋：①無條件轉(zhuǎn)移；②③為有條件轉(zhuǎn)移；在②③中，雖然目標(biāo)值變壞，但搜索范圍變大；是隨機產(chǎn)生的

四.計算舉例（4）236⑵①②③注釋：①有條件轉(zhuǎn)移；②為無條件轉(zhuǎn)移；在③中，停在4-3-1-2狀態(tài)，目標(biāo)值仍為109；四.計算舉例（5）237⑵①②③注釋：①②無條件轉(zhuǎn)移；在③中，停在3-1-4-2狀態(tài)，目標(biāo)值仍為92；

SA沒有歷史最優(yōu)，不會終止在最優(yōu)解，故算法一定要保持歷史最優(yōu)。四.計算舉例（6）238SA終止在最優(yōu)解上的條件：初始溫度足夠高熱平衡時間足夠長終止溫度足夠低降溫過程足夠慢 以上條件實際