計(jì)算智能與深度學(xué)習(xí) 課件 7模擬退火算法、8禁忌搜索算法

第三章模擬退火算法

智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院

2009年3.1模擬退火算法及模型

3.1.1物理退火過程

3.1.2組合優(yōu)化與物理退火的相似性

3.1.3模擬退火算法的基本思想和步驟

3.2模擬退火算法的馬氏鏈描述

3.2.1馬爾可夫鏈

3.2.2模擬退火算法與馬爾可夫鏈

3.3模擬退火算法的關(guān)鍵參數(shù)和操作的設(shè)計(jì)

3.3.1狀態(tài)產(chǎn)生函數(shù)

3.3.2狀態(tài)接受函數(shù)

3.3.3初溫

3.3.4溫度更新函數(shù)

3.3.5內(nèi)循環(huán)終止準(zhǔn)則

3.3.6外循環(huán)終止準(zhǔn)則

智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院

2009年3.4模擬退火算法的改進(jìn)

3.4.1模擬退火算法的優(yōu)缺點(diǎn)

3.4.2改進(jìn)內(nèi)容

3.4.3一種改進(jìn)的模擬退火算法3.5模擬退火算法實(shí)現(xiàn)與應(yīng)用

3.5.130城市TSP問題（d*=423.741byDBFogel）

3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極??；克服初值依賴性。

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算物理退火過程

什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。

3.1.1物理退火過程<1>0山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算數(shù)學(xué)表述

若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|；狀態(tài)空間存在超過兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D|；當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。

3.1.1物理退火過程能量最低狀態(tài)非能量最低狀態(tài)山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)固體在恒定溫度下達(dá)到熱平衡的過程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)若在溫度T，當(dāng)前狀態(tài)i→新狀態(tài)j

若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j

為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i

為當(dāng)前狀態(tài)。

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。

3.1.1物理退火過程山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算相似性比較

3.1.2組合優(yōu)化與物理退火的相似性組合優(yōu)化問題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過程Metropolis抽樣過程等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算基本步驟

給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。

3.1.3模擬退火算法的基本思想和步驟山東大學(xué)威海分校信息工程學(xué)院2009年3.1模擬退火算法及模型

智能優(yōu)化計(jì)算影響優(yōu)化結(jié)果的主要因素

給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。

3.1.3模擬退火算法的基本思想和步驟三函數(shù)兩準(zhǔn)則初始溫度山東大學(xué)威海分校信息工程學(xué)院2009年3.2模擬退火算法的馬氏鏈描述

智能優(yōu)化計(jì)算定義

3.2.1馬爾科夫鏈特性：馬氏鏈具有記憶遺忘特性，它只記憶前一時(shí)刻的狀態(tài)。山東大學(xué)威海分校信息工程學(xué)院2009年3.2模擬退火算法的馬氏鏈描述

智能優(yōu)化計(jì)算定義

一步轉(zhuǎn)移概率：

n步轉(zhuǎn)移概率：若解空間有限，稱馬爾可夫鏈為有限狀態(tài)；若，稱馬爾可夫鏈為時(shí)齊的。

3.2.1馬爾科夫鏈山東大學(xué)威海分校信息工程學(xué)院2009年3.2模擬退火算法的馬氏鏈描述

智能優(yōu)化計(jì)算模擬退火算法對(duì)應(yīng)了一個(gè)馬爾可夫鏈

模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法；若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時(shí)齊算法。分析收斂性

3.2.2模擬退火算法與馬爾科夫鏈山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算原則

產(chǎn)生的候選解應(yīng)遍布全部解空間方法

在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生

3.3.1狀態(tài)產(chǎn)生函數(shù)山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算原則

