1、離散優(yōu)化求解工業(yè)布局問(wèn)題的蟻群算法Y.Hani*,L.Amodeo,F.Yalaoui,H.ChenISTIT-OSI,CNRS2732UniversitedeTechnologiedeTroyes,12rueMarieCurieBP2060,10010Troyescedex,FranceReceived26August2005;accepted6October2006Availableonline12January2007摘要本文提出了一個(gè)與局部搜索相結(jié)合的被用于布局問(wèn)題中的混合蟻群優(yōu)化算法-ACO_GLSACO_GLS適用于工業(yè)中的情況,其被法國(guó)的鐵路系統(tǒng)設(shè)施SNCF用在列車的維修中.結(jié)果

2、說(shuō)明,與實(shí)際布局相比,這種實(shí)現(xiàn)有近20%勺改善.由于問(wèn)題建模為一個(gè)二次分配問(wèn)題LEMQAP,我們將我們的方法與一些可以解決此問(wèn)題的最正確啟發(fā)式方法做了比擬.實(shí)驗(yàn)結(jié)果說(shuō)明,在小型實(shí)例中,ACO_GLS法表現(xiàn)更好,而對(duì)于大型實(shí)例,其計(jì)算結(jié)果依舊令人滿意.關(guān)鍵詞：布局問(wèn)題；二次分配問(wèn)題；蟻群優(yōu)化；局部搜索1 .介紹設(shè)施布局問(wèn)題FLP是一個(gè)發(fā)現(xiàn)機(jī)器的很好的配置,在一個(gè)給定的設(shè)備以優(yōu)化生產(chǎn)流程的同時(shí)最小化總本錢的設(shè)備或其他資源.它對(duì)一個(gè)制造系統(tǒng)的性能具有重要意義.設(shè)施布局問(wèn)題在很多方面都有應(yīng)用,如廠房組織的應(yīng)用,新的生產(chǎn)建設(shè)單位,或設(shè)備分配.一個(gè)完整的布局描述的問(wèn)題可以從Kusiak和Heragu,19

3、87中找到.布局問(wèn)題是眾所周知的NP-難度SahniandGonzales,1976,可以在許多經(jīng)典的理論研究中發(fā)現(xiàn).然而,只有少數(shù)工業(yè)布局案例在文獻(xiàn)中被解決.應(yīng)用遺傳算法,希克斯2006提出了一個(gè)遺傳算法,用于如何在一個(gè)制造單元中最小化物質(zhì)運(yùn)動(dòng)并將其應(yīng)用到資本主義工業(yè)生產(chǎn)的實(shí)際問(wèn)題中,Lee等人2005提出了一種解決多樓層設(shè)施的布局問(wèn)題,包括墻壁和通道的內(nèi)部結(jié)構(gòu)的遺傳算法.馬丁2004提出了一個(gè)與時(shí)尚產(chǎn)業(yè)有關(guān)的研究課題.大量的研究已對(duì)FLP進(jìn)行論述；大局部是基于二次分配問(wèn)題QAP.存在其他類型,諸如混合整數(shù)規(guī)劃MontreuilandLaforge,1990;montreuilet等人,19

4、93;Meller,1999和圖論模型CaccettaandKusumah,2001.很多解決布局問(wèn)題的方法是基于元啟發(fā)式算法,如遺傳算法TAM1992;Tavakkoli-MonghaddainandShayan,1998;Lee等人,2005,禁忌搜索ChiangandChiang,1998,模擬退火B(yǎng)aykasoglu等人,2001;Chwif等人1998;MirandImaam,2001和蟻群算法Solimanpur等人,2004;Sol-imanpur等人2005.其他方法結(jié)合了遺傳算法與模擬退火算法Balakrishnan等人,2003,由Armour等人開發(fā)工藝1964.為了保證

5、得到到一個(gè)最小計(jì)算時(shí)間的全局最優(yōu)解,metaheu-ristics通常包括像這樣的2-optLin,1965局部搜索方法.另一種方法被稱為引導(dǎo)本地搜索GLSVoudouris,1997選取一個(gè)本地搜索和許可前逃離局部極小值,從而保證全局收斂性.GLS系統(tǒng)已成功應(yīng)用于旅行商問(wèn)題TSPVoudouris,1999和QAP訶題米爾斯等,2003.蟻群優(yōu)化ACO是一種廣泛用于解決二次分配問(wèn)題的方法.首次應(yīng)用是由Mani-ezzo等人提出的1994.從那以后,許多應(yīng)用程序問(wèn)題和二次差異問(wèn)題在解決方案生成、局部搜索方法和信息素更新時(shí)被提出.斯圖和多里戈1999重申了蟻群算法求解QAP問(wèn)題的方法,在執(zhí)行過(guò)程

