第二章禁忌搜索算法

《第二章禁忌搜索算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章禁忌搜索算法智能優(yōu)化計算2.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禁忌搜索的實現(xiàn)與應(yīng)用2.4.130城市TSP問題（d*=423.741byDBFogel）2.4.2基于禁忌搜索算法的系統(tǒng)辨識智能優(yōu)化計算2.1局部搜索智能優(yōu)化計算函數(shù)優(yōu)化問題中在距離空間中，通常的鄰域定義是以一點為中心的一個球體；組合優(yōu)化問題中2.1.1鄰域的概念2.1局部搜索智能優(yōu)化計算例TS

2、P問題解的一種表示方法為D={x=(i1,i2,…,in)

3、i1,i2,…,in是1,2,…,n的排列}，定義它的鄰域映射為2－opt，即x中的兩個元素進(jìn)行對換，N(x)中共包含x的Cn2=n(n-1)/2個鄰居和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鄰域的概念2.1局部搜索智能優(yōu)化計算例TSP問題解的鄰域映射可由2－opt，推廣到k－opt。鄰域概念的重要性鄰域的構(gòu)造依

4、賴于決策變量的表示，鄰域的結(jié)構(gòu)在現(xiàn)代優(yōu)化算法中起重要的作用。2.1.1鄰域的概念2.1局部搜索智能優(yōu)化計算STEP1選定一個初始可行解x0，記錄當(dāng)前最優(yōu)解xbest:=x0,T=N(xbest)；STEP2當(dāng)T{xbest}=Φ時，或滿足其他停止運算準(zhǔn)則時，輸出計算結(jié)果，停止運算；否則，從T中選一集合S，得到S中的最好解xnow；若f(xnow)

5、CDE)，f(xbest)=45，定義鄰域映射為對換兩個城市位置的2-opt，選定A城市為起點。2.1.3局部搜索示例2.1局部搜索智能優(yōu)化計算五個城市的對稱TSP問題方法1：全鄰域搜索第1步N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，對應(yīng)目標(biāo)函數(shù)為f(x)={45,43,45,60,60,59,44}xbest:=xnow=(ACBDE)2.1.3局部搜索示例ABCDE2.1局部搜索智能優(yōu)化計算五個城市的對稱TSP問題方法1：全鄰域搜索第2步N(xbes

6、t)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，對應(yīng)目標(biāo)函數(shù)為f(x)={43,45,44,59,59,58,43}xbest:=xnow=(ACBDE)2.1.3局部搜索示例2.1局部搜索智能優(yōu)化計算五個城市的對稱TSP問題方法2：一步隨機搜索第1步從N(xbest)中隨機選一點，如xnow=(ACBDE)，對應(yīng)目標(biāo)函數(shù)為f(xnow)=43<45xbest:=xnow=(ACBDE)2.1.3局部搜索示例2.1局部搜索智能優(yōu)化計算五個城市的對稱TSP問題方法2：一步隨

7、機搜索第2步從N(xbest)中又隨機選一點，如xnow=(ADBCE)，對應(yīng)目標(biāo)函數(shù)為f(xnow)=44>43xbest:=xnow=(ACBDE)2.1.3局部搜索示例2.1局部搜索智能優(yōu)化計算五個城市的對稱TSP問題簡單易行，但無法保證全局最優(yōu)性；局部搜索主要依賴起點的選取和鄰域的結(jié)構(gòu)；為了得到好的解，可以比較不同的鄰域結(jié)構(gòu)和不同的初始點；如果初始點的選擇足夠多，總可以計算出全局最優(yōu)解。2.1.3局部搜索示例2.2禁忌搜索智能優(yōu)化計算算法的提出禁忌搜索（Tabusearch）是局部鄰域搜索算法的推廣，F(xiàn)redGlover在1986年提出

8、這個概念，進(jìn)而形成一套完整算法。算法的特點禁忌——禁止重復(fù)前面的工作。跳出局部最優(yōu)點。2.2.1算法的主要思路http://spot.colorado.edu/~glover/2.2禁忌搜索智能優(yōu)化計算四城市非對稱TSP問題初始解x0=(ABCD)，f(x0)=4，鄰域映射為兩個城市順序?qū)Q的2－opt，始、終點都是A城市。2.2.2禁忌搜索示例2.2禁忌搜索智能優(yōu)化計算四城市非對稱TSP問題第1步解的形式禁忌對象及長度候選解f(x0)=42.2.2禁忌搜索示例ABCDBCDABC對換評價值CD4.5BC7.5BD8?2.2禁忌搜索智能優(yōu)化計算

9、四城市非對稱TSP問題第2步解的形式禁忌對象及長度候選解f(x1)=4.52.2.2禁忌搜索示例ABDCBCDABC3對換評價值CD4.5BC3.5B