朱傳軍　曹　靜　張超勇　連坤雷

1.湖北工業(yè)大學，武漢，4300682.華中科技大學數(shù)字制造裝備與技術國家重點實驗室，武漢，430074

基于改進殖民競爭算法的最小碰集求解

朱傳軍1曹靜1張超勇2連坤雷2

1.湖北工業(yè)大學，武漢，4300682.華中科技大學數(shù)字制造裝備與技術國家重點實驗室，武漢，430074

利用改進殖民競爭算法生成企業(yè)設備的最小候選集，其最小候選集就是企業(yè)設備的最小碰集。在對殖民競爭算法進行深入研究的基礎上，引入自由國家的概念，同時對算法流程中帝國初始化階段和帝國內同化及更新階段進行改進，提高了算法效率。與DMDSE-Tree算法進行了對比，在計算90%的最小碰集時，改進殖民競爭算法具有良好的效率。最后，通過某企業(yè)實例對算法的有效性進行了驗證。實驗結果表明，該方法能有效應用于企業(yè)設備選擇組合優(yōu)化問題的求解。

企業(yè)規(guī)劃；殖民競爭算法；最小碰集；設備選擇

0　引言

在現(xiàn)實生活中有很多問題可以轉化為與集合族的每個集合交集為非空的最小集合，即最小碰集問題，如基于模型的診斷中從最小沖突集生成診斷、在基因表達式分析中尋找解釋基因特性的片段問題、集體用戶公費購買書籍時的決策問題等都可以通過計算最小碰集而得到解決。計算最小碰集問題是一個NP難問題，研究者一直在尋找提高求解最小碰集效率的方法。Reiter[1]在基于模型診斷中最早提出計算最小碰集的方法——HS-Tree方法，由于該方法在求解過程中加入剪枝策略和關閉策略，故該方法會丟失正確解。為了保證求解出所有的最小碰集，Greiner等[2]對文獻[1]方法進行了改進，給出了結合非循環(huán)圖的HS-DAG方法。至今，國內外已有許多學者對求解最小碰集問題進行了研究和改進，提出了許多求解方法，主要包括精確求解和近似求解方法。精確求解方法有：基于BNB-HSSE的算法[3]、基于CHS樹和遞歸布爾算法的組合算法[4]、HSSE樹和二元標記組合算法[5]、分枝縮減方法[6]和基于動態(tài)極大度的最小碰集求解方法(DMDSE-Tree)[7]。對于規(guī)模很大的復雜系統(tǒng)，精確方法在時間和空間上仍然不符合工程實際問題的需求，而且求解復雜系統(tǒng)完全意義上的最優(yōu)解也沒有太大的現(xiàn)實意義。因此，一些學者提出了最小碰集的近似求解方法，如離散粒子群算法[8]、二進制粒子群優(yōu)化算法[9]和采用啟發(fā)式函數(shù)的低成本近似最小碰集算法STACCATO[10]等。

Atashpaz-Gargari等[11]通過模擬人類社會發(fā)展中殖民競爭過程，提出了殖民競爭算法(colonial competitive algorithm,CCA)，它是基于群體的元啟發(fā)式算法，比遺傳算法與粒子群優(yōu)化算法具有更好的收斂性，近年來得到了越來越廣泛的應用。例如，F(xiàn)orouharfard等[12]將殖民競爭算法應用于求解中轉庫的物流計劃問題；Kaveh等[13]將殖民競爭算法應用于結構最優(yōu)化設計；Nazari等[14]將殖民競爭算法用于混流生產(chǎn)中的產(chǎn)品外包問題；Sarayloo等[15]用殖民競爭算法解決動態(tài)單元化制造問題。此外，學者們還對殖民競爭算法進行了一些改進，并將其應用于解決組合優(yōu)化問題[16]、多產(chǎn)品混流裝配線平衡問題[17]和數(shù)據(jù)聚類問題[18]。本文運用改進殖民競爭算法研究近似求解最小碰集問題，并通過企業(yè)設備選擇的組合優(yōu)化問題驗證了算法的有效性。

1　改進的殖民競爭算法求解最小碰集問題

在深入研究殖民競爭算法的基礎上，本文提出了一種改進的殖民競爭算法，其核心在于引入自由國家的概念。殖民競爭算法中兩個重要的國家類型是殖民國家和殖民地，事實上還存在第三種國家——自由國家。這三類國家在改進的殖民競爭算法中的功能定義如下：

