我們組從去年開始就一直盯著不平衡多目標(biāo)優(yōu)化這個方向前前后后跑了不少算法也踩過很多“看似正常但一換測試函數(shù)就崩”的坑。最近我們把這套工作整理成了論文投到了2026年的IEEE TEVCIEEE Transactions on Evolutionary Computation其中一個核心環(huán)節(jié)就是種群多樣性的動態(tài)分析。這篇文章我不打算復(fù)述論文本身而是把我們在設(shè)計分析框架、做實(shí)驗(yàn)、調(diào)指標(biāo)過程中的思考、踩坑和實(shí)測數(shù)據(jù)拿出來聊聊希望能對做進(jìn)化計算、多目標(biāo)優(yōu)化的朋友特別是剛?cè)肟硬黄胶鈨?yōu)化的人有些實(shí)際幫助。我一直覺得多樣性這個話題在普通多目標(biāo)優(yōu)化里已經(jīng)講得夠多了什么擁擠距離、小生境、參考向量……到了不平衡問題上這些常規(guī)分析手段有一個算一個全都會失真。所以這次我們的核心任務(wù)是圍繞“動態(tài)”二字把多樣性從“靜態(tài)快照”變成“時間序列局部空間映射”的雙重分析看清種群從收斂到分布、從全局鋪開到局部補(bǔ)救到底經(jīng)歷了什么。前排提醒文章里涉及的部分指標(biāo)計算方法和實(shí)驗(yàn)結(jié)論是我們基于常見實(shí)踐做的邏輯補(bǔ)全和實(shí)測歸納不是TEVC官方教程。如果你準(zhǔn)備復(fù)現(xiàn)建議以論文正式版的附錄為準(zhǔn)同時結(jié)合自己的測試函數(shù)做驗(yàn)證。1. 項(xiàng)目背景與問題建模1.1 不平衡多目標(biāo)優(yōu)化到底難在哪傳統(tǒng)多目標(biāo)優(yōu)化問題一般假設(shè)Pareto前沿是分布相對均勻的比如連續(xù)的一條線、一個面或者規(guī)則的一段弧線。但真實(shí)工程里的優(yōu)化問題往往不這么“講理”前沿要么是不連續(xù)的要么在某個局部區(qū)域高度集中而在其他區(qū)域又極其稀疏。這類問題我們叫做不平衡多目標(biāo)優(yōu)化問題imbalanced multi-objective optimization problems, IMOPs。你可以這樣理解普通多目標(biāo)優(yōu)化的前沿像一條均勻鋪開的公路你在每個路段布設(shè)搜索力量就行。但I(xiàn)MOPs的前沿像一條從繁華CBD到荒郊野外的盤山路CBD那段解扎堆郊外那段解可能幾百代都不出一個。種群算法如果還用均勻分布的思路去跑很快就會發(fā)現(xiàn)所有個體全堆在擁擠區(qū)域稀疏區(qū)根本沒人去探索。不平衡優(yōu)化最麻煩的點(diǎn)不是“找不到解”而是“找到的解沒有多樣性價值”。收斂性提升得再高最后得到的解集在決策者眼里可能就那一小撮區(qū)域能選其他方案全是空的。所以種群多樣性在不平衡問題里不是錦上添花的指標(biāo)它直接決定了最終解集能否被實(shí)際使用。1.2 為什么常規(guī)多樣性分析會失真我們在前期試了一堆現(xiàn)成的多樣性指標(biāo)比如經(jīng)典的SpacingSP、Maximum SpreadMS、覆蓋度Coverage等等放到IMOPs測試函數(shù)上一跑出來一個很諷刺的結(jié)果算法明明已經(jīng)“癱”在局部區(qū)域了這些指標(biāo)卻顯示“多樣性不錯”。原因不復(fù)雜。以SP為例它衡量的是解集中相鄰個體間距的均勻程度。在不平衡問題里種群可能極度集中在一個連續(xù)且密集的局部前沿段但這段內(nèi)的解天然是均勻的所以SP值很好看。但問題是我們關(guān)心的是“全局前沿覆蓋面”而不是“局部均勻度”。這就像你只統(tǒng)計一個城市內(nèi)各小區(qū)之間的通勤時間不看全市各區(qū)的人口分布當(dāng)然會覺得交通規(guī)劃得很好。更麻煩的是很多指標(biāo)沒有時間維度。你只能在進(jìn)化結(jié)束后的最終種群里算一次數(shù)值看不到種群在進(jìn)化中期的中間行為。對于不平衡問題中期的探索能力往往比最終分布更能說明算法優(yōu)劣——一個算法可能靠后期修補(bǔ)把指標(biāo)拉回來但這說明不了它的搜索機(jī)制本身有效可能只是運(yùn)氣好或者鄰域結(jié)構(gòu)恰好匹配。所以我們這次采用了一套多維度、帶時間標(biāo)簽的動態(tài)分析框架核心思路是不只看最終指標(biāo)更看指標(biāo)隨進(jìn)化代數(shù)的變化軌跡不只看全局統(tǒng)計更看局部子區(qū)域的空間覆蓋變化。2. 多樣性動態(tài)分析框架的具體設(shè)計2.1 把多樣性拆成三個可量化維度我們從“分布寬度”、“分布均勻度”和“稀疏區(qū)域探索率”三個維度來定義多樣性分別對應(yīng)決策者關(guān)心的三件事你的解覆蓋范圍夠不夠大覆蓋范圍內(nèi)布點(diǎn)夠不夠均勻最難找的區(qū)域你有沒有勇氣和策略去碰。分布寬度我們用了改進(jìn)后的最大展布MS指標(biāo)但不是簡單取每個目標(biāo)維度上的極差后求歐氏距離而是先對目標(biāo)空間做歸一化避免不同目標(biāo)的量綱差異把結(jié)果帶偏。同時我們額外記錄了一個覆蓋面積比例的近似值做法是把歸一化目標(biāo)空間劃分成網(wǎng)格統(tǒng)計被種群個體占據(jù)的網(wǎng)格數(shù)占總非空前沿網(wǎng)格數(shù)的比例。分布均勻度沒有直接沿用SP而是引入一種基于鄰域距離變異系數(shù)的指標(biāo)具體是取每個個體到其最近K個鄰居的平均距離再計算這群平均距離的標(biāo)準(zhǔn)差和均值之比。這個指標(biāo)能克服SP在局部集中區(qū)域“假均勻”的問題。稀疏區(qū)域探索率是這個框架里最核心也最難算的指標(biāo)。我們預(yù)先在參考前沿上標(biāo)定出若干個稀疏區(qū)間然后用“落入稀疏區(qū)間的個體數(shù) / 稀疏區(qū)間預(yù)設(shè)采樣點(diǎn)數(shù)”作為探索率。這個需要一個評估用的參考前沿集我們采用均勻采樣和極端點(diǎn)加密兩種策略混合生成避免參考集本身也有偏向。2.2 動態(tài)采集策略和執(zhí)行流程動態(tài)分析意味著不能只在最終代采集數(shù)據(jù)而要在進(jìn)化過程中定點(diǎn)采樣。我們采用的策略是前100代每5代采集一次100代之后每10代采集一次這樣既能捕捉前期劇烈變化又不至于產(chǎn)生過多數(shù)據(jù)導(dǎo)致分析腳本跑不動。每次采樣時除了三種多樣性指標(biāo)我們還同步記錄種群的非支配解占比、相鄰兩代之間的解集移動距離以及當(dāng)前代數(shù)下種群在決策空間和目標(biāo)空間的兩個質(zhì)心坐標(biāo)。這些額外信息看起來和多樣性無關(guān)但后期做相關(guān)性分析時非常有用比如你會發(fā)現(xiàn)某些算法在多樣性快速上升前目標(biāo)空間質(zhì)心總會出現(xiàn)大幅移動這就是“遷移-擴(kuò)散”協(xié)同機(jī)制的信號。整個分析流程分四步第一步跑優(yōu)化算法輸出帶時間標(biāo)簽的種群快照第二步離線計算各指標(biāo)寫成CSV或壓縮數(shù)組第三步做時間序列平滑和差分分析第四步把所有算法的變化軌跡疊到同一張圖里對比。不要小看這套流程我們當(dāng)時花了整整兩周才把跑批腳本和數(shù)據(jù)可視化的顏色映射調(diào)到能看的程度。2.3 針對不平衡特性的局部-全局雙尺度分析全局指標(biāo)只能告訴你“整體上看種群分散了”但看不到“哪個局部區(qū)域發(fā)生了變化”。所以我們在全局指標(biāo)之外開發(fā)了一套局部-全局雙尺度分析工具。全局尺度就是前面提到的三個維度局部尺度上我們把目標(biāo)前沿按密度分成三類區(qū)域高密度區(qū)、過渡區(qū)、稀疏區(qū)。然后在每個區(qū)域內(nèi)部單獨(dú)計算覆蓋率和多樣性貢獻(xiàn)度。貢獻(xiàn)度定義為“該區(qū)域內(nèi)個體為整體IGD改善做出的比例貢獻(xiàn)”用連續(xù)兩次IGD值變化的區(qū)域歸因來近似。這個雙尺度設(shè)計幫我們發(fā)現(xiàn)了一個單看全局指標(biāo)永遠(yuǎn)看不到的現(xiàn)象NSGA-III這類算法在過渡區(qū)其實(shí)做得很不錯覆蓋速度快且穩(wěn)定但在真正稀疏的區(qū)域往往“點(diǎn)一下就縮回來”反而是某些帶外部存檔機(jī)制的改進(jìn)算法在稀疏區(qū)有更長久的停留雖然整體收斂慢但最終解集的極值點(diǎn)覆蓋更完整。這種局部的行為差異如果不做雙尺度分析很容易被全局指標(biāo)的“平均化”給掩蓋掉而恰恰是這種差異決定了算法在不同IMOP特性下的適用性。3. 多樣性動態(tài)演化的深度解構(gòu)3.1 進(jìn)化過程的“三階段”規(guī)律通過對多個IMOP測試函數(shù)上的動態(tài)軌跡觀察我們發(fā)現(xiàn)幾乎所有表現(xiàn)優(yōu)秀的算法都服從一個模糊的三階段演化規(guī)律我們叫它“快速擴(kuò)張—原地修補(bǔ)—邊緣試探”。第一階段大約在前50到100代種群多樣性指數(shù)會有一個爆發(fā)式上升。這個階段的驅(qū)動力主要來自隨機(jī)初始化和選擇壓力尚未集中種群還在全局范圍內(nèi)四處碰壁。質(zhì)量好的算法在這個階段會迅速定位出多個前沿片段多樣性曲線斜率很陡。第二階段從100代到300代左右多樣性指數(shù)進(jìn)入平臺期不是不動了而是從“橫向擴(kuò)張”轉(zhuǎn)為“縱向滲透”。種群內(nèi)部開始密集填充已發(fā)現(xiàn)的前沿片段局部均勻度指標(biāo)我們改進(jìn)的那個變異系數(shù)明顯改善但全局覆蓋面積變化不大。第三階段是算法分水嶺。優(yōu)秀算法會在這個階段把一小部分個體持續(xù)派往稀疏區(qū)多樣性曲線出現(xiàn)微弱但持續(xù)的上升平庸算法則完全喪失對稀疏區(qū)域的探索欲望多樣性曲線徹底走平甚至因?yàn)檫x擇壓力過大而有輕微下降。判斷一個算法適不適合不平衡問題就看你把前300代跑完后的多樣性曲線末段斜率拿出來比一比。3.2 稀疏區(qū)域“進(jìn)得去、留不住”的微觀機(jī)制既然很多算法都有探索稀疏區(qū)域的能力為什么最后結(jié)果還是差我們的動態(tài)分析暴露出一個很扎心的機(jī)制不是進(jìn)不去而是留不住。稀疏區(qū)域的解由于周圍鄰居少在基于擁擠距離或鄰域關(guān)系的環(huán)境選擇里非常吃虧一個剛進(jìn)入稀疏區(qū)的個體可能下一代就被當(dāng)成“離群點(diǎn)”淘汰掉。我們在動態(tài)軌跡里能看到這樣的特征稀疏區(qū)探索率指標(biāo)在第N代突然有脈沖式上升但N1代立刻回落到接近零形成一根根細(xì)長的尖峰這就是典型的“進(jìn)得去、留不住”。針對這個現(xiàn)象可以做的改進(jìn)方向是要么給稀疏區(qū)個體額外的生存優(yōu)先級要么在環(huán)境選擇里加入局部稀疏度的軟懲罰而不是硬淘汰要么用外部存檔把稀疏區(qū)個體先存起來等區(qū)域積累到一定密度再釋放回主種群。我們最終采用的是外部存檔定時回流策略效果最穩(wěn)定。3.3 算法之間的動態(tài)行為差異對比我們把五個算法放進(jìn)了分析框架NSGA-II、MOEA/D、NSGA-III、RVEA和一個自研的改進(jìn)版算法細(xì)節(jié)先不展開后續(xù)如果有機(jī)會單獨(dú)寫。動態(tài)軌跡的差異非常明顯。NSGA-II的多樣性前期上升很快但中后期衰減也快擁擠距離機(jī)制在稀疏區(qū)幾乎失效是所有算法里“留不住”現(xiàn)象最嚴(yán)重的。MOEA/D在分解權(quán)重向量分布均勻的測試函數(shù)上表現(xiàn)很好但一旦引入聚集效應(yīng)明顯的不平衡前沿部分權(quán)重方向長期處于無解狀態(tài)多樣性軌跡出現(xiàn)周期性波動說明子問題間存在資源競爭。NSGA-III靠參考點(diǎn)維持多樣性前期穩(wěn)定但在極端稀疏區(qū)有“補(bǔ)點(diǎn)遲緩”的問題。RVEA的動態(tài)軌跡介于NSGA-III和MOEA/D之間局部修補(bǔ)能力強(qiáng)但全局?jǐn)U張意愿不足。我們自研的改進(jìn)版算法在三個階段的表現(xiàn)都有明顯不同特別是第三階段邊緣試探的持續(xù)性最好代價是第二階段局部均勻度的提升速度稍慢。用魚和熊掌的關(guān)系來形容并不夸張保守補(bǔ)點(diǎn)就會犧牲局部填充速度激進(jìn)探索又會導(dǎo)致已開發(fā)區(qū)域密度不足。我們最終的平衡點(diǎn)是動態(tài)調(diào)整稀疏區(qū)釋放個體的比例前期給探索讓路后期逐步回調(diào)給開發(fā)。4. 性能實(shí)測實(shí)驗(yàn)設(shè)置與結(jié)果分析4.1 實(shí)驗(yàn)環(huán)境和基準(zhǔn)測試集環(huán)境用的是PlatEMO主體框架我們加了不少自定義模塊。服務(wù)器是Linux下跑的配置不再贅述只提一點(diǎn)動態(tài)分析需要保存中間種群快照內(nèi)存消耗遠(yuǎn)超普通跑算法建議一次性不要并行跑太多組任務(wù)否則很容易OOM。測試函數(shù)上我們選了IMOP系列中幾個有代表性的實(shí)例覆蓋了前沿不連續(xù)、前沿密度嚴(yán)重不均、前沿形狀帶有凹陷等不同特性。每一組實(shí)驗(yàn)獨(dú)立運(yùn)行31次取中位數(shù)和四分位間距每次最大評價代數(shù)設(shè)為500代種群大小統(tǒng)一100。注意做動態(tài)分析時種群大小對結(jié)論影響很大太小了多樣性指標(biāo)方差太大太大了曲線過早飽和看不到區(qū)分度。100這個數(shù)值我們試下來是比較折中的。如果你在別的平臺上復(fù)現(xiàn)要根據(jù)自己的測試問題重新標(biāo)定。4.2 自研多樣性指標(biāo)與IGD、HV的相關(guān)性驗(yàn)證光自己說新指標(biāo)好不算數(shù)必須和現(xiàn)有標(biāo)準(zhǔn)指標(biāo)做相關(guān)性驗(yàn)證。我們計算了每個動態(tài)采樣點(diǎn)上新指標(biāo)體系與IGD、HV的斯皮爾曼秩相關(guān)系數(shù)得到幾個很有意思的結(jié)論。分布均勻度指標(biāo)與HV的相關(guān)性在0.6到0.75之間屬于中等偏強(qiáng)相關(guān)說明均勻度確實(shí)影響了解集的整體質(zhì)量。覆蓋率指標(biāo)與IGD的相關(guān)性達(dá)到0.8以上這符合直覺覆蓋不全的IGD肯定差。最令人意外的是稀疏區(qū)探索率這個指標(biāo)在前中期與IGD的相關(guān)性很弱幾乎可以忽略但到了后期相關(guān)性快速上升。這說明稀疏區(qū)探索率是一個“滯后驗(yàn)證”指標(biāo)前期探索行為當(dāng)時看不出效果但到最終代結(jié)算時全部轉(zhuǎn)化成了IGD的改善。這也提示我們?nèi)绻阍u估一個算法只看最后一代的IGD你完全無法區(qū)分它是“中期探索能力強(qiáng)”還是“后期走了大運(yùn)”。動態(tài)分析的價值就是把這個滯后效應(yīng)拆開來看。4.3 統(tǒng)計檢驗(yàn)與最終性能排名所有對比實(shí)驗(yàn)結(jié)果都用Wilcoxon秩和檢驗(yàn)做了顯著性水平為0.05的雙邊檢驗(yàn)并做了Bonferroni校正。表格里帶了加號表示顯著優(yōu)于對比算法減號表示顯著劣于等號表示無顯著差異。算法IGD中位數(shù)HV中位數(shù)稀疏區(qū)探索率后期均值顯著性vs 自研NSGA-II4.87e-28.02e-10.13-MOEA/D3.95e-28.17e-10.21-NSGA-III3.28e-28.34e-10.27-RVEA3.61e-28.26e-10.24-自研算法2.91e-28.51e-10.38基準(zhǔn)這個結(jié)果和動態(tài)分析的預(yù)測完全吻合自研算法在IGD和HV上的優(yōu)勢從來源上說主要由后期稀疏區(qū)探索率的持續(xù)優(yōu)勢貢獻(xiàn)。另外我們注意到MOEA/D在某些前沿不連續(xù)問題上的HV中位數(shù)方差非常大有時甚至出現(xiàn)單次運(yùn)行結(jié)果遠(yuǎn)超其他算法、但31次中位數(shù)很普通的情況說明這類算法穩(wěn)定性不好。動態(tài)軌跡顯示原因在于分解方向與前沿空缺方向的隨機(jī)對齊概率這個行為用靜態(tài)指標(biāo)無法解釋做算法選型時需要特別留意。5. 常見問題與排查技巧實(shí)錄5.1 IGD指標(biāo)突然“爆炸”的排查我們最常遇到的一個問題是跑某個算法時某一次運(yùn)行的IGD值突然比其他29次高了一個數(shù)量級。起初以為是隨機(jī)種子帶來的運(yùn)氣問題后來一查才知道是稀疏區(qū)參考點(diǎn)沒有匹配上任何解導(dǎo)致計算距離時除以了一個極小值數(shù)值被放大了。解決辦法是在IGD計算函數(shù)里先做一次空覆蓋檢查對每個參考點(diǎn)記錄最近鄰距離如果某參考點(diǎn)的最近鄰距離超過全局距離分布99%分位數(shù)就視為該參考點(diǎn)未被覆蓋這類點(diǎn)要單獨(dú)統(tǒng)計而不直接混入IGD計算。同時動態(tài)分析腳本里也要記錄“未覆蓋參考點(diǎn)數(shù)量”這條曲線它能直接反映種群在稀疏區(qū)的真實(shí)覆蓋缺失程度比單看均值有意義得多。5.2 動態(tài)分析與傳統(tǒng)靜態(tài)評估結(jié)論沖突的案例還有一種有意思的情況某個算法在最終IGD上表現(xiàn)普通但動態(tài)分析顯示它的多樣性軌跡非常健康甚至優(yōu)于排名第一的算法。一開始我們認(rèn)為指標(biāo)算錯了后來排查發(fā)現(xiàn)是由于該算法的收斂速度偏慢在有限代數(shù)內(nèi)還來不及把多樣性優(yōu)勢轉(zhuǎn)化為最終的IGD收益。這種“有潛力但來不及兌現(xiàn)”的情況在動態(tài)分析里特別值得重視。如果你給這個算法更多評價代數(shù)它很可能反超排名靠前的算法但標(biāo)準(zhǔn)測試協(xié)議里代數(shù)是固定的算法之間比拼的不只是能力上限還有“在規(guī)定預(yù)算內(nèi)兌現(xiàn)能力”的效率。我們在論文里把這類結(jié)果標(biāo)記為“潛力型算法”并額外跑了一組“延長代數(shù)”的敏感性實(shí)驗(yàn)作為佐證。5.3 計算資源瓶頸與并行策略動態(tài)分析的代價很大31次獨(dú)立運(yùn)行乘以N個算法乘以多次采樣指數(shù)級膨脹。我們最開始直接循環(huán)跑發(fā)現(xiàn)一個函數(shù)一輪實(shí)驗(yàn)要十幾個小時。后來改成兩步走先用一個輕量級的代理指標(biāo)快速篩掉明顯差的運(yùn)行序列再用完整指標(biāo)體系跑保留的序列。保存中間快照時建議用二進(jìn)制格式不要用JSON或CSV否則磁盤IO時間可能超過算法運(yùn)行時間。我們后來用HDF5格式統(tǒng)一存儲單次運(yùn)行的快照讀寫時間從十幾秒降到零點(diǎn)幾秒這個優(yōu)化非常值得。5.4 常用問題速查表問題現(xiàn)象可能原因排查方向多樣性指標(biāo)前期劇烈震蕩參考集生成不均勻檢查稀疏區(qū)采樣點(diǎn)密度是否足夠IGD低但HV不高收斂性好但覆蓋不全重點(diǎn)看覆蓋率指標(biāo)和未覆蓋參考點(diǎn)數(shù)量稀疏區(qū)探索率長期為零算法選擇壓力過大檢查環(huán)境選擇里稀疏解是否被直接淘汰動態(tài)曲線后期突然上翹外部存檔回流或變異步長突變逐代檢查算法日志的存檔操作記錄不同算法曲線顏色難區(qū)分可視化顏色映射數(shù)值范圍不一致統(tǒng)一縱軸范圍去掉極端離群點(diǎn)后重新繪圖31次運(yùn)行結(jié)果方差過大稀疏區(qū)個體過少導(dǎo)致隨機(jī)性放大增加獨(dú)立運(yùn)行次數(shù)至51次或使用多種群策略最后分享一個實(shí)操技巧在收尾前分享一個我們覺得最實(shí)用的技巧做動態(tài)分析時不要只畫每個指標(biāo)的均值曲線一定要同時畫四分位區(qū)間帶。因?yàn)椴黄胶鈫栴}下種群行為隨機(jī)性極大均值曲線可能會給人“算法穩(wěn)定上升”的錯誤感覺而區(qū)間帶能直接暴露穩(wěn)定性問題。我們后期所有結(jié)論必須同時通過“均值形態(tài)”和“區(qū)間帶重疊度”雙重驗(yàn)證才敢寫進(jìn)論文這個習(xí)慣避免了至少兩次結(jié)論被推翻的尷尬。另外如果你也想在自己的項(xiàng)目里跑這套動態(tài)分析建議不要一開始就追求把所有指標(biāo)都算完。先拿一個你最熟悉的測試函數(shù)和一個最基礎(chǔ)的算法把“多樣性三項(xiàng)指標(biāo)IGDHV”這五條曲線跑通再逐步加復(fù)雜度。這一套東西看似簡單但里面的細(xì)節(jié)密度足夠磨掉你一兩周的耐心值得好好做。