呂聰穎

(南陽(yáng)理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，河南 南陽(yáng) 473000)

基于新穎蟻群算法的加工中心組成問(wèn)題研究*

呂聰穎

(南陽(yáng)理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，河南 南陽(yáng) 473000)

針對(duì)蟻群算法求解加工中心組成問(wèn)題易陷入早熟收斂狀態(tài)的缺點(diǎn),提出了將聽覺信號(hào)、記憶矩陣與蟻群算法相融合的一種新穎蟻群算法。在仿真實(shí)驗(yàn)中，分別采用蟻群算法、加入聽覺信號(hào)的蟻群算法、加入記憶矩陣的蟻群算法和新穎蟻群算法對(duì)加工中心組成問(wèn)題進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，新穎蟻群算法能夠有效提高蟻群算法的全局尋優(yōu)能力，收斂速度快，且所求得的組功效優(yōu)于以上三個(gè)策略及以往的混合遺傳算法。

新穎蟻群算法；信息素；聽覺信號(hào)；記憶矩陣

1 引言

加工中心組成問(wèn)題CF(Cell Formation)[1]是在成組技術(shù)的指導(dǎo)下對(duì)m臺(tái)機(jī)器進(jìn)行組織，根據(jù)機(jī)器之間的相似系數(shù)來(lái)形成加工中心，從而提高生產(chǎn)的標(biāo)準(zhǔn)化、專業(yè)化和自動(dòng)化程度，進(jìn)而獲得最大的經(jīng)濟(jì)效益。

蟻群算法[2,3]以正反饋及分布式計(jì)算的特點(diǎn)，在CF問(wèn)題的求解中獲得了廣泛應(yīng)用，但種種研究表明[4～11]，該算法在求解CF問(wèn)題時(shí)易陷入早熟收斂狀態(tài)。為此，本文結(jié)合CF問(wèn)題，提出了聽覺信號(hào)、記憶矩陣與蟻群算法相融合的一種新穎蟻群算法NACA(Novel Ant Colony Algorithm)。聽覺信號(hào)的引入使得精英個(gè)體對(duì)整個(gè)種群的指導(dǎo)作用得以發(fā)揮，記憶矩陣的建立使得螞蟻不斷積累自身經(jīng)驗(yàn)和社會(huì)經(jīng)驗(yàn)，從而更有效地進(jìn)行搜索。以往文獻(xiàn)中未出現(xiàn)這兩個(gè)策略。

2 加工中心組成問(wèn)題的數(shù)學(xué)模型

2.1 問(wèn)題描述

設(shè)有m臺(tái)機(jī)器要組成若干個(gè)加工中心，每個(gè)加工中心最多可有q臺(tái)機(jī)器、最少p臺(tái)機(jī)器，有n種工件要在這些機(jī)器上加工，已知工件和機(jī)器的關(guān)系矩陣A=[aij]n*m,如果工件j需要在機(jī)器i加工，則aij=1，否則為0。

問(wèn)：如何組成加工中心，才能使總的各中心的機(jī)器相似性最大？

2.2 模型的建立

(1)相關(guān)參數(shù)。

k表示加工中心；Ncell表示加工中心總數(shù)，Ncellmin≤Ncell≤Ncellmax,且Ncellmin=[m/q],Ncellmax=[m/p]。

另外，加工中心按自然數(shù)從1開始進(jìn)行編號(hào)，即加工中心1,加工中心2,加工中心3,…,顯然，最后一個(gè)加工中心的編號(hào)應(yīng)為Ncell。

Sij表示機(jī)器i和機(jī)器j的相似系數(shù)(i,j=1,2,…,m),則:

Sij∈[0,1],且

其中，ngij為需在機(jī)器i和j上加工的工件數(shù)量；ngi為需在機(jī)器i上加工的工件數(shù)量。

(2)決策變量。

(3)成組技術(shù)中加工中心組成問(wèn)題的數(shù)學(xué)模型。