6、中,蟻群算法是求解QAP'可題的一個(gè)很好的方法.StutzleandHoos2000研究提出的最大-最小蟻群系統(tǒng)算法MMAS,只允許最正確解決方案添加Pheromo信息素,跟蹤更新過(guò)程中的一條.這個(gè)綁定被用于跟蹤水平,以防止過(guò)早地搜索收斂.Gambardella等人1997提出了一種混合蟻群算法求解QAPhas-qap.它們的方法的獨(dú)創(chuàng)性在于信息素的追蹤是不用于構(gòu)建解決方案,而是在本地搜索中不斷修改和完善.它們提出的大多數(shù)算法對(duì)于小實(shí)例都是有效的.然而,隨著問(wèn)題規(guī)模的增大即資源,它們的表現(xiàn)越來(lái)越差.solimanpur等人2004提出了一個(gè)蟻群優(yōu)化算法,用于解決單元問(wèn)布局問(wèn)題,如QAP

7、它們提出了一種基于每個(gè)任務(wù)的局部奉獻(xiàn)度計(jì)算的下限用于maniezzo1999的技術(shù).由于問(wèn)題的復(fù)雜性,它被限制在30個(gè)部門內(nèi).在一個(gè)之前的研究中,antabu泰爾比先前的研究,etal.,2001利用蟻群算法和禁忌搜索程序,已將其成功地應(yīng)用于QAF%大實(shí)例的情況即256資源.本文提出了一種為一個(gè)QA叨法求解一個(gè)設(shè)施規(guī)劃布局問(wèn)題建模.它是基于一個(gè)GLS程序,擺脫局部極小蟻群優(yōu)化方法.該方法首先被應(yīng)用到一個(gè)特定的工業(yè)問(wèn)題中,然后,在數(shù)量很少的情況,以及從公共庫(kù)QAPL舊實(shí)例的性能下(Burkard等人,1991),我們的測(cè)試結(jié)果與Solimanpur(2004),Gambardella(1997)

8、和泰爾比等人(2001)相比,根本一致.本文的其余四個(gè)局部是：第二局部描述的設(shè)施布局問(wèn)題和工業(yè)實(shí)例建模,如QAP第三局部提出了螞蟻算法,和引導(dǎo)本地搜索程序求解QA端問(wèn)題.第四、五局部展示建模和結(jié)果對(duì)工業(yè)問(wèn)題和評(píng)估了用于一些QAPLIB實(shí)例中所提出的方法的性能.最后,第五局部得出結(jié)論.2 .問(wèn)題描述和制定2.1 描述這個(gè)問(wèn)題來(lái)自于一個(gè)由平行鐵路建立的建筑物組成的火車維修設(shè)施.每輛車根本上跨越了兩個(gè)建筑物,X1和X2專業(yè)繪畫和拆卸分別如圖1所示.車輛首先在外軌被處理,其次移至內(nèi)軌上,然后在結(jié)束它們的路線之前,沿著一個(gè)給定的序列移至兩個(gè)建筑之間.為了解決這個(gè)問(wèn)題,每一個(gè)軌道被分解成區(qū)域,稱為車輛的位

9、置,在那里進(jìn)行維修任務(wù).圖1車輛路徑在火車維護(hù)設(shè)施被處理的車輛分批到達(dá),并根據(jù)其序列在不同的建筑物中行駛.它們被處理的車輛分批到達(dá),并根據(jù)其序列在不同的建筑物中行駛.它們可以乘跨波特在一個(gè)固定的軌跡進(jìn)行橫向移動(dòng).一個(gè)在軌道交通允許平行的軌道運(yùn)動(dòng).一些任務(wù)需要很長(zhǎng)時(shí)間,它可以在很長(zhǎng)的時(shí)間里占據(jù)一些位置.這些任務(wù)代表瓶頸車間.在目前車間,由于缺乏定位,經(jīng)常為了讓其他汽車訪問(wèn)全文,一些車輛必須搬出去.目前車間的布局已被證實(shí)非常制約生產(chǎn)線規(guī)劃布局.問(wèn)題是要在一個(gè)建筑中找到一個(gè)資源的布局,以便優(yōu)化它們之間的生產(chǎn)流.圖2建筑布局說(shuō)明：1 .建筑面積4.循環(huán)通道2 .汽車位置5.橫線的運(yùn)輸機(jī)3 .不能通過(guò)的