(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；

(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；

(3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法

具體形式對(duì)算法影響不大一般采用min[1,exp(-?C/t)]

3.3.2狀態(tài)接受函數(shù)山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算收斂性分析

通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時(shí)難以得到精確的參數(shù)；初溫應(yīng)充分大；實(shí)驗(yàn)表明

初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間；

3.3.3初溫山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算方法

（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗(yàn)公式。

3.3.3初溫山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)數(shù)值計(jì)算估計(jì)方法示例智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算時(shí)齊算法的溫度下降函數(shù)

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。

3.3.4溫度更新函數(shù)山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算非時(shí)齊模擬退火算法

每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解時(shí)齊算法——常用的Metropolis抽樣穩(wěn)定準(zhǔn)則

（1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；（2）連續(xù)若干步的目標(biāo)值變化較?。唬?）按一定的步數(shù)抽樣（固定長(zhǎng)度）。 （4）有接受和拒絕的比率控制跌代步數(shù)（比如給定一個(gè)跌代步長(zhǎng)上限U和接受比率指標(biāo)R）

3.3.5內(nèi)循環(huán)終止準(zhǔn)則山東大學(xué)威海分校信息工程學(xué)院2009年3.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)智能優(yōu)化計(jì)算常用方法

（1）設(shè)置終止溫度的閾值；（2）設(shè)置外循環(huán)迭代次數(shù)；（3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變；（4）概率分析方法(接受概率控制法）。

3.3.6外循環(huán)終止準(zhǔn)則山東大學(xué)威海分校信息工程學(xué)院2009年3.4模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算模擬退火算法的優(yōu)點(diǎn)

質(zhì)量高；初值魯棒性強(qiáng)；簡(jiǎn)單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn)

由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長(zhǎng)。

3.4.1模擬退火算法的優(yōu)缺點(diǎn)山東大學(xué)威海分校信息工程學(xué)院2009年3.4模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的可行方案

（1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)；（2）設(shè)計(jì)高效的退火歷程；（3）避免狀態(tài)的迂回搜索；（4）采用并行搜索結(jié)構(gòu)；（5）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式；（6）選擇合適的初始狀態(tài)；（7）設(shè)計(jì)合適的算法終止準(zhǔn)則。

3.4.2改進(jìn)內(nèi)容山東大學(xué)威海分校信息工程學(xué)院2009年3.4模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的方式

（1）增加升溫或重升溫過程，避免陷入局部極?。唬?）增加記憶功能（記憶“Bestsofar”狀態(tài)）；（3）增加補(bǔ)充搜索過程（以最優(yōu)結(jié)果為初始解）；（4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)；（5）結(jié)合其它搜索機(jī)制的算法；（6）上述各方法的綜合。

3.4.2改進(jìn)內(nèi)容山東大學(xué)威海分校信息工程學(xué)院2009年3.4模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的思路

（1）記錄“Bestsofar”狀態(tài)，并即時(shí)更新；（2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù)m1步保持不變則認(rèn)為Metropolis抽樣穩(wěn)定，若連續(xù)m2次退溫過程中所得最優(yōu)解不變則認(rèn)為算法收斂。

3.4.3一種改進(jìn)的模擬退火算法山東大學(xué)威海分校信息工程學(xué)院2009年3.4模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的退火過程

（1）給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為s(0)=s，i=p=0；（2）令t=ti，以t，s*和s(i)調(diào)用改進(jìn)的抽樣過程，返回其所得最優(yōu)解s*’和當(dāng)前狀態(tài)s’(k)，令當(dāng)前狀態(tài)s(i)=s’(k)；（3）判斷C(s*)<C(s*’)?若是，則令p=p+1；否則，令s*=s*’，p=0；（4）退溫ti+1=update(ti)，令i=i+1；（5）判斷p>m2?若是，則轉(zhuǎn)第(6)步；否則，返回第(2)步；（6）以最優(yōu)解s*作為最終解輸出，停止算法。

3.4.3一種改進(jìn)的模擬退火算法山東大學(xué)威海分校信息工程學(xué)院2009年3.4模擬退火算法的改進(jìn)智能優(yōu)化計(jì)算改進(jìn)的抽樣過程

（1）令k=0時(shí)的初始當(dāng)前狀態(tài)為s’(0)=s(i)，q=0；（2）由狀態(tài)s通過狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新狀態(tài)s’，計(jì)算增量?C’=C(s’)-C(s)；（3）若?C’<0，則接受s’作為當(dāng)前解，并判斷C(s*’)>C(s’)?若是，則令s*’=s’，q=0；否則，令q=q+1。若?C’>0，則以概率exp(-?C’/t)接受s’作為下一當(dāng)前狀態(tài)；（4）令k=k+1，判斷q>m1?若是，則轉(zhuǎn)第(5)步；否則，返回第(2)步；（5）將當(dāng)前最優(yōu)解s*’和當(dāng)前狀態(tài)s’(k)返回改進(jìn)退火過程。

3.4.3一種改進(jìn)的模擬退火算法山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算

3.5.130城市TSP問題（d*=423.741byDBFogel）

TSPBenchmark問題

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算算法流程

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算初始溫度的計(jì)算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)（1）互換操作，隨機(jī)交換兩個(gè)城市的順序；（2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序；（3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。

