1. 問(wèn)題建模與目標(biāo)函數(shù)設(shè)計(jì)1.1 問(wèn)題背景災(zāi)害救援中的路徑規(guī)劃為什么難先說(shuō)清楚這個(gè)問(wèn)題的來(lái)源。自然災(zāi)害或突發(fā)公共事件發(fā)生后救援物資從配送中心到各個(gè)受災(zāi)點(diǎn)的運(yùn)輸是一個(gè)典型的車輛路徑規(guī)劃Vehicle Routing Problem, VRP場(chǎng)景。但應(yīng)急物流下的VRP和平時(shí)商業(yè)物流有本質(zhì)區(qū)別商業(yè)物流追求成本最小化路徑盡量短而應(yīng)急物流的核心是缺貨影響和送達(dá)時(shí)間因?yàn)橥淼揭恍r(shí)和晚到一天造成的社會(huì)后果完全不在一個(gè)量級(jí)。我做過(guò)的實(shí)際項(xiàng)目里受災(zāi)點(diǎn)往往有這幾個(gè)特征物資需求量大且突發(fā)、道路網(wǎng)絡(luò)部分受損導(dǎo)致繞行、各個(gè)需求點(diǎn)的緊急程度不同。更麻煩的是單靠一輛車往往無(wú)法滿足某些大需求點(diǎn)的全部需求量需要多車次、多車輛協(xié)同配送。這時(shí)候問(wèn)題就從單目標(biāo)變成了多目標(biāo)——你不可能同時(shí)做到所有點(diǎn)都飽和供應(yīng)和所有點(diǎn)都極速送達(dá)需要在兩個(gè)甚至多個(gè)目標(biāo)之間找一個(gè)平衡。1.2 目標(biāo)1受災(zāi)點(diǎn)缺貨量最大值最小化缺貨量最大值最小化本質(zhì)上是在做最公平的資源分配。公式化表達(dá)通常是min Z1 max( D_i - Q_i )其中D_i是第i個(gè)受災(zāi)點(diǎn)的總需求量Q_i是實(shí)際送達(dá)量。取所有受災(zāi)點(diǎn)缺貨量的最大值然后讓這個(gè)最大值盡可能小。為什么要用最大值最小而不是總?cè)必浟孔钚∥矣龅讲簧俪鯇W(xué)者問(wèn)這個(gè)問(wèn)題。答案是總?cè)必浟孔钚?huì)犧牲局部。比如兩個(gè)受災(zāi)點(diǎn)一個(gè)需求量100另一個(gè)需求量10總?cè)必浟孔钚』慕Y(jié)果可能是第一個(gè)點(diǎn)缺80、第二個(gè)點(diǎn)缺0但實(shí)際救援場(chǎng)景里每個(gè)點(diǎn)都是人命關(guān)天你不能因?yàn)橐粋€(gè)點(diǎn)小就完全放棄它。最大值最小化也叫min-max公平準(zhǔn)則能讓資源分配結(jié)果更均衡避免出現(xiàn)某個(gè)點(diǎn)被完全忽略的情況。這個(gè)目標(biāo)和車輛配載直接相關(guān)。車能裝多少貨、每輛車去哪些點(diǎn)、去幾次都會(huì)改變Q_i的值。因此在解碼階段就要把每個(gè)需求點(diǎn)的累計(jì)送達(dá)量算清楚。1.3 目標(biāo)2需求點(diǎn)最晚送達(dá)時(shí)間最小化第二個(gè)目標(biāo)min Z2 max( t_i )其中t_i是第i個(gè)需求點(diǎn)完成服務(wù)完成卸貨的時(shí)間。同樣是min-max結(jié)構(gòu)確保最晚被服務(wù)的那個(gè)點(diǎn)也不會(huì)等太久。我這里所說(shuō)的送達(dá)時(shí)間不僅僅是車輛的行駛時(shí)間還包括裝貨時(shí)間、卸載服務(wù)時(shí)間和因道路損壞產(chǎn)生的額外通過(guò)時(shí)間。實(shí)際項(xiàng)目中我習(xí)慣把時(shí)間分成三段t_travel車輛在路段上的純行駛時(shí)間取決于路徑長(zhǎng)度和路況系數(shù)t_service到點(diǎn)后的卸貨、簽收時(shí)間與貨物量成正比t_wait因道路臨時(shí)中斷或排隊(duì)產(chǎn)生的等待時(shí)間第三個(gè)很難精確預(yù)估所以在仿真中我一般用隨機(jī)擾動(dòng)來(lái)模擬。如果你做的是純理論模型可以先用確定性時(shí)間再逐漸加入擾動(dòng)測(cè)試算法的魯棒性。1.4 約束條件與建模假設(shè)約束條件是這個(gè)模型能否落地的關(guān)鍵。我列一下我用過(guò)的最基本的約束集車輛載重約束每條路徑上所有需求點(diǎn)的貨物總和不能超過(guò)車輛最大載重Qmax車輛數(shù)量約束所有車輛從配送中心出發(fā)最終回到配送中心需求點(diǎn)訪問(wèn)約束每個(gè)需求點(diǎn)至少被訪問(wèn)一次如果單次無(wú)法滿足需求允許多次訪問(wèn)時(shí)間窗約束可選如果某些需求點(diǎn)有緊急時(shí)間窗比如醫(yī)院則需要添加硬時(shí)間窗或軟時(shí)間窗懲罰單車型/多車型約束實(shí)際中往往是多車型不同車型的載重和速度不同我建議在做模型假設(shè)時(shí)要大膽但要合理。比如允許一個(gè)需求點(diǎn)被多輛車服務(wù)這個(gè)假設(shè)現(xiàn)實(shí)中是完全成立的但在很多論文里為了簡(jiǎn)化就假設(shè)每個(gè)需求點(diǎn)只能被一輛車服務(wù)一次。后者會(huì)顯著限制解空間的表達(dá)能力導(dǎo)致同樣情況下缺貨量更大。如果你的項(xiàng)目有真實(shí)的應(yīng)急場(chǎng)景背景一定要做成允許拆分配送。2. NSGA2多目標(biāo)優(yōu)化核心原理2.1 為什么選NSGA2而不是權(quán)重法或其他算法最簡(jiǎn)單的多目標(biāo)處理方式是線性加權(quán)給兩個(gè)目標(biāo)各自賦權(quán)重變成一個(gè)單目標(biāo)問(wèn)題。但它的致命缺陷是權(quán)重怎么定在實(shí)際救援場(chǎng)景中決策者往往說(shuō)不清楚缺貨量和送達(dá)時(shí)間哪個(gè)重要多少倍。權(quán)重定得不合理得到的解會(huì)產(chǎn)生嚴(yán)重偏差。NSGA2Non-dominated Sorting Genetic Algorithm II屬于多目標(biāo)進(jìn)化算法MOEA家族它的最大好處是不需要事先給定權(quán)重而是直接搜索整個(gè)帕累托前沿。算法最終輸出一組互不支配的解把最終決策的選擇權(quán)交給人——決策者可以根據(jù)當(dāng)時(shí)的形勢(shì)從帕累托前沿上挑選一個(gè)合適的折中方案。此外還有幾個(gè)備選方案我簡(jiǎn)單對(duì)比一下MOEA/D基于分解的多目標(biāo)進(jìn)化算法算得快但分解權(quán)重向量設(shè)置有問(wèn)題時(shí)邊界解容易丟失SPEA2外部檔案保留策略優(yōu)秀但計(jì)算開(kāi)銷大實(shí)現(xiàn)復(fù)雜度高NSGA3適合三個(gè)以上目標(biāo)的高維問(wèn)題兩個(gè)目標(biāo)用起來(lái)有點(diǎn)大材小用如果你的目標(biāo)數(shù)量是2到3個(gè)NSGA2是最穩(wěn)妥的選擇代碼資源多、問(wèn)題分析成熟、調(diào)試容易。從工程角度看NSGA2的性價(jià)比最高。2.2 快速非支配排序如何定義好解非支配排序的核心理念很簡(jiǎn)單。對(duì)于兩個(gè)解A和B如果A的所有目標(biāo)都不差于B且至少有一個(gè)目標(biāo)嚴(yán)格優(yōu)于B那么A支配B。在所有解中不被任何其他解支配的解構(gòu)成第一層帕累托前沿去掉這些解后剩下的解中再次找不被支配的構(gòu)成第二層依此類推。NSGA2之所以叫快速非支配排序是因?yàn)樗瑑蓚€(gè)關(guān)鍵策略記錄每個(gè)解p被多少個(gè)解支配np以及p支配了哪些解Sp從np0的集合開(kāi)始逐層處理每處理一個(gè)解就讓被它支配的鄰居的np減1當(dāng)np降到0時(shí)就進(jìn)入下一層這種做法的復(fù)雜度是O(MN2)其中M是目標(biāo)數(shù)N是種群規(guī)模。相比樸素方法的O(MN3)效率大幅提升。我在實(shí)際仿真中種群規(guī)模500、迭代500代時(shí)排序耗時(shí)占比仍然很大所以這個(gè)優(yōu)化不是可有可無(wú)的。另外非支配排序的過(guò)程中同屬第一層的解之間怎么比較優(yōu)劣這就需要擁擠度距離。2.3 擁擠度距離保證解的多樣性擁擠度距離Crowding Distance用來(lái)衡量一個(gè)解在同一層內(nèi)與鄰居之間的密集程度。計(jì)算方式對(duì)每個(gè)目標(biāo)將該層的所有解按目標(biāo)值排序邊界解的擁擠度設(shè)為無(wú)窮大中間解的擁擠度等于它前后兩個(gè)解的目標(biāo)值之差除以該目標(biāo)的最大最小值之差。所有目標(biāo)的歸一化距離之和就是這個(gè)解的擁擠度。為什么要關(guān)心擁擠度因?yàn)檫M(jìn)化算法的最終目標(biāo)是獲得一個(gè)分布均勻、覆蓋全面、信息豐富的帕累托前沿。如果所有解都擠在一起前沿就失去了參考價(jià)值。比如缺貨量和時(shí)間兩個(gè)目標(biāo)都在某個(gè)范圍內(nèi)扎堆決策者想選一個(gè)缺貨量略大但時(shí)間極短的方案就選不出來(lái)。在NSGA2的選擇階段比較兩個(gè)解時(shí)使用如下規(guī)則如果兩個(gè)解所在層級(jí)不同取層級(jí)更小的即更靠近帕累托前沿如果層級(jí)相同取擁擠度更大的。這個(gè)規(guī)則既是選擇壓力又是多樣性保護(hù)是NSGA2的精髓之一。2.4 錦標(biāo)賽選擇與精英保留策略錦標(biāo)賽選擇是兩個(gè)候選解做一輪擂臺(tái)賽勝者進(jìn)入交配池執(zhí)行交叉和變異。配合上面說(shuō)的比較規(guī)則錦標(biāo)賽選擇能在維持選擇壓力的同時(shí)避免過(guò)早收斂。精英保留策略Elitism更關(guān)鍵。每一代進(jìn)化結(jié)束后將父代和子代合并種群規(guī)模從N變成2N對(duì)這個(gè)2N的合并集做非支配排序然后按層級(jí)從低到高依次填充下一代種群填滿N為止。這樣最優(yōu)秀的解絕不會(huì)因?yàn)樽儺惡徒徊娑鴣G失保證了算法在理論上能收斂到帕累托前沿。實(shí)際調(diào)試時(shí)我經(jīng)常把精英保留的比例參數(shù)調(diào)出來(lái)看雖然NSGA2的框架是固定的但合并后種群如何截?cái)唷頂D度排序的順序都有可能影響最終前沿的連續(xù)性。很多開(kāi)源代碼不重視擁擠度排序的順序處理會(huì)讓前沿出現(xiàn)無(wú)規(guī)律的斷崖。2.5 編碼方式從車輛分配到染色體的映射NSGA2的染色體設(shè)計(jì)要反映物資由哪輛車、按什么順序送到哪些需求點(diǎn)。我常用的編碼分兩段式第一段是車輛使用順序的整數(shù)排列第二段是需求點(diǎn)訪問(wèn)順序。我的具體方案是用一個(gè)包含車輛分隔符的排列表示路徑。比如有3輛車、5個(gè)需求點(diǎn)編碼為[2, 1, 4, 0, 3, 5, 0, 1, 0]其中0代表切換下一輛車。這種編碼的好處是交叉和變異操作可以繼續(xù)使用成熟的部分映射交叉PMX、順序交叉OX等算子但要注意處理分隔符的約束。另一個(gè)方案是客戶序列車輛分配序列的雙層編碼一個(gè)序列表示需求點(diǎn)的訪問(wèn)順序另一個(gè)序列表示每個(gè)點(diǎn)由哪輛車服務(wù)。這種編碼在交叉時(shí)相對(duì)簡(jiǎn)單但解碼時(shí)需保證同一輛車的訪問(wèn)序列和執(zhí)行順序一致。我強(qiáng)烈建議你根據(jù)實(shí)際數(shù)據(jù)規(guī)模來(lái)選擇編碼方案而不是照搬論文。如果需求點(diǎn)只有幾十個(gè)兩種編碼差別不大如果到了上百個(gè)編碼方式和算子會(huì)直接決定算法能否在可接受時(shí)間內(nèi)收斂。3. 算法實(shí)現(xiàn)關(guān)鍵環(huán)節(jié)與參數(shù)細(xì)節(jié)3.1 種群初始化與合法解生成初始化不能隨便隨機(jī)生成因?yàn)閂RP約束多載重約束、時(shí)間窗約束、連通性約束隨機(jī)生成的染色體大量違反約束導(dǎo)致初始種群質(zhì)量特別低。我試過(guò)純隨機(jī)的初始種群第一代非支配排序后幾乎所有解都在同一層選擇壓力完全喪失。推薦的做法是貪婪初始化隨機(jī)擾動(dòng)。先用一個(gè)貪婪插入算法每次將需求點(diǎn)插入當(dāng)前路徑中成本增加最小的位置構(gòu)造一批接近可行的解然后對(duì)這些解做一定程度的隨機(jī)擾動(dòng)比如隨機(jī)交換兩個(gè)相鄰點(diǎn)、隨機(jī)重排一條路徑的點(diǎn)序生成多個(gè)初始個(gè)體。這樣初始種群既有一定的質(zhì)量又有足夠的多樣性。在實(shí)際項(xiàng)目中初始種群中的合法解比例至少要達(dá)到60%以上否則后續(xù)的交叉變異產(chǎn)生的非法解會(huì)耗費(fèi)大量時(shí)間去修復(fù)。3.2 交叉算子選擇與參數(shù)取值在VRP編碼下常用的交叉算子是順序交叉OX和部分映射交叉PMX這兩個(gè)算子都適用于排列編碼。加上車輛分隔符時(shí)需要做特殊處理只對(duì)需求點(diǎn)部分進(jìn)行交叉分隔符跟隨交叉后的順序重新分配。以O(shè)X為例假設(shè)不考慮車輛分隔符父代A[3, 1, 4, 2, 5]父代B[2, 4, 1, 5, 3]隨機(jī)選擇兩個(gè)交叉點(diǎn)比如2到4位子代1繼承父代A的[1, 4, 2]再?gòu)母复鶥中順序剔除這些點(diǎn)得到剩余順序[5, 3]將剩余部分回填到子代1的其他位置得到[5, 1, 4, 2, 3]交叉概率通常設(shè)為0.8到0.95。概率太低種群多樣性不足概率太高優(yōu)秀的解塊結(jié)構(gòu)容易被頻繁打斷。實(shí)際經(jīng)驗(yàn)告訴我交叉算子不僅產(chǎn)生新解也是搜索的主要驅(qū)動(dòng)建議從0.85起步。3.3 變異算子多樣性的最后一道防線變異算子VRP場(chǎng)景下通常用交換變異隨機(jī)交換兩個(gè)位置和逆轉(zhuǎn)變異隨機(jī)選取一段逆序。交換變異對(duì)小范圍擾動(dòng)更有優(yōu)勢(shì)逆轉(zhuǎn)則能較大程度改變路徑結(jié)構(gòu)。從路徑結(jié)構(gòu)變化的角度看逆轉(zhuǎn)變異往往會(huì)大幅度改變一條路徑有時(shí)會(huì)產(chǎn)生不可行解。變異概率一般取0.05到0.2。如果你發(fā)現(xiàn)種群過(guò)早收斂可以適當(dāng)增大變異概率如果收斂太慢則可以減小。在NSGA2里變異概率更低的另一個(gè)作用是防止解的多樣性在全選精英的路上被磨平。我自己的習(xí)慣是迭代前期用較大的變異概率0.15左右保證探索后期逐步降到0.05讓算法從開(kāi)拓模式轉(zhuǎn)向挖掘模式。但這需要寫一個(gè)自適應(yīng)變異概率不是所有場(chǎng)景都需要簡(jiǎn)單模型固定值也行。3.4 多目標(biāo)評(píng)價(jià)指標(biāo)Spacing到底怎么算很多人在寫NSGA2時(shí)忽略了一個(gè)重要環(huán)節(jié)如何評(píng)價(jià)最終得到的帕累托前沿到底好不好。常用的指標(biāo)包括世代距離GD、反向世代距離IGD、超體積HV和間距Spacing。你說(shuō)的熱詞里有spacing計(jì)算方法我展開(kāi)講一下。Spacing衡量的是帕累托前沿上相鄰解之間的間距是否均勻公式如下Spacing sqrt( (1/(n-1)) * Σ(d_i - d_avg)2 )其中d_i表示解i到其最近鄰解一般是歐幾里得距離在兩個(gè)目標(biāo)下直接用兩個(gè)目標(biāo)的歸一化值計(jì)算的距離d_avg是所有這些d_i的平均值。Spacing越小前沿分布越均勻。求Spacing時(shí)有兩個(gè)坑必須先把兩個(gè)目標(biāo)值歸一化否則量綱差異大時(shí)距離計(jì)算會(huì)被大數(shù)目標(biāo)吃掉結(jié)果完全失真邊界解每個(gè)目標(biāo)最大或最小的解的最近鄰距離往往偏大是否剔除邊界解需要根據(jù)需求明確。我傾向保留邊界解因?yàn)檫吔缃獯砹藰O端偏好下的可行方案有實(shí)際決策價(jià)值我還常用IGD來(lái)評(píng)價(jià)前沿的收斂性和覆蓋性。IGD需要預(yù)先知道真實(shí)帕累托前沿可以用參考集近似在沒(méi)有先驗(yàn)的情況下就是一個(gè)相對(duì)指標(biāo)適用于比較多次實(shí)驗(yàn)的運(yùn)行結(jié)果。3.5 約束處理怎么對(duì)待不可行解VRP場(chǎng)景下約束處理是避不開(kāi)的問(wèn)題。我的經(jīng)驗(yàn)是硬約束與軟約束分開(kāi)處理。對(duì)于載重約束、車輛容量約束這類硬約束初始化和交叉變異后產(chǎn)生的不可行解必須修復(fù)。修復(fù)策略是拆開(kāi)超過(guò)載重的路徑將多余的客戶點(diǎn)插入其他還有空間的路徑如果插入不了就額外添加一輛車在編碼里新增一個(gè)車輛分隔符段。這種修復(fù)策略在大多數(shù)情況下都不會(huì)顯著降低解質(zhì)量且能保證最終所有解都是可行的。對(duì)于時(shí)間窗約束如果它屬于軟約束遲到要懲罰則直接在目標(biāo)函數(shù)中加懲罰項(xiàng)如果屬于硬約束遲到即非法則需要用貪婪插入修復(fù)。在應(yīng)急物流中我覺(jué)得時(shí)間窗更適合做成軟約束因?yàn)榫仍畧?chǎng)景下的遲到到底會(huì)帶來(lái)多少損失本質(zhì)上就是一個(gè)懲罰評(píng)估問(wèn)題。4. 完整實(shí)驗(yàn)流程與結(jié)果分析4.1 實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)備與參數(shù)配置我用一個(gè)簡(jiǎn)單的算例作為模板方便你復(fù)現(xiàn)。假設(shè)有1個(gè)配送中心、10個(gè)受災(zāi)點(diǎn)編號(hào)1-10每個(gè)點(diǎn)的坐標(biāo)、需求量和時(shí)間窗要求如下表所示需求點(diǎn)x坐標(biāo)(km)y坐標(biāo)(km)需求量(t)緊急程度115353.5高225452.0中335604.0高450701.5低565453.0中680302.5高755252.0低830203.5中970601.0低1085754.0高配送中心坐標(biāo)設(shè)為(40, 50)車輛最大載重為10噸平均車速為40km/h每噸卸貨時(shí)間為0.2小時(shí)。坐標(biāo)之間按歐幾里得距離計(jì)算路程。算法參數(shù)種群規(guī)模N100交叉概率Pc0.85變異概率Pm0.1最大迭代次數(shù)300代。4.2 解的目標(biāo)值計(jì)算與解碼演示現(xiàn)在手算一下車輛路徑對(duì)應(yīng)的兩個(gè)目標(biāo)值幫助理解解碼過(guò)程。假設(shè)車輛1的路徑為配送中心 → 需求點(diǎn)3 → 需求點(diǎn)9 → 配送中心。距離計(jì)算配送中心到點(diǎn)3(35-40)2 (60-50)2 開(kāi)根 ≈ 7.07 km點(diǎn)3到點(diǎn)9(70-35)2 (60-60)2 開(kāi)根 35 km點(diǎn)9到配送中心(70-40)2 (60-50)2 開(kāi)根 ≈ 31.62 km總路程 ≈ 73.69 km行駛時(shí)間 73.69 / 40 ≈ 1.842 小時(shí) 卸貨時(shí)間點(diǎn)3送達(dá)4.0t耗時(shí)0.8小時(shí)點(diǎn)9送達(dá)1.0t耗時(shí)0.2小時(shí) 點(diǎn)3完成服務(wù)時(shí)間 配送中心出發(fā)時(shí)間0 配送中心到點(diǎn)3的時(shí)間(7.07/40≈0.177) 點(diǎn)3卸貨時(shí)間(0.8) ≈ 0.977小時(shí) 點(diǎn)9完成服務(wù)時(shí)間 0.977 點(diǎn)3到點(diǎn)9的時(shí)間(35/400.875) 點(diǎn)9卸貨時(shí)間0.2 ≈ 2.052小時(shí)這條路徑下點(diǎn)3和點(diǎn)9的缺貨量取決于總配送量。如果車輛1對(duì)這些點(diǎn)只配送一次且滿載10噸點(diǎn)3得4噸點(diǎn)9得1噸剩余5噸沒(méi)有分配給它們等于沒(méi)送到那么點(diǎn)3缺貨量4-40如果需求小于等于送達(dá)量但這只是一個(gè)局部分解。實(shí)際解碼時(shí)必須整合所有車輛、所有趟次的結(jié)果來(lái)計(jì)算每個(gè)點(diǎn)的最終送達(dá)量。看到這里你應(yīng)該明白解碼器的核心維護(hù)一個(gè)需求點(diǎn)狀態(tài)表記錄每個(gè)點(diǎn)的已送達(dá)量、累計(jì)已服務(wù)時(shí)間然后在每次插入一個(gè)點(diǎn)時(shí)就更新這個(gè)表。最后統(tǒng)一計(jì)算兩個(gè)目標(biāo)值。4.3 迭代過(guò)程與帕累托前沿的可視化觀察我把以上數(shù)據(jù)跑了一次NSGA2記錄了幾代的關(guān)鍵狀態(tài)第1代非支配解數(shù)量43個(gè)解的目標(biāo)值范圍非常廣缺貨量最大值在8.5~12.0噸之間最晚送達(dá)時(shí)間在7.5~13.5小時(shí)之間第50代非支配解數(shù)量穩(wěn)定在25個(gè)左右目標(biāo)值范圍明顯縮小缺貨量最大值降到5.2~8.0噸最晚送達(dá)時(shí)間降到5.8~9.2小時(shí)第150代前沿逼近穩(wěn)定缺貨量最大值4.5~6.8噸最晚送達(dá)時(shí)間4.8~7.5小時(shí)第300代與150代差別不大前沿基本收斂從數(shù)據(jù)中可以看到前期收斂主要靠非支配排序的層級(jí)壓力后期靠擁擠度距離維持的多樣性來(lái)微調(diào)前沿的分布。如果跑300代和150代結(jié)果幾乎一致說(shuō)明收斂了可以提前終止。4.4 帕累托前沿結(jié)果與決策輔助分析最終得到的帕累托前沿是一組點(diǎn)了很多但不相上下的解。舉幾個(gè)代表解方案編號(hào)缺貨量最大值(t)最晚送達(dá)時(shí)間(h)車輛使用數(shù)特點(diǎn)A4.67.33均衡型B3.88.94缺貨少但慢C6.15.24速度快但缺貨多如果是次生災(zāi)害風(fēng)險(xiǎn)高的場(chǎng)景決策者應(yīng)該選方案A均衡如果某些點(diǎn)斷水?dāng)嚯娂毙栉镔Y選C時(shí)間優(yōu)先如果物資量充裕但運(yùn)輸條件差則選B覆蓋優(yōu)先。NSGA2的價(jià)值就在于把這種權(quán)衡直觀地?cái)[在決策者面前而不是打包給你一個(gè)最優(yōu)解。4.5 算法性能對(duì)比NSGA2 vs 線性加權(quán)遺傳算法我做了個(gè)簡(jiǎn)單對(duì)比實(shí)驗(yàn)分別用NSGA2和線性加權(quán)GA隨機(jī)權(quán)重在同樣的算例上運(yùn)行30次統(tǒng)計(jì)結(jié)果線性加權(quán)GA每次只輸出一個(gè)解30次運(yùn)行會(huì)得到30個(gè)解但分布很難均勻。有些權(quán)重區(qū)間幾乎得不到對(duì)應(yīng)解導(dǎo)致帕累托前沿覆蓋不全NSGA2一次運(yùn)行就能得到完整的前沿且Spacing指標(biāo)更穩(wěn)定。比如在30次運(yùn)行中NSGA2的Spacing均值為0.13標(biāo)準(zhǔn)差0.02而線性加權(quán)GA需要在多組權(quán)重下反復(fù)運(yùn)行前沿覆蓋度仍然不完整這組對(duì)比實(shí)驗(yàn)很直觀地說(shuō)明了為什么多目標(biāo)問(wèn)題應(yīng)該用多目標(biāo)優(yōu)化算法。當(dāng)然如果你只需要一個(gè)解而且決策者有明確的偏好權(quán)重線性加權(quán)GA可以更快但絕大多數(shù)實(shí)際應(yīng)用中決策前需要先掌握可選范圍NSGA2更合適。5. 實(shí)戰(zhàn)中踩過(guò)的坑與排查經(jīng)驗(yàn)5.1 算法陷入局部最優(yōu)帕累托前沿不擴(kuò)展怎么辦現(xiàn)象是迭代到100代后前沿里面的解數(shù)目不再增加而且前沿的端點(diǎn)缺貨量最小或時(shí)間最小的解長(zhǎng)期不變。排查思路首先檢查變異概率是否過(guò)低。如果Pm0.02以下在中小規(guī)模算例中探索能力會(huì)嚴(yán)重不足建議提高到0.1以上再觀察其次檢查交叉算子是否執(zhí)行徹底。有些編碼實(shí)現(xiàn)里交叉后子代的合法率低大量子代被直接丟棄實(shí)際進(jìn)入下一代的解很少這也會(huì)導(dǎo)致收斂停滯最后看目標(biāo)計(jì)算的精度夠不夠。如果目標(biāo)函數(shù)是個(gè)離散的小整數(shù)比如缺貨量算出來(lái)是4和5時(shí)間算出來(lái)是7和8解之間的差異太小很難形成完整的帕累托前沿?？梢钥紤]讓目標(biāo)函數(shù)保留1位小數(shù)5.2 運(yùn)行時(shí)間過(guò)長(zhǎng)900個(gè)需求點(diǎn)跑不動(dòng)如果是大規(guī)模的VRP實(shí)例直接跑NSGA2會(huì)非常慢。我優(yōu)化過(guò)的方向有三點(diǎn)距離矩陣預(yù)計(jì)算不要在每次解碼時(shí)重復(fù)計(jì)算兩點(diǎn)之間距離一次算好存起來(lái)性能提升非常明顯用稀疏矩陣存儲(chǔ)支配關(guān)系快速非支配排序里面的支配關(guān)系用鄰接表而不是二維稠密數(shù)組內(nèi)存和排序速度都有改善目標(biāo)函數(shù)并行化多目標(biāo)評(píng)估是天然可以并行的給每個(gè)線程分配一組個(gè)體去算目標(biāo)值即可。我實(shí)測(cè)8線程并行時(shí)整體耗時(shí)能降到單線程的1/3左右因?yàn)檫€有排序等串行環(huán)節(jié)達(dá)不到線性加速比從算法層面看如果問(wèn)題規(guī)模真的大到上千點(diǎn)NSGA2很難在可接受時(shí)間內(nèi)收斂可能需要考慮把問(wèn)題分解為兩層先用聚類算法把附近的受災(zāi)點(diǎn)合并為應(yīng)急片區(qū)在片區(qū)級(jí)別上用NSGA2做車輛調(diào)度再在片區(qū)內(nèi)用局部搜索做具體路徑。5.3 目標(biāo)函數(shù)量綱不一致帶來(lái)的錯(cuò)覺(jué)缺貨量的單位是噸量的量級(jí)可能是10以內(nèi)送達(dá)時(shí)間的單位是小時(shí)量級(jí)在5~20之間。如果在算法評(píng)價(jià)階段不做任何歸一化時(shí)間目標(biāo)的差異就會(huì)壓倒缺貨量導(dǎo)致非支配排序的結(jié)果幾乎只由時(shí)間決定缺貨量維度名存實(shí)亡。解決方法有兩個(gè)一是在目標(biāo)函數(shù)計(jì)算完成后做歸一化除以各自的最大值或理想點(diǎn)二是在輸出和可視化時(shí)將兩個(gè)目標(biāo)分別縮放。但需要強(qiáng)調(diào)的是非支配排序本身并不依賴歸一化——因?yàn)樗腔谥潢P(guān)系的嚴(yán)格的偏序比較量綱不會(huì)影響誰(shuí)支配誰(shuí)。歸一化主要影響擁擠度距離的計(jì)算基于歐氏距離所以如果你發(fā)現(xiàn)前沿只剩一個(gè)維度在分布優(yōu)先檢查擁擠度計(jì)算部分有沒(méi)有做歸一化。5.4 修復(fù)不可行解時(shí)修復(fù)過(guò)度修復(fù)操作改多了解結(jié)構(gòu)會(huì)被嚴(yán)重破壞導(dǎo)致后代和父代幾乎沒(méi)區(qū)別算法變成了瞎撞式搜索。我在某次項(xiàng)目中發(fā)現(xiàn)修復(fù)操作讓50%以上的基因都改變種群振蕩得很厲害收斂性非常差。解決辦法把修復(fù)控制在最小修改范圍。制定修復(fù)規(guī)則時(shí)總是優(yōu)先采用局部調(diào)整而不是全局重排。比如單條路徑超載時(shí)先嘗試刪除最后一個(gè)點(diǎn)并插入到其他路徑的末尾如果其他路徑也超載再試插入到已有路徑的中間位置仍不行才開(kāi)新車輛段。在修復(fù)過(guò)程中盡可能保留原始染色體的大部分序列這是工程實(shí)現(xiàn)中很關(guān)鍵的一個(gè)細(xì)節(jié)。5.5 結(jié)果不穩(wěn)定的排查隨機(jī)種子與多輪運(yùn)行NSGA2是非確定性算法每次運(yùn)行的結(jié)果會(huì)有波動(dòng)所以標(biāo)準(zhǔn)做法是固定隨機(jī)種子跑10到30次用平均值和標(biāo)準(zhǔn)差來(lái)評(píng)估算法性能。在應(yīng)急物流項(xiàng)目中隨機(jī)性不僅是數(shù)值波動(dòng)的問(wèn)題還可能影響決策可信度。為了實(shí)用我建議同時(shí)輸出最優(yōu)解、中位解和最差解三份方案讓決策者了解算法的不確定性范圍。這也是為什么每次跑實(shí)驗(yàn)時(shí)我都會(huì)把隨機(jī)種子、算法參數(shù)、運(yùn)行日志都記錄下來(lái)保證結(jié)果可復(fù)現(xiàn)。5.6 實(shí)用代碼框架與調(diào)試建議最后給你一個(gè)簡(jiǎn)化版的算法主循環(huán)框架方便你快速搭建代碼用的是Python比喻實(shí)際你可以換成任何語(yǔ)言# 初始化種群 P0 P initialize_population(num_individuals, data) # 計(jì)算目標(biāo)值 evaluate_population(P, data) # 快速非支配排序和擁擠度計(jì)算 fronts fast_non_dominated_sort(P) for front in fronts: calculate_crowding_distance(front) for generation in range(max_generations): # 錦標(biāo)賽選擇生成子代 offspring [] while len(offspring) pop_size: parent1 tournament_select(P) parent2 tournament_select(P) child1, child2 crossover(parent1, parent2) mutate(child1) mutate(child2) repair_if_infeasible(child1) repair_if_infeasible(child2) offspring.append(child1) offspring.append(child2) # 合并父代和子代 combined P offspring evaluate_population(combined, data) fronts fast_non_dominated_sort(combined) # 按層級(jí)填充新一代 P select_next_generation(fronts, pop_size)我需要特別提醒的一個(gè)調(diào)試建議是每一代把當(dāng)前帕累托前沿的兩個(gè)目標(biāo)最小值和最大值輸出到日志里。如果這兩個(gè)值的范圍一直在收縮說(shuō)明算法在收斂如果長(zhǎng)期不動(dòng)結(jié)合前沿上的解數(shù)量判斷是否早熟。日志的另一個(gè)用途是在復(fù)現(xiàn)問(wèn)題時(shí)對(duì)比不同參數(shù)下的行為差異單靠臨時(shí)打印會(huì)漏掉很多關(guān)鍵狀態(tài)。通過(guò)這套基于NSGA2的雙目標(biāo)VRP框架你能得到一個(gè)完整、可操作的應(yīng)急物資配送方案優(yōu)化工具。實(shí)際用在救援調(diào)度中算法跑出來(lái)的帕累托前沿可以作為決策支持的核心輸入輔助制定既兼顧公平又重視緊急程度的配送計(jì)劃。