10、位置6.在軌道上運(yùn)輸換句話說(shuō),該問(wèn)題也就是在一所房子里找到一個(gè)新的資源配置,如圖2為了優(yōu)化或最小化所有資源之間的生產(chǎn)流程或設(shè)備設(shè)施.我們認(rèn)為在將N種資源分配到一個(gè)建筑物的N個(gè)站點(diǎn)或其上的位置上中.給定一個(gè)距離矩陣D,其中的每個(gè)元素Dk,w表示位置K和W之間的距離為k,w=1,2, .,N,一個(gè)流矩陣,其中每個(gè)元素的連接,表示一個(gè)資源i和j之間的流動(dòng)本錢,i、j取值為1,2,.,No流量本錢取決于一個(gè)給定的時(shí)間范圍內(nèi)的資源的數(shù)量之間的行程.由于程序限制,所以考慮的問(wèn)題矩陣的流量是不對(duì)稱的.而距離矩陣是對(duì)稱的.計(jì)算距離與最小車輛數(shù)將在一棟建筑來(lái)做個(gè)交換.圖3為例,D(2,3)=0,D(1,3)=1

11、(通過(guò)交叉位置2)和D(2,6)=2(通過(guò)交叉位置1和5).2.2二次分配問(wèn)題(QAP)QAP歷來(lái)用于一些假設(shè)的FLP模型.在我們的工業(yè)問(wèn)題中,車輛位置的尺寸確定之間的位置和距離計(jì)算Dk,w預(yù)定義的數(shù)字值.因此,它是可能將我們的問(wèn)題限定為一個(gè)QAP問(wèn)題.圖3建筑內(nèi)部的距離計(jì)算的一個(gè)例子QAP首次由koopmansffi貝克曼(1957)提出,它是一個(gè)通過(guò)分配一組設(shè)備到一套位置上,以減少與此相關(guān)的本錢的問(wèn)題,該問(wèn)題不僅與距離和位置有關(guān),也和流動(dòng)有關(guān).f表示設(shè)施i和j之間的流dk,w,瓦特位置之間的距離k和w.一個(gè)變量P(i,j)被定義為:P(i,j)=4如果該設(shè)備被分配到位置其他情況大多數(shù)情況下

12、,設(shè)備i1簽署地點(diǎn)j1和設(shè)施i2指定位置j2相關(guān)的本錢被認(rèn)為是流動(dòng)的fi也和距離Dj1j2.因此,解可以寫成如下形式：最小數(shù)Zjj2fi1i2di1i2P(i1,j1,p(i2,j2)s.t.一jiP(i,j)=1,一i'P(i,j)=1將問(wèn)題建模后,我們采用基于蟻群優(yōu)化的方法來(lái)解決它.3.蟻群優(yōu)化算法和局部搜索算法在第一章中,我們首先提出了蟻群優(yōu)化算法和一般算法.然后,我們?cè)敿?xì)描述了蟻群算法的元素適應(yīng)的布局問(wèn)題.我們結(jié)合蟻群算法并將其用于一個(gè)引導(dǎo)本地搜索中.這一方法的定義和應(yīng)用程序的二次分配問(wèn)題在第3.2節(jié)有提及.完整的算法ACO_GLS第3.3節(jié).3.1蟻群優(yōu)化蟻群算法的原理Cor

13、ne等人,1999;Dorigo等人,2000是基于螞蟻尋找食物的方式.每只螞蟻在確定自己的路線之前都需要考慮概率選擇所有其他的螞蟻群體成員的信息素的蹤跡,它的過(guò)程中,信息素的蹤跡是一個(gè)跟蹤每一只螞蟻留下的氣味的方式.這種信息素隨著測(cè)試時(shí)間而蒸發(fā),因此選擇為每個(gè)螞蟻的概率隨時(shí)間的變化.在許多螞蟻的路徑中,對(duì)食品的路徑將人物化的痕跡,因此所有的螞蟻信息素高的將遵循相同的路徑.這種集體行為,基于共享內(nèi)部記憶的所有螞蟻殖民地之間可以適應(yīng)用于以下最優(yōu)化問(wèn)題的解決：真正的螞蟻搜索空間成為空間的組合問(wèn)題的解決方案.源食物量成為相應(yīng)的求解目標(biāo)函數(shù)的評(píng)價(jià).信息素路徑成為一種自適應(yīng)共享存儲(chǔ)器.蟻群優(yōu)化ACO的問(wèn)

14、題,因此可以被編碼為尋找圖中的最短路徑.一個(gè)蟻群算法的第一個(gè)應(yīng)用程序是旅行商問(wèn)題.在一般情況下,蟻群算法適用于人工螞蟻的概念,它可以表示為以下幾個(gè)步驟：第1步：參數(shù)初始化.第2步：解決方案的構(gòu)建.第3步：本地搜索算法.第4步：信息素更新規(guī)那么.第5步：返回到第2步,直到得到一個(gè)滿意的給定的停止準(zhǔn)那么.適用于布局的蟻群算法問(wèn)題是由以下要素組成：1 .結(jié)構(gòu)化解決方案,2 .啟發(fā)式信息,3 .信息素更新,4 .選擇概率,5 .本地搜索,6 .多樣化.7 .1.1解決方案的構(gòu)建在該算法中,它被假定每個(gè)螞蟻?zhàn)畛醴峙湟粋€(gè)任務(wù),i到位置j上,記為i,j,然后將另一個(gè)任務(wù)分配到另一個(gè)位置k上,如此繼續(xù),直到獲

