多主體優化系統

組合最優化，在應用數學和理論計算機科學的領域中，組合優化是在一個有限的對象集中找出最優對象的一類課題。在很多組合優化的問題中，窮舉搜索/枚舉法是不可行的。組合優化的問題的特徵是可行解的集是離散或者可以簡化到離散的，並且目標是找到最優解。常見的例子有旅行商問題和最小生成樹。二維的例子，比如服裝廠做衣服，衣服分成很多塊，這些塊需要從布料上切下來。怎麼切，剩下的廢布料最少？三維的例子，如集裝優化。

組合優化的難處，主要是加進來拓撲分析，不同的拓撲形態下，不同部分的約束關係便不同，算法也就要調整。如果給定一個拓撲形態，組合優化往往就退化成一個整數優化的問題了。 ^[1] 

羣集智能(Swarm intelligence, SI)是一種研究分散型的自組織系統中的集體行為的人工智能技術。

典型的羣集智能系統由一羣簡單的主體構成，每個主體和其它主體以及它們的環境作局部的交互。儘管通常沒有集中控制機制來指示這些主體如何協作，但這些簡單的局部交互行為通常能湧現出複雜的全局行為。當前主要的幾種羣集智能方法包括蟻羣算法和粒子羣優化。 ^[1] 

揹包問題（Knapsack problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定揹包中。

相似問題經常出現在商業、組合數學，計算複雜性理論、密碼學和應用數學等領域中。也可以將揹包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V。 ^[1] 

圖着色問題（英語：Graph Coloring Problem，簡稱GCP），又稱着色問題，是最著名的NP-完全問題之一。

給定一個無向圖

，其中

為頂點集合，

為邊集合，圖着色問題即為將

分為K個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。其優化版本是希望獲得最小的K值。 ^[1] 

旅行推銷員問題（最短路徑問題）（英語：Travelling salesman problem,TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。它是組合優化中的一個NP困難問題，在運籌學和理論計算機科學中非常重要。

TSP是旅行購買者問題與車輛路徑問題的一種特殊情況。

在計算複雜性理論中，TSP的做決定版本（其中，給定長度L，任務是決定圖中是否有路徑比L還要短）屬於NP完全問題。因此隨着城市數量的增多，任何TSP算法最壞情況下的運行時間都有可能隨着城市數量的增多超多項式（可能是指數）級別增長。

問題在1930年首次被形式化，並且是在最優化中研究最深入的問題之一。許多優化方法都用它作為一個基準。儘管問題在計算上很困難，但已經有了大量的啓發式和精確方法，因此可以完全求解城市數量上萬的實例，並且甚至能在誤差1%範圍內估計上百萬個城市的問題。

甚至純粹形式的TSP都有若干應用，如企劃、物流、芯片製造。稍作修改，就是DNA測序等許多領域的一個子問題。在這些應用中，“城市”的概念用來表示客户、焊接點或DNA片段，而“距離”的概念表示旅行時間或成本或DNA片段之間的相似性度量。TSP還用在天文學中，觀察很多源的天文學家希望減少在源之間轉動望遠鏡的時間。許多應用（如資源或時間窗口有限）中，可能會加入額外的約束。 ^[1]