神經(jīng)網(wǎng)絡(luò)第二章 禁忌搜索算法課件

第二章禁忌搜索算法

智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年第二章禁忌搜索算法智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院12.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問(wèn)題（d*=423.741byDBFogel）

2.4.2基于禁忌搜索算法的系統(tǒng)辨識(shí)智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院22.1局部搜索

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

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

2.1.1鄰域的概念

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算函數(shù)優(yōu)化問(wèn)題中2.32.1局部搜索

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

TSP問(wèn)題解的一種表示方法為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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算例2.1.1鄰42.1局部搜索

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

TSP問(wèn)題解的鄰域映射可由2－opt，推廣到k－opt。鄰域概念的重要性

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算例2.1.1鄰52.1局部搜索

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

選定一個(gè)初始可行解x0，記錄當(dāng)前最優(yōu)解xbest:=x0,T=N(xbest)；STEP2（*注意集合S選取的大小）

當(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ù)SETP2。2.1.2局部搜索算法

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算STEP12.162.1局部搜索

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

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題72.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題82.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題92.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題102.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題112.1局部搜索

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題122.2禁忌搜索

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

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

/~glover/廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算算法的提出2.2.132.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題142.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

f(x0)=4局部最優(yōu)搜索算法：已經(jīng)達(dá)到局部最優(yōu)而停止。禁忌搜索算法：允許從候選集中選一個(gè)最好的對(duì)換。2.2.2禁忌搜索示例

ABCDBCDABC對(duì)換評(píng)價(jià)值CD4.5BC7.5BD8?廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題152.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ABDCBCDABC3對(duì)換評(píng)價(jià)值CD4.5BC3.5BD4.5?T廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題162.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ACDBBCDAB3C2對(duì)換評(píng)價(jià)值CD8BC4.5BD7.5?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題172.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

f(x3)=7.5*所有解都被禁忌，咋辦？*禁忌對(duì)象、*禁忌長(zhǎng)度的選取2.2.2禁忌搜索示例

ACBDBCDAB23C1對(duì)換評(píng)價(jià)值CD4.5BC4.5BD3.5TTT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題182.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ACBDBCDAB12C0對(duì)換評(píng)價(jià)值CD4.5BC4.5BD3.5?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題192.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ADBCBCDAB01C2對(duì)換評(píng)價(jià)值CD7.5BC8BD4.5?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題202.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

f(x5)=8－－》死循環(huán)2.2.2禁忌搜索示例

ADCBBCDAB20C1對(duì)換評(píng)價(jià)值CD3.5BC4.5BD4?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題212.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌表的主222.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