15、得一個(gè)完整的解決方案.一個(gè)禁忌列表代表螞蟻已經(jīng)分配的一系列任務(wù),也就是列表對(duì)i,j0這個(gè)列表保證所有的任務(wù)都被分配到給定的地點(diǎn).任務(wù)的分配標(biāo)準(zhǔn)要考慮到分配的概率與一個(gè)給定的位置,并取決于兩個(gè)條件,一個(gè)與每只螞蟻的可見(jiàn)度有關(guān),另一個(gè)那么與整個(gè)蟻群所存放的信息素的數(shù)量有關(guān).8 .1.2啟發(fā)式信息螞蟻并不是完全盲目行動(dòng),它們會(huì)計(jì)算出一個(gè)給定的任務(wù)分配給某個(gè)地點(diǎn)的本錢.這個(gè)本錢考慮到流動(dòng)和距離矩陣.啟發(fā)式信息,也叫可見(jiàn)度,是一個(gè)函數(shù)的分配本錢.在文獻(xiàn)中使用的幾個(gè)公式,并且每一個(gè)僅適用于一個(gè)給定的問(wèn)題.關(guān)于二次分配、任務(wù)的分配取決于分配的任務(wù).將本錢與分配i,l的關(guān)系定義如下：i1C(i,l)=

16、3;(fgMdsi+fi.(s)Mdis)(1)sz1其中r表示資源的下一個(gè)排列施工.其可視性表示移動(dòng)的可取性,被定義為1-na=三1八s式frsidsi-firsdis在2中參加1分子的的原因是為了防止被0整除.這個(gè)公式說(shuō)明任務(wù)對(duì)目標(biāo)函數(shù)的奉獻(xiàn)較小將更有可能被選中.3.1.3信息素更新信息素的更新機(jī)制可以用下面的公式表示：4t=*/tT+£:3k其中SITt是信息素的分配的任務(wù),它為每只螞蟻分配的任務(wù)i及其地點(diǎn)l的迭代相聯(lián)系.當(dāng)一只螞蟻選擇了該任務(wù),數(shù)量品t隨之增加.快速收斂到局部最優(yōu)解為大的收斂結(jié)果.最終,(4)k、.bestfit3ikfitk表示通過(guò)螞蟻分配的任務(wù)的跟蹤級(jí)別的

17、變化的大小.正如所見(jiàn),越小的是更適合的解決方案,通過(guò)螞蟻k獲得適合度k,而越大將會(huì)使螞蟻k選擇的路徑水平越高.3.1.4選擇概率螞蟻選擇任務(wù)i分配到1的位置,通過(guò)以下概率：#-ii1-二ii5二二ii1-二iii"Tabuk其中一個(gè)有助于使整個(gè)螞蟻近1和每只螞蟻根據(jù)自己的能見(jiàn)度選擇近0之間的平衡.我們注意到如果相關(guān)的信息素的數(shù)量是有意義的或假設(shè)與此相關(guān)的本錢很低,那么,一個(gè)任務(wù)會(huì)被分配到一個(gè)位置.最終,具有最大概率的任務(wù)被分配到位置i上.3.1.5本地搜索我們選擇本地搜索的方法2-opt是簡(jiǎn)單的,并很好地應(yīng)用于QA睇法中soii-manpu等人,2004.該方法適用于一個(gè)給定的解決方

18、案的所有可能的排列的任務(wù).每個(gè)突變以最小的本錢為出發(fā)點(diǎn),選擇一個(gè)局部極小值.這個(gè)過(guò)程是重復(fù)的,直到不再注意到改良為止.為了在交換過(guò)程中限制計(jì)算時(shí)間,我們做了如下簡(jiǎn)化；如果交換了置換幾元素和%之間的位置,那么客觀的差函數(shù)值那么將是:Ljj=dii-djjf；-一f二j二jdij-djif二ji一f1二j.、6.一dki-dkjf孤j-fk：dik-djkfjk一fi二kk寸,j這個(gè)代數(shù)式是由GambardEiia等人在1997年提出的,他們提出了一個(gè)混合蟻群算法應(yīng)用到二次分配中的問(wèn)題叫做一個(gè)HAS-QA算法時(shí)簡(jiǎn)化的來(lái)的.本地搜索不一定導(dǎo)致全局最小.在大多數(shù)情況下,它收斂到局部極小.為此,引導(dǎo)本地

