基于corba的分布式遺傳算法在csp問題中的應(yīng)用

基于corba的分布式遺傳算法在csp問題中的應(yīng)用

1tsp分布式計算tsp（交通便利的商業(yè)手段）是一個通過證明非營利時間復(fù)雜性來優(yōu)化的問題。它的簡單描述是：平面上有N(N>0）個城市，一推銷員欲遍歷所有城市，且每個城市僅能訪問一次，并最后回到起始點(diǎn)，問按照怎樣的城市遍歷順序，路徑長度最短。即搜索子集X={1,2，…，n}（X的元素表示n個城市的編號）的一個排列π（X={v1,v2，…，vn}），使得取最小值。d(vi,vi+1）表示城市vi到城市vi+1的距離。根據(jù)排列組合理論，顯然規(guī)模為N的TSP問題的有效解個數(shù)為N選。隨著N線性增大，有效解搜索空間呈指數(shù)速度增長。由于該問題的典型性，使得快速、有效解決TSP有著重要的理論價值和應(yīng)用價值。求解TSP問題比較成熟的算法有遺傳算法、Hopfiled人工神經(jīng)網(wǎng)絡(luò)、模擬退火等，其中遺傳算法是被認(rèn)為是求解效率較高的一種算法。遺傳算法依照自然界生物進(jìn)化規(guī)律，通過對染色體的選擇、雜交和變異操作來獲取問題空間中的最優(yōu)解或次優(yōu)解。簡單遺傳算法是一種串行算法，適合于對小規(guī)模TSP問題求解。對大規(guī)模TSP問題，則在處理器速度和內(nèi)存大小方面對機(jī)器有極高要求，而現(xiàn)階段計算機(jī)硬件制造技術(shù)尚未達(dá)到該水平，所以利用并行計算代替串行計算便成了一種必然。孤島模型是并行遺傳算法，它的依據(jù)是：自然進(jìn)化過程中總存在大量物種在彼此獨(dú)立的空間向前進(jìn)化，這種在不同空間獨(dú)立進(jìn)化的自然過程，可被抽象為并行演化。孤島模型目前的軟件實(shí)現(xiàn)方式有以下三種：一、在同一并行機(jī)上，多處理器并行計算；二、在單機(jī)上串行模擬；三、在網(wǎng)絡(luò)環(huán)境中，通過TCP/IP協(xié)議，并行計算。由于經(jīng)濟(jì)原因，國內(nèi)多數(shù)大學(xué)或研究部門很缺少并行機(jī)計算環(huán)境。且并行機(jī)上的軟件因?qū)Ｓ冕槍π蕴珡?qiáng)，開發(fā)人員比較少。單機(jī)模擬對TSP問題規(guī)模有局限。用TCP/IP協(xié)議在網(wǎng)絡(luò)上實(shí)現(xiàn)遺傳算法的分布式計算需要約定與實(shí)現(xiàn)通信規(guī)程，設(shè)計開銷大，且軟件互通性差。從軟件可重用性角度來看，使用通用的類和組件開發(fā)是今后分布式計算的發(fā)展潮流?；谝陨系目紤]，以下討論用CORBA分布式求解TSP問題的方法。2采用分布式遺傳統(tǒng)計法求解tsp問題的corba實(shí)現(xiàn)2.1客戶機(jī)/服務(wù)器程序間通信采用CORBA技術(shù)實(shí)現(xiàn)分布式遺傳算法有以下優(yōu)點(diǎn)：（1）利用PC機(jī)組成的計算機(jī)局域網(wǎng)通信速度快，且易實(shí)現(xiàn)分布式并行計算。在局域網(wǎng)環(huán)境中，利用CORBA實(shí)現(xiàn)分布式計算的條件已經(jīng)具備，不增加硬件投資；（2）通信協(xié)議透明性。利用Socket技術(shù)設(shè)計客戶機(jī)/服務(wù)器程序時，需要自己定義和實(shí)現(xiàn)一套通信規(guī)程。而CORBA與Socket技術(shù)相比的優(yōu)勢是：CORBA在TCP層之上，實(shí)現(xiàn)了IIOP協(xié)議。它以O(shè)RB實(shí)現(xiàn)客戶機(jī)與服務(wù)器程序間通信的中間件，ORB尋找適配完成請求工作的對象，并在服務(wù)器對象執(zhí)行操作后返回結(jié)果。由于CORBA對待遠(yuǎn)程調(diào)用就像調(diào)用本地方法一樣，大大簡化了程序設(shè)計工作；（3）硬件無關(guān)性，平臺透明性。CORBA的主要作用是用來屏蔽網(wǎng)絡(luò)硬件的差異性和操作系統(tǒng)的異構(gòu)性，使應(yīng)用軟件能夠比較平滑地運(yùn)行于不同平臺上。同時在平衡負(fù)載、連接管理和調(diào)度方面起著協(xié)調(diào)作用。這種開放性充分利用了現(xiàn)有資源；（4)CORBA代表的軟組件、軟總線是未來程序設(shè)計的發(fā)展趨勢，利用CORBA有利于程序在將來保持長期有效性。2.2應(yīng)用服務(wù)器層圖1示出了利用CORBA實(shí)現(xiàn)分布式遺傳算法求解TSP問題的軟件結(jié)構(gòu)模型。該結(jié)構(gòu)分成三層：第一層是瀏覽器層。用戶通過因特網(wǎng)瀏覽可以訪問該主頁，通過頁面中嵌入的JavaApplet程序，自定義TSP問題的規(guī)模、節(jié)點(diǎn)數(shù)據(jù)，最終能從該程序中得到計算結(jié)果。用戶不必關(guān)心執(zhí)行分布式計算的實(shí)際物理地址和實(shí)現(xiàn)算法；第二層是應(yīng)用服務(wù)器層，應(yīng)用服務(wù)器包括WWW服務(wù)器和TSP問題分布式計算應(yīng)用服務(wù)器。WWW服務(wù)器通過HTTP協(xié)議與用戶端的瀏覽器通信，而TSP問題分布式計算應(yīng)用服務(wù)器在目錄服務(wù)器注冊后，提供CORBA對象接口被瀏覽器中的Applet程序遠(yuǎn)程調(diào)用，二者間通過IIOP協(xié)議進(jìn)行通信。TSP問題分布式計算應(yīng)用服務(wù)器的任務(wù)是發(fā)現(xiàn)現(xiàn)存孤島，并將用戶的計算任務(wù)和計算數(shù)據(jù)發(fā)送給各個孤島，并以松耦合的形式控制多個孤島計算，它自身并不做任何計算操作。由于Java語言的安全性限制，應(yīng)用服務(wù)器中的兩個程序必須運(yùn)行在一臺計算機(jī)中。目錄服務(wù)器是第三方軟件，它主要提供命名服務(wù)，目前在小系統(tǒng)中可以采用JDK中的命名服務(wù)，對大系統(tǒng)可以采用LDAP服務(wù)器；第三層是分布式遺傳算法的實(shí)際計算進(jìn)程。圖1中的每個孤島都代表運(yùn)行在不同計算機(jī)中的遺傳算法的計算進(jìn)程。2.3并行遺傳算法tsp采用CORBA實(shí)現(xiàn)分布式遺傳算法與并行遺傳算法相比較，有以下優(yōu)點(diǎn)：（1）并行機(jī)中各孤島采用的計算方法是一致的，易同時收斂于同一局部最優(yōu)解。而基于網(wǎng)絡(luò)的分布式計算模型中，各個孤島可以采用不同的演化計算方法來對問題求解，各個孤島只要求通信接口一致即可，內(nèi)部的實(shí)現(xiàn)對個孤島對象之間是透明的。不同孤島采用不同的計算方法，甚至是采用神經(jīng)網(wǎng)絡(luò)或模擬退火算法進(jìn)行計算，均可以在本軟件結(jié)構(gòu)中靈活實(shí)現(xiàn)。孤島間的相異性，是對自然進(jìn)化中各孤島有自己不同特色的方式進(jìn)化的成功模擬，從而從自然演化的多態(tài)性，可以映射本最優(yōu)化求解問題中各孤島求解結(jié)果分布的空間多態(tài)性。這對組合優(yōu)化問題求解，避免求解區(qū)間過早收斂于某一局部最優(yōu)區(qū)間是大有幫助的；（2）在并行遺傳算法計算過程中，為了動態(tài)平衡各個孤島間的計算負(fù)載，常采用征兵方式或招募方式。但是二者實(shí)現(xiàn)無論是采用緊耦合還是松耦合，進(jìn)程間都需要一種N2次（如果同時有N個孤島）查詢，時間復(fù)雜度較高。而圖1的三層結(jié)構(gòu)中，繁忙孤島進(jìn)程可以直接去TSP問題分布式計算應(yīng)用服務(wù)器獲取空閑孤島進(jìn)程的ORB引用實(shí)例，然后完成計算負(fù)載的轉(zhuǎn)移。比并行計算中的負(fù)載平衡要易于實(shí)現(xiàn)。3實(shí)驗(yàn)方法和計算3.1實(shí)驗(yàn)程序設(shè)計隨著計算機(jī)網(wǎng)絡(luò)應(yīng)用水平的提高，軟件跨平臺計算能力成為衡量軟件質(zhì)量的一個重要指標(biāo)。C語言是一種高效率的程序設(shè)計語言，目前在集中式遺傳算法計算中采用C++比較多。但C++程序設(shè)計難度較高，且對分布式網(wǎng)絡(luò)計算能力不及Java，所以本次實(shí)驗(yàn)使用Java作為程序設(shè)計語言。Java是目前最為流行的跨平臺計算語言，且能方便地嵌入到HTML頁面中，在網(wǎng)絡(luò)上發(fā)布。因此實(shí)驗(yàn)中選擇JDK1.3作為程序設(shè)計語言。該程序可以真正實(shí)現(xiàn)一次編譯后，在各種裝有Java虛擬機(jī)的操作系統(tǒng)上執(zhí)行，無需修改。實(shí)驗(yàn)中計算的TSP問題是規(guī)模為34的中國旅行商問題CTSP(ChinaTravelingSalesmanProblem),34個城市分別為31個直轄市、省會和自治區(qū)首府，2個特別行政區(qū)（香港、澳門）以及臺北。孤島采用簡單遺傳算法進(jìn)行計算，其具體實(shí)現(xiàn)過程見文獻(xiàn)。雜交算子是部分映射雜交算子，個體適應(yīng)度是環(huán)路長度。雜交父體的選擇使用聯(lián)賽機(jī)制，即每次從群體中隨機(jī)選擇num(num為聯(lián)賽規(guī)模）條染色體，然后將這些個體按適應(yīng)度大小排序，適應(yīng)度最小的兩個作為雜交父體，而最大的兩個則被新生個體替代。實(shí)驗(yàn)中雜交發(fā)生概率置為1，變異發(fā)生概率置為0。本次實(shí)驗(yàn)中存在3個孤島（在3臺計算機(jī)上運(yùn)行），每個孤島每繁衍multiplyNumber/4代就向鄰近島遷移部分個體（multiplyNumber為最大繁衍代數(shù)）。在4次遷移中，遷移目的孤島任意，以保持算法的隨機(jī)性。遷入個體集取代被遷入子群體中適應(yīng)度最差的個體集。3.2遺傳算法比較當(dāng)采用排序遷出式策略，孤島子群體規(guī)模為1200，遷移率為20‰，繁衍代數(shù)為25000時，實(shí)驗(yàn)得到最短回路（路徑長度為15676千米）。該路徑是：合肥--南京--上海--杭州--臺北--福州--南昌--武漢--長沙--廣州--澳門--香港--?？?-南寧--昆明--貴陽--重慶--成都--拉薩--烏魯木齊--西寧--蘭州--銀川--呼和浩特--哈爾濱--長春--沈陽--北京--天津--濟(jì)南--石家莊--太原--西安--鄭州--合肥與該遺傳算法的集中式計算結(jié)果（15704千米）相比較，環(huán)路長度縮短28千米。由于關(guān)于34點(diǎn)CTSP問題的計算結(jié)果不多，于是從該環(huán)路中除去香港、澳門、重慶三個城市，再將回路長度與31點(diǎn)CTSP問題的最短路徑作比較。用遺傳算法得到的最優(yōu)解比用Hopfield神經(jīng)網(wǎng)絡(luò)求出的全局最優(yōu)解15449千米長度少32千米；但比文獻(xiàn)中的最優(yōu)解15404千米略差。對比來看，該結(jié)果是很不錯的。關(guān)于算法求解的最優(yōu)性測試在論文第5部分有詳細(xì)的驗(yàn)證。4試驗(yàn)中顯示的三個規(guī)律4.1未算例sagct調(diào)查問卷的統(tǒng)計描述分布式遺傳算法的個體遷移有多種策略。實(shí)驗(yàn)中比較了“最優(yōu)遷移策略”和“隨機(jī)遷移策略”對計算結(jié)果的影響程度。“最優(yōu)遷移策略”BM(BestMigration）從孤島的整個群體中選擇最優(yōu)個體集遷移給目標(biāo)孤島，遷移前需要對整個群體的個體適應(yīng)度排序；在“隨機(jī)遷移策略”RM(RandomMigration）中，隨機(jī)選擇個體集遷移。有資料表明隨機(jī)選擇所產(chǎn)生的效果至少不比其它任何方法差。為了驗(yàn)證該規(guī)律，于是對各群體規(guī)模做50次計算，然后從中挑選回路長度最小的30項作為有效統(tǒng)計項，求其算術(shù)平均值。使用這種統(tǒng)計方法的原因是遺傳算法具有隨機(jī)性，用均值比較，更利于反映普遍性規(guī)律。圖2、圖3示出了在子群體規(guī)模（subP）為1200、1500時，隨遷移率MR(MigrationRate）的變化，BM策略和RM策略的解質(zhì)量。從圖中可以看出BM策略與RM策略解質(zhì)量相當(dāng)，總體走勢與解分布比較一致，但BM策略在最優(yōu)解上比RM策略稍勝一籌。BM在遷出前必須對整個子群體的適應(yīng)度排序，排序算法最佳的平均時間為O(nlogn），開銷是很大的；而采用RM無需排序，時間花費(fèi)很小，且所得到的解并無太大懸殊，尚可以接受。所以在實(shí)際應(yīng)用中應(yīng)視具體情況采用不同的策略，當(dāng)遷移頻率較高時可選擇RM，當(dāng)遷移頻率較低時可選擇BM。論文中的以下實(shí)驗(yàn)均使用RM策略。4.2子群體規(guī)模司bp測試遷移率即一個孤島向其它孤島遷移的個體數(shù)占其整個子群體規(guī)模的比例。這個比例既不能太低，也不能太高。太低的遷移率對鄰近孤島的影響甚微，不足以改變現(xiàn)狀；而太高的遷移率不僅使得通信開銷增大，還可能使群體中的個體失去多樣性，不利于最優(yōu)解的產(chǎn)生。作者對遷移率為5‰、10‰、15‰、20‰、25‰，子群體規(guī)模（subP）為1200、1500、1800、2100的參數(shù)組合進(jìn)行了測試，如圖4、圖5所示。結(jié)果表明遷移率在20‰附近易求得最優(yōu)解。解分布并不嚴(yán)格遵守此規(guī)律，在相鄰的遷移率有反復(fù)，這正體現(xiàn)了遺傳算法求解的隨機(jī)性。4.3衍代的生物量和時間在尋求最優(yōu)解的過程中，實(shí)驗(yàn)中首先設(shè)置的繁衍代數(shù)是5000，但計算后發(fā)現(xiàn)結(jié)果不盡人意，于是以5000為步長，保持其它參數(shù)不變，將繁衍代數(shù)逐漸增大到35000。繁衍代數(shù)在達(dá)到一定的值以后，解趨于穩(wěn)定。達(dá)到平衡后，就需要其它環(huán)境中的優(yōu)秀個體突破地理限制，遷移進(jìn)來以幫助其改善后代，跳出局部最優(yōu)，達(dá)到全局最優(yōu)。所以，繁衍代數(shù)并不是多多益善，繁衍代數(shù)越大、時間花費(fèi)越多，它只要達(dá)到了求解要求即可。圖6、圖7示出了繁衍代數(shù)RG(ReproductionGeneration）在15000、20000、25000、30000、35000，子群體規(guī)模為1200和1500，遷移率為20‰時的解質(zhì)量情況。5設(shè)置幾何節(jié)點(diǎn)分布由于當(dāng)前沒有其它數(shù)據(jù)可以直接驗(yàn)證分布式遺傳算法解TSP問題的有效性和評估求解質(zhì)量，作者設(shè)計了三組標(biāo)準(zhǔn)幾何分布數(shù)據(jù)，對上述的分布式遺傳算法和參數(shù)設(shè)置規(guī)律加以驗(yàn)證。這三組數(shù)據(jù)分別是100×50的矩形邊界上30等分點(diǎn)的坐標(biāo)、100×100的正方形邊界上40等分點(diǎn)的坐標(biāo)和直徑為100的圓邊界上35等分點(diǎn)的坐標(biāo)，節(jié)點(diǎn)分布如圖8所示。選擇這3組數(shù)據(jù)進(jìn)行驗(yàn)證是基于兩點(diǎn)考慮：（1）這些幾何圖形很容易證明沿其邊界順序連接各點(diǎn)得到的回路長度最短；（2）驗(yàn)證遺傳算法求解與拓?fù)浣Y(jié)構(gòu)無關(guān)。實(shí)驗(yàn)結(jié)果如表1所示。以上數(shù)據(jù)表明實(shí)驗(yàn)規(guī)律對于N=35左右的TSP問題是適用的，而且遺傳算法求解確實(shí)與拓?fù)浣Y(jié)構(gòu)無關(guān)。6實(shí)驗(yàn)結(jié)果及反思論文提出了基于CORBA的分布式遺傳算法模型，它是求解大規(guī)模NP問題的一種有效途徑。作者利用Java語言，在計算機(jī)局域網(wǎng)環(huán)境中實(shí)現(xiàn)了該軟件模型，并通過該算法對CTSP問題求解，發(fā)現(xiàn)了其中關(guān)于孤島計算參數(shù)設(shè)置與最優(yōu)解影響的三組實(shí)驗(yàn)規(guī)律。由于從理論上分析該算法有一定困難，作者設(shè)計了多組數(shù)據(jù)來驗(yàn)證其有效性、求解