3.5.130城市TSP問題（d*=423.741byDBFogel）

283591467283591467283591467281593467283419567235981467山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算參數(shù)設(shè)定

截止溫度tf=0.01;

退溫系數(shù)alpha=0.90;

內(nèi)循環(huán)次數(shù)L=200*CityNum;

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過程

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行結(jié)果

3.5.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算換熱器模型兩級(jí)管殼式換熱器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高度非線性，其目標(biāo)函數(shù)通常是多峰(谷)的，具有很多局部最優(yōu)解。

3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算優(yōu)化目標(biāo)以換熱器系統(tǒng)的總費(fèi)用年值最小作為優(yōu)化設(shè)計(jì)的目標(biāo)。其中，f1(X)是兩級(jí)換熱器的初始投資，f2(X)是兩級(jí)換熱器年維護(hù)費(fèi)(包括除垢、保養(yǎng)、維修等)，f3(X)是冷卻水資源費(fèi)以及管程壓降能耗費(fèi)，f4(X)是殼程壓降能耗費(fèi)。

3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算優(yōu)化目標(biāo)經(jīng)過分析，優(yōu)化問題的獨(dú)立變量共12個(gè)，分別是一級(jí)換熱器煤油出口溫度t2、冷卻水流量G1、兩個(gè)換熱器的管內(nèi)徑d1，d2和管間距S1，S2、折流板間距B1，B2、折流板開口角α1，α2、單管長(zhǎng)度L1，L2。

3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算應(yīng)用模擬退火算法解決優(yōu)化設(shè)計(jì)狀態(tài)表示——12個(gè)變量的實(shí)數(shù)表示；初始溫度——100；結(jié)束溫度——0.001；狀態(tài)產(chǎn)生函數(shù)——，η為擾動(dòng)幅度參數(shù)，ξ為隨機(jī)擾動(dòng)變量，隨機(jī)擾動(dòng)可服從柯西、高斯、均勻分布。降溫因子——0.98；馬氏鏈長(zhǎng)度——1200。

3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用山東大學(xué)威海分校信息工程學(xué)院2009年3.5模擬退火算法的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算優(yōu)化結(jié)果優(yōu)化目標(biāo)值——0.25565E＋06

獨(dú)立變量取值——

3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用t2℃G1Kg/sd1mmS1mmB1mα1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2mα2弧度L2m5.9423416.7793527.740120.729532.199285.78314山東大學(xué)威海分校信息工程學(xué)院2009年第三章結(jié)束智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院2009年第二章禁忌搜索算法

智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

2.1.1鄰域的概念

2.1.2局部搜索算法

2.1.3局部搜索示例

2.2禁忌搜索

2.2.1算法的主要思路

2.2.2禁忌搜索示例2.3禁忌搜索的關(guān)鍵參數(shù)和操作

2.3.1變化因素

2.3.2禁忌表

2.3.3其他

2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

2.4.130城市TSP問題（d*=423.741byDBFogel）

2.4.2基于禁忌搜索算法的系統(tǒng)辨識(shí)智能優(yōu)化計(jì)算山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算函數(shù)優(yōu)化問題中

在距離空間中，通常的鄰域定義是以一點(diǎn)為中心的一個(gè)球體；組合優(yōu)化問題中

2.1.1鄰域的概念

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算例

TSP問題解的一種表示方法為D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列}，定義它的鄰域映射為2－opt，即x中的兩個(gè)元素進(jìn)行對(duì)換，N(x)中共包含x的Cn2=n(n-1)/2個(gè)鄰居和x本身。例如：x=(1,2,3,4)，則C42=6，N(x)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}2.1.1鄰域的概念

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算例

TSP問題解的鄰域映射可由2－opt，推廣到k－opt，即對(duì)k個(gè)元素按一定規(guī)則互換。鄰域概念的重要性

鄰域的構(gòu)造依賴于決策變量的表示，鄰域的結(jié)構(gòu)在現(xiàn)代優(yōu)化算法中起重要的作用。2.1.1鄰域的概念

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算STEP1

選定一個(gè)初始可行解x0，記錄當(dāng)前最優(yōu)解xbest:=x0,T=N(xbest)；STEP2

當(dāng)T\{xbest}=Φ時(shí)，或滿足其他停止運(yùn)算準(zhǔn)則時(shí)，輸出計(jì)算結(jié)果，停止運(yùn)算；否則，從T中選一集合S，得到S中的最好解xnow；若f(xnow)<f(xbest)，則xbest:=xnow

