本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #636
- 日期：2026-03-18
摘要
本文從評估函數的局部性和全局性方面提出了計算進化的新視角，用於解決經典組合問題：k-著色問題（決策問題）和最小著色問題（最佳化問題）。我們首先回顧目前的演算法，並將著色問題建模為多智能體系統。然後我們表明，傳統演算法（局部搜索，如模擬退火）與分佈式演算法（如Alife&AER模型）的本質區別在於評估函數：模擬退火利用全局資訊來評估整個系統的狀態，稱為全局評估函數（GEF）方法； Alife&AER模型使用局部資訊來評估單一智慧體的狀態，稱為局部評估函數（LEF）方法。我們比較了 LEF 和 GEF 方法解決 k 著色問題和最小著色問題的效能。電腦實驗結果表明，LEF 與 GEF 方法（模擬退火和貪婪）相當，在許多問題實例中，LEF 擊敗了 GEF 方法。同時，我們分析了GEF和LEF之間的關係：一致性和不一致。一致性定理表明，當 LEF 與 GEF 一致時，LEF 的納許均衡與 GEF 的局部最優相同。這個定理部分解釋了為什麼 LEF 可以引導系統實現全域目標。提出了一些建構一致 LEF 的規則。除了一致性之外，我們還給出了 LEF 和 GEF 的圖片，並展示了它們在探索啟發式方面的差異。