2.3.1變化因素

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算解的簡(jiǎn)單變232.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算向量分量的242.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算目標(biāo)值的變252.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的262.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的272.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的282.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的292.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的302.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的312.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的322.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的332.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的342.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的352.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的362.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的372.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的382.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的392.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

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

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌長(zhǎng)度的402.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌長(zhǎng)度的412.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ì)象。（如果一個(gè)對(duì)目標(biāo)影響大的變化成為被禁對(duì)象，應(yīng)該使其自由，^_^）2.3.2禁忌表

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算特赦（藐視422.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算候選集合的432.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算評(píng)價(jià)函數(shù)（1）直接評(píng)價(jià)函數(shù)，通過(guò)目標(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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算評(píng)價(jià)函數(shù)442.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算記憶頻率信452.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算記憶頻率信462.3禁忌搜索的關(guān)鍵參數(shù)和操作

智能優(yōu)化計(jì)算終止規(guī)則（1）確定步數(shù)終止，無(wú)法保證解的效果，應(yīng)記錄當(dāng)前最優(yōu)解；（2）頻率控制原則，當(dāng)某一個(gè)解、目標(biāo)值或元素序列的頻率超過(guò)一個(gè)給定值時(shí)，終止計(jì)算；（3）目標(biāo)控制原則，如果在一個(gè)給定步數(shù)內(nèi)，當(dāng)前最優(yōu)值沒(méi)有變化，可終止計(jì)算；（4）目標(biāo)值偏離程度原則，如果目標(biāo)值與問(wèn)題的下界（求極?。┬∮诮o定的誤差，可終止計(jì)算。2.3.3其他

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算終止規(guī)則472.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算TSPBenchmark問(wèn)題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問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算TSPBenc482.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算算法流程492.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算初始條件禁忌長(zhǎng)度為50從2－opt鄰域中隨機(jī)選擇200個(gè)鄰域解，選出其中100個(gè)最佳解組成候選集終止步數(shù)20002.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算初始條件502.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程512.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程522.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程532.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程542.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程552.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程562.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程572.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程582.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程592.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程602.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

智能優(yōu)化計(jì)算初始條件禁忌長(zhǎng)度為10從2－opt鄰域中隨機(jī)選擇200個(gè)鄰域解，選出其中100個(gè)最佳解組成候選集終止步數(shù)2000

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算初始條件612.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程622.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程632.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程642.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程652.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程662.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程672.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程682.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程692.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程702.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

2.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程712.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用

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

禁忌長(zhǎng)度50禁忌長(zhǎng)度102.4.130城市TSP問(wèn)題（d*=423.741byDBFogel）

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.4禁忌搜索的實(shí)現(xiàn)與應(yīng)用智能優(yōu)化計(jì)算運(yùn)行過(guò)程比較72第二章結(jié)束智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年第二章結(jié)束智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2073第二章禁忌搜索算法

智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年第二章禁忌搜索算法智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院742.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問(wèn)題（d*=423.741byDBFogel）

2.4.2基于禁忌搜索算法的系統(tǒng)辨識(shí)智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算廣東藥學(xué)院醫(yī)藥信息工程學(xué)院752.1局部搜索

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

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

2.1.1鄰域的概念

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算函數(shù)優(yōu)化問(wèn)題中2.762.1局部搜索

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

TSP問(wèn)題解的一種表示方法為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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算例2.1.1鄰772.1局部搜索

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

TSP問(wèn)題解的鄰域映射可由2－opt，推廣到k－opt。鄰域概念的重要性

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算例2.1.1鄰782.1局部搜索

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

選定一個(gè)初始可行解x0，記錄當(dāng)前最優(yōu)解xbest:=x0,T=N(xbest)；STEP2（*注意集合S選取的大小）

當(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ù)SETP2。2.1.2局部搜索算法

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算STEP12.1792.1局部搜索

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

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題802.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題812.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題822.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題832.1局部搜索

智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題方法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é)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題842.1局部搜索

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.1局部搜索智能優(yōu)化計(jì)算五個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題852.2禁忌搜索

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

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

/~glover/廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算算法的提出2.2.862.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題872.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

f(x0)=4局部最優(yōu)搜索算法：已經(jīng)達(dá)到局部最優(yōu)而停止。禁忌搜索算法：允許從候選集中選一個(gè)最好的對(duì)換。2.2.2禁忌搜索示例

ABCDBCDABC對(duì)換評(píng)價(jià)值CD4.5BC7.5BD8?廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題882.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ABDCBCDABC3對(duì)換評(píng)價(jià)值CD4.5BC3.5BD4.5?T廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題892.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ACDBBCDAB3C2對(duì)換評(píng)價(jià)值CD8BC4.5BD7.5?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題902.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

f(x3)=7.5*所有解都被禁忌，咋辦？*禁忌對(duì)象、*禁忌長(zhǎng)度的選取2.2.2禁忌搜索示例

ACBDBCDAB23C1對(duì)換評(píng)價(jià)值CD4.5BC4.5BD3.5TTT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題912.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ACBDBCDAB12C0對(duì)換評(píng)價(jià)值CD4.5BC4.5BD3.5?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題922.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

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

ADBCBCDAB01C2對(duì)換評(píng)價(jià)值CD7.5BC8BD4.5?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題932.2禁忌搜索

智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題

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

f(x5)=8－－》死循環(huán)2.2.2禁忌搜索示例

ADCBBCDAB20C1對(duì)換評(píng)價(jià)值CD3.5BC4.5BD4?TT廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.2禁忌搜索智能優(yōu)化計(jì)算四城市非對(duì)稱(chēng)TSP問(wèn)題942.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌表的主952.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

2.3.1變化因素

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算解的簡(jiǎn)單變962.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算向量分量的972.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

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

廣東藥學(xué)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算目標(biāo)值的變982.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的992.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1002.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1012.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1022.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1032.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1042.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1052.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1062.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1072.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1082.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1092.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1102.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1112.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é)院醫(yī)藥信息工程學(xué)院2008年2.3禁忌搜索的關(guān)鍵參數(shù)和操作智能優(yōu)化計(jì)算禁忌對(duì)象的1122.3禁忌搜索的關(guān)鍵參數(shù)和操作

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

（1）t可以為常數(shù)，易于實(shí)現(xiàn)；（2）