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