華中科技大學(xué)工程優(yōu)化設(shè)計(jì)-啟發(fā)式方法

1、工程優(yōu)化設(shè)計(jì)內(nèi)容提要 工程優(yōu)化問(wèn)題建模工程優(yōu)化問(wèn)題建模 優(yōu)化數(shù)學(xué)理論優(yōu)化數(shù)學(xué)理論 一維搜索方法一維搜索方法 無(wú)約束問(wèn)題直接搜索方法無(wú)約束問(wèn)題直接搜索方法 無(wú)約束問(wèn)題間接接搜索方法無(wú)約束問(wèn)題間接接搜索方法 約束問(wèn)題直接搜索方法約束問(wèn)題直接搜索方法 線性規(guī)劃與二次規(guī)劃問(wèn)題求解線性規(guī)劃與二次規(guī)劃問(wèn)題求解 約束問(wèn)題間接搜索方法約束問(wèn)題間接搜索方法 啟發(fā)式算法啟發(fā)式算法 優(yōu)化軟件系統(tǒng)優(yōu)化軟件系統(tǒng)啟發(fā)式方法啟發(fā)式方法啟發(fā)式方法: : 從其他事物發(fā)展變化規(guī)律中受到啟發(fā)，模仿它們從其他事物發(fā)展變化規(guī)律中受到啟發(fā)，模仿它們變化過(guò)程，將它們的變化規(guī)則引入優(yōu)化搜索過(guò)程中。變化過(guò)程，將它們的變化規(guī)則引入優(yōu)化搜索過(guò)程中

2、。典型的方法有：典型的方法有：TabuTabu搜索法搜索法模擬退火方法模擬退火方法遺傳算法遺傳算法1.1. 人工神經(jīng)網(wǎng)絡(luò)方法人工神經(jīng)網(wǎng)絡(luò)方法基本思想基本思想 在可行區(qū)域中隨機(jī)地在可行區(qū)域中隨機(jī)地N N個(gè)點(diǎn)，又在個(gè)點(diǎn)，又在N N點(diǎn)中取點(diǎn)中取p p個(gè)較個(gè)較小目標(biāo)值的點(diǎn)，這小目標(biāo)值的點(diǎn)，這p p個(gè)點(diǎn)所處的區(qū)域作為逼近最優(yōu)解一個(gè)新個(gè)點(diǎn)所處的區(qū)域作為逼近最優(yōu)解一個(gè)新的、縮小了的范圍。如此下去，使此范圍不斷縮小。的、縮小了的范圍。如此下去，使此范圍不斷縮小。啟發(fā)式方法一。隨機(jī)實(shí)驗(yàn)法（一。隨機(jī)實(shí)驗(yàn)法（Monte-Carlo方法）方法）算法：算法：1.1.置初始置初始D= =a1,b1a2,b2 an,bn；