，T=N(xbest)；否則T:=T\S；重復(fù)STEP2。2.1.2局部搜索算法

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱TSP問題

初始解為xbest=(ABCDE)，f(xbest)=45，定義鄰域映射為對(duì)換兩個(gè)城市位置的2-opt，選定A城市為起點(diǎn)。2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱TSP問題方法1：全鄰域搜索

第1步

N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，對(duì)應(yīng)目標(biāo)函數(shù)為f(x)={45,43,45,60,60,59,44}

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

ABCDE山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱TSP問題方法1：全鄰域搜索

第2步

N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，對(duì)應(yīng)目標(biāo)函數(shù)為f(x)={43,45,44,59,59,58,43}

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱TSP問題方法2：一步隨機(jī)搜索

第1步

從N(xbest)中隨機(jī)選一點(diǎn)，如xnow=(ACBDE)，對(duì)應(yīng)目標(biāo)函數(shù)為f(xnow)=43<45

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱TSP問題方法2：一步隨機(jī)搜索

第2步

從N(xbest)中又隨機(jī)選一點(diǎn)，如xnow=(ADBCE)，對(duì)應(yīng)目標(biāo)函數(shù)為f(xnow)=44>43

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱TSP問題簡(jiǎn)單易行，但無法保證全局最優(yōu)性；局部搜索主要依賴起點(diǎn)的選取和鄰域的結(jié)構(gòu)；為了得到好的解，可以比較不同的鄰域結(jié)構(gòu)和不同的初始點(diǎn)；如果初始點(diǎn)的選擇足夠多，總可以計(jì)算出全局最優(yōu)解。2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題解（solution)的表示：向量五個(gè)任務(wù)分到三臺(tái)計(jì)算機(jī)上的一種分配方安：2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題鄰域（Neighborhood）定義我們定義兩種鄰域映射：1、單向移動(dòng)（one-waymoveortransfer):重新分配一個(gè)任務(wù)從其當(dāng)前機(jī)器到另一臺(tái)機(jī)器。2、雙向移動(dòng)（two-wayexchange):交換分配于兩臺(tái)不同機(jī)器上的任務(wù)。2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題鄰域解（Neighbor）評(píng)估（evaluation）對(duì)于目標(biāo)1最小化執(zhí)行與通信代價(jià)之和。任務(wù)重分配收益（reassignmentgain)就是代價(jià)（cost）的減少。

這里xip表示第i個(gè)任務(wù)在第p臺(tái)機(jī)器上的執(zhí)行代價(jià)（時(shí)間）2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題鄰域解（Neighbor）評(píng)估（evaluation）重新分配任務(wù)i之后，需要更新（update）第i個(gè)任務(wù)的鄰接任務(wù)的重分配收益：2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題鄰域解（Neighbor）評(píng)估（evaluation）重新分配任務(wù)i之后，需要更新（update）第i個(gè)任務(wù)的鄰接任務(wù)的重分配收益：2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題鄰域解（Neighbor）評(píng)估（evaluation）重新分配任務(wù)i之后，需要更新（update）第i個(gè)任務(wù)的鄰接任務(wù)的重分配收益：2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題鄰域解（Neighbor）評(píng)估（evaluation）重新分配任務(wù)i之后，需要更新（update）第i個(gè)任務(wù)的的重分配收益：2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題約束懲罰收益？2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.1局部搜索

智能優(yōu)化計(jì)算TAP問題對(duì)于目標(biāo)2，最小化周轉(zhuǎn)時(shí)間（turnaroundtime)或者說最小化完成時(shí)間（completiontime)

鄰域結(jié)構(gòu)的定義：分流負(fù)載最終的機(jī)器（themostloadedmachine,i.e.criticalmachine):transferandexchange。2.1.3局部搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算算法的提出

禁忌搜索（Tabusearch）是局部鄰域搜索算法的推廣，F(xiàn)redGlover在1986年提出這個(gè)概念，進(jìn)而形成一套完整算法。算法的特點(diǎn)禁忌——禁止重復(fù)前面的工作。跳出局部最優(yōu)點(diǎn)。2.2.1算法的主要思路

/~glover/山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

初始解x0=(ABCD)，f(x0)=4，鄰域映射為兩個(gè)城市順序?qū)Q的2－opt，始、終點(diǎn)都是A城市。2.2.2禁忌搜索示例

山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第1步解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x0)=42.2.2禁忌搜索示例

ABCDBCDABC對(duì)換評(píng)價(jià)值CD4.5BC7.5BD8?山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第2步解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x1)=4.52.2.2禁忌搜索示例