目標(biāo)函數(shù)：

(1)

約束條件：

(2)

(3)

yik,yk=0或1，?i,k

(4)

目標(biāo)函數(shù)式(1)是使成組的相似性最大化，即期望將所有相似的機(jī)器指定在同一個(gè)加工中心；式(2)用來(lái)保證一臺(tái)機(jī)器只能指定在一個(gè)加工中心；式(3)用來(lái)保證每個(gè)中心的機(jī)器數(shù)不大于其最大容量q且不小于其最小容量p；式(4)為決策變量。

3 基于新穎蟻群算法的加工中心組成問(wèn)題

在構(gòu)建算法之前，首先做出如下定義：

設(shè)搜索空間維度為m(即機(jī)器臺(tái)數(shù))，種群數(shù)目為N，當(dāng)前迭代次數(shù)為t，總迭代次數(shù)為gen。

3.1 信息素的表示和更新

采用矩陣L來(lái)表示信息素：

其中，ljk(1≤j≤m,1≤k≤Ncellmax)表示將機(jī)器j指定在加工中心k所產(chǎn)生的信息素值。

迭代過(guò)程中，每只螞蟻完成搜索后需對(duì)信息素進(jìn)行更新。針對(duì)螞蟻i(1≤i≤N),對(duì)信息素的更新公式定義為：

ljk(t)=(1-ρ)ljk(t-1)+γF(xi)

(5)

其中，ρ為控制信息素值的參數(shù)；γ為信息素增加常數(shù)；F(xi)為螞蟻i搜索到的解所對(duì)應(yīng)的適應(yīng)度值(即目標(biāo)函數(shù)值)。

3.2 聽覺信號(hào)的形成和處理

文獻(xiàn)[12]指出，螞蟻有兩種發(fā)聲方法，即靠叩擊或敲打物體發(fā)聲和摩擦發(fā)聲，發(fā)聲的功能之一是召喚同伴。叩擊發(fā)聲的聲頻最大值可達(dá)4 kHz～5 kHZ,摩擦發(fā)聲的聲頻為1 kHz～4 kHz。

在此，為了加快算法的收斂速度，選取每一代適應(yīng)度最高的個(gè)體作為精英個(gè)體，記為Elite(1≤Elite≤N)。當(dāng)Elite發(fā)現(xiàn)優(yōu)良食物源時(shí)，將對(duì)整個(gè)種群發(fā)出聲音信號(hào)，以此召喚其它螞蟻。

根據(jù)文獻(xiàn)[13]所述的聽覺信息傳輸通路，分兩個(gè)階段來(lái)模擬聽覺的形成。

第一階段：聽覺反饋，模擬聽覺信號(hào)的形成。

定義2螞蟻i與Elite的差異度為：

i∈{1,2,…,N}

(6)

文獻(xiàn)[14]指出，對(duì)于800 Hz以上的頻率，聽覺信號(hào)完全滿足對(duì)數(shù)頻率。為此，聽覺信號(hào)產(chǎn)生公式定義為：

(7)

那么，螞蟻i從該聽覺信號(hào)中獲得的啟發(fā)信息究竟有多少呢？

第二階段：聽覺信號(hào)的處理，模擬大腦皮層的聽覺中樞接收和理解聽覺信號(hào)的過(guò)程，見式(8)：

(8)

3.3 記憶性

對(duì)于加工中心組成問(wèn)題，定義螞蟻i(1≤i≤N)的記憶矩陣如下：

步驟1如果螞蟻i在第t代獲得的解優(yōu)于第t-1代，則根據(jù)當(dāng)前位置向量xi=(xi1,xi2,…,xim)來(lái)更新記憶矩陣，設(shè)螞蟻i的自身經(jīng)驗(yàn)積累強(qiáng)度為α(α>1)。如果xij=k(1≤j≤m；1≤k≤Ncellmax)，則令:

(9)