3、2.2.生成隨機(jī)數(shù)生成隨機(jī)數(shù)rik和點(diǎn)：和點(diǎn)：xik=ai+rik(bi-ai),滿足滿足g(xk)0, k=1,2,N.3. 計(jì)算計(jì)算f(xk), k=1,2,3,N. 按按f(xk)從小到大排列從小到大排列xk. 取前取前p個(gè)個(gè)xk， k=1,2,p.4. 計(jì)算計(jì)算5. 如果如果 ，結(jié)束，輸出，結(jié)束，輸出x1, f(x1)。6. 否則，否則， 設(shè)設(shè) ,轉(zhuǎn)（轉(zhuǎn)（2）。）。啟發(fā)式方法2/112111)( ;,.,2 , 1,pjijipipjjipixxnixxiiiiiixbxa3,3i隨機(jī)實(shí)驗(yàn)法（隨機(jī)實(shí)驗(yàn)法（Monte-Carlo方法）方法）算法分析：算法分析：1.1.鄰域大小變化。鄰域大

4、小變化。2.2.鄰域（解范圍）逐漸縮小，鄰域（解范圍）逐漸縮小，鄰域位置跳動(dòng)鄰域位置跳動(dòng)。3.3.基于整體分布狀況，選擇新鄰域位置。基于整體分布狀況，選擇新鄰域位置。啟發(fā)式方法隨機(jī)實(shí)驗(yàn)法（隨機(jī)實(shí)驗(yàn)法（Monte-Carlo方法）方法）算法思想：算法思想：對(duì)于一當(dāng)前點(diǎn)，確定其鄰域集合。如果鄰對(duì)于一當(dāng)前點(diǎn)，確定其鄰域集合。如果鄰域集合中有更好的點(diǎn)，將當(dāng)前點(diǎn)移至此點(diǎn)，否則，當(dāng)域集合中有更好的點(diǎn)，將當(dāng)前點(diǎn)移至此點(diǎn)，否則，當(dāng)前點(diǎn)為局部最優(yōu)點(diǎn)。前點(diǎn)為局部最優(yōu)點(diǎn)。啟發(fā)式方法二。下山法二。下山法xcxn算法：算法：1.1.置置t=0, xt=0, xmaxmax=x=x0 0, f, fmaxmax=;=;

5、2. 2.置置local=FALSE, local=FALSE, 隨機(jī)取隨機(jī)取x xc c, ,計(jì)算計(jì)算f(xf(xc c);); 3. 3.選選p p個(gè)鄰域點(diǎn)，取最小點(diǎn)個(gè)鄰域點(diǎn)，取最小點(diǎn)x xn n; ; 4. 如果如果f(xc)f(xn), xc=xn;轉(zhuǎn)（轉(zhuǎn)（3）。）。 5. 否則，否則，local=TRUElocal=TRUE，t=t+1;t=t+1; 6. 如果如果 f(xf(xc c)f)fmaxmax, ,則則 x xmaxmax=x=xc c,f,fmaxmax=f(x=f(xc c) )； 7. 7.如果如果tMAX,t1, 1-0.0-1, 1-0.例：例：10011001

6、的鄰域的鄰域= = 0001 0001，11011101 1011 1011，1000 1000 下山法下山法算法分析：算法分析：1.1.鄰域大小不變。鄰域大小不變。2.2.鄰域連續(xù)移動(dòng)。鄰域連續(xù)移動(dòng)。3.3.基于局部變化趨勢(shì)，選擇新鄰域所處（搜索）方向?；诰植孔兓厔?shì)，選擇新鄰域所處（搜索）方向。啟發(fā)式方法下山法下山法算法思想：算法思想：對(duì)于一當(dāng)前點(diǎn)，確定其鄰域集合。在鄰域?qū)τ谝划?dāng)前點(diǎn)，確定其鄰域集合。在鄰域集合中選一點(diǎn)集合中選一點(diǎn), ,如果該如果該點(diǎn)點(diǎn)更好，將當(dāng)前點(diǎn)移至此點(diǎn)，否更好，將當(dāng)前點(diǎn)移至此點(diǎn)，否則，仍然則，仍然以一定的概率將當(dāng)前點(diǎn)轉(zhuǎn)移到此以一定的概率將當(dāng)前點(diǎn)轉(zhuǎn)移到此( (較差較差

7、) )點(diǎn)。點(diǎn)。啟發(fā)式方法三。模擬退火算法（三。模擬退火算法（Simulated Annealing）xcxnPr(E=E(r)=e-E(r)/kT/ZE=1E=2E=3E=4穩(wěn)態(tài)能量T=200.2690.2560.2430.2322.378T=50.3290.2690.2210.1812.254T=0.5 0.8650.1170.0160.0021.55當(dāng)溫度較小時(shí)當(dāng)溫度較小時(shí), ,分子集合處于最小能量狀態(tài)概率增大分子集合處于最小能量狀態(tài)概率增大! !當(dāng)當(dāng)T T充分小時(shí)充分小時(shí), ,以較大的概率處于小的能量狀態(tài)以較大的概率處于小的能量狀態(tài)!啟發(fā)式方法退火過(guò)程退火過(guò)程能量能量f(X)大大能量能量

8、f(X)小小物質(zhì)表面物質(zhì)表面狀態(tài)狀態(tài) X1物質(zhì)表面物質(zhì)表面狀態(tài)狀態(tài) X2物質(zhì)表面物質(zhì)表面狀態(tài)狀態(tài) X3溫度下降足夠慢時(shí)溫度下降足夠慢時(shí),X,X1 1,X,X2 2,X,X3 3為穩(wěn)定狀態(tài)為穩(wěn)定狀態(tài). .它們是對(duì)應(yīng)溫度的穩(wěn)態(tài)能量狀態(tài)它們是對(duì)應(yīng)溫度的穩(wěn)態(tài)能量狀態(tài). .啟發(fā)式方法退火過(guò)程退火過(guò)程能量能量f(X)大大能量能量f(X)小小物質(zhì)表面物質(zhì)表面狀態(tài)狀態(tài) X1物質(zhì)表面物質(zhì)表面狀態(tài)狀態(tài) X2物質(zhì)表面物質(zhì)表面狀態(tài)狀態(tài) X3溫度下降溫度下降過(guò)快過(guò)快時(shí)時(shí),X,X1 1,X,X2 2,X,X3 3為非穩(wěn)定狀態(tài)為非穩(wěn)定狀態(tài). .它們它們不是不是對(duì)應(yīng)溫度的穩(wěn)態(tài)能量狀態(tài)對(duì)應(yīng)溫度的穩(wěn)態(tài)能量狀態(tài). .特別是特別是X

9、 X3 3, ,還夾雜著前面還夾雜著前面X X2 2與與X X1 1的表面特性的表面特性, ,因?yàn)橛行┑胤降哪芰窟€沒(méi)有充分釋放因?yàn)橛行┑胤降哪芰窟€沒(méi)有充分釋放. .啟發(fā)式方法三。模擬退火算法（三。模擬退火算法（Simulated Annealing）T狀態(tài)狀態(tài)X X優(yōu)化目標(biāo)優(yōu)化目標(biāo)f(X)f(X) E X X1 1X X2 2T T代表穩(wěn)態(tài)下一次狀態(tài)遷移時(shí)允許的能量變化幅度代表穩(wěn)態(tài)下一次狀態(tài)遷移時(shí)允許的能量變化幅度, ,所以所以, , T T充分大時(shí)充分大時(shí), ,系統(tǒng)處于各個(gè)狀態(tài)概率相同系統(tǒng)處于各個(gè)狀態(tài)概率相同; ; T T小時(shí)小時(shí), ,由于變遷范圍限制由于變遷范圍限制, ,系統(tǒng)處于各個(gè)狀態(tài)概

