做網(wǎng)絡(luò)流優(yōu)化的人應(yīng)該都有過這種體驗(yàn)約束一多教科書上那套最大流、最小費(fèi)用流的增廣路算法就開始吃緊。我最近處理一個(gè)有向網(wǎng)絡(luò)的最小成本流量分配問題除了基本的容量約束、流量守恒還摻了分段非線性成本和多個(gè)源匯點(diǎn)LINGO、線性規(guī)劃松弛都試了一圈效果不理想最后靠在Matlab里實(shí)現(xiàn)遺傳算法GA配合路徑流量編碼把整套求解器跑通了結(jié)果相當(dāng)穩(wěn)。這篇就把完整思路、關(guān)鍵代碼框架、調(diào)參心得和踩過的坑全部分享出來。先說結(jié)論遺傳算法解決約束優(yōu)化網(wǎng)絡(luò)流問題核心不在于“用GA替代所有網(wǎng)絡(luò)流算法”而在于把網(wǎng)絡(luò)流的約束結(jié)構(gòu)合理地融進(jìn)編碼和適應(yīng)度函數(shù)里。約束處理好了收斂速度和穩(wěn)定性都讓人滿意處理不好種群散成一鍋粥跑了上百代都得不到一個(gè)可行解。1. 問題長什么樣約束優(yōu)化網(wǎng)絡(luò)流問題的數(shù)學(xué)表達(dá)與破題思路1.1 先從一段具體場景說起想象一個(gè)有向圖 G(V, E)節(jié)點(diǎn) V 里有源點(diǎn) s 和匯點(diǎn) t每條有向邊 e 有容量上限 c_e單位流量成本 w_e。經(jīng)典最小費(fèi)用流問題是從 s 往 t 輸送固定流量 F怎么分配各邊流量 f_e讓總費(fèi)用最低同時(shí)保證每條邊不超容量、中間節(jié)點(diǎn)流入等于流出。這個(gè)模型看起來成熟可一旦約束升級傳統(tǒng)方法就難受了。我現(xiàn)在遇到的實(shí)際問題是部分邊的成本不是線性函數(shù)而是隨負(fù)載變化的分段函數(shù)運(yùn)輸量越大單位成本跳變除了匯點(diǎn)整體流量約束還必須滿足某些中間節(jié)點(diǎn)的流量下限相當(dāng)于區(qū)域保底供給同一個(gè)網(wǎng)絡(luò)里有多個(gè)源點(diǎn)和多個(gè)匯點(diǎn)每個(gè)匯點(diǎn)的需求量還不同。這類問題寫成等式和不等式約束以后可行域非常崎嶇。單純形法能處理線性目標(biāo)但非線性成本沒法直接用增廣路算法處理固定費(fèi)用和分段費(fèi)用時(shí)每輪都要重新修改殘量網(wǎng)絡(luò)的費(fèi)用結(jié)構(gòu)實(shí)現(xiàn)復(fù)雜度陡增商用求解器能解但授權(quán)成本高而且想嵌入到自己寫的仿真系統(tǒng)里也不方便。這時(shí)候遺傳算法就用得上了。它不要求目標(biāo)函數(shù)連續(xù)、可導(dǎo)也不要求可行域是凸集你只要能把“一組變量取值算出一個(gè)得分”它就能在這個(gè)得分的地形上做種群的進(jìn)化搜索。網(wǎng)絡(luò)流問題恰好具備這個(gè)特點(diǎn)流量分配方案可以編碼成染色體目標(biāo)函數(shù)可以直接算費(fèi)用和違約束程度。1.2 為什么傳統(tǒng)方法在這里吃癟傳統(tǒng)網(wǎng)絡(luò)流算法之所以高效是因?yàn)樗疃纫蕾噯栴}的線性結(jié)構(gòu)和特殊約束結(jié)構(gòu)。最大流用層次圖BFS最小費(fèi)用流用SPFA或Dijkstra配合勢能函數(shù)這些算法都在“線性費(fèi)用”和“純?nèi)萘考s束”的框架下做文章。一旦約束結(jié)構(gòu)變化比如加入耦合約束、非線性費(fèi)用、多商品約束算法的理論基礎(chǔ)就動(dòng)搖了一大半。我在實(shí)際測試中的體驗(yàn)是用經(jīng)典的連續(xù)最短路增廣法處理非線性成本時(shí)每輪增廣的最優(yōu)路徑會隨流量分配而變化嚴(yán)格來說需要重新計(jì)算全局殘差導(dǎo)致程序反復(fù)迭代效率極差。如果網(wǎng)絡(luò)規(guī)模到了幾十個(gè)節(jié)點(diǎn)上百條邊直接用動(dòng)態(tài)規(guī)劃枚舉路徑組合也完全是不現(xiàn)實(shí)的。而GA處理這些復(fù)雜約束的方式說白了就是“粗糙但靈活”。它不追求每一步都嚴(yán)格朝向最優(yōu)方向而是保留一個(gè)候選解群體通過選擇、交叉、變異不斷篩選。哪怕目標(biāo)函數(shù)是不連續(xù)的黑盒函數(shù)GA依然能給你一個(gè)可用的近似最優(yōu)解。對于工程場景這往往比為了絕對最優(yōu)而犧牲開發(fā)效率更加實(shí)惠。1.3 遺傳算法憑什么接得住這個(gè)活GA求解網(wǎng)絡(luò)流問題的邏輯鏈條其實(shí)很清晰用染色體表示一個(gè)流量分配方案用適應(yīng)度函數(shù)評估這個(gè)方案的好壞包括費(fèi)用、流量達(dá)成度和約束違反程度通過選擇算子保留優(yōu)秀的方案通過交叉算子組合出更優(yōu)的新方案通過變異算子探索新的流量組合。這套機(jī)制不需要你對網(wǎng)絡(luò)流理論有多深的掌握只要能把“方案如何表示”“好壞如何量化”這兩個(gè)問題答清楚GA就能跑起來。這也是我推薦非算法研究背景的人用GA處理復(fù)雜網(wǎng)絡(luò)流問題的原因門檻低部署快核心精力可以花在建模和調(diào)參上而不是重寫一套組合優(yōu)化算法。當(dāng)然GA不是銀彈。如果網(wǎng)絡(luò)規(guī)模超大比如上萬條邊GA的收斂速度和精度會明顯吃虧那種場景更適合列生成、分支定界或者專用的分解算法。但中小規(guī)模工程問題GA的性價(jià)比非常高。2. 建模與編碼把網(wǎng)絡(luò)流塞進(jìn)GA的染色體里2.1 決策變量的編碼方式選擇編碼是GA里最關(guān)鍵的決策直接決定后續(xù)算子怎么寫。求解網(wǎng)絡(luò)流問題時(shí)我見過兩種主流編碼思路。第一種是邊流量編碼。染色體向量直接表示每條邊上的流量長度等于邊數(shù) E。優(yōu)點(diǎn)是直觀改哪個(gè)變量就是調(diào)動(dòng)哪條邊缺點(diǎn)也很明顯隨機(jī)生成的染色體大概率不滿足流量守恒和容量約束。為了約束違例你得在適應(yīng)度函數(shù)里加一堆懲罰項(xiàng)相當(dāng)于把可行性重建的難度扔給算法本身搜索效率會被拖累。第二種是路徑流量編碼。先枚舉或啟發(fā)式生成一組從源點(diǎn)到匯點(diǎn)的候選路徑染色體每個(gè)基因表示一條候選路徑上的流量。由于每條路徑本身就是滿足流量守恒的任何一組路徑流量疊加后中間節(jié)點(diǎn)依然滿足流入等于流出守恒約束天然滿足。剩下要處理的只有容量約束和特定節(jié)點(diǎn)的流量下限約束。我強(qiáng)烈推薦路徑流量編碼這是我在多次調(diào)試后確定下來的主力方案。它的另一個(gè)好處是解碼邏輯很簡單恢復(fù)網(wǎng)絡(luò)流只要按路徑累加流量連矩陣運(yùn)算都不用怎么操心。路徑候選集怎么來對中小規(guī)模網(wǎng)絡(luò)可以用深度優(yōu)先搜索枚舉簡單路徑網(wǎng)絡(luò)稍大用K最短路徑算法抽取前K條或者先跑幾次最短路算法收集常見路徑。備選路徑寧多勿少因?yàn)槿绻顑?yōu)解里某條關(guān)鍵路徑壓根不在候選集里你怎么進(jìn)化都不可能找到它。2.2 目標(biāo)函數(shù)與約束條件的轉(zhuǎn)化懲罰函數(shù)法細(xì)節(jié)編碼確定后下一個(gè)問題就是適應(yīng)度函數(shù)。網(wǎng)絡(luò)流問題天然分兩塊目標(biāo)費(fèi)用和約束滿足度。我采用的思路是加權(quán)目標(biāo) 懲罰項(xiàng)[ fit(x) totalCost(x) \alpha \cdot violCap(x) \beta \cdot violDemand(x) ]其中 totalCost 是所有邊上的流量費(fèi)用總和violCap 是容量超限的總量violDemand 是各匯點(diǎn)需求未滿足的總量α、β是懲罰系數(shù)。這里有個(gè)容易翻車的細(xì)節(jié)懲罰系數(shù)的量級必須與目標(biāo)費(fèi)用處于同一數(shù)量級或者略大但不要大得離譜。我見過有人把懲罰系數(shù)設(shè)成 1e8結(jié)果GA前幾十代全部被“超級懲罰”主導(dǎo)所有個(gè)體都在拼命降違約束目標(biāo)費(fèi)用反而被忽略了最后收斂到一個(gè)費(fèi)用很低但流量完全不對的“假最優(yōu)”。懲罰系數(shù)的正確調(diào)法是先做幾次隨機(jī)種群預(yù)實(shí)驗(yàn)統(tǒng)計(jì)隨機(jī)方案的violCap和violDemand均值再讓α·violCap和totalCost的期望大致處于同一數(shù)量級。除了懲罰還可以做修復(fù)。比如容量超限時(shí)把超限路徑的流量按比例削減讓它降到容量以內(nèi)。修復(fù)思路能顯著提升搜索效率但會增加代碼復(fù)雜度。我個(gè)人的做法是簡單問題只懲罰不修復(fù)復(fù)雜問題懲罰加修復(fù)雙管齊下。等代碼框架穩(wěn)定后再增加修復(fù)邏輯不遲。2.3 初始化種群別讓第一批個(gè)體全是廢物初始化種群的目標(biāo)是讓初始個(gè)體盡可能覆蓋可行域和近可行域。我常用的三個(gè)策略把一部分個(gè)體初始化為沿最短路徑按當(dāng)前成本均勻分配的流量方案把一部分個(gè)體初始化為均勻隨機(jī)分配流量模擬雜亂搜索把一部分個(gè)體初始化為只在少數(shù)路徑上集中運(yùn)輸、其他路徑為零的方案模擬真實(shí)調(diào)度中的“主干道依賴”?；旌铣跏蓟鼙ＷC第一代里既有可行的保守方案又有探索性的亂序方案GA的選擇壓力就有米下鍋。如果初始種群全是隨機(jī)生成的流量向量很大概率所有個(gè)體都極度違反約束適應(yīng)度曲線一開始就被懲罰項(xiàng)淹沒了。在Matlab里初始化一個(gè)路徑流量個(gè)體非常簡單核心就一句話pop(i,:) rand(1, numPaths) .* rand(1, numPaths) * initScale;initScale 可以用總流量需求除以路徑條數(shù)來估算這樣初始解的流量總量不會偏離需求太遠(yuǎn)。3. Matlab代碼實(shí)現(xiàn)主循環(huán)、算子與調(diào)參實(shí)錄3.1 算法主框架與數(shù)據(jù)結(jié)構(gòu)組織我用的Matlab版本是R2023b全程手寫GA沒有用自帶的全局優(yōu)化工具箱這樣對算子和懲罰邏輯能完全掌控。整個(gè)求解器分成三個(gè)文件main_ga_network.m主腳本、fitness_network.m適應(yīng)度函數(shù)、run_ga_core.mGA主循環(huán)。網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)用一個(gè)struct組織% 邊表 edges [ 1 2 10 2.0; % 起點(diǎn) 終點(diǎn) 容量 單位成本 1 3 8 3.5; 2 4 6 1.8; 3 4 10 2.2; 2 5 7 4.0; 4 5 9 3.0; 3 5 12 2.8; 5 6 15 1.5; ]; % 將邊表轉(zhuǎn)成結(jié)構(gòu)體 G.edges edges(:,1:2); G.cap edges(:,3); G.cost edges(:,4);候選路徑用一個(gè)元胞數(shù)組存每一行是路徑經(jīng)過的節(jié)點(diǎn)序列。我用的測試網(wǎng)絡(luò)有6個(gè)節(jié)點(diǎn)8條邊枚舉出10條簡單路徑作為候選集合。主循環(huán)的結(jié)構(gòu)是標(biāo)準(zhǔn)GA套路for gen 1:maxGen % 計(jì)算適應(yīng)度 fits zeros(popSize,1); for i 1:popSize fits(i) fitness_network(pop(i,:), G, paths, demands); end % 精英保留 [~, idxBest] min(fits); elite pop(idxBest,:); % 錦標(biāo)賽選擇 newPop zeros(popSize, numPaths); for i 1:popSize candidateIdx randi(popSize, 2, 1); [~, winIdx] min(fits(candidateIdx)); newPop(i,:) pop(candidateIdx(winIdx),:); end % 交叉 for i 1:2:popSize-1 if rand pc alpha rand(1, numPaths); newPop(i,:) alpha .* newPop(i,:) (1-alpha) .* newPop(i1,:); newPop(i1,:) (1-alpha) .* newPop(i,:) alpha .* newPop(i1,:); end end % 變異 for i 1:popSize if rand pm mutPos randi(numPaths); newPop(i, mutPos) max(0, newPop(i, mutPos) randn * mutScale); end end pop newPop; pop(1,:) elite; % 精英回填 end這段代碼不是完整工程但體現(xiàn)了手寫GA的所有關(guān)鍵環(huán)節(jié)。注意我這里交叉用了實(shí)數(shù)編碼常用的算術(shù)交叉變異用了高斯擾動(dòng)都是針對連續(xù)流量變量設(shè)計(jì)的。3.2 適應(yīng)度函數(shù)把網(wǎng)絡(luò)流約束寫成可計(jì)算的懲罰適應(yīng)度函數(shù)是這段代碼的心臟。實(shí)現(xiàn)邏輯按三步走第一步根據(jù)染色體重建網(wǎng)絡(luò)流。將每條路徑的流量加到它經(jīng)過的每條邊上得到每條邊上的總流量 f_e。第二步計(jì)算目標(biāo)費(fèi)用 totalCost。這里我實(shí)現(xiàn)了分段線性成本如果某條邊流量超過一個(gè)閾值單位成本上浮一個(gè)比例用來模擬擁堵費(fèi)用。第三步計(jì)算約束違例量。function fitVal fitness_network(x, G, paths, demands) numEdges size(G.edges, 1); edgeFlow zeros(numEdges, 1); % 重建流 for p 1:length(paths) pathNodes paths{p}; for k 1:length(pathNodes)-1 u pathNodes(k); v pathNodes(k1); eid find(G.edges(:,1)u G.edges(:,2)v); if ~isempty(eid) edgeFlow(eid) edgeFlow(eid) x(p); end end end % 費(fèi)用含分段成本 totalCost 0; for e 1:numEdges if edgeFlow(e) G.cap(e) * 0.7 totalCost totalCost G.cost(e) * edgeFlow(e); else totalCost totalCost G.cost(e) * edgeFlow(e) * 1.5; end end % 容量違例 violCap sum(max(0, edgeFlow - G.cap)); % 需求違例這里簡化為匯點(diǎn)總需求 sinkFlow 0; for p 1:length(paths) if pathEndsAtSink(paths{p}) sinkFlow sinkFlow x(p); end end violDemand max(0, demands.total - sinkFlow); alpha 5; beta 5; fitVal totalCost alpha * violCap beta * violDemand; end在實(shí)際運(yùn)行中這個(gè)函數(shù)會被調(diào)用幾千次性能值得摳一下。比如find操作邊表每次線性搜索很慢可以預(yù)先構(gòu)建一個(gè)從 (u,v) 到邊編號的映射矩陣這樣解碼時(shí)直接索引不需要循環(huán)find。我在完整代碼里就是這么做的運(yùn)行速度快了至少三倍。3.3 參數(shù)標(biāo)定一組能跑到收斂的默認(rèn)參數(shù)GA號稱沒有免費(fèi)午餐參數(shù)標(biāo)定從來不是拍腦袋。我跑完實(shí)驗(yàn)以后把常用的參數(shù)范圍和我的默認(rèn)值整理成了一張表新手可以直接照著填。參數(shù)建議范圍我的默認(rèn)值調(diào)整依據(jù)種群規(guī)模 popSize50~200120太小容易早熟太大浪費(fèi)算力最大迭代數(shù) maxGen100~500300看收斂曲線平臺期位置再定交叉概率 pc0.6~0.90.8太高破壞好個(gè)體太低探索不足變異概率 pm0.05~0.20.1突變太少容易陷局部最優(yōu)變異步長 mutScale0.5~2.01.0與流量量級有關(guān)按測試網(wǎng)絡(luò)總流量估算精英保留數(shù)1~21保證最優(yōu)個(gè)體不被交叉變異破壞懲罰系數(shù) alpha/beta與目標(biāo)量級一致5用隨機(jī)種群預(yù)實(shí)驗(yàn)校準(zhǔn)特別說三個(gè)參數(shù)背后的邏輯。種群規(guī)模 popSize 是我最看重的參數(shù)。我試過把 popSize 從 120 調(diào)到 40同樣問題收斂曲線明顯變差達(dá)到相同適應(yīng)度的代數(shù)多了幾乎一倍。原因是網(wǎng)絡(luò)流的候選路徑多點(diǎn)基因位數(shù)變長小種群根本撐不起足夠的多樣性。變異概率 pm 也很敏感。低于 0.05 時(shí)算法很容易卡在局部最優(yōu)因?yàn)榻徊嬷粫岩延谢蚪M合翻來覆去缺少新的流量擾動(dòng)。但如果超過 0.3算法就退化成隨機(jī)搜索了我觀察到的現(xiàn)象是收斂曲線不斷起伏、沒有明顯下降平臺。0.1~0.15 是一個(gè)比較穩(wěn)的甜蜜區(qū)間。懲罰系數(shù) alpha 和 beta 不一定要設(shè)得很大。我一開始設(shè) 100結(jié)果算法前幾十代都在瘋狂壓低違約束費(fèi)用優(yōu)化幾乎停滯后來按隨機(jī)方案違約束量的均值反推把懲罰系數(shù)降到和費(fèi)用量級接近的 5效果立竿見影。3.4 運(yùn)行結(jié)果示意與收斂性分析說一組實(shí)測數(shù)據(jù)。我的六節(jié)點(diǎn)八邊測試網(wǎng)絡(luò)兩個(gè)源點(diǎn)兩個(gè)匯點(diǎn)路徑候選集10條總需求定為30。GA跑300代種群120交叉概率0.8變異概率0.1。記錄下來的每代最優(yōu)適應(yīng)度從第1代的158.6一路降到第220代附近的97.2后面基本維持小幅波動(dòng)。整個(gè)收斂過程有三個(gè)明顯階段前30代適應(yīng)度快速下降主要靠懲罰項(xiàng)縮小說明種群在快速淘汰嚴(yán)重違約束的個(gè)體30~150代適應(yīng)度緩慢下降費(fèi)用項(xiàng)的優(yōu)化開始起主導(dǎo)作用種群在微調(diào)流量分配150代以后基本進(jìn)入平臺期最優(yōu)個(gè)體的流量分配模式變化很小只有變異偶爾產(chǎn)生小幅擾動(dòng)。平臺期出現(xiàn)后可以再疊加一輪局部搜索比如用爬坡法對最優(yōu)個(gè)體做精細(xì)微調(diào)往往還能再擠出2%~5%的費(fèi)用優(yōu)化。這個(gè)“GA找全局爬坡找局部”的組合套路是我試過性價(jià)比最高的優(yōu)化方式。4. 常見問題與排查技巧實(shí)錄4.1 早熟、停滯、抖動(dòng)三個(gè)讓人頭疼的癥狀早熟是GA最常見的翻車現(xiàn)場表現(xiàn)為收斂曲線在很早期就壓平適應(yīng)度遠(yuǎn)高于預(yù)期。本質(zhì)原因是種群多樣性丟失太快強(qiáng)勢個(gè)體迅速占領(lǐng)整個(gè)種群。我在網(wǎng)絡(luò)流GA里遇到早熟時(shí)排查順序依次是看變異概率是不是太低先調(diào)高一檔試試看初始化是不是太單一各路方案都初始化為最短路徑流量等于把所有個(gè)體都推向同一個(gè)局部區(qū)域看種群規(guī)模是否和染色體長度不匹配路徑一多基因位數(shù)當(dāng)然多種群需要同步擴(kuò)大。停滯則是另一種情況收斂曲線已經(jīng)到一個(gè)不錯(cuò)的值但離最優(yōu)還有距離就是不動(dòng)了。這時(shí)候最有效的操作不是繼續(xù)調(diào)GA參數(shù)而是回去檢查候選路徑集合。我遇到過網(wǎng)絡(luò)結(jié)構(gòu)很簡單但候選路徑里缺了一條關(guān)鍵的旁路導(dǎo)致最優(yōu)解根本無法表達(dá)這時(shí)候GA再怎么進(jìn)化都找不到它。補(bǔ)上路徑之后收斂立即打破。抖動(dòng)則是收斂曲線的值忽上忽下沒有穩(wěn)定的下降趨勢。這通常意味著交叉和變異太激進(jìn)好基因被頻繁破壞。把交叉概率下調(diào)到0.6左右或者減少變異幅度曲線就會平滑很多。另外精英保留是保證曲線單調(diào)不下降的重要機(jī)制別省這一步。4.2 約束條件總是不滿足怎么辦如果跑了很久適應(yīng)度還是很高或者最終解雖然適應(yīng)度低、但解碼出來容量超限嚴(yán)重說明懲罰機(jī)制出了問題。我整理了三種典型情況癥狀可能原因解決方案最終解違容量約束懲罰系數(shù)太小GA寧違約也要省費(fèi)用加大 alpha或改用修復(fù)算子修正流量匯點(diǎn)流量遠(yuǎn)低于需求需求懲罰項(xiàng)被其他約束淹沒單獨(dú)給需求項(xiàng)一個(gè)較大的保底懲罰值每條邊都壓著容量上限但整體費(fèi)用偏高懲罰太小算法在用結(jié)構(gòu)風(fēng)險(xiǎn)換成本檢查分段成本閾值是否合理提高成本梯度還有一個(gè)容易忽略的點(diǎn)如果懲罰系數(shù)設(shè)計(jì)成線性懲罰個(gè)體違約束程度的微小差異可能沒有拉開適應(yīng)度差距選擇壓力不足。這時(shí)候可以把違約束量平方比如alpha * violCap^2讓更惡劣的個(gè)體被迅速淘汰。我在項(xiàng)目后期就換成了平方懲罰效果比線性懲罰穩(wěn)定得多。4.3 性能優(yōu)化讓GA跑得更快這個(gè)問題的核心不是讓電腦跑得快而是讓適合度評估快。GA迭代幾千次每一次都要重建網(wǎng)絡(luò)流、算費(fèi)用、算約束違例再造上幾百個(gè)個(gè)體的重復(fù)計(jì)算累積起來非?？捎^。我實(shí)測中主要的性能瓶頸有三處都做了針對性優(yōu)化用邊映射矩陣替代線性查找。前面提過把(u,v)對映射成邊編號解碼路徑流量時(shí)直接用矩陣索引減少了90%的find調(diào)用。適應(yīng)度函數(shù)向量化。不要循環(huán)每個(gè)個(gè)體調(diào)用函數(shù)而是把整個(gè)種群一次傳入用矩陣運(yùn)算批量計(jì)算所有個(gè)體的適應(yīng)度。Matlab對向量化的提升非常顯著。預(yù)計(jì)算路徑-邊關(guān)聯(lián)矩陣。提前算好一個(gè)邏輯矩陣P行是路徑列是邊P(p,e)1表示路徑p經(jīng)過邊e這樣解碼操作就變成一次矩陣乘法edgeFlow P * x再也沒有循環(huán)。如果還想更快可以把罪耗時(shí)的適應(yīng)度函數(shù)用編譯后的MEX實(shí)現(xiàn)但中小規(guī)模網(wǎng)絡(luò)下向量化已經(jīng)足夠沒必要上MEX。4.4 問題排查速查表這里整理一張可以直接打印出來對照的速查表都是我調(diào)試途中實(shí)際遇到的問題序號現(xiàn)象排查方向處理建議1前幾代適應(yīng)度巨大且無下降初始種群全是垃圾個(gè)體縮小隨機(jī)擾動(dòng)范圍引入最短路徑初始化2收斂后最優(yōu)解約束違例懲罰不足提高懲罰系數(shù)或改平方懲罰3種群多樣性快速丟失選擇壓過大/變異過低增大變異概率、改用均勻選擇4交叉后代比父代更差算術(shù)交叉步長過大改用隨機(jī)線性插值或減少alpha差異5運(yùn)行時(shí)間隨路徑數(shù)爆炸解碼循環(huán)太多構(gòu)建路徑-邊矩陣向量化解碼6候選路徑不含最優(yōu)結(jié)構(gòu)收斂平臺過高增加K短路徑枚舉補(bǔ)路徑7變異后流量出現(xiàn)負(fù)值變異擾動(dòng)未夾緊對流量變量做max(0,x)截?cái)?需求始終不足需求懲罰沒有合理加權(quán)將beta設(shè)成alpha的2倍或單獨(dú)保底這幾個(gè)問題幾乎覆蓋了我在GA求解網(wǎng)絡(luò)流問題中遇到的所有坑。對照排查大部分情況十分鐘內(nèi)能定位。5. 關(guān)于擴(kuò)展方向與一點(diǎn)個(gè)人經(jīng)驗(yàn)這段代碼給我的最大啟發(fā)是GA作為一種“結(jié)構(gòu)友好型”算法特別適合處理那些傳統(tǒng)算法無法優(yōu)雅處理的有約束組合優(yōu)化問題。路徑流量編碼這個(gè)思想不只能解決單商品網(wǎng)絡(luò)流擴(kuò)展到多商品流也非常直接把染色體拆成多個(gè)商品塊每塊對應(yīng)一組路徑流量再把共享邊的容量約束用懲罰函數(shù)統(tǒng)一處理即可。我的第二個(gè)體會是寫GA代碼時(shí)不要急著引入工具箱自帶的ga函數(shù)。自己手寫一遍選擇、交叉、變異之后你對算法行為的理解會完全不一樣。等遇到復(fù)雜問題時(shí)你才能判斷到底是參數(shù)錯(cuò)了還是編碼錯(cuò)了還是約束懲罰設(shè)計(jì)錯(cuò)了而不是對著黑盒API干瞪眼。最后再分享一個(gè)小技巧調(diào)試階段把每一代最優(yōu)個(gè)體的路徑流量分布打印出來仔細(xì)觀察它長什么樣。你很快會發(fā)現(xiàn)網(wǎng)絡(luò)流問題的GA解有很強(qiáng)的稀疏性——真正承擔(dān)大流量的路徑通常只有幾條其他路徑流量趨近于零。利用這個(gè)規(guī)律可以設(shè)計(jì)“路徑裁剪”策略把連續(xù)的零流量路徑壓縮掉降低問題維度讓算法在更小的搜索空間里跑得更準(zhǔn)。這個(gè)小改動(dòng)后續(xù)幫我把求解效率提升了一大截。