第三章禁忌搜索-文庫吧
2025-08-25 14:44 本頁面
【正文】 的 2opt，選定 A城市為起點。 13 2. 局域搜索 ? 示例 全鄰域搜索 第 1步 N(xbest)={(ABCDE)， (ACBDE)， (ADCBE)， (AECDB)， (ABDCE)， (ABEDC)， (ABCED)}， 對應目標函數(shù)為 f(x)={45, 43, 45, 60, 60, 59, 44} xbest=xnow=(ACBDE) 一 .前言 A B C D E 14 2. 局域搜索 ? 示例 全鄰域搜索 第 2步 N(xbest)={(ACBDE)， (ABCDE)， (ADBCE)， (AEBDC)， (ACDBE)， (ACEDB)， (ACBED)}， 對應目標函數(shù)為 f(x)={43, 45, 44, 59, 59, 58, 43} xbest=(ACBDE) 一 .前言 15 2. 局域搜索 ? 優(yōu)劣性 ① 通用易實現(xiàn)，易于理解 ② 搜索效果依賴于初始點和鄰域結構，極易陷入局優(yōu) 一 .前言 0x0x16 2. 局域搜索 ? 優(yōu)劣性 ① 通用易實現(xiàn)，易于理解 ② 搜索效果依賴于初始點和鄰域結構，極易陷入局優(yōu) 一 .前言 為了獲得好解 ，可以采用的策略 有 (1)擴大鄰域結構，(2)變鄰域結構， (3)多初始點 。但這些策略依然無法保證算法具備跳出局優(yōu)的能力。 17 2. 局域搜索 ? 優(yōu)劣性 ① 通用易實現(xiàn)，易于理解 ② 搜索效果依賴于初始點和鄰域結構，極易陷入局優(yōu) 一 .前言 為了獲得好解 ，可以采用的策略 有 (1)擴大鄰域結構，(2)變鄰域結構， (3)多初始點 。但這些策略依然無法保證算法具備 跳出局優(yōu) 的能力。 18 1. TS（ Tabu Search）的提出 ? 人類在選擇過程中具有記憶功能，比如走迷宮時，當發(fā)現(xiàn)有可能又回到某個地點的時候總會有意識地避開先前選擇的方向而選擇其他的可能性，這樣就可以確定性的避開迂回搜索。 ? 借鑒人類的智能思考特性，采用禁忌策略盡量避免迂回搜索就構成了 TS算法。 ? Glover在 1977年提出 TS。相對于 LS， TS的優(yōu)點是能夠通過接受劣解來逃離局優(yōu)，在 90年代初開始受到廣泛的關注。 二 .禁忌搜索 19 2. 構成要素 ? 解的表達 ① 編碼方法：用數(shù)學的形式來表示問題的解。 ② 初始解的產(chǎn)生：隨機產(chǎn)生或者采用啟發(fā)式方法產(chǎn)生一個可行解。 ③ 評價函數(shù) C(x)的構造：往往直接將目標函數(shù)f(x)作為評價函數(shù)。 二 .禁忌搜索 20 2. 構成要素 ? 鄰域及鄰域移動 ① 定義鄰域移動 s，例如，在函數(shù)優(yōu)化問題中鄰域移動可以定義為給定步長和移動方向；在組合優(yōu)化問題中鄰域移動可以定義為某種排練序列置換。 ② 鄰域是由當前解 x及其通過定義的鄰域移動能夠達到的所有解構成的集合。 二 .禁忌搜索 注意：移動的意義是靈活的，目的是便于搜索。 21 2. 構成要素 ? 禁忌表 禁忌表 (T表 )的作用：防止搜索出現(xiàn)循環(huán) ① 將移動、移動分量或適值作為禁忌對象 ② 表的長度稱為 TabuSize，可以用來控制局域搜索和廣域搜索 ③ 表是動態(tài)更新的：把最新的解記入，最老的解從表中釋放（解禁） 二 .禁忌搜索 22 2. 構成要素 ? 選擇策略 選擇策略的作用：保證 TS具有跳出局優(yōu)的能力 當前解 x每一步總是移動到鄰域 N(x)中未被禁忌的最優(yōu)解，即若 則令 ，本次移動到鄰域 N(x)中未被禁忌的最優(yōu)解 二 .禁忌搜索 ? ? ? ? ? ? ? ?? ?( ) ( ) , \kC s x O pt C s x s x N x T??()kx s x?()ksx23 2. 構成要素 ? 渴望水平 渴望水平 A(s,x)是一個取決于 s和 x的值，若有 成立，則 s(x)不受 T表限制。也就是說即使存在 x仍然可以移動到 s(x)。 A(s,x)一般選取為歷史上所能達到的最優(yōu)函數(shù)值。 二 .禁忌搜索 ? ?? ? ? ?,C s x A s x?()s x T?禁忌策略和 渴望 水平構成 了
教學課件相關推薦
鄂ICP備17016276號-1