10、率則不相同系統(tǒng)處于各個(gè)狀態(tài)概率則不相同. .啟發(fā)式方法三。模擬退火算法（三。模擬退火算法（Simulated Annealing）T1區(qū)域區(qū)域區(qū)域區(qū)域區(qū)域區(qū)域由于區(qū)域較大且整體較低，第一次穩(wěn)態(tài)點(diǎn)以較大概率落入由于區(qū)域較大且整體較低，第一次穩(wěn)態(tài)點(diǎn)以較大概率落入此區(qū)域該區(qū)域稱為穩(wěn)態(tài)區(qū)域此區(qū)域該區(qū)域稱為穩(wěn)態(tài)區(qū)域. .啟發(fā)式方法三。模擬退火算法（三。模擬退火算法（Simulated Annealing）T1T2區(qū)域區(qū)域區(qū)域區(qū)域區(qū)域區(qū)域如果第一退火時(shí)間不夠長(zhǎng)，第一次穩(wěn)態(tài)點(diǎn)落入整體最優(yōu)區(qū)域的概率較小如果第一退火時(shí)間不夠長(zhǎng)，第一次穩(wěn)態(tài)點(diǎn)落入整體最優(yōu)區(qū)域的概率較小, ,落入次優(yōu)區(qū)域的概率增大落入次優(yōu)區(qū)域的概率

