簡(jiǎn)介本資源是一套基于MATLAB實(shí)現(xiàn)的禁忌搜索算法求解0-1背包問(wèn)題的完整代碼包面向算法初學(xué)者、優(yōu)化方向課程設(shè)計(jì)者及智能優(yōu)化算法實(shí)踐者聚焦經(jīng)典組合優(yōu)化問(wèn)題的啟發(fā)式求解。壓縮包共4個(gè)文件3個(gè)MATLAB源碼文件1個(gè)Excel數(shù)據(jù)文件總大小僅8KB輕量易部署main.m為主控腳本封裝禁忌搜索全流程near.m負(fù)責(zé)鄰域解生成如物品交換或翻轉(zhuǎn)newlist.m管理解列表與禁忌表更新邏輯data1.xls提供標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)含物品重量、價(jià)值及背包容量。已有1797人學(xué)習(xí)下載代碼結(jié)構(gòu)清晰、注釋充分可直接運(yùn)行復(fù)現(xiàn)算法迭代過(guò)程支持快速修改禁忌長(zhǎng)度、鄰域策略等關(guān)鍵參數(shù)以對(duì)比性能是理解禁忌搜索避免局部最優(yōu)機(jī)制與應(yīng)用于實(shí)際約束優(yōu)化問(wèn)題的理想教學(xué)與實(shí)驗(yàn)范例。1. 項(xiàng)目概述當(dāng)禁忌搜索遇上背包問(wèn)題背包問(wèn)題這個(gè)在算法世界里經(jīng)久不衰的經(jīng)典幾乎每個(gè)學(xué)計(jì)算機(jī)或者運(yùn)籌學(xué)的人都繞不開(kāi)。它就像一個(gè)精明的旅行者總想在有限的行李箱容量?jī)?nèi)塞進(jìn)價(jià)值最高的物品組合。傳統(tǒng)的動(dòng)態(tài)規(guī)劃解法雖然精確但一旦物品數(shù)量我們稱之為“規(guī)模”上去了計(jì)算量就會(huì)指數(shù)級(jí)爆炸讓人望而卻步。這時(shí)候我們就需要一些“聰明”的啟發(fā)式算法來(lái)尋找一個(gè)優(yōu)秀的、雖然不是絕對(duì)最優(yōu)但足夠好的解。禁忌搜索Tabu Search, TS就是其中一員悍將。我第一次接觸用禁忌搜索解背包問(wèn)題是在一個(gè)資源調(diào)度項(xiàng)目的攻堅(jiān)階段。面對(duì)上百個(gè)任務(wù)和有限的計(jì)算資源精確求解根本不可能而簡(jiǎn)單的貪心算法效果又太差。當(dāng)時(shí)就想能不能用TS試試結(jié)果一用就發(fā)現(xiàn)這玩意兒在解決這類組合優(yōu)化問(wèn)題上確實(shí)有它的獨(dú)到之處。它不像模擬退火那樣依賴概率性的“跳坑”也不像遺傳算法那樣需要維護(hù)一個(gè)種群。TS更像一個(gè)固執(zhí)又聰明的探險(xiǎn)家它會(huì)在當(dāng)前解的鄰域里不斷尋找更好的點(diǎn)同時(shí)用一個(gè)“禁忌表”記住最近走過(guò)的路避免在原地打轉(zhuǎn)從而有效地跳出局部最優(yōu)的陷阱。用MATLAB來(lái)實(shí)現(xiàn)這個(gè)組合對(duì)于算法研究和快速原型驗(yàn)證來(lái)說(shuō)簡(jiǎn)直是絕配。MATLAB強(qiáng)大的矩陣運(yùn)算和直觀的繪圖功能能讓我們把算法的搜索過(guò)程、解的變化軌跡看得一清二楚這對(duì)于理解算法行為和調(diào)參至關(guān)重要。今天我就把自己從理論到代碼實(shí)現(xiàn)再到參數(shù)調(diào)優(yōu)的完整經(jīng)驗(yàn)和踩過(guò)的坑系統(tǒng)地梳理一遍。無(wú)論你是算法初學(xué)者想找一個(gè)有挑戰(zhàn)的練手項(xiàng)目還是工程師需要在項(xiàng)目中快速驗(yàn)證一個(gè)啟發(fā)式方案的可行性這篇文章都能給你提供一條清晰的路徑和可直接運(yùn)行的代碼骨架。2. 禁忌搜索算法核心原理與設(shè)計(jì)思路2.1 算法思想記憶與引導(dǎo)的智慧禁忌搜索的核心思想可以用一個(gè)非常生活化的場(chǎng)景來(lái)理解你在山里尋找最高峰最優(yōu)解。從某個(gè)山坡初始解出發(fā)你環(huán)顧四周探索鄰域找到附近一個(gè)更高的點(diǎn)更好的解就移動(dòng)過(guò)去。但如果只這么做你很容易爬上最近的一個(gè)小山頭局部最優(yōu)就以為到頂了因?yàn)樗闹芸雌饋?lái)都比這里低。TS的聰明之處在于它有一個(gè)“記憶”它會(huì)把最近幾步走過(guò)的路比如從A點(diǎn)到B點(diǎn)這個(gè)移動(dòng)動(dòng)作標(biāo)記為“禁忌”在一段時(shí)間內(nèi)不允許再走回頭路。這樣即使當(dāng)前點(diǎn)四周沒(méi)有更高的地方它也會(huì)被迫選擇一個(gè)“非禁忌”的、哪怕暫時(shí)看起來(lái)差一點(diǎn)的路線移動(dòng)從而有機(jī)會(huì)離開(kāi)這個(gè)小山頭去尋找真正的最高峰。這個(gè)“記憶”就是禁忌表Tabu List。它通常記錄最近若干次移動(dòng)的屬性例如這次移動(dòng)翻轉(zhuǎn)了哪個(gè)物品的選擇狀態(tài)而不是記錄完整的解。這樣既節(jié)省了內(nèi)存又能有效防止循環(huán)。禁忌表有長(zhǎng)度稱為禁忌長(zhǎng)度Tabu Tenure。一個(gè)動(dòng)作在禁忌表里待滿這個(gè)長(zhǎng)度后就會(huì)被釋放重新變?yōu)榭蛇x。這模擬了人的短期記憶會(huì)逐漸淡忘的過(guò)程。除了禁忌表TS還有一個(gè)非常重要的機(jī)制叫藐視準(zhǔn)則Aspiration Criterion。這是一個(gè)“破禁”原則。它的邏輯是如果某個(gè)被禁忌的移動(dòng)能產(chǎn)生一個(gè)比歷史最好解還要好的解那么我們就應(yīng)該毫不猶豫地打破禁忌接受這個(gè)移動(dòng)。畢竟我們的終極目標(biāo)是找到更好的解規(guī)則應(yīng)該服務(wù)于目標(biāo)。2.2 針對(duì)0-1背包問(wèn)題的定制化設(shè)計(jì)要把TS應(yīng)用到0-1背包問(wèn)題上我們需要定義幾個(gè)關(guān)鍵組件解的表達(dá)Solution Representation最直接的方式就是用一個(gè)二進(jìn)制向量來(lái)表示。假設(shè)有N個(gè)物品解向量X [x1, x2, ..., xN]其中xi1表示選擇第i個(gè)物品xi0表示不選。例如X[1,0,1,0]表示選擇了第1和第3個(gè)物品。鄰域結(jié)構(gòu)Neighborhood Structure這是TS的“搜索范圍”定義。對(duì)于二進(jìn)制向量最常用的鄰域操作是“翻轉(zhuǎn)Flip”或“交換Swap”。翻轉(zhuǎn)改變某一個(gè)物品的選擇狀態(tài)0變1或1變0。一次翻轉(zhuǎn)操作就是從一個(gè)解移動(dòng)到它的一個(gè)鄰居。這種鄰域大小是N即每個(gè)解有N個(gè)鄰居。交換選擇一個(gè)當(dāng)前選中的物品和一個(gè)當(dāng)前未選中的物品交換它們的狀態(tài)。這能保證總物品數(shù)量如果重量相等或總價(jià)值結(jié)構(gòu)發(fā)生更大變化。 對(duì)于背包問(wèn)題翻轉(zhuǎn)操作更簡(jiǎn)單直接也是我們實(shí)現(xiàn)中最常用的。但需要注意的是單純的翻轉(zhuǎn)很可能產(chǎn)生不可行解總重量超過(guò)背包容量C。因此鄰域移動(dòng)必須結(jié)合可行性處理。禁忌對(duì)象Tabu Object禁忌表里記什么通常記錄被翻轉(zhuǎn)的物品的索引i。例如如果在第t次迭代中我們翻轉(zhuǎn)了第3個(gè)物品那么就將(3)加入禁忌表。在接下來(lái)的禁忌長(zhǎng)度L次迭代內(nèi)禁止再次翻轉(zhuǎn)第3個(gè)物品。這能有效防止算法在“選A”和“不選A”之間來(lái)回振蕩。評(píng)價(jià)函數(shù)Evaluation Function對(duì)于可行解評(píng)價(jià)函數(shù)就是物品總價(jià)值我們追求最大化。對(duì)于不可行解必須給予懲罰。一種常見(jiàn)方法是采用罰函數(shù)法Fitness(X) total_value - penalty * max(0, total_weight - C)。其中penalty是一個(gè)很大的正數(shù)懲罰系數(shù)。這樣算法在搜索時(shí)會(huì)自動(dòng)傾向于向可行域靠近并且會(huì)優(yōu)先優(yōu)化可行解的價(jià)值。初始解生成一個(gè)好的初始解能加快收斂?？梢圆捎煤?jiǎn)單的貪心算法按價(jià)值重量比價(jià)值/重量降序排列物品依次放入背包直到放不下為止。這個(gè)解是可行的且質(zhì)量通常不錯(cuò)。2.3 與其它啟發(fā)式算法的對(duì)比思考為什么選TS而不是模擬退火SA或遺傳算法GAvs 模擬退火SA通過(guò)一個(gè)逐漸降低的“溫度”來(lái)控制接受差解的概率從而跳出局部最優(yōu)。它的搜索更“隨機(jī)”和“全局”。TS則通過(guò)禁忌表強(qiáng)制性地引導(dǎo)搜索走向新區(qū)域搜索更“確定”和“有方向”。在背包問(wèn)題上TS通常收斂更快但參數(shù)禁忌長(zhǎng)度設(shè)置對(duì)性能影響敏感。vs 遺傳算法GA通過(guò)種群進(jìn)化、交叉、變異來(lái)搜索并行性好能探索解空間的不同區(qū)域。但GA操作復(fù)雜需要設(shè)計(jì)交叉算子且對(duì)于背包問(wèn)題交叉后容易產(chǎn)生不可行解修復(fù)機(jī)制復(fù)雜。TS是單點(diǎn)搜索結(jié)構(gòu)更簡(jiǎn)單更易于針對(duì)特定問(wèn)題定制鄰域和禁忌策略。注意沒(méi)有一種算法在所有問(wèn)題上都是最好的。選擇TS是因?yàn)樗诮M合優(yōu)化問(wèn)題中表現(xiàn)穩(wěn)健且其“禁忌”思想非常直觀易于理解和實(shí)現(xiàn)。對(duì)于中等規(guī)模的背包問(wèn)題TS往往能在可接受的時(shí)間內(nèi)找到質(zhì)量非常高的解。3. MATLAB實(shí)現(xiàn)詳解與核心代碼拆解下面我將結(jié)合代碼一步步拆解如何在MATLAB中實(shí)現(xiàn)禁忌搜索求解0-1背包問(wèn)題。我會(huì)先給出整體框架然后深入每個(gè)關(guān)鍵函數(shù)。3.1 問(wèn)題數(shù)據(jù)定義與初始化首先我們需要定義問(wèn)題。假設(shè)我們有N個(gè)物品每個(gè)物品有重量w和價(jià)值v背包容量為C。%% 1. 問(wèn)題參數(shù)設(shè)置 N 100; % 物品數(shù)量 C 500; % 背包容量 w randi([1, 50], 1, N); % 隨機(jī)生成物品重量范圍1~50 v randi([10, 100], 1, N); % 隨機(jī)生成物品價(jià)值范圍10~100 % 計(jì)算價(jià)值重量比用于生成初始解 ratio v ./ w; [~, sorted_idx] sort(ratio, ‘descend’);這里用隨機(jī)數(shù)生成問(wèn)題實(shí)例方便測(cè)試。在實(shí)際應(yīng)用中w,v,C是你的實(shí)際數(shù)據(jù)。3.2 禁忌搜索主循環(huán)框架主函數(shù)是算法的驅(qū)動(dòng)核心它控制著迭代的流程。%% 2. 禁忌搜索參數(shù) max_iter 1000; % 最大迭代次數(shù) tabu_tenure 10; % 禁忌長(zhǎng)度 penalty 1000; % 不可行解懲罰系數(shù) %% 3. 初始化 % 生成初始解貪心 current_solution zeros(1, N); current_weight 0; for i 1:length(sorted_idx) idx sorted_idx(i); if current_weight w(idx) C current_solution(idx) 1; current_weight current_weight w(idx); end end current_value sum(v .* current_solution); best_solution current_solution; best_value current_value; best_weight current_weight; % 初始化禁忌表記錄物品索引和剩余禁忌期 tabu_list zeros(1, N); % tabu_list(i)k 表示物品i還有k次迭代被禁忌 % 記錄迭代過(guò)程用于分析 history_best_value zeros(1, max_iter); history_current_value zeros(1, max_iter); %% 4. 禁忌搜索主循環(huán) for iter 1:max_iter % 尋找當(dāng)前解的所有鄰域解通過(guò)單次翻轉(zhuǎn) best_candidate_value -inf; best_candidate_index -1; best_candidate_solution []; best_candidate_weight 0; % 遍歷所有可能的翻轉(zhuǎn) for i 1:N % 復(fù)制當(dāng)前解并翻轉(zhuǎn)第i位 candidate current_solution; candidate(i) 1 - candidate(i); % 計(jì)算新解的重量和價(jià)值 cand_weight sum(w .* candidate); cand_value sum(v .* candidate); % 計(jì)算適應(yīng)度含懲罰 if cand_weight C fitness cand_value - penalty * (cand_weight - C); else fitness cand_value; end % 判斷是否優(yōu)于當(dāng)前最佳候選解 % 滿足藐視準(zhǔn)則優(yōu)于歷史最優(yōu)或該移動(dòng)非禁忌 is_tabu (tabu_list(i) 0); is_aspired (cand_weight C) (cand_value best_value); if (fitness best_candidate_value) (~is_tabu || is_aspired) best_candidate_value fitness; best_candidate_index i; best_candidate_solution candidate; best_candidate_weight cand_weight; best_candidate_real_value cand_value; % 記錄真實(shí)價(jià)值不含懲罰 end end % 更新當(dāng)前解 if best_candidate_index ~ -1 current_solution best_candidate_solution; current_value best_candidate_real_value; current_weight best_candidate_weight; % 更新禁忌表1. 所有條目禁忌期減12. 將本次移動(dòng)加入禁忌表 tabu_list max(0, tabu_list - 1); % 禁忌期遞減 tabu_list(best_candidate_index) tabu_tenure; % 設(shè)置新的禁忌 % 更新歷史最優(yōu)解 if (current_weight C) (current_value best_value) best_value current_value; best_solution current_solution; best_weight current_weight; end else % 如果沒(méi)找到可行移動(dòng)理論上很少發(fā)生可以執(zhí)行一個(gè)隨機(jī)移動(dòng)或重啟 % 這里簡(jiǎn)單跳過(guò) warning(‘在迭代 %d 未找到可接受移動(dòng)?！? iter); end % 記錄歷史 history_best_value(iter) best_value; history_current_value(iter) current_value; % 可以添加提前終止條件例如最優(yōu)解連續(xù)多代未改進(jìn) if iter 50 all(diff(history_best_value(iter-50:iter)) 0) fprintf(‘迭代 %d: 最優(yōu)解已連續(xù)50代未更新提前終止。\n’, iter); break; end end代碼關(guān)鍵點(diǎn)解析鄰域搜索這里采用了最簡(jiǎn)單的“全鄰域”搜索即評(píng)估翻轉(zhuǎn)每一個(gè)物品產(chǎn)生的候選解。對(duì)于大規(guī)模問(wèn)題N1000這可能會(huì)成為性能瓶頸此時(shí)可以考慮隨機(jī)采樣部分鄰域。適應(yīng)度計(jì)算fitness用于比較候選解的好壞。對(duì)于可行解它就是價(jià)值對(duì)于不可行解它等于價(jià)值減去一個(gè)懲罰項(xiàng)。懲罰系數(shù)penalty需要設(shè)置得足夠大通常要遠(yuǎn)大于物品的最大價(jià)值以確保任何不可行解的適應(yīng)度都低于任何可行解。移動(dòng)接受準(zhǔn)則這是TS的核心邏輯。一個(gè)移動(dòng)被接受的條件是它是所有候選解中適應(yīng)度最高的并且它不在禁忌表中或者它滿足藐視準(zhǔn)則。藐視準(zhǔn)則這里定義為“產(chǎn)生的新解是可行的并且其真實(shí)價(jià)值超過(guò)了歷史最優(yōu)值”。禁忌表更新采用“遞減”模式。每次迭代所有禁忌項(xiàng)的剩余期數(shù)減1最小為0。然后將本次執(zhí)行的移動(dòng)翻轉(zhuǎn)的物品索引的禁忌期數(shù)設(shè)為tabu_tenure。提前終止一個(gè)實(shí)用的技巧是監(jiān)控歷史最優(yōu)解。如果最優(yōu)解在連續(xù)多代如50代內(nèi)都沒(méi)有提升可以認(rèn)為算法已經(jīng)收斂或陷入僵局提前結(jié)束循環(huán)以節(jié)省時(shí)間。3.3 結(jié)果可視化與分析算法跑完了我們得看看效果。MATLAB的繪圖功能這時(shí)就派上大用場(chǎng)了。%% 5. 結(jié)果輸出與可視化 fprintf(‘問(wèn)題規(guī)模: %d個(gè)物品背包容量: %d\n’, N, C); fprintf(‘禁忌搜索找到的最優(yōu)價(jià)值: %.2f\n’, best_value); fprintf(‘對(duì)應(yīng)背包重量: %.2f (容量: %d)\n’, best_weight, C); fprintf(‘選中物品數(shù)量: %d\n’, sum(best_solution)); % 繪制搜索過(guò)程 figure(‘Position‘, [100, 100, 1200, 400]); subplot(1,2,1); plot(1:iter, history_best_value(1:iter), ‘b-‘, ‘LineWidth‘, 1.5); hold on; plot(1:iter, history_current_value(1:iter), ‘r-.’, ‘LineWidth‘, 1); xlabel(‘迭代次數(shù)‘); ylabel(‘物品總價(jià)值‘); title(‘禁忌搜索過(guò)程曲線‘); legend(‘歷史最優(yōu)值‘, ‘當(dāng)前解價(jià)值‘, ‘Location‘, ‘best‘); grid on; % 繪制最終解的物品價(jià)值-重量分布 selected_idx find(best_solution 1); unselected_idx find(best_solution 0); subplot(1,2,2); scatter(w(selected_idx), v(selected_idx), 60, ‘filled‘, ‘MarkerFaceColor‘, ‘g‘); hold on; scatter(w(unselected_idx), v(unselected_idx), 30, ‘x‘, ‘MarkerEdgeColor‘, ‘r‘); xlabel(‘物品重量‘); ylabel(‘物品價(jià)值‘); title(‘最終解物品分布綠色為選中‘); % 畫(huà)一條容量線 line([C, C], ylim, ‘Color‘, ‘k‘, ‘LineStyle‘, ‘–‘, ‘LineWidth‘, 2); text(C*1.02, max(v)*0.9, sprintf(‘容量%d‘, C), ‘FontSize‘, 10); grid on;左邊的圖展示了算法迭代過(guò)程中“當(dāng)前解”和“歷史最優(yōu)解”的價(jià)值變化。你能看到歷史最優(yōu)解是階梯式上升的而當(dāng)前解則上下波動(dòng)這正是TS在探索接受非最優(yōu)移動(dòng)和利用找到更優(yōu)解之間平衡的體現(xiàn)。右邊的散點(diǎn)圖直觀展示了哪些物品被選中綠色實(shí)心點(diǎn)哪些被舍棄紅色叉號(hào)以及它們相對(duì)于背包容量線黑色虛線的分布有助于我們定性分析解的質(zhì)量。4. 關(guān)鍵參數(shù)調(diào)優(yōu)與性能分析禁忌搜索的性能很大程度上依賴于參數(shù)設(shè)置。盲目調(diào)參事倍功半理解參數(shù)背后的意義才能有的放矢。4.1 核心參數(shù)影響分析禁忌長(zhǎng)度Tabu Tenure作用控制短期記憶的時(shí)長(zhǎng)。長(zhǎng)度太短算法容易在局部最優(yōu)解附近循環(huán)頻繁重復(fù)相同的移動(dòng)長(zhǎng)度太長(zhǎng)會(huì)過(guò)度限制搜索空間導(dǎo)致算法探索效率低下收斂緩慢。調(diào)優(yōu)經(jīng)驗(yàn)一個(gè)經(jīng)典的啟發(fā)式設(shè)置是tabu_tenure sqrt(N)到N/5之間其中N是問(wèn)題規(guī)模物品數(shù)?？梢詮膕qrt(N)開(kāi)始嘗試。在我的實(shí)驗(yàn)中對(duì)于N100的問(wèn)題禁忌長(zhǎng)度在7到15之間效果較好。一個(gè)實(shí)用的方法是動(dòng)態(tài)調(diào)整禁忌長(zhǎng)度例如在一個(gè)范圍內(nèi)隨機(jī)取值可以增加搜索的多樣性。懲罰系數(shù)Penalty作用將不可行解的量綱統(tǒng)一到與目標(biāo)函數(shù)價(jià)值可比并引導(dǎo)搜索向可行域靠近。調(diào)優(yōu)經(jīng)驗(yàn)必須足夠大確保任何不可行解的適應(yīng)度都低于最差的可行解。一個(gè)安全的設(shè)置是penalty max(v) * 10或更大。但也不是越大越好過(guò)大的懲罰會(huì)使適應(yīng)度函數(shù)在不可行域變得“陡峭”可能影響搜索的平滑性。可以設(shè)為max(v) * (1 N/10)。最大迭代次數(shù)Max Iterations作用控制算法的總計(jì)算預(yù)算。迭代次數(shù)越多找到更好解的機(jī)會(huì)越大但耗時(shí)也越長(zhǎng)。調(diào)優(yōu)經(jīng)驗(yàn)這通常取決于你對(duì)時(shí)間的要求和解的質(zhì)量的權(quán)衡?？梢越Y(jié)合“提前終止條件”來(lái)設(shè)置一個(gè)較大的值如2000或5000讓算法在收斂后自動(dòng)停止。監(jiān)控歷史最優(yōu)解曲線是判斷迭代是否足夠的最佳方式。鄰域大小在我們的實(shí)現(xiàn)中每次迭代評(píng)估全部N個(gè)鄰居全鄰域搜索。對(duì)于大規(guī)模問(wèn)題N5000這會(huì)導(dǎo)致單次迭代耗時(shí)過(guò)長(zhǎng)。此時(shí)可以采用候選列表策略Candidate List Strategy即每次只隨機(jī)評(píng)估一部分如k50或100個(gè)鄰居。雖然可能錯(cuò)過(guò)當(dāng)前最好的移動(dòng)但大大提升了迭代速度整體上往往能在相同時(shí)間內(nèi)探索更多樣化的區(qū)域。4.2 進(jìn)階策略增強(qiáng)搜索能力基礎(chǔ)的TS有時(shí)會(huì)陷入一個(gè)“高原區(qū)”即所有鄰域移動(dòng)都無(wú)法改善解。為了提升性能可以引入以下策略多樣化與集中化搜索集中化Intensification當(dāng)找到一個(gè)有希望的區(qū)域時(shí)進(jìn)行更精細(xì)的搜索。例如可以臨時(shí)縮短禁忌長(zhǎng)度或者記錄“精英解”的特征在后續(xù)搜索中傾向于包含這些特征。多樣化Diversification當(dāng)搜索停滯時(shí)主動(dòng)跳出當(dāng)前區(qū)域。方法包括重啟用新的隨機(jī)初始解重新開(kāi)始、進(jìn)行一系列強(qiáng)制擾動(dòng)如隨機(jī)翻轉(zhuǎn)多個(gè)物品、或者引入一個(gè)長(zhǎng)期記憶頻率記憶懲罰那些經(jīng)常被訪問(wèn)的解的屬性鼓勵(lì)探索低頻區(qū)域。實(shí)現(xiàn)思路可以監(jiān)控最優(yōu)解未更新的迭代次數(shù)。如果超過(guò)閾值如200次則觸發(fā)一個(gè)多樣化操作比如隨機(jī)改變當(dāng)前解中20%的物品狀態(tài)然后繼續(xù)搜索。自適應(yīng)禁忌長(zhǎng)度讓禁忌長(zhǎng)度根據(jù)搜索狀態(tài)動(dòng)態(tài)變化。例如當(dāng)搜索過(guò)程頻繁接受移動(dòng)時(shí)可以增加禁忌長(zhǎng)度以加強(qiáng)探索當(dāng)搜索停滯時(shí)可以減少禁忌長(zhǎng)度以加強(qiáng)局部搜索。一種簡(jiǎn)單實(shí)現(xiàn)tabu_tenure base_tenure randn() * variance其中base_tenure是基礎(chǔ)長(zhǎng)度variance是擾動(dòng)方差?；旌纤惴▽S與其他算法的思想結(jié)合。例如TS與局部搜索LS結(jié)合在TS的每次迭代中對(duì)找到的新當(dāng)前解執(zhí)行一個(gè)快速的局部搜索如首次改進(jìn)爬山法將其推到最近的局部最優(yōu)然后再由TS負(fù)責(zé)跳出這個(gè)局部最優(yōu)。這種“TSLS”的框架在很多問(wèn)題上效果顯著。4.3 性能評(píng)估與對(duì)比實(shí)驗(yàn)如何知道你的TS實(shí)現(xiàn)得好不好需要設(shè)計(jì)實(shí)驗(yàn)來(lái)評(píng)估。與精確解對(duì)比小規(guī)模對(duì)于物品數(shù)N較小如30的問(wèn)題可以用動(dòng)態(tài)規(guī)劃求出精確最優(yōu)解。然后運(yùn)行TS多次如30次計(jì)算1)平均誤差(最優(yōu)值 - TS平均值) / 最優(yōu)值2)找到最優(yōu)解的成功率。這可以驗(yàn)證算法邏輯的正確性和有效性。與其它啟發(fā)式算法對(duì)比中大規(guī)模對(duì)于無(wú)法精確求解的大規(guī)模問(wèn)題可以對(duì)比不同啟發(fā)式算法在相同計(jì)算時(shí)間或迭代次數(shù)下的解的質(zhì)量。常見(jiàn)的對(duì)比對(duì)象包括簡(jiǎn)單貪心算法按價(jià)值重量比排序作為基線。模擬退火算法SA對(duì)比收斂速度和最終解質(zhì)量。遺傳算法GA對(duì)比在復(fù)雜實(shí)例上的魯棒性。商業(yè)求解器如MATLAB的intlinprog對(duì)于混合整數(shù)線性規(guī)劃形式的背包問(wèn)題可以用求解器求精確解或高質(zhì)量上界作為參考。魯棒性測(cè)試在不同類型的問(wèn)題實(shí)例上測(cè)試你的TS實(shí)現(xiàn)。例如隨機(jī)實(shí)例重量和價(jià)值隨機(jī)生成。相關(guān)實(shí)例物品價(jià)值與重量高度正相關(guān)或負(fù)相關(guān)。大重量實(shí)例單個(gè)物品重量接近背包容量。 觀察算法在不同場(chǎng)景下的表現(xiàn)是否穩(wěn)定。在MATLAB中你可以編寫一個(gè)測(cè)試腳本批量生成不同規(guī)模的實(shí)例運(yùn)行不同參數(shù)的TS并自動(dòng)記錄結(jié)果到表格或文件中便于分析。% 示例簡(jiǎn)單對(duì)比實(shí)驗(yàn)框架 instances {‘rand_50‘, ‘rand_100‘, ‘corr_100‘}; % 不同實(shí)例 algorithms {‘TS‘, ‘Greedy‘, ‘SA‘}; % 不同算法 results cell(length(instances), length(algorithms)); for i 1:length(instances) [w, v, C] generate_instance(instances{i}); % 自定義實(shí)例生成函數(shù) for j 1:length(algorithms) switch algorithms{j} case ‘TS‘ [best_val, ~] taboo_search(w, v, C); % 你的TS函數(shù) case ‘Greedy‘ best_val greedy_algorithm(w, v, C); case ‘SA‘ best_val simulated_annealing(w, v, C); end results{i, j} best_val; end end % 可以用table或直接plot展示結(jié)果對(duì)比5. 常見(jiàn)問(wèn)題、調(diào)試技巧與避坑指南在實(shí)際編碼和調(diào)試過(guò)程中你肯定會(huì)遇到各種問(wèn)題。下面是我總結(jié)的一些典型坑點(diǎn)和解決思路。5.1 算法收斂性問(wèn)題問(wèn)題表現(xiàn)算法很快幾十次迭代就停滯不前歷史最優(yōu)解不再更新或者一直在幾個(gè)相近的解之間循環(huán)。排查與解決檢查禁忌長(zhǎng)度這是最常見(jiàn)的原因。禁忌長(zhǎng)度設(shè)得太小比如1或2算法記憶太短容易陷入短循環(huán)。嘗試增加禁忌長(zhǎng)度到sqrt(N)附近。檢查鄰域結(jié)構(gòu)如果只使用“單次翻轉(zhuǎn)”鄰域搜索步長(zhǎng)可能太小?？梢試L試引入大鄰域操作如“雙次翻轉(zhuǎn)”同時(shí)改變兩個(gè)物品的狀態(tài)或“交換操作”。這能幫助算法跳出某些局部最優(yōu)。檢查初始解如果初始解質(zhì)量太差算法可能一開(kāi)始就困在糟糕的區(qū)域。嘗試用不同的方法生成多個(gè)初始解或者直接從一個(gè)隨機(jī)可行解開(kāi)始。引入多樣化機(jī)制如4.2節(jié)所述實(shí)現(xiàn)一個(gè)簡(jiǎn)單的重啟策略。當(dāng)最優(yōu)解連續(xù)stagnation_iter代未更新時(shí)保留歷史最優(yōu)解但將當(dāng)前解重置為一個(gè)新的隨機(jī)解或擾動(dòng)歷史最優(yōu)解然后繼續(xù)搜索。5.2 解不可行問(wèn)題問(wèn)題表現(xiàn)算法最終輸出的best_solution的總重量超過(guò)了背包容量C。排查與解決檢查懲罰系數(shù)這是罪魁禍?zhǔn)住土P系數(shù)penalty設(shè)置得太小導(dǎo)致不可行解的適應(yīng)度可能比某些差一點(diǎn)的可行解還要高算法就會(huì)傾向于選擇不可行解。確保penalty max(v)。一個(gè)簡(jiǎn)單的測(cè)試手動(dòng)構(gòu)造一個(gè)明顯不可行但價(jià)值很高的解計(jì)算其適應(yīng)度它應(yīng)該遠(yuǎn)小于一個(gè)可行的、價(jià)值很低的解的適應(yīng)度。檢查藐視準(zhǔn)則在代碼的移動(dòng)接受部分要確保只有可行解才能觸發(fā)藐視準(zhǔn)則。即判斷is_aspired時(shí)必須同時(shí)滿足cand_weight C和cand_value best_value。如果忽略了可行性檢查一個(gè)不可行但價(jià)值虛高因?yàn)閼土P不夠的解可能會(huì)被破格接受。最終解修復(fù)作為一種后處理保障可以在算法結(jié)束后對(duì)best_solution執(zhí)行一個(gè)簡(jiǎn)單的修復(fù)程序。如果它不可行則按價(jià)值重量比升序移除物品直到總重量滿足約束。雖然這有點(diǎn)“作弊”但在實(shí)際應(yīng)用中確保解可行是首要的。5.3 MATLAB實(shí)現(xiàn)性能優(yōu)化問(wèn)題表現(xiàn)當(dāng)物品數(shù)量N很大比如超過(guò)5000時(shí)算法運(yùn)行非常慢。排查與解決向量化操作這是MATLAB性能提升的關(guān)鍵。避免在循環(huán)內(nèi)對(duì)向量進(jìn)行點(diǎn)乘求和。例如計(jì)算候選解的價(jià)值和重量% 低效做法在循環(huán)內(nèi) cand_weight 0; cand_value 0; for j 1:N if candidate(j)1 cand_weight cand_weight w(j); cand_value cand_value v(j); end end % 高效做法向量化 cand_weight w * candidate‘; % 或者 sum(w .* candidate) cand_value v * candidate‘; % 或者 sum(v .* candidate)減少全鄰域搜索如4.1節(jié)所述使用候選列表。每次迭代不是評(píng)估所有N個(gè)鄰居而是隨機(jī)選擇k個(gè)k N進(jìn)行評(píng)估。這能極大減少單次迭代的計(jì)算量。預(yù)計(jì)算與緩存如果問(wèn)題規(guī)模固定可以預(yù)計(jì)算一些信息。但TS中每次移動(dòng)只改變一個(gè)物品解的總重量和價(jià)值可以增量更新而不需要每次都重新計(jì)算全部。% 假設(shè)我們知道當(dāng)前解的重量 current_weight 和價(jià)值 current_value % 當(dāng)翻轉(zhuǎn)物品 i 時(shí) if current_solution(i) 1 % 原來(lái)是選的現(xiàn)在不選 new_weight current_weight - w(i); new_value current_value - v(i); else % 原來(lái)沒(méi)選現(xiàn)在選 new_weight current_weight w(i); new_value current_value v(i); end這比每次都做向量點(diǎn)乘要快得多尤其是在鄰域搜索的循環(huán)內(nèi)。5.4 參數(shù)敏感性與實(shí)驗(yàn)設(shè)計(jì)問(wèn)題不知道如何設(shè)置參數(shù)感覺(jué)效果時(shí)好時(shí)壞。建議進(jìn)行系統(tǒng)的參數(shù)實(shí)驗(yàn)。固定其他參數(shù)變化一個(gè)參數(shù)如禁忌長(zhǎng)度在多個(gè)問(wèn)題實(shí)例上運(yùn)行算法記錄平均最終解質(zhì)量和運(yùn)行時(shí)間。用MATLAB的繪圖功能畫(huà)出參數(shù)與性能的關(guān)系曲線。你會(huì)發(fā)現(xiàn)性能往往在一個(gè)參數(shù)區(qū)間內(nèi)比較穩(wěn)定這就是你可以使用的參數(shù)范圍。不要追求一個(gè)“萬(wàn)能”的最優(yōu)參數(shù)理解參數(shù)的影響趨勢(shì)更重要。最后分享一個(gè)我調(diào)試時(shí)的小技巧大量使用MATLAB的圖形化輸出。除了繪制收斂曲線你還可以實(shí)時(shí)輸出當(dāng)前解、禁忌表狀態(tài)、接受移動(dòng)的類型是普通移動(dòng)還是破禁移動(dòng)等信息到圖形或命令行。這能讓你直觀地“看到”算法的行為對(duì)于理解算法動(dòng)態(tài)和定位問(wèn)題非常有幫助。例如如果你發(fā)現(xiàn)很長(zhǎng)一段時(shí)間都沒(méi)有發(fā)生“破禁”移動(dòng)可能意味著懲罰系數(shù)設(shè)得太高或者鄰域結(jié)構(gòu)太局限導(dǎo)致算法無(wú)法找到能觸發(fā)藐視準(zhǔn)則的解。調(diào)試算法就像偵探破案這些可視化線索就是你的關(guān)鍵證據(jù)。本文還有配套的精品資源點(diǎn)擊獲取