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

申請免費(fèi)試用、咨詢電話：400-8352-114

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

讓 x := s(x)

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

網(wǎng)站提醒和聲明

本文內(nèi)容來自自互聯(lián)網(wǎng)公開信息或用戶自發(fā)貢獻(xiàn)，該文觀點(diǎn)僅代表作者本人，版權(quán)歸原作者所有。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。若發(fā)現(xiàn)侵權(quán)或違規(guī)內(nèi)容請聯(lián)系電話4008352114或郵箱442699841@qq.com，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

發(fā)布：2026-01-23 19:35 編輯：xiaona [打印此頁] [關(guān)閉]