11、增大. .啟發(fā)式方法三。模擬退火算法（三。模擬退火算法（Simulated Annealing）T1T2區(qū)域區(qū)域區(qū)域區(qū)域區(qū)域區(qū)域降低溫度，第二次穩(wěn)態(tài)點(diǎn)以較大概率落入上次穩(wěn)態(tài)區(qū)域中降低溫度，第二次穩(wěn)態(tài)點(diǎn)以較大概率落入上次穩(wěn)態(tài)區(qū)域中較低的子區(qū)域較低的子區(qū)域算法：算法：1.1.置置t=0, T=Tt=0, T=T0 0,x,xc c=x=x0 0, ,計(jì)算計(jì)算f(xf(xc c);); 2. 2.置置steady=FALSE;steady=FALSE; 3. 3.選選1 1個(gè)鄰域點(diǎn)，個(gè)鄰域點(diǎn)，x xn n=generate(x=generate(xc c);); 4. 如果如果f(xf(xc c)f

12、(x)f(xn n), x), xc c=x=xn n; ; 否則，如果否則，如果 random(0,1)random(0,1)exp-(f(xexp-(f(xn n)-f(x)-f(xc c)/T)/T x xc c=x=xn n; ; 5. 如果如果抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則不滿足，轉(zhuǎn)（不滿足，轉(zhuǎn)（3）；）； 6. 否則，否則，steady=TRUE;steady=TRUE; 7. 7.退溫退溫 T=g(T,t),T=g(T,t),換代換代t=t+1; 8. 如果如果退火結(jié)束準(zhǔn)則退火結(jié)束準(zhǔn)則不滿足，轉(zhuǎn)（不滿足，轉(zhuǎn)（2）；9.9.否則，輸出否則，輸出x xc c,f(x,f(xc c) )，結(jié)

13、束。結(jié)束。啟發(fā)式方法t:t:迭代的代數(shù)迭代的代數(shù); T:; T:溫度，隨溫度，隨t t下降下降. .模擬退火算法（模擬退火算法（Simulated Annealing）1.0f=e-x/T關(guān)鍵要素：關(guān)鍵要素：1.1.狀態(tài)產(chǎn)生函數(shù)狀態(tài)產(chǎn)生函數(shù)Generate(xGenerate(xc c) )：鄰域結(jié)構(gòu)：鄰域結(jié)構(gòu)+ +挑選概率分布。挑選概率分布。2.2.狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)：T T一定時(shí)，下降接受概率要大于上升接受概率。一定時(shí)，下降接受概率要大于上升接受概率。 exp(-exp(-f/T)f/T) T T減小時(shí)，減小時(shí)，上升接受概率逐漸減小。上升接受概率逐漸減小。 T T為零時(shí)，只接受下降狀

14、態(tài)。為零時(shí)，只接受下降狀態(tài)。3. 初溫初溫T0：初溫越大，獲得全局解可能性性越大，但計(jì)算量也：初溫越大，獲得全局解可能性性越大，但計(jì)算量也 大。經(jīng)驗(yàn)做法：均勻抽樣一組狀態(tài)，取目標(biāo)值方差。大。經(jīng)驗(yàn)做法：均勻抽樣一組狀態(tài)，取目標(biāo)值方差。4. 溫度更新函數(shù)溫度更新函數(shù)g(T,t)：?。喝(T,t)=sT, 0s1.5. 抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則：（1 1）k k0 0步目標(biāo)均值穩(wěn)定；步目標(biāo)均值穩(wěn)定；(2) k(2) k0 0步目標(biāo)值穩(wěn)定步目標(biāo)值穩(wěn)定; ; (3) (3) 步數(shù)大于給定值。步數(shù)大于給定值。6.6.退火結(jié)束準(zhǔn)則退火結(jié)束準(zhǔn)則：（：（1 1）T T小于給定值；小于給定值； (2) (2)

15、代數(shù)大于給定值；代數(shù)大于給定值； （3 3）t t0 0代最優(yōu)值穩(wěn)定。代最優(yōu)值穩(wěn)定。模擬退火算法（模擬退火算法（Simulated Annealing）算法分析：算法分析：1.1.鄰域結(jié)構(gòu)。鄰域結(jié)構(gòu)。2.2.基于概率的轉(zhuǎn)移方向控制?；诟怕实霓D(zhuǎn)移方向控制。3.3.可以回彈?？梢曰貜?。4.4.著名的全局解求法。著名的全局解求法。5.5.計(jì)算量較大。計(jì)算量較大。啟發(fā)式方法模擬退火算法（模擬退火算法（Simulated Annealing）算法思想：算法思想：1.1.前三算法都有鄰域結(jié)構(gòu)定義要求，其中前三算法都有鄰域結(jié)構(gòu)定義要求，其中Monte-CarloMonte-Carlo法由距離定法由距離定義

16、，義，SASA和上山法還要初值。和上山法還要初值。2.2.鄰域的使用實(shí)際上隱含著對(duì)鄰域的使用實(shí)際上隱含著對(duì)f(x)f(x)連續(xù)性的假設(shè)。但基于離散變量的組合優(yōu)化不滿連續(xù)性的假設(shè)。但基于離散變量的組合優(yōu)化不滿足這種假設(shè)。也就是說(shuō)，足這種假設(shè)。也就是說(shuō)，x x相鄰并不一定有相鄰并不一定有f(x)f(x)相近。這樣，鄰域搜索和相近。這樣，鄰域搜索和Monte-Monte-CarloCarlo法中范圍縮小法就失效。法中范圍縮小法就失效。3.3.不用鄰域，優(yōu)化迭代中換代采樣問(wèn)題怎樣解決？（不用鄰域，優(yōu)化迭代中換代采樣問(wèn)題怎樣解決？（a)a)下一代采樣點(diǎn)的生成；（下一代采樣點(diǎn)的生成；（b)b)怎樣怎樣繼承