19、搜索法GLS被用作“penaiize,當(dāng)局部最小值發(fā)現(xiàn)為了收斂到全局最小.GLS等在后面進(jìn)行詳細(xì)說(shuō)明.3.1.6多樣化通過(guò)Gambardella等人1997使用.多元化機(jī)制被激活,如果迭代次數(shù)max_iter期間,沒(méi)有改善,最好的解決方案是檢測(cè)產(chǎn)生.多元化經(jīng)營(yíng)-消除所有信息包含的信息素的信息素矩陣重新初始化和隨機(jī)產(chǎn)生新的當(dāng)前解所有的螞蟻卻一分帽子收到最好的解決方案,由搜索到目前為止.另一種可能性是刪除所有信息素的路徑,除了最正確的解決方案.蟻群算法我們提出了以下的一般和2-opt蟻群優(yōu)化算法.步驟1:為所有任務(wù)和位置初始化參數(shù),步驟2:為每只螞蟻分配任務(wù)的位置與概率P,更新信息素,如果最好的解

20、決方案是沒(méi)有改善的max_iter迭代,=0,但最好的解決方案,步驟3:回到步驟2直到滿足停止準(zhǔn)那么.3.2引導(dǎo)本地搜索GLS引導(dǎo)本地搜索GLSMills等人,2003是一種元啟發(fā)式算法在局部搜索算法的頂部.當(dāng)給定的局部搜索算法解決局部最優(yōu),GLS勺變化目標(biāo)函數(shù),以增廣目標(biāo)函數(shù)增加處分,相關(guān)的功能包含在局部最優(yōu).本地搜索,然后繼續(xù)搜索使用增強(qiáng)目標(biāo)函數(shù).解決方案功能的選擇取決于問(wèn)題類型,每個(gè)特征定義必須有以下組件：1 .指示功能I"s的指示功能特點(diǎn)是目前在當(dāng)前的解決方案或不.如果特征FI在溶液S?口0否那么現(xiàn)在它等于1.2 .一個(gè)本錢函數(shù)qs對(duì)美國(guó)有網(wǎng)絡(luò)連接的本錢3 .一個(gè)點(diǎn)球r最初設(shè)

21、置為0,用來(lái)懲罰網(wǎng)絡(luò)局部極小的發(fā)生.當(dāng)本地搜索返回一個(gè)局部最小,GLS曾加功能的刑罰具有效用最大化的利用s,fi定義如下:Ci(s)這個(gè)想法的特點(diǎn)是為了懲罰,第一具有高本錢的.GL或用一種增強(qiáng)本錢函數(shù),以引導(dǎo)本地搜索出本地最正確.的想法是,使當(dāng)?shù)氐淖畎嘿F的解決方案,在周圍的搜索空間,在相同的功能是不預(yù)先發(fā)送.n(8).'.Hg(s)、Ii(s)pii1其中Gs是本錢函數(shù)和Ko用來(lái)改變尋找解決方案的多樣化的參數(shù).Ko較高的值會(huì)導(dǎo)致更多的多樣化的搜索.地理中的應(yīng)用他QAP題與以下類：即實(shí)現(xiàn)特征網(wǎng)絡(luò)；Pi溶液的對(duì)應(yīng)任務(wù)的分配我的位置P.功能網(wǎng)絡(luò)連接的本錢取決于我對(duì)解決美國(guó)所有其他任務(wù)的任務(wù)相

22、互作用.這個(gè)本錢是由nc(i,二i)="fRjji的值很好的適應(yīng)了QAP題:fij-Dij(10)GL敦術(shù)在該QAP題中的應(yīng)用可以歸納為以下:從當(dāng)前的解決方案,一個(gè)本地搜索的方法例如使用2-opt找到一個(gè)局部最小值,以增強(qiáng)本錢函數(shù).如果這個(gè)最小的本錢不增加比發(fā)現(xiàn)的最低本錢,它被保存為最好的解決方案.最后,具有最大效用的分配將有相應(yīng)的懲罰增加所述GLSQAP法可以被概括為如下:步驟1:計(jì)算步驟2:最優(yōu)解=初始解s.步驟3:相對(duì)于增強(qiáng)本錢函數(shù)執(zhí)行本地搜索2-opt,*是目前發(fā)現(xiàn)的解決方案具有低本錢擴(kuò)張如果本錢*本錢S.,由*代替S.找到任務(wù)功能的具有最大的效用,讓它成為在；Pi為例.增加