步驟2設(shè)第t代的最優(yōu)解所對(duì)應(yīng)的位置向量為X=(X1,X2,…,Xm),螞蟻i的社會(huì)經(jīng)驗(yàn)積累強(qiáng)度為β(β>1)。如果Xj=k(1≤j≤m；1≤k≤Ncellmax),則令:

(10)

其中，α和β采用異步時(shí)變的方法設(shè)置：

es=esstart-t×(esstart-esend)/gen,es=α,β

(11)

開始時(shí)，設(shè)置α較大，β較小，這樣可使螞蟻傾向于搜索整個(gè)空間；后期則相反，可使螞蟻傾向于搜索全局最優(yōu)解。

3.4 概率選擇公式

(12)

根據(jù)公式(12)可得螞蟻i的概率選擇矩陣Pi：

3.5 可行解的獲得

概率矩陣表明加工中心問(wèn)題的潛在解，對(duì)矩陣進(jìn)行解碼可得加工中心組成問(wèn)題的解。

首先，針對(duì)螞蟻i，定義數(shù)組b[Ncellmax+1]來(lái)記錄指定于每個(gè)加工中心的機(jī)器數(shù)目(b[k]記錄指定于加工中心k的機(jī)器數(shù)目)，初始均為0。

最后，為了保證獲得的解是可行的，還須判斷b[k]是否滿足b[k]≥p: 如果滿足，則該解是可行的。如果不滿足，則撤消加工中心k，并對(duì)該中心的機(jī)器重新進(jìn)行分配：從xi可獲得所有分配在該中心的機(jī)器，如機(jī)器j。那么，需從概率矩陣Pi的第j行中找出滿足p<所分配的機(jī)器數(shù)目