(1)殖民國家。殖民國家都盡力同化它的殖民地，并且盡力占有越來越多殖民地。

(2)殖民地。殖民地都盡力向殖民國家學習，爭取成為殖民國家或者自由國家。

(3)自由國家。自由國家都盡力向殖民國家學習，并努力成為殖民國家。

改進殖民競爭算法與原始的殖民競爭算法的主要區(qū)別在于帝國初始化階段、帝國內同化和更新階段，這是因為這些階段中增加了自由國家的算法操作。

1.1帝國初始化

改進殖民競爭算法中的初始群體有三類國家：殖民國家、殖民地和自由國家，其參數(shù)包括Nimp、Ncol和Nind，分別為三類國家的數(shù)量。因此，算法初始化階段國家總數(shù)Npop=Nimp+Nind+Ncol。對群體初始化后，按算法參數(shù)首先挑選出Nimp個殖民國家和Ncol個殖民地，其余種群數(shù)就是Nind個自由國家。構造帝國的方法與原始的殖民競爭算法相同，自由國家不受所有的帝國影響，因此帝國中不包含任何自由國家。算法初始化階段國家的分類如圖1所示。

1.2算法編碼

編碼是運用殖民競爭算法求解遇到的首要問題，也是應用成功與否的關鍵問題。二進制編碼是最常用的編碼方式，運算較易于實現(xiàn)。

為保證初始群體中的個體接近最小碰集，減少進化的代數(shù)，并且減小極小化操作的運算量，初始群體中個體元素個數(shù)的平均值(即染色體中基因為“1”的基因數(shù)的平均值)約為最小碰集中元素的個數(shù)的平均值。設X為最小碰集中元素的平均個數(shù)，基因取“1”的概率為β，則

β=X/N

(1)

一般情況下，X是未知的，所以只能估計β的取值。根據(jù)經(jīng)驗，β取值應為0.1～0.5。當集合個數(shù)n變大時，β取值也相應變大。

設染色體為Y，染色體上的i(i

1.3評價適應度

適應度函數(shù)是殖民競爭算法的核心，它的優(yōu)劣直接關系到算法搜索的效率。適應度是表示某一個體相對于目標函數(shù)的優(yōu)劣程度，在算法中還用來確定該個體繁殖后代能力的大小。適應度函數(shù)也稱為評價函數(shù)，是用來判斷群體中的個體的優(yōu)劣程度的指標，它一般根據(jù)所求問題的目標函數(shù)來進行評估。

對群體中每一個體指定一個適應度的值，要根據(jù)問題求解的實際接近程度來確定。對于最小碰集的求解，有以下兩個必要條件：①它是碰集；②它的任意真子集都不能是碰集。本文中采用的適應度函數(shù)為f(x)=t。其中，t表示當前個體與集合族中集合有非空交集的集合個數(shù)。集合的任意真子集是否為碰集，與集合中元素的個數(shù)沒有直接關系，這里無法表示出來。根據(jù)適應度函數(shù)算法收斂于碰集，而不是最小碰集，這就需要將求得的碰集轉化為最小碰集。

1.4極小化操作

本文加入極小化操作的目的就是將得到的超集轉化為對應的最小碰集。其方法就是將個體中基因為“1”的位置變?yōu)椤?”再求其適應度，若適應度不變，則保留變化，直至對所有的基因為“1”的位置執(zhí)行上述操作，個體就變成了最小碰集。

在個體中基因為“1”的位置大多數(shù)是相互關聯(lián)的，即該位置上的“1”是否能轉化為“0”與其他位置上的“1”是否轉化為“0”有關。這要根據(jù)吸收后的集合中元素對應的位置，如果吸收后的集合中含有2個或2個以上的元素，則這些元素是關聯(lián)的，否則就不是關聯(lián)的。

如果從首位開始掃描基因串，就會發(fā)現(xiàn)基因串中前面的“1”轉化為“0”的概率比后面的“1”大，則基因串后面的基因位所代表的個體比前面的基因位所代表的個體更容易出現(xiàn)在最小碰集中。為了使含有基因串前面位置所代表元素的最小碰集出現(xiàn)的概率與其他最小碰集出現(xiàn)的概率基本相同，應采用一種隨機性的掃描方法來將超集轉化為最小碰集。