17、前面搜索的成果，或繼承前面搜索的成果，或保持好的采樣點(diǎn)？（保持好的采樣點(diǎn)？（c)c)怎樣實(shí)現(xiàn)采樣的多樣性？怎樣實(shí)現(xiàn)采樣的多樣性？4.4.從物種進(jìn)化過(guò)程中適者生存、優(yōu)勝劣汰規(guī)律得到啟發(fā)，設(shè)計(jì)采樣方法：（從物種進(jìn)化過(guò)程中適者生存、優(yōu)勝劣汰規(guī)律得到啟發(fā)，設(shè)計(jì)采樣方法：（a)a)生成：生成：下一代由上一代生成；（下一代由上一代生成；（b)b)下一代保持上一代（父母）的部分特征，具有繼承性；下一代保持上一代（父母）的部分特征，具有繼承性；(c)(c)下一代由兩個(gè)上一代個(gè)體生成，不同于父母，同時(shí)可能隨機(jī)地發(fā)生異化。下一代由兩個(gè)上一代個(gè)體生成，不同于父母，同時(shí)可能隨機(jī)地發(fā)生異化。啟發(fā)式方法四。遺傳算法（四。

18、遺傳算法（Genetic Algorithms）算法：算法：1.1.隨機(jī)產(chǎn)生一組初始個(gè)體（設(shè)計(jì)變量值隨機(jī)產(chǎn)生一組初始個(gè)體（設(shè)計(jì)變量值x xi i）構(gòu)成初始種群）構(gòu)成初始種群X=xX=x1 1,x,x2 2,x,xm m ， 計(jì)算適配值（計(jì)算適配值（f(x), f(x), 或或p(f(x)p(f(x)）. .2.2.判斷算法收斂準(zhǔn)則是否滿足，若滿足，判斷算法收斂準(zhǔn)則是否滿足，若滿足，輸出結(jié)果，輸出結(jié)果，結(jié)束。結(jié)束。3.3.根據(jù)適配值大小，選擇復(fù)制種群中若干個(gè)體根據(jù)適配值大小，選擇復(fù)制種群中若干個(gè)體S=xS=x1 1,x,x2 2,x,xk k X, X, 即即 S= S=selectselect

19、(X);(X);4.4.對(duì)于對(duì)于S S中兩個(gè)不同的個(gè)體中兩個(gè)不同的個(gè)體x xi i和和x xj j, , 按照交叉概率執(zhí)行交叉操作。即：如果按照交叉概率執(zhí)行交叉操作。即：如果 random(0,1)p random(0,1)pc c, x, xchildchild= =crossovercrossover(x(xi i,x,xj j), ), 放放x xchildchild到到C.C.5.5.對(duì)于對(duì)于C C中每個(gè)個(gè)體中每個(gè)個(gè)體x, x, 按照變異概率執(zhí)行變異操作。即：如果按照變異概率執(zhí)行變異操作。即：如果 random(0,1)p random(0,1)pm m, x, xm m= =muta

20、tionmutation(x), (x), 放放x xm m到到M;M;否則，直接放否則，直接放x x到到M.M.6.6.置下一代種群置下一代種群X X為為M,M,計(jì)算它們的適配值，轉(zhuǎn)計(jì)算它們的適配值，轉(zhuǎn)(2).(2).啟發(fā)式方法遺傳算法（遺傳算法（Genetic Algorithms）算法要素：算法要素：1.1.編碼：設(shè)計(jì)變量用數(shù)字串表示編碼：設(shè)計(jì)變量用數(shù)字串表示, ,如二進(jìn)制如二進(jìn)制 1011000110110001，十進(jìn)制，十進(jìn)制 9801568798015687。2.2.選擇：比例選擇策略，適配值大個(gè)體生存概率高選擇：比例選擇策略，適配值大個(gè)體生存概率高. .令令遺傳算法（遺傳算法（G

21、enetic Algorithms）nkkikkixfxfa11)(/ )(a0=0a2a1ai-1an=1aidifor(int i=1; i=|S|; i+) p=random(0,1); If ai-1p=ai, select xi; f(xi)越大，di越大，p落入ai-1,ai的可能性就越大。算法要素：算法要素：3.3.交叉：（交叉：（a)a)一點(diǎn)交叉法一點(diǎn)交叉法遺傳算法（遺傳算法（Genetic Algorithms）x1=1 0 1 1 0 0 1 1 0 1 1 1 1 0 =xchild1x2=0 0 1 0 1 1 0 0 0 1 0 0 0 1 =xchild2隨機(jī)定位隨

