函數(shù)優(yōu)化實戰(zhàn)：從Pareto前沿到NSGA-II工程落地)
簡介這份資源面向需要在MATLAB環(huán)境下處理多目標(biāo)優(yōu)化問題的學(xué)生、科研人員與數(shù)學(xué)建模競賽選手核心是提供一套可直接運行的多目標(biāo)優(yōu)化模型代碼與遺傳算法工具箱。包內(nèi)共64個文件以60個m腳本為主體輔以txt說明、ps與pdf文檔壓縮包約2.74MB涵蓋目標(biāo)函數(shù)定義、約束設(shè)定、算法選擇與結(jié)果可視化等模塊并附帶遺傳算法相關(guān)函數(shù)與測試函數(shù)集便于用戶替換自己的目標(biāo)函數(shù)后快速求解。已有2540人學(xué)習(xí)下載說明其在教學(xué)與競賽場景中具有一定參考價值。讀者可借此理解帕累托最優(yōu)解集與帕累托前沿的求解思路掌握種群進化、選擇、交叉與變異等遺傳算法關(guān)鍵環(huán)節(jié)并利用配套可視化手段對結(jié)果進行解釋與決策從而在工程設(shè)計與科研建模中完成多目標(biāo)權(quán)衡。1. 多目標(biāo)函數(shù)優(yōu)化為什么你的“最優(yōu)解”在別人眼里一文不值你調(diào)了三天三夜的一組參數(shù)在測試集上把準(zhǔn)確率刷到了 0.94結(jié)果產(chǎn)品經(jīng)理看了一眼說“延遲太高線上跑不動”。你換了一組延遲達標(biāo)的參數(shù)算法負(fù)責(zé)人又說“召回掉了兩個點這個版本不能發(fā)”。這不是誰在刁難你這是典型的多目標(biāo)函數(shù)優(yōu)化問題你要同時讓多個互相拉扯的指標(biāo)都好看而它們往往此消彼長。單目標(biāo)優(yōu)化只有一個“最好”多目標(biāo)優(yōu)化沒有。它給你的是一組“誰也不比誰全面差”的解叫 Pareto 最優(yōu)解集。理解這一點是從“調(diào)參玄學(xué)”走向“可解釋取舍”的分水嶺。這篇筆記面向正在做模型調(diào)參、資源調(diào)度、推薦排序、工程參數(shù)整定的從業(yè)者把多目標(biāo)函數(shù)優(yōu)化從概念、選型、代碼實現(xiàn)到踩坑講透讓你能自己跑出一整條 Pareto 前沿而不是靠拍腦袋定一組參數(shù)。2. 先搞清楚 Pareto 支配多目標(biāo)優(yōu)化的地基多目標(biāo)優(yōu)化的所有算法判斷“哪個解更好”都依賴同一個規(guī)則Pareto 支配。如果解 A 在所有目標(biāo)上都不比解 B 差且至少在一個目標(biāo)上嚴(yán)格更好就說 A 支配 B。被支配的解可以直接淘汰剩下的互不支配的解構(gòu)成 Pareto 前沿。這個定義聽起來簡單但它是后面所有算法——無論是加權(quán)求和、NSGA-II 還是 MOEA/D——的共同語言。不把這個地基打牢后面調(diào)參數(shù)就是盲人摸象。2.1 目標(biāo)沖突的三種典型形態(tài)實際工程里目標(biāo)之間的關(guān)系大致分三類。第一類是直接沖突比如模型精度和推理延遲想提精度往往要加參數(shù)、加計算量延遲就上去了。第二類是部分相關(guān)比如召回率和覆蓋率提高召回通常也會拉高覆蓋率但到某個點后覆蓋率飽和召回繼續(xù)漲反而引入噪聲。第三類是約束型目標(biāo)比如“內(nèi)存占用不超過 2GB”它不是要優(yōu)化的方向而是一條硬邊界超過就直接判死。分清形態(tài)決定了你后面怎么建模。直接沖突適合用 Pareto 方法求前沿部分相關(guān)可以先做相關(guān)性分析把冗余目標(biāo)合并約束型目標(biāo)不要塞進目標(biāo)函數(shù)里加權(quán)而是作為可行性判據(jù)否則權(quán)重調(diào)起來會非常難受。我一般會先畫一張目標(biāo)兩兩之間的散點圖看一眼形狀再決定用哪套方案這一步花十分鐘能省后面幾小時的瞎調(diào)。2.2 加權(quán)求和法最快上手也最容易翻車加權(quán)求和是最直覺的做法把多個目標(biāo)乘上權(quán)重加起來變成一個單目標(biāo)然后隨便找個優(yōu)化器去解。它的優(yōu)點是實現(xiàn)成本極低缺點是權(quán)重和 Pareto 前沿的關(guān)系是非線性的而且當(dāng) Pareto 前沿是非凸的時候加權(quán)求和根本取不到中間那些解。下面是一個最小可復(fù)現(xiàn)的例子用加權(quán)求和去逼近一條二維 Pareto 前沿import numpy as np # 兩個目標(biāo)f1 想最小化f2 想最小化 def f1(x): return x ** 2 def f2(x): return (x - 2) ** 2 # 加權(quán)求和w 越大越偏向 f1 def weighted_sum(x, w): return w * f1(x) (1 - w) * f2(x) # 在 [-2, 4] 上粗掃每個權(quán)重取最優(yōu) x results [] for w in np.linspace(0, 1, 21): xs np.linspace(-2, 4, 2000) vals [weighted_sum(x, w) for x in xs] best_x xs[int(np.argmin(vals))] results.append((w, best_x, f1(best_x), f2(best_x))) for r in results[::5]: print(fw{r[0]:.2f} x{r[1]:.3f} f1{r[2]:.3f} f2{r[3]:.3f})這段代碼的邏輯是對每個權(quán)重 w把雙目標(biāo)壓成單目標(biāo)在 x 的取值范圍內(nèi)暴力搜索最小值。參數(shù)說明上np.linspace(0, 1, 21)控制權(quán)重粒度粒度太粗會漏掉前沿上的拐點np.linspace(-2, 4, 2000)是決策變量的搜索分辨率分辨率不夠會讓“最優(yōu) x”有偏差。跑完你會看到隨著 w 變化f1 和 f2 此消彼長這就是 Pareto 前沿的雛形。但注意這個例子里前沿恰好是凸的加權(quán)求和還能覆蓋。如果你把 f2 改成(x - 2) ** 2 0.5 * np.sin(5 * x)這種帶波動的形式前沿出現(xiàn)非凸區(qū)域加權(quán)求和就會漏解。這是加權(quán)求和最經(jīng)典的翻車點很多人調(diào)了半天權(quán)重發(fā)現(xiàn)“怎么都取不到中間那個解”原因就在這里。2.3 什么時候該放棄加權(quán)求和判斷標(biāo)準(zhǔn)很直接如果你畫出來的 Pareto 前沿明顯有凹陷或者你對權(quán)重的物理意義說不清楚就該換方法。權(quán)重說不清楚是常態(tài)——精度和延遲的權(quán)重到底該是 0.7 比 0.3 還是 0.6 比 0.4沒人能拍板。這時候用基于支配關(guān)系的多目標(biāo)進化算法直接輸出一整組解讓決策者在前沿上挑比逼著一個人定權(quán)重靠譜得多。3. 用 NSGA-II 跑出完整 Pareto 前沿NSGA-II 是工程界用得最多的多目標(biāo)進化算法之一核心機制有三塊快速非支配排序、擁擠度距離、精英保留。它不需要你給權(quán)重跑完直接給你一組互不支配的解。這一章用一個二維測試函數(shù)把整套流程跑通你能直接抄去改自己的目標(biāo)函數(shù)。3.1 快速非支配排序與擁擠度距離非支配排序的作用是給種群分層第一層是當(dāng)前種群里所有不被任何人支配的解第二層是去掉第一層后不被支配的解以此類推。分層保證了收斂性——層數(shù)越低的解越接近真實前沿。擁擠度距離則保證多樣性同一層里某個解周圍越稀疏它的擁擠度越大越容易被保留防止所有解擠在前沿的一小段上。這兩者配合的邏輯是先按層排序?qū)拥偷膬?yōu)先層相同再按擁擠度排擁擠度大的優(yōu)先。這樣既往前沿推又鋪得開。理解了這個你調(diào) NSGA-II 的參數(shù)時就知道該盯什么——種群太小會擠迭代太少層分不開。3.2 一個可復(fù)現(xiàn)的 NSGA-II 最小實現(xiàn)下面用純 NumPy 寫一個精簡版 NSGA-II目標(biāo)函數(shù)用經(jīng)典的 ZDT1 變體決策變量 10 維兩個最小化目標(biāo)import numpy as np def objectives(x): # x: (n, 10)返回 (n, 2) f1 x[:, 0] g 1 9 * np.mean(x[:, 1:], axis1) f2 g * (1 - np.sqrt(f1 / g)) return np.column_stack([f1, f2]) def dominates(a, b): # a 是否支配 b return np.all(a b) and np.any(a b) def fast_non_dominated_sort(objs): n len(objs) fronts [[]] S [[] for _ in range(n)] n_dom np.zeros(n, dtypeint) for i in range(n): for j in range(n): if i j: continue if dominates(objs[i], objs[j]): S[i].append(j) elif dominates(objs[j], objs[i]): n_dom[i] 1 if n_dom[i] 0: fronts[0].append(i) k 0 while fronts[k]: nxt [] for i in fronts[k]: for j in S[i]: n_dom[j] - 1 if n_dom[j] 0: nxt.append(j) k 1 fronts.append(nxt) return fronts[:-1] def crowding_distance(objs, front): if len(front) 2: return {i: float(inf) for i in front} dist {i: 0.0 for i in front} for m in range(objs.shape[1]): sorted_idx sorted(front, keylambda i: objs[i, m]) dist[sorted_idx[0]] float(inf) dist[sorted_idx[-1]] float(inf) span objs[sorted_idx[-1], m] - objs[sorted_idx[0], m] if span 0: continue for k in range(1, len(sorted_idx) - 1): dist[sorted_idx[k]] ( objs[sorted_idx[k 1], m] - objs[sorted_idx[k - 1], m] ) / span return dist def nsga2(pop_size100, n_gen200, n_var10): pop np.random.rand(pop_size, n_var) for _ in range(n_gen): objs objectives(pop) fronts fast_non_dominated_sort(objs) # 交叉變異 idx np.random.permutation(pop_size) children pop[idx].copy() cross_mask np.random.rand(pop_size, n_var) 0.9 partner pop[np.random.permutation(pop_size)] children np.where(cross_mask, 0.5 * children 0.5 * partner, children) children np.random.normal(0, 0.05, children.shape) children np.clip(children, 0, 1) # 合并父子選前 pop_size 個 merged np.vstack([pop, children]) mobjs objectives(merged) mfronts fast_non_dominated_sort(mobjs) new_pop [] for front in mfronts: if len(new_pop) len(front) pop_size: new_pop.extend(front) else: dist crowding_distance(mobjs, front) remain sorted(front, keylambda i: -dist[i]) new_pop.extend(remain[:pop_size - len(new_pop)]) break pop merged[new_pop] return pop, objectives(pop) pop, objs nsga2() print(前沿解數(shù)量:, len(objs)) print(f1 范圍:, objs[:, 0].min(), objs[:, 0].max()) print(f2 范圍:, objs[:, 1].min(), objs[:, 1].max())邏輯說明fast_non_dominated_sort用 O(n2) 的樸素實現(xiàn)方便你讀懂分層過程生產(chǎn)環(huán)境可以換成基于排序的 O(n log n) 版本。crowding_distance對每個目標(biāo)維度排序把邊界解的距離設(shè)為無窮大保證端點不丟中間解累加相鄰間距。主循環(huán)里先交叉變異生成子代再把父代和子代合并做一次非支配排序按層和擁擠度截斷回原種群大小這就是精英保留。參數(shù)說明pop_size100是種群規(guī)模二維目標(biāo)下 100 夠用目標(biāo)數(shù)超過 3 個建議加到 200 以上n_gen200是迭代代數(shù)太少前沿不收斂太多浪費時間一般看前沿是否穩(wěn)定交叉概率 0.9 和變異標(biāo)準(zhǔn)差 0.05 是常用起點變異太大前沿會散太小會早熟。跑完打印的 f1、f2 范圍能幫你判斷前沿鋪得開不開。3.3 結(jié)果怎么看前沿質(zhì)量的兩個指標(biāo)跑出前沿后別只看“解多不多”。兩個關(guān)鍵指標(biāo)是收斂性和分布性。收斂性看前沿離真實前沿有多近可以用超體積Hypervolume衡量選一個參考點前沿和參考點圍成的面積越大越好。分布性看解是否均勻鋪開可以用間距指標(biāo)Spacing衡量值越小越均勻。實操中我一般會跑三次不同隨機種子把三次的超體積畫成箱線圖如果波動很大說明種群太小或變異太猛。這一步很多人跳過結(jié)果拿著一次偶然跑好的前沿去匯報換個種子就崩了。4. 避坑與排查多目標(biāo)優(yōu)化最常見的五個翻車現(xiàn)場這一章全是血淚經(jīng)驗。多目標(biāo)優(yōu)化的坑不像單目標(biāo)那樣報錯給你看它往往是“結(jié)果看起來對其實完全不能用”。下面五條按“現(xiàn)象 → 原因 → 解決”寫遇到對應(yīng)情況直接對號入座。4.1 前沿全擠在一端另一端一個解都沒有現(xiàn)象跑完一看所有解都偏向精度高、延遲也高的區(qū)域低延遲那半邊完全空白。原因通常是初始化范圍太窄或者變異算子步長太小種群根本沒探索到另一側(cè)。解決先把決策變量的初始化范圍拉滿檢查每個維度的上下界是否合理再把變異標(biāo)準(zhǔn)差調(diào)大比如從 0.05 提到 0.15跑一輪看前沿是否鋪開。如果還不行檢查目標(biāo)函數(shù)是不是量綱差太多一個目標(biāo)在 0 到 1另一個在 0 到 10000擁擠度計算會被大量綱目標(biāo)主導(dǎo)。4.2 迭代到后面前沿幾乎不動但明顯沒到最優(yōu)現(xiàn)象前 50 代前沿還在推進后面 150 代幾乎原地踏步超體積不再增長。原因多半是早熟收斂種群多樣性丟了。解決引入小生境或重啟機制每隔若干代把最擁擠區(qū)域的一部分解重新隨機初始化或者換用 MOEA/D 這類基于分解的算法它對多樣性的維持機制不同。另一個常見原因是交叉算子太激進把好解打散了把交叉概率從 0.9 降到 0.7 試試。4.3 目標(biāo)數(shù)超過三個后結(jié)果完全沒法看現(xiàn)象三目標(biāo)還能勉強看四目標(biāo)、五目標(biāo)跑出來一堆解但根本分不清哪個好可視化也畫不出來。原因高維目標(biāo)空間下非支配解的比例急劇上升幾乎整個種群都互不支配選擇壓力消失。解決要么降維用主成分分析或相關(guān)性分析把冗余目標(biāo)合并要么改用基于參考點的算法比如 NSGA-III它用一組參考方向引導(dǎo)種群分布。別硬用 NSGA-II 跑五目標(biāo)那是給自己找罪受。4.4 約束條件被當(dāng)成目標(biāo)加權(quán)結(jié)果全是不可行解現(xiàn)象明明要求內(nèi)存不超過 2GB結(jié)果前沿里一半的解都超了只是超得少所以加權(quán)后總分還行。原因把硬約束塞進了目標(biāo)函數(shù)做懲罰項懲罰系數(shù)沒調(diào)好。解決把約束單獨拿出來做可行性判斷不可行解直接給一個很大的支配層級讓它永遠(yuǎn)排在可行解后面。懲罰項方法只在約束很難嚴(yán)格滿足時才用而且懲罰系數(shù)要大到讓不可行解毫無競爭力。4.5 拿單目標(biāo)的最優(yōu)解去對比多目標(biāo)前沿現(xiàn)象匯報時被問“你這組解比之前單目標(biāo)調(diào)的那組好在哪”答不上來。原因單目標(biāo)最優(yōu)解只是前沿上的一個點甚至可能不在前沿上。解決把之前單目標(biāo)調(diào)出來的那組參數(shù)也丟進目標(biāo)函數(shù)算一下畫在前沿圖上看它落在哪個位置。如果它被前沿支配說明多目標(biāo)方法確實找到了更全面的解如果它就在前沿上說明你的多目標(biāo)搜索還沒超過人工調(diào)參得繼續(xù)調(diào)算法參數(shù)。5. 從 Pareto 前沿到最終決策把選擇權(quán)交還給業(yè)務(wù)跑出前沿只是第一步真正難的是從幾十上百個解里挑一個上線。這一步?jīng)]有算法能替你做但有幾個技巧能讓決策過程不那么痛苦。5.1 拐點法找前沿上“性價比”突變的位置Pareto 前沿上通常存在拐點拐點之前犧牲一點目標(biāo) A 能換來大量目標(biāo) B 的改善拐點之后再犧牲 A 換來的 B 就很少了。找拐點的方法是對前沿做分段線性擬合計算每個點的斜率變化斜率突變處就是拐點。我一般會把拐點附近的幾個解單獨標(biāo)出來讓業(yè)務(wù)方在這幾個里選而不是面對一整條曲線發(fā)呆。import numpy as np # objs: (n, 2) 前沿解按 f1 升序排列 objs objs[np.argsort(objs[:, 0])] # 計算相鄰點斜率 slopes np.diff(objs[:, 1]) / np.diff(objs[:, 0]) # 斜率變化最大的位置即拐點候選 knee_idx np.argmax(np.abs(np.diff(slopes))) 1 print(拐點候選:, objs[knee_idx])這段代碼先按 f1 排序再算相鄰點的斜率斜率變化最大的位置就是拐點。參數(shù)上如果前沿噪聲大先做一次滑動平均再算斜率否則拐點會跳來跳去。5.2 用業(yè)務(wù)約束做二次篩選拐點法給的是“數(shù)學(xué)上合理”的候選但業(yè)務(wù)上可能還有硬性要求比如“延遲必須低于 50ms”。這時候直接在前沿上按約束切一刀把不滿足的解全去掉剩下的再按拐點或超體積貢獻排序。這一步的關(guān)鍵是約束要提前說清楚別等選完了才說“這個不行”那前面的搜索白做了。5.3 一個我常犯的錯誤早期我做多目標(biāo)優(yōu)化總想著“跑出前沿就完事了”結(jié)果每次匯報都被問“所以你到底推薦哪個”。后來我養(yǎng)成了一個習(xí)慣跑完前沿后自己先按業(yè)務(wù)約束篩一遍挑出三個候選分別寫清楚每個候選的取舍——A 方案精度高 2 個點但延遲多 15msB 方案延遲達標(biāo)但召回低 1 個點C 方案居中。把選擇權(quán)交出去但把信息補全。這樣業(yè)務(wù)方做決定快也不會回頭怪算法沒給結(jié)論。多目標(biāo)函數(shù)優(yōu)化不是讓你找到一個“完美解”而是讓你把取舍這件事從黑匣子里拿出來擺到桌面上。希望幫到你。本文還有配套的精品資源點擊獲取 多目標(biāo)函數(shù)優(yōu)化實戰(zhàn)：從Pareto前沿到NSGA-II工程落地
簡介這份資源面向需要在MATLAB環(huán)境下處理多目標(biāo)優(yōu)化問題的學(xué)生、科研人員與數(shù)學(xué)建模競賽選手核心是提供一套可直接運行的多目標(biāo)優(yōu)化模型代碼與遺傳算法工具箱。包內(nèi)共64個文件以60個m腳本為主體輔以txt說明、ps與pdf文檔壓縮包約2.74MB涵蓋目標(biāo)函數(shù)定義、約束設(shè)定、算法選擇與結(jié)果可視化等模塊并附帶遺傳算法相關(guān)函數(shù)與測試函數(shù)集便于用戶替換自己的目標(biāo)函數(shù)后快速求解。已有2540人學(xué)習(xí)下載說明其在教學(xué)與競賽場景中具有一定參考價值。讀者可借此理解帕累托最優(yōu)解集與帕累托前沿的求解思路掌握種群進化、選擇、交叉與變異等遺傳算法關(guān)鍵環(huán)節(jié)并利用配套可視化手段對結(jié)果進行解釋與決策從而在工程設(shè)計與科研建模中完成多目標(biāo)權(quán)衡。1. 多目標(biāo)函數(shù)優(yōu)化為什么你的“最優(yōu)解”在別人眼里一文不值你調(diào)了三天三夜的一組參數(shù)在測試集上把準(zhǔn)確率刷到了 0.94結(jié)果產(chǎn)品經(jīng)理看了一眼說“延遲太高線上跑不動”。你換了一組延遲達標(biāo)的參數(shù)算法負(fù)責(zé)人又說“召回掉了兩個點這個版本不能發(fā)”。這不是誰在刁難你這是典型的多目標(biāo)函數(shù)優(yōu)化問題你要同時讓多個互相拉扯的指標(biāo)都好看而它們往往此消彼長。單目標(biāo)優(yōu)化只有一個“最好”多目標(biāo)優(yōu)化沒有。它給你的是一組“誰也不比誰全面差”的解叫 Pareto 最優(yōu)解集。理解這一點是從“調(diào)參玄學(xué)”走向“可解釋取舍”的分水嶺。這篇筆記面向正在做模型調(diào)參、資源調(diào)度、推薦排序、工程參數(shù)整定的從業(yè)者把多目標(biāo)函數(shù)優(yōu)化從概念、選型、代碼實現(xiàn)到踩坑講透讓你能自己跑出一整條 Pareto 前沿而不是靠拍腦袋定一組參數(shù)。2. 先搞清楚 Pareto 支配多目標(biāo)優(yōu)化的地基多目標(biāo)優(yōu)化的所有算法判斷“哪個解更好”都依賴同一個規(guī)則Pareto 支配。如果解 A 在所有目標(biāo)上都不比解 B 差且至少在一個目標(biāo)上嚴(yán)格更好就說 A 支配 B。被支配的解可以直接淘汰剩下的互不支配的解構(gòu)成 Pareto 前沿。這個定義聽起來簡單但它是后面所有算法——無論是加權(quán)求和、NSGA-II 還是 MOEA/D——的共同語言。不把這個地基打牢后面調(diào)參數(shù)就是盲人摸象。2.1 目標(biāo)沖突的三種典型形態(tài)實際工程里目標(biāo)之間的關(guān)系大致分三類。第一類是直接沖突比如模型精度和推理延遲想提精度往往要加參數(shù)、加計算量延遲就上去了。第二類是部分相關(guān)比如召回率和覆蓋率提高召回通常也會拉高覆蓋率但到某個點后覆蓋率飽和召回繼續(xù)漲反而引入噪聲。第三類是約束型目標(biāo)比如“內(nèi)存占用不超過 2GB”它不是要優(yōu)化的方向而是一條硬邊界超過就直接判死。分清形態(tài)決定了你后面怎么建模。直接沖突適合用 Pareto 方法求前沿部分相關(guān)可以先做相關(guān)性分析把冗余目標(biāo)合并約束型目標(biāo)不要塞進目標(biāo)函數(shù)里加權(quán)而是作為可行性判據(jù)否則權(quán)重調(diào)起來會非常難受。我一般會先畫一張目標(biāo)兩兩之間的散點圖看一眼形狀再決定用哪套方案這一步花十分鐘能省后面幾小時的瞎調(diào)。2.2 加權(quán)求和法最快上手也最容易翻車加權(quán)求和是最直覺的做法把多個目標(biāo)乘上權(quán)重加起來變成一個單目標(biāo)然后隨便找個優(yōu)化器去解。它的優(yōu)點是實現(xiàn)成本極低缺點是權(quán)重和 Pareto 前沿的關(guān)系是非線性的而且當(dāng) Pareto 前沿是非凸的時候加權(quán)求和根本取不到中間那些解。下面是一個最小可復(fù)現(xiàn)的例子用加權(quán)求和去逼近一條二維 Pareto 前沿import numpy as np # 兩個目標(biāo)f1 想最小化f2 想最小化 def f1(x): return x ** 2 def f2(x): return (x - 2) ** 2 # 加權(quán)求和w 越大越偏向 f1 def weighted_sum(x, w): return w * f1(x) (1 - w) * f2(x) # 在 [-2, 4] 上粗掃每個權(quán)重取最優(yōu) x results [] for w in np.linspace(0, 1, 21): xs np.linspace(-2, 4, 2000) vals [weighted_sum(x, w) for x in xs] best_x xs[int(np.argmin(vals))] results.append((w, best_x, f1(best_x), f2(best_x))) for r in results[::5]: print(fw{r[0]:.2f} x{r[1]:.3f} f1{r[2]:.3f} f2{r[3]:.3f})這段代碼的邏輯是對每個權(quán)重 w把雙目標(biāo)壓成單目標(biāo)在 x 的取值范圍內(nèi)暴力搜索最小值。參數(shù)說明上np.linspace(0, 1, 21)控制權(quán)重粒度粒度太粗會漏掉前沿上的拐點np.linspace(-2, 4, 2000)是決策變量的搜索分辨率分辨率不夠會讓“最優(yōu) x”有偏差。跑完你會看到隨著 w 變化f1 和 f2 此消彼長這就是 Pareto 前沿的雛形。但注意這個例子里前沿恰好是凸的加權(quán)求和還能覆蓋。如果你把 f2 改成(x - 2) ** 2 0.5 * np.sin(5 * x)這種帶波動的形式前沿出現(xiàn)非凸區(qū)域加權(quán)求和就會漏解。這是加權(quán)求和最經(jīng)典的翻車點很多人調(diào)了半天權(quán)重發(fā)現(xiàn)“怎么都取不到中間那個解”原因就在這里。2.3 什么時候該放棄加權(quán)求和判斷標(biāo)準(zhǔn)很直接如果你畫出來的 Pareto 前沿明顯有凹陷或者你對權(quán)重的物理意義說不清楚就該換方法。權(quán)重說不清楚是常態(tài)——精度和延遲的權(quán)重到底該是 0.7 比 0.3 還是 0.6 比 0.4沒人能拍板。這時候用基于支配關(guān)系的多目標(biāo)進化算法直接輸出一整組解讓決策者在前沿上挑比逼著一個人定權(quán)重靠譜得多。3. 用 NSGA-II 跑出完整 Pareto 前沿NSGA-II 是工程界用得最多的多目標(biāo)進化算法之一核心機制有三塊快速非支配排序、擁擠度距離、精英保留。它不需要你給權(quán)重跑完直接給你一組互不支配的解。這一章用一個二維測試函數(shù)把整套流程跑通你能直接抄去改自己的目標(biāo)函數(shù)。3.1 快速非支配排序與擁擠度距離非支配排序的作用是給種群分層第一層是當(dāng)前種群里所有不被任何人支配的解第二層是去掉第一層后不被支配的解以此類推。分層保證了收斂性——層數(shù)越低的解越接近真實前沿。擁擠度距離則保證多樣性同一層里某個解周圍越稀疏它的擁擠度越大越容易被保留防止所有解擠在前沿的一小段上。這兩者配合的邏輯是先按層排序?qū)拥偷膬?yōu)先層相同再按擁擠度排擁擠度大的優(yōu)先。這樣既往前沿推又鋪得開。理解了這個你調(diào) NSGA-II 的參數(shù)時就知道該盯什么——種群太小會擠迭代太少層分不開。3.2 一個可復(fù)現(xiàn)的 NSGA-II 最小實現(xiàn)下面用純 NumPy 寫一個精簡版 NSGA-II目標(biāo)函數(shù)用經(jīng)典的 ZDT1 變體決策變量 10 維兩個最小化目標(biāo)import numpy as np def objectives(x): # x: (n, 10)返回 (n, 2) f1 x[:, 0] g 1 9 * np.mean(x[:, 1:], axis1) f2 g * (1 - np.sqrt(f1 / g)) return np.column_stack([f1, f2]) def dominates(a, b): # a 是否支配 b return np.all(a b) and np.any(a b) def fast_non_dominated_sort(objs): n len(objs) fronts [[]] S [[] for _ in range(n)] n_dom np.zeros(n, dtypeint) for i in range(n): for j in range(n): if i j: continue if dominates(objs[i], objs[j]): S[i].append(j) elif dominates(objs[j], objs[i]): n_dom[i] 1 if n_dom[i] 0: fronts[0].append(i) k 0 while fronts[k]: nxt [] for i in fronts[k]: for j in S[i]: n_dom[j] - 1 if n_dom[j] 0: nxt.append(j) k 1 fronts.append(nxt) return fronts[:-1] def crowding_distance(objs, front): if len(front) 2: return {i: float(inf) for i in front} dist {i: 0.0 for i in front} for m in range(objs.shape[1]): sorted_idx sorted(front, keylambda i: objs[i, m]) dist[sorted_idx[0]] float(inf) dist[sorted_idx[-1]] float(inf) span objs[sorted_idx[-1], m] - objs[sorted_idx[0], m] if span 0: continue for k in range(1, len(sorted_idx) - 1): dist[sorted_idx[k]] ( objs[sorted_idx[k 1], m] - objs[sorted_idx[k - 1], m] ) / span return dist def nsga2(pop_size100, n_gen200, n_var10): pop np.random.rand(pop_size, n_var) for _ in range(n_gen): objs objectives(pop) fronts fast_non_dominated_sort(objs) # 交叉變異 idx np.random.permutation(pop_size) children pop[idx].copy() cross_mask np.random.rand(pop_size, n_var) 0.9 partner pop[np.random.permutation(pop_size)] children np.where(cross_mask, 0.5 * children 0.5 * partner, children) children np.random.normal(0, 0.05, children.shape) children np.clip(children, 0, 1) # 合并父子選前 pop_size 個 merged np.vstack([pop, children]) mobjs objectives(merged) mfronts fast_non_dominated_sort(mobjs) new_pop [] for front in mfronts: if len(new_pop) len(front) pop_size: new_pop.extend(front) else: dist crowding_distance(mobjs, front) remain sorted(front, keylambda i: -dist[i]) new_pop.extend(remain[:pop_size - len(new_pop)]) break pop merged[new_pop] return pop, objectives(pop) pop, objs nsga2() print(前沿解數(shù)量:, len(objs)) print(f1 范圍:, objs[:, 0].min(), objs[:, 0].max()) print(f2 范圍:, objs[:, 1].min(), objs[:, 1].max())邏輯說明fast_non_dominated_sort用 O(n2) 的樸素實現(xiàn)方便你讀懂分層過程生產(chǎn)環(huán)境可以換成基于排序的 O(n log n) 版本。crowding_distance對每個目標(biāo)維度排序把邊界解的距離設(shè)為無窮大保證端點不丟中間解累加相鄰間距。主循環(huán)里先交叉變異生成子代再把父代和子代合并做一次非支配排序按層和擁擠度截斷回原種群大小這就是精英保留。參數(shù)說明pop_size100是種群規(guī)模二維目標(biāo)下 100 夠用目標(biāo)數(shù)超過 3 個建議加到 200 以上n_gen200是迭代代數(shù)太少前沿不收斂太多浪費時間一般看前沿是否穩(wěn)定交叉概率 0.9 和變異標(biāo)準(zhǔn)差 0.05 是常用起點變異太大前沿會散太小會早熟。跑完打印的 f1、f2 范圍能幫你判斷前沿鋪得開不開。3.3 結(jié)果怎么看前沿質(zhì)量的兩個指標(biāo)跑出前沿后別只看“解多不多”。兩個關(guān)鍵指標(biāo)是收斂性和分布性。收斂性看前沿離真實前沿有多近可以用超體積Hypervolume衡量選一個參考點前沿和參考點圍成的面積越大越好。分布性看解是否均勻鋪開可以用間距指標(biāo)Spacing衡量值越小越均勻。實操中我一般會跑三次不同隨機種子把三次的超體積畫成箱線圖如果波動很大說明種群太小或變異太猛。這一步很多人跳過結(jié)果拿著一次偶然跑好的前沿去匯報換個種子就崩了。4. 避坑與排查多目標(biāo)優(yōu)化最常見的五個翻車現(xiàn)場這一章全是血淚經(jīng)驗。多目標(biāo)優(yōu)化的坑不像單目標(biāo)那樣報錯給你看它往往是“結(jié)果看起來對其實完全不能用”。下面五條按“現(xiàn)象 → 原因 → 解決”寫遇到對應(yīng)情況直接對號入座。4.1 前沿全擠在一端另一端一個解都沒有現(xiàn)象跑完一看所有解都偏向精度高、延遲也高的區(qū)域低延遲那半邊完全空白。原因通常是初始化范圍太窄或者變異算子步長太小種群根本沒探索到另一側(cè)。解決先把決策變量的初始化范圍拉滿檢查每個維度的上下界是否合理再把變異標(biāo)準(zhǔn)差調(diào)大比如從 0.05 提到 0.15跑一輪看前沿是否鋪開。如果還不行檢查目標(biāo)函數(shù)是不是量綱差太多一個目標(biāo)在 0 到 1另一個在 0 到 10000擁擠度計算會被大量綱目標(biāo)主導(dǎo)。4.2 迭代到后面前沿幾乎不動但明顯沒到最優(yōu)現(xiàn)象前 50 代前沿還在推進后面 150 代幾乎原地踏步超體積不再增長。原因多半是早熟收斂種群多樣性丟了。解決引入小生境或重啟機制每隔若干代把最擁擠區(qū)域的一部分解重新隨機初始化或者換用 MOEA/D 這類基于分解的算法它對多樣性的維持機制不同。另一個常見原因是交叉算子太激進把好解打散了把交叉概率從 0.9 降到 0.7 試試。4.3 目標(biāo)數(shù)超過三個后結(jié)果完全沒法看現(xiàn)象三目標(biāo)還能勉強看四目標(biāo)、五目標(biāo)跑出來一堆解但根本分不清哪個好可視化也畫不出來。原因高維目標(biāo)空間下非支配解的比例急劇上升幾乎整個種群都互不支配選擇壓力消失。解決要么降維用主成分分析或相關(guān)性分析把冗余目標(biāo)合并要么改用基于參考點的算法比如 NSGA-III它用一組參考方向引導(dǎo)種群分布。別硬用 NSGA-II 跑五目標(biāo)那是給自己找罪受。4.4 約束條件被當(dāng)成目標(biāo)加權(quán)結(jié)果全是不可行解現(xiàn)象明明要求內(nèi)存不超過 2GB結(jié)果前沿里一半的解都超了只是超得少所以加權(quán)后總分還行。原因把硬約束塞進了目標(biāo)函數(shù)做懲罰項懲罰系數(shù)沒調(diào)好。解決把約束單獨拿出來做可行性判斷不可行解直接給一個很大的支配層級讓它永遠(yuǎn)排在可行解后面。懲罰項方法只在約束很難嚴(yán)格滿足時才用而且懲罰系數(shù)要大到讓不可行解毫無競爭力。4.5 拿單目標(biāo)的最優(yōu)解去對比多目標(biāo)前沿現(xiàn)象匯報時被問“你這組解比之前單目標(biāo)調(diào)的那組好在哪”答不上來。原因單目標(biāo)最優(yōu)解只是前沿上的一個點甚至可能不在前沿上。解決把之前單目標(biāo)調(diào)出來的那組參數(shù)也丟進目標(biāo)函數(shù)算一下畫在前沿圖上看它落在哪個位置。如果它被前沿支配說明多目標(biāo)方法確實找到了更全面的解如果它就在前沿上說明你的多目標(biāo)搜索還沒超過人工調(diào)參得繼續(xù)調(diào)算法參數(shù)。5. 從 Pareto 前沿到最終決策把選擇權(quán)交還給業(yè)務(wù)跑出前沿只是第一步真正難的是從幾十上百個解里挑一個上線。這一步?jīng)]有算法能替你做但有幾個技巧能讓決策過程不那么痛苦。5.1 拐點法找前沿上“性價比”突變的位置Pareto 前沿上通常存在拐點拐點之前犧牲一點目標(biāo) A 能換來大量目標(biāo) B 的改善拐點之后再犧牲 A 換來的 B 就很少了。找拐點的方法是對前沿做分段線性擬合計算每個點的斜率變化斜率突變處就是拐點。我一般會把拐點附近的幾個解單獨標(biāo)出來讓業(yè)務(wù)方在這幾個里選而不是面對一整條曲線發(fā)呆。import numpy as np # objs: (n, 2) 前沿解按 f1 升序排列 objs objs[np.argsort(objs[:, 0])] # 計算相鄰點斜率 slopes np.diff(objs[:, 1]) / np.diff(objs[:, 0]) # 斜率變化最大的位置即拐點候選 knee_idx np.argmax(np.abs(np.diff(slopes))) 1 print(拐點候選:, objs[knee_idx])這段代碼先按 f1 排序再算相鄰點的斜率斜率變化最大的位置就是拐點。參數(shù)上如果前沿噪聲大先做一次滑動平均再算斜率否則拐點會跳來跳去。5.2 用業(yè)務(wù)約束做二次篩選拐點法給的是“數(shù)學(xué)上合理”的候選但業(yè)務(wù)上可能還有硬性要求比如“延遲必須低于 50ms”。這時候直接在前沿上按約束切一刀把不滿足的解全去掉剩下的再按拐點或超體積貢獻排序。這一步的關(guān)鍵是約束要提前說清楚別等選完了才說“這個不行”那前面的搜索白做了。5.3 一個我常犯的錯誤早期我做多目標(biāo)優(yōu)化總想著“跑出前沿就完事了”結(jié)果每次匯報都被問“所以你到底推薦哪個”。后來我養(yǎng)成了一個習(xí)慣跑完前沿后自己先按業(yè)務(wù)約束篩一遍挑出三個候選分別寫清楚每個候選的取舍——A 方案精度高 2 個點但延遲多 15msB 方案延遲達標(biāo)但召回低 1 個點C 方案居中。把選擇權(quán)交出去但把信息補全。這樣業(yè)務(wù)方做決定快也不會回頭怪算法沒給結(jié)論。多目標(biāo)函數(shù)優(yōu)化不是讓你找到一個“完美解”而是讓你把取舍這件事從黑匣子里拿出來擺到桌面上。希望幫到你。本文還有配套的精品資源點擊獲取