第三章禁忌搜索(編輯修改稿)
2024-11-03 14:44 本頁面
【文章內(nèi)容簡介】 TS的兩大核心移動規(guī)則 24 2. 構(gòu)成要素 ? 停止準(zhǔn)則 ① 設(shè)定最大迭代次數(shù) ② 得到滿意解 ③ 設(shè)定某個對象的最大禁忌頻率 二 .禁忌搜索 25 3. 算法流程 Step 1 選一個初始點 x( )，令 ， ，渴望水平 ，迭代指標(biāo) k=0； Step 2 若 ，則停止；否則令 k=k+1；若kNG(其中 NG為最大迭代次數(shù) )，則停止； 二 .禁忌搜索 xX? xx? ? T ??*( , ) ( )A s x C x?? ? \N x T ??注： 表示非正常終止，造成的原因：鄰域小， T表長。正常設(shè)置為 T表長度 鄰域大小。Step 2的作用是設(shè)置循環(huán)體出口。 ? ? \N x T ??26 3. 算法流程 Step 3 若 且 ，令 ，轉(zhuǎn) Step 5； Step 4 若 ，令 ； 二 .禁忌搜索 ? ?? ? ? ?? ? ? ? ? ?? ?,LC s x O p t C s x s x N x??? ?? ? ( , )LC s x A s x? ()Lx s x?注： Step 3的作用破禁檢查 ? ?? ? ? ?? ? ? ? ? ?? ?,\KC s x O p t C s x s x N x T??()Kx s x?注： Step 4的作用鄰域選優(yōu) 27 3. 算法流程 Step 5 若 ，令 ， ， ； Step 6 更新 T表，轉(zhuǎn) Step 2 ； 二 .禁忌搜索 注： Step 5的作用更新歷史最好解及渴望水平 ? ? ? ?C x C x ?? xx? ? ? ? ? ?C x C x? ?? ? ? ?,A s x C x ??注： x存入 T表中的第一個位置 28 4. TS克服局優(yōu)分析 ? 從鄰域搜索的方法看 移向 N(x)\T中最好的解，而不與當(dāng)前解比較， 是 N(x)\T中的最好點，但 可能劣于 二 .禁忌搜索 ? ? ? ? ? ? ? ?? ?,\Ks x O pt s x s x N x T??? ?Ksx ? ?? ?KC s x? ?*Cx29 4. TS克服局優(yōu)分析 ? 從選優(yōu)規(guī)則看 始終保持歷史最優(yōu)解，不以當(dāng)前解為最優(yōu) ? 從停止規(guī)則上看 不以最優(yōu)判據(jù)為停止規(guī)則，而是指定最大迭代步數(shù)為停止條件，這樣不能保證最優(yōu)性。 二 .禁忌搜索 30 1. 問題提出 由 7層不同的絕緣材料構(gòu)成的一種絕緣體，應(yīng)如何排 列順序，可獲得最好的絕緣性能 ? 三 .算法舉例 31 2. 算法設(shè)計 ? 編碼方式：順序編碼 ? 初始解的產(chǎn)生：隨機產(chǎn)生，如 2573461 ? 適值函數(shù)：極大化目標(biāo)值 ? 鄰域移動方式： 2opt，即兩兩交換 ? 其他參數(shù)：禁忌對象為鄰域移動方式， T表長度設(shè)為 3， NG設(shè)為 5 三 .算法舉例 32 ① 初始表 初始編碼： 2573461 結(jié)論：交換 4和 5 三 .算法舉例 移動 5， 4 6 7， 4 4 3， 6 2 2， 3 0 4， 1 1 …… …… ? ? 10Cx ???TT表 1 2 3 ? ?xS ? ?Cx? ???*xx? *( , ) ( ) 10A s x C x??33 ② 迭代
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1