ABDCBCDABC3對(duì)換評(píng)價(jià)值CD4.5BC3.5BD4.5?T山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第3步解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x2)=3.52.2.2禁忌搜索示例

ACDBBCDAB3C2對(duì)換評(píng)價(jià)值CD8BC4.5BD7.5?TT山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第4步解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x3)=7.5

禁忌長(zhǎng)度的選取2.2.2禁忌搜索示例

ACBDBCDAB23C1對(duì)換評(píng)價(jià)值CD4.5BC4.5BD3.5TTT山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第4步（如果減小禁忌長(zhǎng)度）解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x3)=7.52.2.2禁忌搜索示例

ACBDBCDAB12C0對(duì)換評(píng)價(jià)值CD4.5BC4.5BD3.5?TT山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第5步解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x4)=4.52.2.2禁忌搜索示例

ADBCBCDAB01C2對(duì)換評(píng)價(jià)值CD7.5BC8BD4.5?TT山東大學(xué)威海分校信息工程學(xué)院20092.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱TSP問題

第6步解的形式禁忌對(duì)象及長(zhǎng)度候選解

f(x5)=82.2.2禁忌搜索示例

ADCBBCDAB20C1對(duì)換評(píng)價(jià)值CD3.5BC4.5BD4?TT山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌表的主要指標(biāo)（兩項(xiàng)指標(biāo)）禁忌對(duì)象：禁忌表中被禁的那些變化元素禁忌長(zhǎng)度：禁忌的步數(shù)狀態(tài)變化（三種變化）解的簡(jiǎn)單變化解向量分量的變化目標(biāo)值變化

2.3.1變化因素

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算解的簡(jiǎn)單變化

2.3.1變化因素

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算向量分量的變化

設(shè)原有的解向量為(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本變化為

(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)

即只有第i個(gè)分量發(fā)生變化。也包含多個(gè)分量變化的情形。2.3.1變化因素

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算目標(biāo)值的變化

目標(biāo)值的變化隱含著解集合的變化。2.3.1變化因素

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況1：禁忌對(duì)象為簡(jiǎn)單的解變化禁忌長(zhǎng)度為4，從2－opt鄰域中選出最佳的5個(gè)解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況1：禁忌對(duì)象為簡(jiǎn)單的解變化第1步——

xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況1：禁忌對(duì)象為簡(jiǎn)單的解變化第2步——

xnow=(ACBDE)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。2.3.2禁忌表

xnext=(ACBED)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況1：禁忌對(duì)象為簡(jiǎn)單的解變化第3步——

xnow=(ACBED)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)}Can_N(xnow)={(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)}。2.3.2禁忌表

xnext=(ABCED)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況1：禁忌對(duì)象為簡(jiǎn)單的解變化第4步——

xnow=(ABCED)，f(xnow)=44，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)，(ABCED;44)}Can_N(xnow)={(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)}。2.3.2禁忌表

xnext=(AECBD)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況1：禁忌對(duì)象為簡(jiǎn)單的解變化第5步——

xnow=(AECBD)，f(xnow)=44，H={(ACBDE;43)，(ACBED;43)，(ABCED;44)，(AECBD;44)}Can_N(xnow)={(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)}。2.3.2禁忌表

xnext=(AEDBC)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況2：禁忌對(duì)象為分量變化禁忌長(zhǎng)度為3，從2－opt鄰域中選出最佳的5個(gè)解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況2：禁忌對(duì)象為分量變化第1步——

xnow=(ABCDE)，f(xnow)=45，H=ΦCan_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況2：禁忌對(duì)象為分量變化第2步——

xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N(xnow)={(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}。2.3.2禁忌表

xnext=(ACBED)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況2：禁忌對(duì)象為分量變化第3步——

xnow=(ACBED)，f(xnow)=43，H={(B,C)，(D,E)}Can_N(xnow)={(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)}。2.3.2禁忌表

xnext=(AEBCD)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況3：禁忌對(duì)象為目標(biāo)值變化禁忌長(zhǎng)度為3，從2－opt鄰域中選出最佳的5個(gè)解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況3：禁忌對(duì)象為目標(biāo)值變化第1步——

xnow=(ABCDE)，f(xnow)=45，H={45}Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

情況3：禁忌對(duì)象為目標(biāo)值變化第2步——

xnow=(ACBDE)，f(xnow)=43，H={45，43}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。2.3.2禁忌表

xnext=(ADBCE)山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌對(duì)象的選取

解的簡(jiǎn)單變化比解的分量變化和目標(biāo)值變化的受禁范圍要小，可能造成計(jì)算時(shí)間的增加，但也給予了較大的搜索范圍；解分量的變化和目標(biāo)值變化的禁忌范圍大，減少了計(jì)算時(shí)間，可能導(dǎo)致陷在局部最優(yōu)點(diǎn)。2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌長(zhǎng)度的選取

（1）t可以為常數(shù)，易于實(shí)現(xiàn)；（2），t是可以變化的數(shù)，tmin和tmax是確定的。

tmin和tmax根據(jù)問題的規(guī)模確定，t的大小主要依據(jù)實(shí)際問題、實(shí)驗(yàn)和設(shè)計(jì)者的經(jīng)驗(yàn)。（3）tmin和tmax的動(dòng)態(tài)選擇。2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算禁忌長(zhǎng)度的選取禁忌長(zhǎng)度過短，一旦陷入局部最優(yōu)點(diǎn)，出現(xiàn)循環(huán)無法跳出；禁忌長(zhǎng)度過長(zhǎng)，造成計(jì)算時(shí)間較大，也可能造成計(jì)算無法繼續(xù)下去。（例）2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算特赦（藐視）原則（1）基于評(píng)價(jià)值的規(guī)則，若出現(xiàn)一個(gè)解的目標(biāo)值好于前面任何一個(gè)最佳候選解，可特赦；（2）基于最小錯(cuò)誤的規(guī)則，若所有對(duì)象都被禁忌，特赦一個(gè)評(píng)價(jià)值最小的解；（3）基于影響力的規(guī)則，可以特赦對(duì)目標(biāo)值影響大的對(duì)象。2.3.2禁忌表

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算候選集合的確定（1）從鄰域中選擇若干目標(biāo)值最佳的鄰居入選；（2）在鄰域中的一部分鄰居中選擇若干目標(biāo)值最佳的狀態(tài)入選；（3）隨機(jī)選取。2.3.3其他

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算評(píng)價(jià)函數(shù)（1）直接評(píng)價(jià)函數(shù)，通過目標(biāo)函數(shù)的運(yùn)算得到評(píng)價(jià)函數(shù)；（2）間接評(píng)價(jià)函數(shù)，構(gòu)造其他評(píng)價(jià)函數(shù)替代目標(biāo)函數(shù)，應(yīng)反映目標(biāo)函數(shù)的特性，減少計(jì)算復(fù)雜性。2.3.3其他

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算記憶頻率信息根據(jù)記憶的頻率信息（禁忌次數(shù)等）來控制禁忌參數(shù)（禁忌長(zhǎng)度等）。例如：如果一個(gè)元素或序列重復(fù)出現(xiàn)或目標(biāo)值變化很小，可增加禁忌長(zhǎng)度以避開循環(huán)；如果一個(gè)最佳目標(biāo)值出現(xiàn)頻率很高，則可以終止計(jì)算認(rèn)為已達(dá)到最優(yōu)值。2.3.3其他

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算記憶頻率信息可記錄的信息：（1）靜態(tài)頻率信息：解、對(duì)換或目標(biāo)值在計(jì)算中出現(xiàn)的頻率；（2）動(dòng)態(tài)頻率信息：從一個(gè)解、對(duì)換或目標(biāo)值到另一個(gè)解、對(duì)換或目標(biāo)值的變化趨勢(shì)。2.3.3其他

山東大學(xué)威海分校信息工程學(xué)院20092.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算終止規(guī)則（1）確定步數(shù)終止，無法保證解的效果，應(yīng)記錄當(dāng)前最優(yōu)解；（2）頻率控制原則，當(dāng)某一個(gè)解、目標(biāo)值或元素序列的頻率超過一個(gè)給定值時(shí)，終止計(jì)算；（3）目標(biāo)控制原則，如果在一個(gè)給定步數(shù)內(nèi)，當(dāng)前最優(yōu)值沒有變化，可終止計(jì)算。2.3.3其他

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算TSPBenchmark問題

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;4502.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算算法流程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算初始條件禁忌長(zhǎng)度為50

從2－opt鄰域中隨機(jī)選擇200個(gè)鄰域解，選出其中100個(gè)最佳解組成候選集終止步數(shù)20002.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.130城市TSP問題（d*=423.741byDBFogel）

山東大學(xué)威海分校信息工程學(xué)院20092.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算運(yùn)行過程

2.4.1