23、相應(yīng)的處分：步驟4:回到步驟3,直到滿足給定的停止準(zhǔn)那么步驟5:S哦到原問(wèn)題的最正確解決方案.3.3完整的算法最后,與GLS勺蟻群優(yōu)化算法的程序如下:步驟1:初始化參數(shù).步驟2:為所有螞蟻(a)分配任務(wù)的位置與給定的分配概率,(b)執(zhí)行本地搜索GLSQAP(c)更新信息素,(d)如果最好的方法是不到maxjter迭代改良,甬=0,但最好的解決Zu0步驟3:回到步驟2,直到滿足停止準(zhǔn)那么.4 .工業(yè)案例應(yīng)用我們認(rèn)為在建筑物的位置或汽車地點(diǎn)分配的資源.給定一個(gè)距離矩陣D,其中每個(gè)元素的DK屣示位置Kf口忱間的距離為k,w=1,2,Nff口一個(gè)流矩陣,其中每個(gè)元素的網(wǎng)絡(luò)連接,表示一個(gè)資源i和j之間的

24、流動(dòng)本錢,為i,j=1,我們的問(wèn)題建模為一個(gè)QAP流量本錢取決于一個(gè)給定的時(shí)間范圍內(nèi)的資源的數(shù)量之間的行程.在所考慮的問(wèn)題,矩陣是非對(duì)稱的,在流證據(jù)的限制.距離矩陣是對(duì)稱的.的距離計(jì)算是相關(guān)的最小數(shù)量的車輛移動(dòng)的建筑物內(nèi),以使交換模型參數(shù)：N變量總數(shù)rj資源j分配到的任務(wù)iDk,w位置WZ間的距離k和瓦特本距離被定義為可使用的數(shù)這兩個(gè)資源之間的位置frij,ri'j'資源RIJ之間生產(chǎn)流程和.此流被評(píng)價(jià)為數(shù)字汽車兩種資源之間傳Prj,kj,如果rj表示分配給位置k0,否那么(11)(12)遞的；1,如果位置是standedized.否那么TESk1,如果是專門的位置0,否那么(

25、13)為了優(yōu)化生產(chǎn)流程,我們定義二次函數(shù)的最小化：Z=££££££frij,rMDkjp»kM%,w14iji'j'kwij如果不可用的位置被排除,應(yīng)添加下面約束：Vk：ZZprij,k=115Vi,j工Prj,k=116kTEk+TESk=117約束15和16是定期分配問(wèn)題的標(biāo)準(zhǔn)約束.約束17意味著,占據(jù)了所有的位置都是專業(yè)的或標(biāo)準(zhǔn)的.5.實(shí)驗(yàn)結(jié)果5.1 參數(shù)該算法利用VisualC+6實(shí)現(xiàn).在奔騰3與1.8兆赫的處理器速度.在該算法中的四個(gè)參數(shù)：螞蟻數(shù)量,a,max_iter和影響該性能的算法等.試運(yùn)行我

26、們的問(wèn)題,每形成要找到適宜的參數(shù).螞蟻數(shù)量的測(cè)試5和60之間,和的結(jié)果與常規(guī)的質(zhì)量之間的折衷一致收斂時(shí)間被發(fā)現(xiàn)表1列出了適當(dāng)?shù)闹?很好的適應(yīng)與GLS?序.個(gè)體螞蟻調(diào)查.這個(gè)值被發(fā)現(xiàn)支持更多的支持信息素的路徑比值0.6說(shuō)明該溶液的建設(shè)一通常,«是接近0.5c在我們的情況下而被發(fā)現(xiàn)的max_iter=10和a=0.6.對(duì)于AN=20.當(dāng)一個(gè)是固定的,這個(gè)值被發(fā)現(xiàn)到很好地適應(yīng)與GLS±程.表1參數(shù)值參數(shù)值A(chǔ)N20Alpha0.6maxiter10005.2 工業(yè)應(yīng)用工業(yè)問(wèn)題包括72個(gè)地點(diǎn)27不能使用,39個(gè)專業(yè)和6個(gè)標(biāo)準(zhǔn)化位置.實(shí)際資源分配作為算法的初始條件.所有計(jì)算是根據(jù)一年的

27、數(shù)據(jù)方案.車間的實(shí)際布局產(chǎn)生然而,425的本錢,我們的算法ACO_GLS出了一種解決方案,與改良19.6%尊重實(shí)際布局.這意味著它收斂與一個(gè)更好的解決方案,這證實(shí)了它有水平解決工業(yè)布局問(wèn)題.我們也找到了問(wèn)題的精確解通過(guò)使用枚舉方法,由于只有六個(gè)任務(wù)需要分配.該溶液是相同的被發(fā)現(xiàn)的算法.這意味著該算法收斂到最正確的解決方案這個(gè)產(chǎn)業(yè)問(wèn)題.建議的應(yīng)用程序可能是有用的未來(lái)產(chǎn)業(yè)案例.事實(shí)上,如上所述在問(wèn)題描述中,行業(yè)正在嘗試提升其性能,這意味著解決其他設(shè)施問(wèn)題.止匕外,實(shí)例進(jìn)行了測(cè)試和結(jié)果進(jìn)行了比擬其他車輛與其他研究.5.3 概括該算法的性能進(jìn)彳T了測(cè)試,從庫(kù)QAPL成傷JBurkard等人,1991.