22、機(jī)定位(b)(b)兩點(diǎn)交叉法兩點(diǎn)交叉法, ,例如例如9 9個(gè)設(shè)備的排列順序?yàn)閭€(gè)設(shè)備的排列順序?yàn)閤:x:x1=264 7358 91 2 418769 = 234187695 xchild1x2=452 1876 93 4 273589 = 412735896 xchild2隨機(jī)定位隨機(jī)定位6/16/1與與5/35/3出現(xiàn)重復(fù)，暫不填出現(xiàn)重復(fù)，暫不填按照從小到大按照從小到大補(bǔ)填所缺碼數(shù)補(bǔ)填所缺碼數(shù)算法要素：算法要素：3.3.交叉：（交叉：（c)Non-ABELc)Non-ABEL法法, x, xchild1child1i=xi=x1 1xx2 2i; xi; xchild2child2i=xi=

23、x2 2xx1 1ii遺傳算法（遺傳算法（Genetic Algorithms）(d)(d)實(shí)數(shù)調(diào)配法，實(shí)數(shù)調(diào)配法， x xchild1child1=sx=sx1 1+(1-s)x+(1-s)x2 2 x xchild2child2=sx=sx2 2+(1-s)x+(1-s)x1 1 0s10s 1010110 1010110 （b)b)交換（交換（SwapSwap） 412735896 - 412537896412735896 - 412537896 (c) (c)逆序（逆序（InverseInverse） 412735896 - 698537214412735896 - 698537214

24、隨機(jī)定位隨機(jī)定位算法分析：算法分析：1.1.隨著種群隨著種群X X的變化，個(gè)體在的變化，個(gè)體在X X中可能重復(fù)，但總個(gè)數(shù)中可能重復(fù)，但總個(gè)數(shù)n n不變，這說(shuō)明有些個(gè)體被徹底淘汰了。不變，這說(shuō)明有些個(gè)體被徹底淘汰了。2.2.如果優(yōu)良個(gè)體被淘汰，會(huì)影響收斂。如果優(yōu)良個(gè)體被淘汰，會(huì)影響收斂。3.3.精英策略是將精英策略是將10%10%的頂級(jí)優(yōu)良個(gè)體直接放入下一代種的頂級(jí)優(yōu)良個(gè)體直接放入下一代種群中，不參加交叉和變異操作。群中，不參加交叉和變異操作。4.4.這樣，這樣，GAGA以概率以概率1 1收斂。收斂。啟發(fā)式方法遺傳算法遺傳算法算法思想：算法思想：在下山法中，搜索方向規(guī)則較為單一，容在下山法中，搜

25、索方向規(guī)則較為單一，容易陷入局部最優(yōu)解，或來(lái)回循環(huán)。方向選擇規(guī)則的多易陷入局部最優(yōu)解，或來(lái)回循環(huán)。方向選擇規(guī)則的多樣化，有利于克服這一問(wèn)題。樣化，有利于克服這一問(wèn)題。與與SASA算法中隨機(jī)的、自動(dòng)跳出局部解的做法不同，算法中隨機(jī)的、自動(dòng)跳出局部解的做法不同，TSTS算法有限地記錄已搜索過(guò)的路徑或局部最優(yōu)解，進(jìn)一算法有限地記錄已搜索過(guò)的路徑或局部最優(yōu)解，進(jìn)一步的搜索主動(dòng)地回避這些搜索方向或步的搜索主動(dòng)地回避這些搜索方向或局部最優(yōu)解局部最優(yōu)解，使使更多的不同的解得到搜索。更多的不同的解得到搜索。啟發(fā)式方法五。禁忌搜索算法（五。禁忌搜索算法（Taboo Search）局部最優(yōu)解局部最優(yōu)解更好的局部最

26、優(yōu)解更好的局部最優(yōu)解雖然這些方向是下降更多，但因?yàn)橐阉阉鬟^(guò)，回避它們！雖然這些方向是下降更多，但因?yàn)橐阉阉鬟^(guò)，回避它們！算法：算法：1 1。給定算法參數(shù)，隨機(jī)產(chǎn)生初始解，置禁忌表。給定算法參數(shù)，隨機(jī)產(chǎn)生初始解，置禁忌表(Tabu-list)(Tabu-list)為空；為空；2 2。如果收斂準(zhǔn)則。如果收斂準(zhǔn)則(stop crtiterion)(stop crtiterion)滿足，結(jié)束并輸出結(jié)果。滿足，結(jié)束并輸出結(jié)果。3 3。由當(dāng)前解產(chǎn)生鄰域解，確定候選解集合。由當(dāng)前解產(chǎn)生鄰域解，確定候選解集合(Candidates)(Candidates)及對(duì)應(yīng)目標(biāo)值；及對(duì)應(yīng)目標(biāo)值；4 4。如果藐視準(zhǔn)則（。如