極小化操作的主要過程如下：

(1)當前操作的對象是否為碰集，若是則轉步驟(2)，否則保持原狀。

(2)從第k(k為隨機取值且k

1.5殖民競爭

與殖民競爭算法相同，改進殖民競爭算法中的殖民競爭首先要計算各個帝國的總能量，一個帝國的總能量由其中的殖民國家和所有的殖民地的能量來確定，計算公式如下：

ECn=Jn+α×mean{Jm}

(2)

其中，ECn是第n個帝國的總能量；α∈(0,1)，用來平衡殖民國家能量在整個帝國能量中占的比重，即α越大，殖民國家能量占的比重越小，反之就越大，通常情況下α=0.1。Jn是殖民國家的能量，Jm是第n個帝國中第m個殖民地的能量。

與殖民競爭算法相同的是，改進的殖民競爭算法中每個帝國都努力地占有更多的殖民地，從而增加自己的總能量。殖民競爭過程會使有些帝國占有越來越多的殖民地，這樣必然使其他帝國逐漸減少所占有的殖民地。其競爭過程實現(xiàn)如下：首先，找出當前能量最小帝國內的最弱殖民地，將該殖民地設為自由狀態(tài)；然后，所有帝國通過競爭來取得對該自由狀態(tài)殖民地的占有權。不同帝國對自由狀態(tài)殖民地的占有由一定的概率來決定，即最強的帝國以最大的概率來占有該殖民地。

競爭過程需要計算不同帝國占有自由狀態(tài)殖民地的概率，為此需要求出各帝國的標準化之后的總能量ECNn：

(3)

其中，ECn和ECNn分別表示帝國的總能量和標準化之后的總能量。由此可求得各帝國對自由狀態(tài)殖民地的占有概率Pn:

(4)

為了將自由殖民地分配給殖民國家，構造如下向量：

P=(p1,p2,…,pNimp)

(5)

然后構造一個與P同樣大小的由均勻分布隨機數(shù)組成的向量R:

R=(r1,r2,…,rNimp)r1,r2,…,rNimp∈U(0,1)

(6)

通過下列運算得到向量D:

D=P-R=(D1,D2,…,DNimp)=

(p1-r1,p2-r2,…,pNimp-rNimp)

(7)

通過以上運算，自由狀態(tài)的殖民地將被D值最大的帝國占有。殖民競爭過程如圖2所示。

圖2　殖民競爭過程示意圖

1.6算法同化過程

在改進殖民競爭算法中，同化分為兩種情況，即帝國內同化和殖民國家與自由國家之間的同化。帝國內同化只涉及殖民國家與殖民地，而與自由國家無關。殖民國家與自由國家之間的同化過程主要包括以下步驟：

(1)每個自由國家首先向所有殖民國家移動，移動過程與殖民地向殖民國家移動步驟相同，通過交叉和變異來實現(xiàn)。本文采用單點交叉運算，隨機產(chǎn)生的變異點，對其基因值取反運算，即將基因值由“1”改為“0”或由“0”改為“1”，產(chǎn)生一個嶄新的個體。

(2)每個自由國家在向每個殖民國家移動之后，會得到一個新的自由國家。對這些新的自由國家進行比較，選擇最優(yōu)的自由國家作為其移動的最終位置。

帝國內同化和殖民國家與自由國家之間同化過程如圖3所示?？梢钥闯觯蹏鴥韧l(fā)生在殖民國家和它的所有殖民地之間，而殖民國家和自由國家之間的同化發(fā)生在每個自由國家和所有殖民國家之間。自由國家在做出最終移動之前，都會向每個殖民國家做出虛擬的移動，在確定最優(yōu)移動位置之后才完成真實的移動。這樣能加快算法的收斂，但是增加了算法的步驟，從而增加了計算時間。

(a)帝國內同化過程

(b)殖民國家與自由國家之間的同化過程圖3　改進算法同化過程

1.7更新過程

改進殖民競爭算法的更新過程有以下三類：

(1)殖民國家與殖民地之間的更新。如果帝國內同化之后新殖民地比殖民國家更優(yōu)，新殖民地就變成殖民國家，如圖4a所示。

(2)自由國家與殖民國家之間的更新。如果最強的自由國家在更新之后比最弱的殖民國家更優(yōu)，該自由國家與殖民國家互換，如圖4b所示。

(a)殖民國家與殖民地之間的更新

(b)自由國家與殖民國家之間的更新

(c)殖民地與自由國家之間的更新圖4　更新過程示意圖

(3)殖民地與自由國家之間的更新。在所有更新完成之后，如果最強的殖民地比最弱的自由國家更優(yōu)，該該殖民地與自由國家互換，如圖4c所示。 1.8帝國刪除

改進的殖民競爭算法中帝國刪除步驟與基本殖民競爭算法相同。

2　實驗結果分析

隨機生成50個數(shù)組，每個數(shù)組元素為10個，每個元素小于或等于20，將每個數(shù)組從小到大排序，相等的數(shù)用0代替，得到數(shù)組。將這50個數(shù)組分成小、中、大規(guī)模共5組，第1組為數(shù)組1～10，第2組為數(shù)組1～20，…，第5組為數(shù)組1～50。分別用改進的殖民競爭算法(MCCA)和基于動態(tài)極大度的極小碰集求解方法(DMDSE-Tree)[7]求解5組數(shù)據(jù)的最小碰集數(shù)和每組數(shù)據(jù)5次運算的平均運算時間。比較兩種方法求解5組數(shù)據(jù)的最小碰集數(shù)和平均運算時間。

試驗計算機配置如下:CPU為Intel Pentium G630 2.70 GHz，內存為2 GB, 操作系統(tǒng)為Windows XP，程序使用Visual C++ 6.0編寫。改進的殖民競爭算法參數(shù)設置如下：Npop=100，Nimp=7，Nind=5, 最大迭代次數(shù)Nmax=100，權重分別取0.2,0.3,…,0.8，測試α=0.6結果最優(yōu)。DMDSE-Tree和MCCA算法求得的最小碰集數(shù)和運算時間見表1和表2。

表1　DMDSE-Tree求解最小碰集數(shù)和平均運算時間表

表2　MCCA求解最小碰集數(shù)和平均運算時間表

統(tǒng)計5組數(shù)據(jù)在兩種方法下的平均運算時間與求解最小碰集數(shù)，并計算時間比例和求解比例，結果見表3。

表3　對比數(shù)據(jù)表

從表3可以看出，在MCCA求解約90%的最小碰集的情況下，MCCA的運行時間要比DMDSE-Tree的運行時間短。雖然MCCA只求解了約90%的最小碰集，但它只用了DMDSE-Tree算法時間的70%左右。可見，在求解部分最小碰集時，改進殖民競爭算法的質量與效率要優(yōu)于DMDSE-Tree算法。同時，本文隨機生成50個數(shù)組數(shù)據(jù)，分別對小、中、大規(guī)模進行求解，均獲得較優(yōu)結果，說明本文算法具有較高的魯棒性。

3　設備選擇組合優(yōu)化中的應用

某企業(yè)采用模塊式生產(chǎn)方式，現(xiàn)有12個制造單元，分別用A,B,…,L來表示，每個制造單元由多臺通用機床組成。企業(yè)將推出一種新產(chǎn)品P1，P1中自制零件有23個。由于產(chǎn)品的批量較小且機床有足夠的生產(chǎn)能力，多個零件可以在同一個制造單元內完成。為使新增產(chǎn)品對現(xiàn)有的生產(chǎn)計劃產(chǎn)生較小的影響，應采用最少的制造單元來完成這批產(chǎn)品。自制零件所對應的制造單元見表4。

表4　零件所對應的制造單元表

采用改進殖民競爭算法求解最小碰集的方法來得到最少的制造單元組，其具體步驟如下：

(1)將制造單元用數(shù)字編號，A為1，B為2，C為3，…，L為12，將零件對應的制造單元用數(shù)字編號代替。取零件對應的制造單元個數(shù)為5(制造單元個數(shù)的最大值)，不足的制造單元用“0”表示，生成一個輸入文件。

(2)用改進的殖民競爭算法的C++語言程序計算最小碰集，算法參數(shù)設置如下：Npop=100，Nimp=7，Nind=5, 最大迭代次數(shù)Nmax=100，權重取0.6。其計算結果與分析見表5。

表5　計算結果與分析

元素個數(shù)最少的最小碰集為：{7，8，9，11，12}，{1，7，9，11，12}，{1，2，7，8，12}、{2，7，8，10，12}，{2，7，8，11，12}，{6，7，9，11，12}，{7，8，9，10，12}。

(3)將元素個數(shù)最少的最小碰集轉換為制造單元組：{G,H,I,K,L}，{A,G,I,K,L}，{A,B,G,H,L}、{B,G,H,J,L}，{B,G,H,K,L}，{F,G,I,K,L}，{G,H,I,J,L}。

若采用上述制造單元組來加工產(chǎn)品P1，則其他的制造單元就不用改變生產(chǎn)計劃，只需要調整這5個制造單元的生產(chǎn)計劃，而且在制品的數(shù)量較小。當批量發(fā)生改變時，批量變更所產(chǎn)生的調整費用也較小。

4　結束語

碰集求解在工程實際中具有很多應用，但它具有計算復雜性。本文針對該問題的組合優(yōu)化特性，提出了殖民競爭算法來尋找最優(yōu)解或近優(yōu)解。在對殖民競爭算法進行深入研究的基礎上，提出了改進的殖民競爭算法，詳細介紹了算法的實施流程和操作步驟。為了驗證算法性能，本文進行了一系列的測試，該算法雖不能保證求出全部的最小碰集，但能夠在可接受的時間內給出絕大部分的最小碰集，并且保證了輸出的結果都是最小碰集。為了保證結果都是不相同的最小碰集，在運算過程中要進行大量的比較，減緩最小碰集求解速度。最后，將最小碰集應用于企業(yè)的設備選擇的組合優(yōu)化問題中。

[1]Reiter R.A Theory of Diagnosis from First Principles [J].Artificial Intelligence,1987,32(1):57-96.

[2]Greiner R,Smith B A,Wilkerson R W.A Correction to the Algorithm in Reiter’s Theory of Diagnosis(Research Note)[J].Artificial Intelligence, 1989, 41(1):79-88.

[3]陳曉梅，孟曉風，喬仁曉.基于BNB-HSSE計算全體碰集的方法[J].儀器儀表學報，2010，31(1)：605-608.

Chen Xiaomei,Meng Xiaofeng,Qiao Renxiao.Method of Computing All Minimal Hitting Set Based on BNB-HSSE [J].Chinese Journal of Scientific Instrument,2010,31(1):605-608.

[4]Wang Ziling, Xu Aiqiang, Wang Dingguo,et al.Research on a New Combined Algorithm for Computing Minimal Hitting Sets[C]//Proceedings of the 2010 International Conference on Measuring Technology and Mechatronics Automation.Changsha,2010: 14-17.

[5]Feng Wenquan, Du Min, Zhao Qi, et al.A Method of Combining HSSE-tree and Binary Label to Compute All Minimal Hitting Sets[C]//2011 Fourth International Symposium on Computational Intelligence and Design.Hangzhou,2011:14-17.

[6]Shi Lei,Cai Xuan.An Exact Fast Algorithm for Minimum Hitting Set[C]//2010 Third International Joint Conference on Computational Science and Optimization.Huangshan, 2010: 64-67.

[7]張立明,歐陽丹彤,曾海林.基于動態(tài)極大度的極小碰集求解方法[J].計算機研究與發(fā)展,2011,48(2)：209-215.

Zhang Liming, Ouyang Dantong,Zeng Hailin.Computing the Minimal Hitting Sets Based on Dynamic Maximum Degree[J].Journal of Computer Research and Development,2011,48( 2):209-215.

[8]蔣榮華,田書林,龍兵.基于DPSO的最小碰集算法的掩蓋故障識別[J].系統(tǒng)工程與電子技術,2009,31(4):997-1001.

Jiang Ronghua,Tian Shulin,Long Bing.Minimal Hitting Sets Algorithm of Identifying Masking False Failure Sets Based on DPSO[J].Systems Engineering and Electronics,2009,31(4):997-1001.

[9]呂曉明，黃考利，連光耀.基于BPSO的多故障最小候選集生成技術[J].系統(tǒng)工程與電子技術, 2012,34(5):961-965.

Lü Xiaoming, Huang Kaoli, Lian Guangyao.Generation of Minimal Candidate Set for Multiple Fault Diagnosis Based on Binary Particle Swarm Optimization[J].Systems Engineering and Electronics,2012,34(5):961-965.

[10]Abreu R,van Gemund A J C.A Low-cost Approximate Minimal Hitting Set Algorithm and Its Application to Model-Based Diagnosis[C]//Proceedings of the 8th Symposium on Abstraction,Reformulation and Approximation.Lake Arrowhead,2009:2-8.

[11]Atashpaz-Gargari E,Lucas C.Imperialist Competitive Algorithm: an Algorithm for Optimization Inspired by Imperialistic Competition[C]//IEEE Congress on Evolutionary Computation.Singapore,2007:4661-4667.

[12]Forouharfard S, Zandieh M.An Imperialist Competitive Algorithm to Schedule of Receiving and Shipping Trucks in Cross-docking Systems[J].The International Journal of Advanced Manufacturing Technology,2010,51(9):1179-1193.

[13]Kaveh A,Talatahari S.Optimum Design of Skeletal Structures Using Imperialist Competitive Algorithm[J].Computers&Structures,2010,88 (21/22):1220-1229.

[14]Nazari-Shirkouhi S,Eivazy H,Ghodsi R,et al.Solving the Integrated Product Mix-outsourcing Problem Using the Imperialist Competitive Algorithm[J].Expert Systems with Applications,2010,37(12):7615-7626.

[15]Sarayloo F,Tavakkoli-Moghaddam R.Imperialistic Competitive Algorithm for Solving a Dynamic Cell Formation Problem with Production Planning[J].Advanced Intelligent Computing Theories and Applications,2010,6215:266-276.

[16]Hadji M M,Vahidi B.A Solution to the Unit Commitment Problem Using Imperialistic Competition Algorithm[J].IEEE Transactions on Power Systems, 2011, 27(1):117-124.

[17]Bagher M,Zandieh M,Farsijani H.Balancing of Stochastic U-type Assembly Lines:an Imperialist Competitive Algorithm[J].The International Journal of Advanced Manufacturing Technology,2011,54(1/4):271-285.

[18]Niknam T,Fard E T,Pourjafarian N,et al.An Efficient Hybrid Algorithm Based on Modified Imperialist Competitive Algorithm and K-means for Data Clustering[J].Engineering Applications of Artificial Intelligence,2011,24 (2):306-317.

(編輯陳勇)

Applying Modified Colonial Competitive Algorithm to Solve Minimal Hitting Set Problems

Zhu Chuanjun1Cao Jing1Zhang Chaoyong2Lian Kunlei2

1.Hubei University of Technology,Wuhan，430068 2.State Key Laboratory of Digital Manufacturing Equipment & Technology，Huazhong University of Science and Technology,Wuhan，430074

A CCA was developed and modified to solve the problem of minimal candidates set.The minimal candidate set was a minimal hitting set. The modified CCA improved performance in initialization, assimilation and rebirth of original CCA by introducing a third type of country, independent country,to the population of countries maintained by CCA.Implementation details of the proposed CCA and modified colonial competitive algorithm(MCCA) were elaborated using an illustrative example.The performance of the algorithms was analyzed,and the results by the MCCA were compared with DMDSE-Tree algorithm.When 90% of the minimal hitting sets are obtained, the MCCA has better efficiency. Finally, the experimental results of certain system verify the effectiveness of the algorithm,which proves that this method can be applied in solving the minimal hitting set of combinatorial optimization problems for selection of equipment effectively.

business planning; colonial competitive algorithm(CCA); minimal hitting set; equipment selection

2014-03-11

國家自然科學基金資助重點項目(51035001)；國家自然科學基金資助項目(51275190)；湖北省自然科學基金資助項目(2012FFB0063，2013CFB025)

TB114.1DOI：10.3969/j.issn.1004-132X.2015.07.011

朱傳軍，男，1971年生。湖北工業(yè)大學機械工程學院副教授、博士。主要研究方向為智能優(yōu)化算法、決策分析。曹靜，女，1970年生。湖北工業(yè)大學機械工程學院講師。張超勇，男，1972年生。華中科技大學數(shù)字制造裝備與技術國家重點實驗室副教授、博士。連坤雷，男，1987年生。華中科技大學數(shù)字制造裝備與技術國家重點實驗室碩士研究生。