28、我們首先比擬我們的算法與HAS-QAPGambardella等人,1997的方法關(guān)于螞蟻殖民地.我們將它與ANTab此較Talbi等人,2001,與其他基于遺傳算法的方法,仿真退火,禁忌搜索或蟻群,并通過(guò)solimanpur等人2004與最近提出的蟻群優(yōu)化算法.該小數(shù)量的問(wèn)題.表3比擬的結(jié)果,所有的引用算法對(duì)于小實(shí)例的位置下降在30和19之間.我們選擇的實(shí)例包括規(guī)那么和QAPLIBf規(guī)那么問(wèn)題.這種差異關(guān)系有利于QAPLIB最知名的解決方案一個(gè)百分比差距.這幾乎是不可能的,相同的實(shí)驗(yàn)設(shè)置為以前的研究,但是,為了給計(jì)算的想法時(shí)間,平均執(zhí)行時(shí)間超過(guò)10個(gè)運(yùn)行顯示在表2.表2證實(shí)了對(duì)于實(shí)例30個(gè)任務(wù)

29、,ACO_GLS能優(yōu)于所有其他比擬算法.為了推廣我們的算法中的應(yīng)用方法,從大量QAPLIEB5例研究不同種類的問(wèn)題.結(jié)果是表3中我們比擬這些算法對(duì)一組12的實(shí)例研究,范圍從35到128個(gè)位置.大實(shí)例.曾經(jīng),我們?nèi)阅塬@得滿意的解決方法ACO_GLS能比HAS-QA更好.如何一實(shí)例.它表示表3,我們的算法大的問(wèn)題,逃離局部極小執(zhí)行更復(fù)雜的本地搜索ntabu是更好一點(diǎn),所以我們可能要對(duì)于較大的實(shí)例,給出的結(jié)果所提出的ACOGLS法被證實(shí)融合完美的情況下,最多40個(gè)地點(diǎn)作為示于表2和3這種性能是中規(guī)中矩的工業(yè)問(wèn)題,由于現(xiàn)實(shí)生活中的問(wèn)題,通常不超過(guò)30?40的位置.因此,這種算法將是一個(gè)非常有用的工具,

30、布局優(yōu)化,在現(xiàn)實(shí)生活中的產(chǎn)業(yè)本文案例中說(shuō)明表2比擬從QAPLIB選擇二次分配情況的結(jié)果最好的結(jié)果是黑體字最優(yōu)解HASQAPANTabuACOSolimanpurACOGLS時(shí)間秒Els19172125480.9230004Tai20b1224553190.2430005Chr25a37963.08220.8957003Bur26a5426670000035Bur26b381785200.01690034Bur26c5426795000034Bur26d3821225000035Bur26e5386859000034Bur26f3782044000034Bur26g10117172000033K

31、ra30a889000.62990.26770035Kra30b914200.071100.0153019Nug3061240.09800.01303數(shù)值表示解決方案的價(jià)值和百分比最著名值之間的平均差距.表3比擬從QAPLIB選擇二次分配情況的結(jié)果最好的結(jié)果是黑體字最優(yōu)解HASQAPANTabuACOGLS時(shí)間秒Tai35a24220021.7620.2150109Tai35b2833154450.3430.04080112Tai40a31393701.9890.4420204Tai50a49414102.8000.7811.28228Tai60a72085723.0700.9191.2534

32、2Tai80a135578640.6630.6631.531524Wil50488160.0610.0080.011197Sko42158120.0760082Sko49234100.1410.0380.10105Sko56345240.1010.0020.19294Sko64484980.1290.0010.008522Esc12864-001292六、總結(jié)在本文中,我們提出了一個(gè)強(qiáng)大的元啟發(fā)式算法的布局問(wèn)題建模為一個(gè)QAP該算法是基于蟻群優(yōu)化和引導(dǎo)本地搜索.GLSJ用資源的本錢函數(shù)為引導(dǎo)本地搜索出一個(gè)局部最優(yōu)解,該算法的開展是出于一個(gè)產(chǎn)業(yè)的案例在列車維修設(shè)施.我們把它應(yīng)用到一個(gè)工業(yè)案例有六