27、果藐視準(zhǔn)則（Aspiration criterionAspiration criterion）滿足，將滿足藐視準(zhǔn)則的解作）滿足，將滿足藐視準(zhǔn)則的解作 為當(dāng)前解，加入為當(dāng)前解，加入禁忌表，禁忌表，更新禁忌表對(duì)象的禁忌長(zhǎng)度（更新禁忌表對(duì)象的禁忌長(zhǎng)度（Tabu lengthTabu length）, , 轉(zhuǎn)（轉(zhuǎn)（2 2）。）。5 5。候選解禁忌屬性判斷；。候選解禁忌屬性判斷；6 6。將非禁忌對(duì)象的最佳解作為當(dāng)前解，加入禁忌表，更新禁忌表對(duì)象的禁。將非禁忌對(duì)象的最佳解作為當(dāng)前解，加入禁忌表，更新禁忌表對(duì)象的禁 忌長(zhǎng)度（忌長(zhǎng)度（Tabu lengthTabu length）, ,轉(zhuǎn)（轉(zhuǎn)（2 2）。）。啟

28、發(fā)式方法禁忌搜索算法（禁忌搜索算法（Taboo Search）算法要素：算法要素：1 1。禁忌對(duì)象：鄰域方向，或鄰域中解。禁忌對(duì)象：鄰域方向，或鄰域中解。2 2。禁忌表：。禁忌表：禁忌對(duì)象未來(lái)不用的迭代次數(shù)之間的關(guān)系表。禁忌對(duì)象未來(lái)不用的迭代次數(shù)之間的關(guān)系表。3 3。藐視準(zhǔn)則：無(wú)論是否被禁忌，只要此條件滿足，就選為當(dāng)前解。如迄今。藐視準(zhǔn)則：無(wú)論是否被禁忌，只要此條件滿足，就選為當(dāng)前解。如迄今 最優(yōu)性（最優(yōu)性（best so farbest so far）; ;4 4。禁忌長(zhǎng)度：禁忌對(duì)象第一次放入禁忌表中設(shè)置的禁止使用的迭代次數(shù)，。禁忌長(zhǎng)度：禁忌對(duì)象第一次放入禁忌表中設(shè)置的禁止使用的迭代次數(shù)，

29、以后每迭代一步，次數(shù)減一。以后每迭代一步，次數(shù)減一。啟發(fā)式方法禁忌搜索算法（禁忌搜索算法（Taboo Search）算法例子：算法例子：目標(biāo)函數(shù)是目標(biāo)函數(shù)是f(x)f(x)，x x是是1,2,3,71,2,3,7的一個(gè)排列。的一個(gè)排列。 鄰域定義為一次交換得到的新解，鄰域定義為一次交換得到的新解，鄰域成員個(gè)數(shù)鄰域成員個(gè)數(shù)6 65 54 43 32 21 12121選選5 5個(gè)較大值記錄在候選集合中。個(gè)較大值記錄在候選集合中。（4 4，5 5）交換未來(lái)）交換未來(lái)3 3次不能采用！次不能采用！T T標(biāo)記被禁忌，此步差值都為負(fù)，任選標(biāo)記被禁忌，此步差值都為負(fù)，任選一個(gè)，跳出局部最優(yōu)解。一個(gè)，跳出局部

30、最優(yōu)解。算法例子：算法例子：目標(biāo)函數(shù)是目標(biāo)函數(shù)是f(x)f(x)，x x是是1,2,3,71,2,3,7的一個(gè)排列。的一個(gè)排列。 此步出現(xiàn)迄今最大值，藐視準(zhǔn)則滿足，此步出現(xiàn)迄今最大值，藐視準(zhǔn)則滿足，雖然被禁忌，仍然選擇（雖然被禁忌，仍然選擇（4 4，5 5）到達(dá)一個(gè)新的山脊。到達(dá)一個(gè)新的山脊。交換（交換（7 7，1 1）算法分析：算法分析：1.1.在搜索過(guò)程中，可以接受劣解，具有跳出陷阱能力。在搜索過(guò)程中，可以接受劣解，具有跳出陷阱能力。2.2.新解不是在當(dāng)前解的鄰域中隨機(jī)產(chǎn)生，而或是優(yōu)于新解不是在當(dāng)前解的鄰域中隨機(jī)產(chǎn)生，而或是優(yōu)于 “ “Best so far”Best so far”解，或