秀珠是個(gè)性急的人，忍耐不住，次日便到金家來(lái)了。一進(jìn)門，就見一輛汽車停在門口，梅麗挾著一包書，從車上下來(lái)。秀珠便叫道：“老八剛下學(xué)嗎？”梅麗回頭一看，笑道：“好幾天不見哩，今天你來(lái)好極了，我約了幾個(gè)人打小撲克你也加入一個(gè)?！毙阒樾Φ溃骸澳銈円患胰唆[罷，肥水不落外人田，別讓我贏去了。”梅麗對(duì)秀珠望著，將左眼目夾了一下，笑道：“你不是我一家人嗎？就讓你贏了去了，也不是肥水落了外人田啦?！毙阒樾Φ溃骸澳氵@小東西，現(xiàn)在也學(xué)會(huì)了一張嘴。我先去見你三嫂，回頭再和你算帳?！泵符愋Φ溃骸拔也慌隆Ｎ业搅隳抢锶パa(bǔ)習(xí)法文，你到那里去找我得了?！闭劗叄符惖钠ば?，得得地響著，已跑遠(yuǎn)了。

如此，可確保最終獲得一個(gè)可行解。

3.6 算法描述

步驟1輸入矩陣A，計(jì)算相關(guān)參數(shù)。初始化種群，并計(jì)算種群的適應(yīng)度值，具有最大適應(yīng)度值的個(gè)體作為Elite。

步驟2如果當(dāng)前迭代次數(shù)t大于最大迭代次數(shù)gen，算法終止，輸出最優(yōu)解。

步驟3N個(gè)個(gè)體進(jìn)行搜索：

步驟3.1根據(jù)式(5)更新信息素值；

步驟3.3根據(jù)式(12)計(jì)算概率值；

步驟3.4將概率矩陣映射為問(wèn)題的可行解；

步驟3.5計(jì)算N個(gè)個(gè)體的適應(yīng)度，選取本次迭代產(chǎn)生的最優(yōu)個(gè)體，如果該最優(yōu)個(gè)體的適應(yīng)度大于Elite的適應(yīng)度，則選該個(gè)體為Elite；

步驟3.6根據(jù)式(9)和式(10)更新記憶矩陣，轉(zhuǎn)步驟2。

4 仿真實(shí)驗(yàn)

4.1 參數(shù)選擇

參數(shù)選擇是群智能算法的一個(gè)難題，目前基本都通過(guò)實(shí)驗(yàn)分析手段確定其取值。本文所提出的NACA主要引入了三個(gè)參數(shù)：增強(qiáng)學(xué)習(xí)因子Q、聽覺清晰度因子c、聽覺中樞靈敏度lmd，三者主要影響聽覺信號(hào)產(chǎn)生和處理函數(shù)的斜率和上限。本文采用不同參數(shù)組合的函數(shù)圖像來(lái)確定它們的取值，過(guò)程如圖1所示。經(jīng)過(guò)分析比對(duì)得出，取c=2.0，Q=25，lmd=0.3，能較好地適應(yīng)大多數(shù)情況。

Figure 1 Function curves for determining the values of Q,c,and lmd

根據(jù)以往研究及實(shí)驗(yàn)結(jié)果[4～11]，將其它參數(shù)設(shè)置為：種群總數(shù)N=40，總迭代次數(shù)gen=1 000，當(dāng)前進(jìn)化代數(shù)t=0，ρ=0.4，γ=0.6，αstart=3，βstart=1.5，αend=1.5，βend=3.0。

4.2 實(shí)例測(cè)試

提出的算法被應(yīng)用于解決文獻(xiàn)[15]所示的基準(zhǔn)問(wèn)題。另外，本文采用的測(cè)試算法均采用VisualC++ 6.0編程實(shí)現(xiàn)，且在同一臺(tái)計(jì)算機(jī)上各運(yùn)行50次，取最優(yōu)解。若當(dāng)前迭代次數(shù)t大于總迭代次數(shù)gen，則算法終止。

(1)簡(jiǎn)單實(shí)例。

該實(shí)例包含了12個(gè)機(jī)器和15個(gè)工件。機(jī)器和工件的初始關(guān)系矩陣A如圖2所示。

Figure 2 Original incidence matrix A of machines/parts

顯然，機(jī)器臺(tái)數(shù)m=12，工件種數(shù)n=15。令q=4，p=2，則3≤Ncell≤6。

采用NACA算法最終獲得的最優(yōu)解為(3,4,1,3,2,1,2,1,4,2,3,2)，其對(duì)應(yīng)的目標(biāo)函數(shù)值為3。由定義1可知，組成加工中心1的機(jī)器有：3,6,8；組成加工中心2的機(jī)器有：5,7,10,12；組成加工中心3的機(jī)器有：1,4,11；組成加工中心4的機(jī)器有：2,9。

蟻群算法、蟻群算法中加入聽覺信號(hào)、蟻群算法中加入記憶矩陣及NACA的收斂性如圖3所示。

Figure 3 Comparison of the convergence speed of the four algorithms

實(shí)例1的測(cè)試結(jié)果表明，NACA可對(duì)一個(gè)具體問(wèn)題進(jìn)行求解，并找到最優(yōu)組成方案，說(shuō)明算法是可行的。

圖3表明，在蟻群算法中分別引入聽覺信號(hào)或記憶矩陣，算法的收斂性要優(yōu)于蟻群算法，由此說(shuō)明在蟻群算法中加入聽覺信號(hào)或記憶矩陣，可加快算法的收斂速度；在蟻群算法中同時(shí)加入聽覺信號(hào)和記憶矩陣，即NACA算法，算法的收斂性要優(yōu)于以上三種算法，從而證明NACA算法具有較快的收斂速度。

(2)其它實(shí)例。

文獻(xiàn)[15]提出采用組功效來(lái)衡量求解加工中心組成問(wèn)題算法的有效性。因此，針對(duì)文獻(xiàn)[15]中的基準(zhǔn)問(wèn)題，采用各算法策略求得的組功效如表1所示。其中，混合遺傳算法的數(shù)據(jù)來(lái)源于文獻(xiàn)[15]。迭代次數(shù)1為前四種算法策略獲得最大組功效所需的最少迭代次數(shù)。迭代次數(shù)2為本文NACA算法獲得最大組功效所需的最少迭代次數(shù)。

表1表明，針對(duì)加工中心基準(zhǔn)問(wèn)題，在蟻群算法中分別引入聽覺信號(hào)或記憶矩陣，求得的組功效要優(yōu)于蟻群算法，由此說(shuō)明在蟻群算法中加入聽覺信號(hào)或記憶矩陣，對(duì)加工中心組成問(wèn)題的求解是有效的；在蟻群算法中同時(shí)加入聽覺信號(hào)或記憶矩陣，即NACA算法，只需較少的迭代次數(shù)就可求得較大的組功效，從而證明NACA算法具有較好的全局尋優(yōu)能力，算法的性能較優(yōu)。

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

本文針對(duì)蟻群算法在求解加工中心組成問(wèn)題時(shí)，容易出現(xiàn)收斂速度慢及陷入局部最優(yōu)的缺點(diǎn)，提出了一種新穎的蟻群算法，即引入了聽覺信號(hào)和記憶矩陣。聽覺信號(hào)的引入可發(fā)揮出精英個(gè)體Elite對(duì)整個(gè)種群進(jìn)化的推動(dòng)作用，記憶矩陣的引

Table 1 Comparison of group efficiency obtained by different algorithms表1 不同算法策略求得的組功效比較

入可促使螞蟻不斷積累經(jīng)驗(yàn)，更好地進(jìn)行搜索。實(shí)驗(yàn)階段，通過(guò)函數(shù)圖像比對(duì)確定了重要參數(shù)的取值；通過(guò)對(duì)簡(jiǎn)單實(shí)例進(jìn)行求解，驗(yàn)證了NACA算法是可行的，收斂性比對(duì)結(jié)果說(shuō)明NACA算法的收斂速度較快；通過(guò)對(duì)基準(zhǔn)問(wèn)題進(jìn)行求解，結(jié)果表明NACA算法獲得較大組功效所需的迭代次數(shù)較少。這一切表明，NACA算法是可行的，收斂速度快，性能較優(yōu)。

[1] Wang Ding-wei,Wang Jun-wei,Wang Hong-feng. Intelligent optimization methods[M]. Beijing: High Education Press,2008.(in Chinese)

[2] Mou De-yi,Liu Jin-feng. An improved ant colony algorithm for aircraft routing[J].Computer Engineering & Science,2012,34(6):136-139.(in Chinese)

[3] Zhang Jian-min,Qiahan·Hezier,Gao Da-li. A study of the logistic distribution routing problem based on the improved ant colony algorithm[J]. Computer Engineering & Science,2010,32(7):117-119.(in Chinese)

[4] Islier A. Group technology by an ant system algorithm[J]. International Journal of Production Research,2005,43 (5): 913-932.

[5] Muruganandam A, Prabhaharan G, Asokan P, et al.A memetic algorithm approach to the cell formation problem[J]. International Journal of Advanced Manufacturing Technology,2005,25(9-10):988-997.

[6] Mak K L,Peng P,Wang X X,et al. An ant colony optimization algorithm for scheduling virtual cellular manufacturing systems[J]. International Journal of Computer Integrated Manufacturing,2007,20 (6):524-537.

[7] Kao Y,Li Y L. Ant colony recognition systems for part clustering problems[J]. International Journal of Production Research,2008,46 (15):4237-4258.

[8] Megala N,Rajendran C,Gopalan R. An ant colony algorithm for cell-formation in cellular manufacturing systems[J]. European Journal of Industrial Engineering,2008,2 (3):298-335.

[9] Spiliopoulos K,Sofianopoulou S. An efficient ant colony optimization system for the manufacturing cells formation problem[J]. International Journal of Advanced Manufacturing Technology,2008,36(5-6):589-597.

[10] Li X,Baki M F,Aneja Y P. An ant colony optimization me-

ta-heuristic for machine-part cell formation problems[J]. Computers & Operations Research,2010,37:2071-2081.

[11] Xing B, Gao W J, Nelwamondo F V, et al. Part-machine clustering: The comparison between adaptive resonance theory neural network and ant colony system[J]. Lecture Notes in Electrical Engineering,Advances in Neural Network Research and Applications,2010,67 (8): 747-755.

[12] Shang Yu-chang. The visual,auditory and tactile communication of the ants[J]. Bulletin of Biology,2006,41(7):21-22.(in Chinese)

[13] Zhang Jun-hui,Gu Xian-hong,Hao Yue. Voice connections and interactions between sows and piglets[J]. China Animal Husbandry & Veterinary Medicine,2011,38(8):113-117.(in Chinese)

[14] Wu Yue-song.A study of underwater target recognition based on auditory model[M].Xi’an:Northwestern Polytechnical University,2005.(in Chinese)

[15] Goncalves J F,Resende M G C. A hybrid genetic algorithm for manufacturing cell formation:TD-5FE6RN[R]. AT&T Labs Research Technical Report,2002.

附中文參考文獻(xiàn)：

[1] 汪定偉,王俊偉,王洪峰.智能優(yōu)化方法[M].北京:高等教育出版社,2008.

[2] 牟德一,劉金鳳.改進(jìn)的蟻群算法在飛行路徑模型中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué),2012,34(6): 136-139.

