分布式蟻群算法在求解NP問題中的應用研究

摘要：集合覆蓋問題已被證明是一個NP完全問題，現在所有的NP完全問題，沒有多項式時間算法求解。目前為集合覆蓋問題的主要的近似算法，復雜或大型集合覆蓋問題，現有的算法很難達到理想的優化效果。

蟻群算法是基于群體智能的進化算法為基礎的小說，關注個體的螞蟻之間的合作，利用信息素正反饋機制，具有很強的尋找更好的解決方案的能力。蟻群算法已成功地應用在許多復雜的優化問題，其優化能力提供了一種新的思路來解決集合覆蓋問題。蟻群算法具有耗時長、易陷入局部最優解的缺點。

關鍵詞：NP完全問題 蟻群算法 群體智能

第一章研究背景

集合覆蓋問題是一個NP問題，NP問題是計算機算法理論最深刻的問題，因為所有的NP完全問題，沒有多項式時間算法求解。集合覆蓋問題是非常廣泛的，許多學者提出了優化算法的集合覆蓋問題。這些算法的近似算法，根據具體問題的特點設計的，特別是問題可以得到較為理想的優化結果。

第二章 蟻群算法

2.1螞蟻的基本習性

螞蟻是一種最古老的社會性昆蟲，其起源可以追溯到100000000年前，大約相同的恐龍時代。像人類一樣，悄悄地與我們的星球億螞蟻數以百萬計，幾乎占據了所有可居住的土地，只有永恒的雪不信的南北足。雖然有成千上萬的螞蟻，但沒有一個是生活，是生活在群體中，建立了自己獨特的螞蟻社會。雖然單個螞蟻是相對簡單的，但整個殖民地的代表是作為社會組織機構的高度，可以完成比在許多情況下，螞蟻個體能力復雜的任務。螞蟻社會個人從事不同的勞動，組織可以在勞動分工執行個體。螞蟻的社會成員的組織分工除外，和相互通信和信息傳輸。螞蟻有一個獨特的信息系統，包括視覺信號，語音通信和更多的無聲的語言是獨特的，即多收集系統包括一個組合，天線信號和代理不同的化學物質作用，煽動其他人。控制自己的螞蟻獨特的環境的能力，是獲得社會行為在其不斷發展的高級形式的過程。

2.2螞蟻的覓食策略

在自然界中，螞蟻的食物來源是隨機分布在鳥巢周圍。經過仔細觀察，我們可以發現，經過一段時間后，螞蟻可以從蟻巢到食物源的最短路徑中找到。單個螞蟻的能力和智慧是非常簡單的，但它們之間相互配合，分工，兩個工人和王后的合作是不可能有足夠的命令筑巢，覓食，完成遷移能力，如打掃巢穴的復雜的行為，如覓食的螞蟻可以通過相互的合作關系的食物來源和巢形成路徑幾乎是直的。

2.3蟻群算法的思想起源

蟻群算法基本模型最初是由意大利學者提出dorig M等于在法國，在1991日舉行的第一屆歐洲人工生命會議上，巴黎：1992 dorig M在他的博士論文中進一步闡述了蟻群算法的核心理念。蟻群算法是受自然界中真實螞蟻的集體行為而提出的，它的很多觀點都來源于真實的螞蟻，所以定義算法的人工螞蟻和螞蟻都很相似，但也有真正的螞蟻的特點沒有；

1）人工螞蟻存在于一個離散的空間中，它們的移動是從一個狀態到另一個狀態的轉換貨

2）人工螞蟻具有一個記憶其本身過去行為的內在狀態參數

3）人工螞蟻不是完全盲從的，它還受到問題空間特征的啟發。例如有的問題中人工螞蟻在產生一個解后改變信息量，而有的問題中人工螞蟻每做出一步選擇就更改信息量，但無論哪種方法，信息量的更新并不是隨時都可進行的。

4）人工螞蟻存在于一個與時間無關聯的環境之中。

為了改善算法的優化效率，人工螞蟻可增加一些性能，如預測未來、局部優化、回退等，這些行為在真實螞蟻中是不存在的。在很多具體應用中，人工螞蟻可在局部優化過程中相互交接信息，還有一些改進螞蟻算法中的人工螞蟻可實現簡單預測。

第三章 基于蟻群算法的集合覆蓋問題求解

3.1集合覆蓋問題描述

集合覆蓋問題是一個最優化問題，它模型化了許多資源選擇

問題，已經被證明是NP難度的。集合覆蓋問題是一個實例（X，F）由一個有窮集X 和一個X的子集族F構成，且X的每一個元素屬于F中的至少一個子集：

我們說S∈F覆蓋了它的元素。這個問題的目的是要找到一個最小規模子集C屬于F，使其所有成員覆蓋X的所有成員：

我們說任何滿足方程的C覆蓋X。圖3.1是集合覆蓋的一個例子，C的規模被定義為它所包含的集合數，而不是這些集合中的元素數。容易看出上式中最小解集規模為3，分別是S3、S4、S5。

為了便于用數學工具來描述集合覆蓋問題，通常將集合覆蓋模型抽象成矩陣形式來表示。

例1 設S={0，1，2，3，4，5，6，7，8，9，10，11}；S1={0，1，2，3，4，5}；S2={4，5，7，8}；

S3={0，3，6，9}；S4={1，4，7，10}；S5={2，5，8，11}；

用矩陣的，第i（1≤i≤12）行表示有窮集S中的第i個元素，第j（1≤j≤5）列表示子集Sj.矩陣元素Cij=1表示子集Sj包含集合S中的第i個元素，可稱j列覆蓋了i行政反之，表示子集Si不包含集合S中的元素，j列不覆蓋i行。按上述方法例1的集合覆蓋模型可以抽象成如圖3.2的矩陣形式，本文稱此矩陣為覆蓋矩陣C。

例1中的集合覆蓋問題轉換成圖3.2所示覆蓋矩陣形式后，在集合覆蓋問題中通常定義5維布爾向量y=（y1，y2，…，y5）T，yj=1（1≤j≤5）表示第j列被選中，yj=0表示第j列被排除。從而集合覆蓋問題的優化可按以下等價的方式描述：

為例1中的各子集Sj配一個權重值wj，則帶權重的集合覆蓋問題可以用如下數學方式描述：

滿足：C.Y≥1，Y∈{0，1}5.

在很多實際問題中，為了更好的利用具體問題的有效信息，一般考慮把能反映問題特性的信息量作為權重值，然后對帶權重的集合覆蓋模型進行優化。

集合覆蓋問題模型有極其廣泛的應用，在實際問題中經常會遇到，目前優化集合覆蓋問題的一些近似算法，對于復雜的或規模較大的集合覆蓋問題的優化效果不太理想。

參考文獻：

[1]M.R Garey and DS Johnson.Computer and Intractability：A Guide to the Theory of NP-Completemess.San Francisco：W.H.Freeman，1979.

[2] Christian Plessl and Marco Platzner.Custom Computing Machines for Set Covering Problem.10th Annual IEEE Symposium on Field-Programmable Custom Computing machines（FCCM’02），2002.