31、是非禁忌的最優(yōu)解，因此，解，或是非禁忌的最優(yōu)解，因此，選選 取優(yōu)良解的概率較大取優(yōu)良解的概率較大。（相比之下，。（相比之下，SASA只隨機(jī)選一個(gè)只隨機(jī)選一個(gè) 鄰域解比較）鄰域解比較）3.3.主動(dòng)回避已搜索的解，減小循環(huán)反復(fù)。主動(dòng)回避已搜索的解，減小循環(huán)反復(fù)。4.4.可以擴(kuò)展為更廣泛的知識(shí)規(guī)則在優(yōu)化搜索中的運(yùn)用?？梢詳U(kuò)展為更廣泛的知識(shí)規(guī)則在優(yōu)化搜索中的運(yùn)用。啟發(fā)式方法TS算法算法算法思想：算法思想：學(xué)習(xí)是一個(gè)漸變的動(dòng)態(tài)過(guò)程，此過(guò)程在數(shù)學(xué)上可學(xué)習(xí)是一個(gè)漸變的動(dòng)態(tài)過(guò)程，此過(guò)程在數(shù)學(xué)上可采用動(dòng)力系統(tǒng)（采用動(dòng)力系統(tǒng)（Dynamical systemDynamical system）建模，動(dòng)力系統(tǒng)隨時(shí)間）

32、建模，動(dòng)力系統(tǒng)隨時(shí)間的推進(jìn)，最終會(huì)達(dá)到某種穩(wěn)定的成熟狀態(tài)。的推進(jìn)，最終會(huì)達(dá)到某種穩(wěn)定的成熟狀態(tài)。 如果用目標(biāo)函數(shù)表征這種穩(wěn)定狀態(tài)，動(dòng)力系統(tǒng)如果用目標(biāo)函數(shù)表征這種穩(wěn)定狀態(tài)，動(dòng)力系統(tǒng)dx/dt=f(x,t)dx/dt=f(x,t)的演化過(guò)程，就是一個(gè)優(yōu)化收斂過(guò)程。的演化過(guò)程，就是一個(gè)優(yōu)化收斂過(guò)程。啟發(fā)式方法六。人工神經(jīng)網(wǎng)絡(luò)方法（六。人工神經(jīng)網(wǎng)絡(luò)方法（Artificial Neural Network, ANN）tf(t,x)粒子粒子x的運(yùn)動(dòng)曲線的運(yùn)動(dòng)曲線單層感知機(jī)的學(xué)習(xí)算法：?jiǎn)螌痈兄獧C(jī)的學(xué)習(xí)算法：1 1。給出初始權(quán)值。給出初始權(quán)值wi i和和；2。給定連續(xù)輸入樣本。給定連續(xù)輸入樣本x(t)=(x0

33、, x1, xn-1)和目標(biāo)輸出和目標(biāo)輸出c(t)=c(x(t);3。計(jì)算實(shí)際輸出。計(jì)算實(shí)際輸出 ，其中，其中f(*)為神經(jīng)元激勵(lì)函數(shù)；為神經(jīng)元激勵(lì)函數(shù)；4。調(diào)整權(quán)值。調(diào)整權(quán)值 ；5。返回第（。返回第（2）步。）步。啟發(fā)式方法人工神經(jīng)網(wǎng)絡(luò)方法（人工神經(jīng)網(wǎng)絡(luò)方法（Artificial Neural Network, ANN）)()()(10niiitxtwfty)()()()() 1(txtytctwtwiiiRRwxyBxAxxcuuufii , , 1 , 1 ,1 , 1 1 1)( , 0 10 1)(x0 x1xn-1yt t為動(dòng)態(tài)系統(tǒng)時(shí)間變量，算法中理解為迭代次數(shù)為動(dòng)態(tài)系統(tǒng)時(shí)間變量，

34、算法中理解為迭代次數(shù)對(duì)于某輸入對(duì)于某輸入 x, ,如果輸出如果輸出y=1,y=1,希望值希望值c=1,c=1,則則 w wi i(t+1)=w(t+1)=wi i(t)(t)。 不變！不變！對(duì)于某輸入對(duì)于某輸入 x, ,如果輸出如果輸出y=1,y=1,希望值希望值c=c=1,1,則則 w wi i(t+1)=w(t+1)=wi i(t)(t) （1)1)11xi i(t)=w(t)=wi i(t)-2(t)-2xi(t), ,w wi i(t+1)(t+1)xi i(t)=w(t)=wi i(t)(t)xi i(t)-(t)-2xi2(t) w min.:E-min.當(dāng)當(dāng)u ui i=w=wjijiv vj j- -i i0=0i=0時(shí)，時(shí)，v vi i=f(u=f(ui i)=1,)=1,v vi i=1-v=1-vi ioldold=0=0所以，所以， -u-ui i v vi i 0離散型離散型HopfieldHopfi