33、個(gè)位置,并找到最正確的解決方案.由于位置的數(shù)量在未來(lái)會(huì)增加,我們提出的蟻群算法的性能進(jìn)行了測(cè)試,一些測(cè)試選自文獻(xiàn)相比,許多現(xiàn)有的算法問(wèn)題.結(jié)果說(shuō)明,性能相比,HAS-QApANTab和Solimanpur等.蟻群算法隨著位置的人數(shù)高達(dá)40的問(wèn)題都可以得到我們的算法ACO_GLS因此,ACO_GLS最適應(yīng)的算法對(duì)該工業(yè)的情況和其他適應(yīng)數(shù)小于40的位置布局問(wèn)題；然而,結(jié)果仍然是令人滿意的,具有較大實(shí)例布局問(wèn)題的.未來(lái)的工作包括對(duì)于大型實(shí)例,尋找更復(fù)雜的本地搜索,找到一個(gè)更好的結(jié)果,可以處理更復(fù)雜的約束問(wèn)題的方法.參考文獻(xiàn)Armour,G.C.,Buffa,E.S.,Vollmann,T.E.,19

34、64.AllocatingfacilitieswithCRAFT.HarvardBusinessReview42,136158.Balakrishnan,J.,Cheng,C-H.,Wong,K-F.,2003.FACOPTauserfriendlyFACilitylayoutOPTimizationsystem.ComputOperatRes30,1625-1641.Baykasouglu,Gindy,N.N.Z.,2001.Asimulatedanealingalgo-rithmfordynamiclayoutproblem.Computers&OperationsResearch

35、28,1403-1426.Burkard,R.E.,Karisch,S.,Rendel,F.,1991.QAPLIB-AQuadraticAssignmentProblemLibrary.EuropeanJournalofOperationalResearch55,115-119,electronicupdate: /fmtbhpl.tu-graz.ac.at/karisch/qaplib.Caccetta,L.,Kusumah,Y.S.,2001.Computationalaspectsofthefacilitylayoutdesignproblem.Non-LinearAnalysis7,

36、5599-5610.Chiang,W.C.,Chiang,C.,1998.Intelligentlocalsearchstrategiesforsolvingfacilitylayoutproblemswiththequadraticassignmentproblemformulation.EuropeanJournalofOper-ationalResearch106,457-488.Chwif,L.,Barretto,M.R.P.,Moscato,L.A.,1998.Asolutiontothefacilitylayoutproblemusingsimulatedanealing.Com-

37、putersinindustry36,125-132.Corne,D.,Dorigo,M.,Glover,F.,1999.NewIdeasinOptimization.MacGrawHill.Dorigo,M.,Bonabeau,E.,Theraulaz,G.,2000.Antalgorithmsandstimergy.FutureGenerationComputerSystems16,851-871.Gambardella,L.M.,Taillard,E.D.,Dorigo,M.AntcoloniesfortheQAP,TechnicalreportIDISIA,1997,pp.497.Hi

38、cks,2006.Ageneticalgorithmtooldesigningmanufacturingfacilitiesinthecapitalgoodsindustry,InternationalJournalofProductionEconomics.Koopmans,T.C.,Beckman,M.,1957.Assignmentproblemsandthelocationofeconomicactivities.Econometrica25,5376.Kusiak,Heragu,S.S.,1987.Thefacilitylayoutproblem.Euro-peanJournalof

39、Operationalresearch29,229-251.Lee,K.Y.,Roh,M.I.,Jeong,H.S.,2005.Animprovedgeneticalgorithmformulti-floorfacilitylayoutproblemshavinginnerstructurewallsandpassages.Computers&OperationsResearch32(4),879899.Lin,S.,1965.Computersolutionsforthetravelingselsmanproblem.BellSystemTechnologyJournal44,224

40、52269.Maniezzo,V.,Colorni,A.,Dorigo,M.Theantsystemappliedtothequadraticassignmentproblem.TechnicalreportIRIDIA/,UniversiteLibredeBruxelles,1994,pp.94128.Maniezzo,V.,1999.Exactandapproximatenondeterministictree-searchproceduresforthequadraticassignmentproblem.INFORMSJournalonComputing11,358-369.Marte

41、ns,J.,2004.Twogeneticalgorithmstosolvealayoutprobleminfashionindustry.EuropeanJournalofOpera-tionalResearch54(1),304322.Meller,R.D.,Narayanan,V.,Vance,P.H.,1999.Optimalfacilitylayoutdesign.OperationsResearchLetters23,117127.Mills,P.,Tsang,E.,Ford,J.,2003.ApplyinganextendedGuidedLocalSearchtotheQuadr

42、aticAssignmentProblem,AnnalsofOR118,121135.Mir,M.,Imaam,M.H.,2001.Ahybridoptimizationapproachforlayoutdesignofunequal-areafacilities.Computers&IndustrialEngineering39,4963.Montreuil,Laforge,A.,1990.Amodelingfarmworkforintegratinglayoutdesignandflownetworkdesign.ProceedingofMaterialHandlingResearchColloquium,4358