基于改進(jìn)殖民競(jìng)爭(zhēng)算法的最小碰集求解

朱傳軍　曹　靜　張超勇　連坤雷

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

基于改進(jìn)殖民競(jìng)爭(zhēng)算法的最小碰集求解

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

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

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

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

0　引言

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

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

1　改進(jìn)的殖民競(jìng)爭(zhēng)算法求解最小碰集問(wèn)題

在深入研究殖民競(jìng)爭(zhēng)算法的基礎(chǔ)上，本文提出了一種改進(jìn)的殖民競(jìng)爭(zhēng)算法，其核心在于引入自由國(guó)家的概念。殖民競(jìng)爭(zhēng)算法中兩個(gè)重要的國(guó)家類型是殖民國(guó)家和殖民地，事實(shí)上還存在第三種國(guó)家——自由國(guó)家。這三類國(guó)家在改進(jìn)的殖民競(jìng)爭(zhēng)算法中的功能定義如下：

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

(2)殖民地。殖民地都盡力向殖民國(guó)家學(xué)習(xí)，爭(zhēng)取成為殖民國(guó)家或者自由國(guó)家。

(3)自由國(guó)家。自由國(guó)家都盡力向殖民國(guó)家學(xué)習(xí)，并努力成為殖民國(guó)家。

改進(jìn)殖民競(jìng)爭(zhēng)算法與原始的殖民競(jìng)爭(zhēng)算法的主要區(qū)別在于帝國(guó)初始化階段、帝國(guó)內(nèi)同化和更新階段，這是因?yàn)檫@些階段中增加了自由國(guó)家的算法操作。

1.1帝國(guó)初始化

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

1.2算法編碼

編碼是運(yùn)用殖民競(jìng)爭(zhēng)算法求解遇到的首要問(wèn)題，也是應(yīng)用成功與否的關(guān)鍵問(wèn)題。二進(jìn)制編碼是最常用的編碼方式，運(yùn)算較易于實(shí)現(xiàn)。

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

β=X/N

(1)

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

設(shè)染色體為Y，染色體上的i(i

1.3評(píng)價(jià)適應(yīng)度

適應(yīng)度函數(shù)是殖民競(jìng)爭(zhēng)算法的核心，它的優(yōu)劣直接關(guān)系到算法搜索的效率。適應(yīng)度是表示某一個(gè)體相對(duì)于目標(biāo)函數(shù)的優(yōu)劣程度，在算法中還用來(lái)確定該個(gè)體繁殖后代能力的大小。適應(yīng)度函數(shù)也稱為評(píng)價(jià)函數(shù)，是用來(lái)判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它一般根據(jù)所求問(wèn)題的目標(biāo)函數(shù)來(lái)進(jìn)行評(píng)估。

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

1.4極小化操作

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

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

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

極小化操作的主要過(guò)程如下：

(1)當(dāng)前操作的對(duì)象是否為碰集，若是則轉(zhuǎn)步驟(2)，否則保持原狀。

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

1.5殖民競(jìng)爭(zhēng)

與殖民競(jìng)爭(zhēng)算法相同，改進(jìn)殖民競(jìng)爭(zhēng)算法中的殖民競(jìng)爭(zhēng)首先要計(jì)算各個(gè)帝國(guó)的總能量，一個(gè)帝國(guó)的總能量由其中的殖民國(guó)家和所有的殖民地的能量來(lái)確定，計(jì)算公式如下：

ECn=Jn+α×mean{Jm}

(2)

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

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

競(jìng)爭(zhēng)過(guò)程需要計(jì)算不同帝國(guó)占有自由狀態(tài)殖民地的概率，為此需要求出各帝國(guó)的標(biāo)準(zhǔn)化之后的總能量ECNn：

(3)

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

(4)

為了將自由殖民地分配給殖民國(guó)家，構(gòu)造如下向量：

P=(p1,p2,…,pNimp)

(5)

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

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

(6)

通過(guò)下列運(yùn)算得到向量D:

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

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

(7)

通過(guò)以上運(yùn)算，自由狀態(tài)的殖民地將被D值最大的帝國(guó)占有。殖民競(jìng)爭(zhēng)過(guò)程如圖2所示。

圖2　殖民競(jìng)爭(zhēng)過(guò)程示意圖

1.6算法同化過(guò)程

在改進(jìn)殖民競(jìng)爭(zhēng)算法中，同化分為兩種情況，即帝國(guó)內(nèi)同化和殖民國(guó)家與自由國(guó)家之間的同化。帝國(guó)內(nèi)同化只涉及殖民國(guó)家與殖民地，而與自由國(guó)家無(wú)關(guān)。殖民國(guó)家與自由國(guó)家之間的同化過(guò)程主要包括以下步驟：

(1)每個(gè)自由國(guó)家首先向所有殖民國(guó)家移動(dòng)，移動(dòng)過(guò)程與殖民地向殖民國(guó)家移動(dòng)步驟相同，通過(guò)交叉和變異來(lái)實(shí)現(xiàn)。本文采用單點(diǎn)交叉運(yùn)算，隨機(jī)產(chǎn)生的變異點(diǎn)，對(duì)其基因值取反運(yùn)算，即將基因值由“1”改為“0”或由“0”改為“1”，產(chǎn)生一個(gè)嶄新的個(gè)體。

(2)每個(gè)自由國(guó)家在向每個(gè)殖民國(guó)家移動(dòng)之后，會(huì)得到一個(gè)新的自由國(guó)家。對(duì)這些新的自由國(guó)家進(jìn)行比較，選擇最優(yōu)的自由國(guó)家作為其移動(dòng)的最終位置。

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

(a)帝國(guó)內(nèi)同化過(guò)程

(b)殖民國(guó)家與自由國(guó)家之間的同化過(guò)程圖3　改進(jìn)算法同化過(guò)程

1.7更新過(guò)程

改進(jìn)殖民競(jìng)爭(zhēng)算法的更新過(guò)程有以下三類：

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

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

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

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

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

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

改進(jìn)的殖民競(jìng)爭(zhēng)算法中帝國(guó)刪除步驟與基本殖民競(jìng)爭(zhēng)算法相同。

2　實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

表4　零件所對(duì)應(yīng)的制造單元表

采用改進(jìn)殖民競(jìng)爭(zhēng)算法求解最小碰集的方法來(lái)得到最少的制造單元組，其具體步驟如下：

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

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

表5　計(jì)算結(jié)果與分析

元素個(gè)數(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)將元素個(gè)數(shù)最少的最小碰集轉(zhuǎn)換為制造單元組：{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}。

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

4　結(jié)束語(yǔ)

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

[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]陳曉梅，孟曉風(fēng)，喬仁曉.基于BNB-HSSE計(jì)算全體碰集的方法[J].儀器儀表學(xué)報(bào)，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]張立明,歐陽(yáng)丹彤,曾海林.基于動(dòng)態(tài)極大度的極小碰集求解方法[J].計(jì)算機(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的最小碰集算法的掩蓋故障識(shí)別[J].系統(tǒng)工程與電子技術(shù),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的多故障最小候選集生成技術(shù)[J].系統(tǒng)工程與電子技術(shù), 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

國(guó)家自然科學(xué)基金資助重點(diǎn)項(xiàng)目(51035001)；國(guó)家自然科學(xué)基金資助項(xiàng)目(51275190)；湖北省自然科學(xué)基金資助項(xiàng)目(2012FFB0063，2013CFB025)

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

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