APS算法之六禁忌搜索TS（上）

文章來(lái)源：泛普軟件禁忌搜索Tabu Search (TS)：它的算法是創(chuàng)立一初始化的方案；基于初始化的方案，算法“移動(dòng)” 到一相鄰的方案。一般來(lái)說(shuō)，許多移動(dòng)是連續(xù)的過(guò)程，方案的質(zhì)量被提高。一個(gè)禁忌 tabu 清單被用于指導(dǎo)搜尋，當(dāng)一特殊的中斷條件達(dá)到時(shí)，算法就結(jié)束。 (如. 當(dāng)運(yùn)行時(shí)間已經(jīng)達(dá)到時(shí))，它是(確定性) 搜尋算法。　它和基因算法GA不同是, 禁忌TS，它是(確定性) 搜尋算法，試圖找到一組合優(yōu)化問(wèn)題的最佳方案。但是，它的算法也還是包括隨機(jī)取樣的方法。禁忌搜索TS: 基本概念：它的約束搜尋是由它的移動(dòng)禁止的分類條件來(lái)進(jìn)行的 (如, tabu)。　爬山探索”“ (對(duì)最小化問(wèn)題) 1. 選擇初始化方案 x 2. 選擇一些移動(dòng)s(x) 如下目標(biāo)函數(shù)值 s(x) < 目標(biāo)函數(shù)值 x 　如果沒(méi)有移動(dòng)存在，那么x 就是最佳的，方法停止。否者 ,

讓 x := s(x)

及回到第二步 2. 它是非常簡(jiǎn)單的探索，其缺點(diǎn)是：局部?jī)?yōu)化，也許不是全局的優(yōu)化。　禁忌搜索TS 特點(diǎn)： l 它的約束搜尋是由它的移動(dòng)禁止的分類條件來(lái)進(jìn)行的 l 是由一“遺忘策略”提供的短期記憶函數(shù)來(lái)自由搜索。熟悉分類的方法：爬山探索, 從它們的開(kāi)始點(diǎn)到一個(gè)本地優(yōu)化采取單向的前進(jìn)。 (在前后最小化里, 山是“倒置”以致于爬山的方向是向下的。) 　在一組合問(wèn)題里，爬山過(guò)程的主要限制：在開(kāi)始點(diǎn)得到本地優(yōu)化，當(dāng)沒(méi)有提高的移動(dòng)是可能的時(shí)候，也許不是一個(gè)全局優(yōu)化。　爬山探索不能保證一個(gè)全局的優(yōu)化。 =>禁忌搜索TS 向?qū)Ь拖褚粋€(gè)探索連續(xù) 探險(xiǎn)。由于沒(méi)有提高移動(dòng)，就不會(huì)成為困惑，也不會(huì)落后到一個(gè)先前出現(xiàn)本地優(yōu)化。爬山法：依賴于初始方案和移動(dòng)的定義“爬山探索”可以找到最佳方案，但是，大部分情況下，它總是局部?jī)?yōu)化。 1，選擇初始化方案 x 和讓 x* := x. 設(shè)置重復(fù)計(jì)數(shù) k := 0, and 開(kāi)始用一個(gè)空的tabu 清單. 2，鄰近的決策方案和選擇最佳方案:
如果刪除所有的禁忌, 那么就去第四步4.
否則設(shè)置 k := k+1 and 選擇最佳的可能的移動(dòng)用相應(yīng)的事先定義好的評(píng)估函數(shù) 3，檢查, 是否從第二步改善目前最佳目標(biāo)函數(shù)值：
如果是真，那么讓 x* := x. 4，檢查, 是否中斷條件達(dá)到:
如果一個(gè)選擇迭代次數(shù)已經(jīng)占用，或是在整個(gè)，或是因?yàn)?x* 是最后的改善, 或如果所有移動(dòng)被禁止，在從第二步直接達(dá)到這一步時(shí)，或如果運(yùn)行時(shí)間被消耗，停止。 x* 是最好的方案.
　否則, 更新tabu清單 and 回到第二步2. l 本地搜索算法的組合（如爬山探索）用禁忌tabu 清單來(lái)克服局部?jī)?yōu)化。 l 禁忌清單tabu使用，提供“約束搜索”的方法。方案的產(chǎn)生關(guān)鍵依賴于禁忌清單的組成內(nèi)容和第4步的更新方法。 l 對(duì)局部?jī)?yōu)化的條件沒(méi)有參照的方法，除非指明那里是局部?jī)?yōu)化在先前找到的最佳方案上的提高。一個(gè)“最好”的移動(dòng)（而不是提高移動(dòng)），在每一步被選擇，在評(píng)估函數(shù)里嵌入使用條件。 l 3個(gè)重要方面：　 1，評(píng)估函數(shù)的定義：
第二步的每一執(zhí)行移動(dòng)，從當(dāng)前的方案x 到一相鄰的方案，產(chǎn)出最大的提高－或, 缺少提高的可能性, 最小化的沒(méi)有提高。在目標(biāo)里，以允許只有非禁忌移動(dòng)的限制為條件。　 2，更新禁忌 tabu清單
使用禁忌清單的主要目標(biāo)是避免回到先前的方案狀態(tài)。禁忌 tabu清單是以移動(dòng)集合，，在最后最近搜索過(guò)程中迭代次數(shù)里，可以“倒退”（或undo) 一個(gè)移動(dòng) 　 3，中斷條件
這里：迭代次數(shù) (要么整個(gè)，要么提高步驟), 或運(yùn)行時(shí)間. （待續(xù)）來(lái)源：AMT

發(fā)布：2007-04-22 10:21 編輯：泛普軟件 · xiaona [打印此頁(yè)] [關(guān)閉]

相關(guān)欄目：

下一篇：數(shù)據(jù)分析的5大技術(shù)走向

哈爾濱OA系統(tǒng)

聯(lián)系方式

成都公司：成都市成華區(qū)建設(shè)南路160號(hào)1層9號(hào)

重慶公司：重慶市江北區(qū)紅旗河溝華創(chuàng)商務(wù)大廈18樓

咨詢：400-8352-114

加微信，免費(fèi)獲取試用系統(tǒng)

QQ在線咨詢

電話咨詢：
4008352114

QQ在線咨詢

APS算法之六禁忌搜索TS（上）

泛普哈爾濱OA快博其他應(yīng)用