[3] 張建民,恰汗·合孜爾,高大利.基于改進(jìn)蟻群算法的物流配送路徑問(wèn)題研究[J]. 計(jì)算機(jī)工程與科學(xué),2010,32(7):117-119.

[12] 尚玉昌. 螞蟻的視覺、聽覺和觸覺通訊[J]. 生物學(xué)通報(bào),2006,41(7):21-22.

[13] 張俊輝,顧憲紅,郝月.母豬與仔豬的聲音聯(lián)系及互作[J].中國(guó)畜牧獸醫(yī),2011,38(8):113-117.

[14] 吳岳松.基于聽覺模型的水下目標(biāo)識(shí)別研究[M].西安：西北工業(yè)大學(xué),2005.

呂聰穎(1981-),女,河南襄城人，碩士，講師，研究方向?yàn)橹悄芩惴?。E-mail:Lvcongying0601@126.com

Lü Cong-ying,born in 1981,MS,lecturer,her research interest includes intelligent algorithm.

A study of the cell formation problems based on a novel ant colony algorithm

Lü Cong-ying

(School of Computer and Information Engineering,Nanyang Institute of Technology,Nanyang 473000,China)

The ant colony algorithm for solving cell formation problems tends to fall into early mature convergence status. In order to overcome this defect, we propose a mixed algorithm of the ant colony algorithm, the auditory signal and the memory matrix. In the simulation experiments, the ant colony algorithm, the ant colony algorithm containing auditory signals, the ant colony algorithm containing memory matrixes, and the proposed novel algorithm are adopted respectively to solve cell formation problems. Experimental results show that the proposed algorithm outperforms the other three in terms of enhancing global optimization capacity and convergence speed of the ant colony algorithm. At the same time, the group efficiency obtained by the proposed algorithm is better than the three aforementioned algorithms and the existing hybrid genetic algorithms.

the novel ant colony algorithm;pheromone;auditory signal;memory matrix

1007-130X(2015)09-1712-06

2014-03-05;

2014-09-13基金項(xiàng)目：國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目(81101490);國(guó)家自然科學(xué)基金資助項(xiàng)目(61175023)

TP301.6

A

10.3969/j.issn.1007-130X.2015.09.019

通信地址：473000 河南省南陽(yáng)市長(zhǎng)江路80號(hào)南陽(yáng)理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院辦公室

Address:School of Computer and Information Engineering,Nanyang Institute of Technology,80 Changjiang Rd,Nanyang 473000,Henan,P.R.China