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