求解大規(guī)模結(jié)構(gòu)樹問題的改進(jìn)算法

求解大規(guī)模結(jié)構(gòu)樹問題的改進(jìn)算法

這是一個(gè)困難的問題，通常用于通信網(wǎng)絡(luò)、能源網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)和大型網(wǎng)絡(luò)。長期以來，它引起了國內(nèi)外許多科學(xué)家的關(guān)注。這是第一個(gè)擴(kuò)展點(diǎn)限制的問題。該算法可以接受小型dhst問題的最佳解。cacerta等人提出了一種解決方案，該算法可以擴(kuò)展到3dmst問題的最佳解。在這項(xiàng)算法的支持下，anderson等人提出了一種基于二元分解信息的lagrangian算法。在模型分類和切割算法的基礎(chǔ)上，belk和其他人提出了基于二元分解信息的lagrangian算法?；跇?biāo)準(zhǔn)分支和切割算法，belk和其他人提出了基于二元分解信息的lagrangian算法。基于標(biāo)準(zhǔn)分支和切割算法，belk和其他人提出了優(yōu)先分支和交叉算法的問題。近年來，許多科學(xué)家研究并應(yīng)用了以遺傳算法和免疫算法為代表的未來計(jì)算方法。其中一些科學(xué)家利用遺傳算法和免疫算法進(jìn)行了驗(yàn)證，并在3dmst問題的解決中提出了解決方案。在本文中，需要使用pruzer計(jì)數(shù)來表示生成樹的編程方法。由薄邊效應(yīng)等人設(shè)計(jì)的算法動(dòng)態(tài)表結(jié)構(gòu)的方法是最好的分解，其中六個(gè)邊灘邊的重量信息由小邊距的數(shù)據(jù)獲得。對于在最優(yōu)解中生成的樹的構(gòu)建方法，拓格倫等人使用了最小邊界值的統(tǒng)計(jì)方法。對于在最優(yōu)解中生成的字段信息，估計(jì)節(jié)點(diǎn)數(shù)為20.1的dcmst問題的權(quán)重及其最優(yōu)解的概率公式，并將其用作執(zhí)行突變操作的依據(jù)（1.1）。各種各樣的算法都可以通過子圖邊緣的節(jié)點(diǎn)來構(gòu)建。不同的DCMST問題可分為兩大類,即non-EuclideanDCMST和EuclideanDCMST完全圖問題.對這兩大類約束最小生成樹問題求解的復(fù)雜性,不同的文獻(xiàn)有不同的看法.多數(shù)文獻(xiàn)作者認(rèn)為,按均勻隨機(jī)方式產(chǎn)生的non-Euclidean問題要比Euclidean問題的求解更為復(fù)雜;與之相反,文獻(xiàn)的作者傾向Euclidean問題的求解更具有挑戰(zhàn)性.通過大量的實(shí)驗(yàn)測試及分析,我們認(rèn)為,以均勻隨機(jī)方法生成non-Euclidean圖例的DCMST問題具有更大的變化性和多樣性,使得這類問題解的結(jié)構(gòu)及求解的難易性具有更大的變化性.一方面,這類問題的Prim解對應(yīng)的度值通常大于5,且在度為3時(shí)問題的最好解與Prim算法解的比值隨不同的問題或分布范圍有所不同.一些文獻(xiàn)證實(shí),Euclidean圖例的DCMST問題對應(yīng)Prim解的度最大為5,且在度值為3或4時(shí)最好解與Prim算法解的比值在一定的范圍內(nèi).當(dāng)度為3時(shí),該指標(biāo)的界限值在不同的文獻(xiàn)分別為5/3,1.5和1.402.文獻(xiàn)作者猜測性地認(rèn)為,該指標(biāo)界限值能進(jìn)一步減小到1.103.另一方面,對均勻隨機(jī)方式產(chǎn)生分布在某一區(qū)間的non-Euclidean問題,隨著結(jié)點(diǎn)數(shù)增加,其解的復(fù)雜度逐漸降低.主要表現(xiàn)在:當(dāng)結(jié)點(diǎn)數(shù)增大到某一值后,該類問題不再是一個(gè)難求的NP-hard問題,較多情形下能以幾乎1的概率構(gòu)造出一棵度值為3的最小生成樹,使其與Prim算法得到的無約束生成樹(對應(yīng)的度值一般大于10)具有相同目標(biāo)值.通過反復(fù)的編程測試及對存在問題的分析,我們發(fā)展了基于度排列的編碼方法,通過利用度維關(guān)系,不需經(jīng)過完全解碼就能求出及利用待考察結(jié)點(diǎn)的關(guān)聯(lián)結(jié)點(diǎn)及構(gòu)成邊的權(quán)重信息;結(jié)合花草果樹的人工種植和培育技術(shù),提出一種帶有嫁接及剪接算子的遺傳算法(ageneticalgorithmwithgraftingandpruningoperators,簡稱GPOGA).通過將該算法用于對DCMST問題進(jìn)行求解,與現(xiàn)有文獻(xiàn)提供的實(shí)驗(yàn)數(shù)據(jù)的對比說明,本文算法在得到最好解精度以及算法的諸多性能指標(biāo)均有很大提高.1dcmst的數(shù)學(xué)模型假設(shè)G=(V,E)為網(wǎng)圖,其中:V={v1,v2,…,vn}是結(jié)點(diǎn)的有限集合,n=|V|為結(jié)點(diǎn)總數(shù);E={e1,e2,…,em}是G中邊的集合,m為邊的總數(shù).設(shè)S={v1′,…,vi′,…,vt′|vi′∈V}?V且|S|≥1;設(shè)T為圖G的所有滿足度約束的生成樹的集合因此,對DCMST問題求解就是尋找G的一棵生成樹,這里用一個(gè)向量x表示,x∈T,使其滿足給定的度約束并使對應(yīng)邊權(quán)重wij(一般指邊長或費(fèi)用,本文以下均指邊長)之和為最小值.DCMST的數(shù)學(xué)模型可描述如下:上述數(shù)學(xué)模型由DCMST問題的優(yōu)化目標(biāo)函數(shù)及約束構(gòu)成,其中:第1個(gè)約束為生成樹包含不同結(jié)點(diǎn)的n-1條邊;第2個(gè)約束為每個(gè)結(jié)點(diǎn)應(yīng)滿足的度約束條件,dc為給定的度約束值;第3個(gè)約束表示生成樹無環(huán)路;第4個(gè)約束為所有結(jié)點(diǎn)的度值和;第5個(gè)約束當(dāng)xij=1時(shí),由結(jié)點(diǎn)<vi,vj>構(gòu)成的邊是生成樹的一條邊.2pgoga算法系統(tǒng)2.1調(diào)整算子的作用在對與排序或路徑長度有關(guān)的組合優(yōu)化問題的求解中,廣泛使用一項(xiàng)被稱為鄰域搜索(localsearch)的策略.其基本思想是,在算子的搜索過程中,應(yīng)充分利用相鄰結(jié)點(diǎn)的路徑長度信息,使結(jié)點(diǎn)或邊交換后的收益最大.文獻(xiàn)指出,鄰域搜索為獲取NP-hard問題的高精度解提供一種有效和可靠的途徑.在類似問題的求解中鄰域搜索策略成為檢驗(yàn)一個(gè)算子或算法是否具有高效性的基本前提.但應(yīng)看到,它的基本出發(fā)點(diǎn)是利用一種貪婪思想,極有可能加速算法陷入局部最優(yōu).文獻(xiàn)的作者也指出,在對DCMST問題的求解中,較小權(quán)重的邊以較大的概率被選取參與變異操作很可能使算法以更大的概率陷入局部最優(yōu).我們發(fā)現(xiàn),當(dāng)使用localsearch策略使算法陷入局部最優(yōu)或消除非正常態(tài)時(shí),一般會(huì)出現(xiàn)一種稱為沖突的現(xiàn)象.而對沖突的檢測和處理,成為本文算法要解決的一個(gè)關(guān)鍵問題.因此,從算子的作用看,如果將帶localsearch的算子歸結(jié)為一種加速算子,則算法應(yīng)包含另一種算子,本文稱它為調(diào)整算子.其作用是雙重的:一方面,它對出現(xiàn)的非正常態(tài)進(jìn)行及時(shí)處理,使得當(dāng)算法陷入局部最優(yōu)時(shí),能對這種情形進(jìn)行有效的檢測,并使其以較大的幾率跳出;另一方面,它同樣包含localsearch使算子的搜索具有更高的效率.為便于敘述,以下先給出與本文算法相關(guān)的幾個(gè)概念.本文所指的樹(生成樹)是指一棵非空樹(n>1,除根結(jié)點(diǎn)之外的元素被分為m(m>0)個(gè)不相交的集合T1,T2,…Tm,其中每一個(gè)集合Ti(1≤i≤m)又是一棵樹,稱為根結(jié)點(diǎn)的子樹,文中稱每棵子樹為樹的一條分支.在本文算法的嫁接和剪接操作中,當(dāng)樹發(fā)生變化時(shí),指以待考察結(jié)點(diǎn)為根結(jié)點(diǎn)的整條分支的移動(dòng).定義1(收益和代價(jià)).對一棵(生成)樹T1,若將某結(jié)點(diǎn)的一條分枝移至另一結(jié)點(diǎn)作為其一條分枝后產(chǎn)生的生成樹為T2,考察分枝移動(dòng)前后生成樹的邊長和的變化,則定義收益(gain)和代價(jià)(cost)分別為公式(2)與公式(3)中,x1ij∈T1,x2ij∈T2.定義2(嫁接).從(生成)樹中選取具有某種優(yōu)良特性的分枝(嫁接枝)接入到待考察結(jié)點(diǎn)中,以形成更好生成樹個(gè)體(指收益大于0)的過程稱為嫁接.定義3(剪接).將(生成)樹中的某一分枝(剪接枝)接入到另一位置,以形成可行個(gè)體或更好生成樹的過程稱為剪接.2.2嫁接算子和策略2.2.1父內(nèi)部控制算法嫁接算子操作可分為兩步:1)根據(jù)結(jié)點(diǎn)及其關(guān)聯(lián)結(jié)點(diǎn)的邊長信息,選擇具有優(yōu)良品質(zhì)的嫁接枝;2)將選擇的嫁接枝重新接入,以形成更好的生成樹個(gè)體,即嫁接后收益大于0.如何選取具有優(yōu)良品質(zhì)的嫁接枝,是嫁接操作的關(guān)鍵所在.要選取一條有效的嫁接枝,需解決以下兩個(gè)關(guān)鍵問題:1)有效利用邊結(jié)點(diǎn)及其關(guān)聯(lián)結(jié)點(diǎn)的邊長信息.為了使嫁接及剪接操作更為有效,對各結(jié)點(diǎn)按其關(guān)聯(lián)結(jié)點(diǎn)構(gòu)成邊的長度進(jìn)行排序,并將排序結(jié)果保存在指針變量pnodesortdis中.2)求任意結(jié)點(diǎn)的父結(jié)點(diǎn)及子結(jié)點(diǎn)關(guān)系本文采用基于度的排列的編碼方法,有關(guān)編碼方法見文獻(xiàn).為此,設(shè)計(jì)了通過利用度維關(guān)系查找某一結(jié)點(diǎn)的父結(jié)點(diǎn)函數(shù)FindPareNode(par1,par2)及其子結(jié)點(diǎn)的函數(shù)FindChildNode(par1,par2),par1,par2為算法所需參數(shù),它們在較好情形下的時(shí)間復(fù)雜度均為O(1),在最壞情形下的時(shí)間復(fù)雜度為O(n).FindPareNode的基本思想是,從當(dāng)前位置向前掃描,記錄掃描過的結(jié)點(diǎn)的度值,根據(jù)掃描過的結(jié)點(diǎn)與度值的關(guān)系計(jì)算出其父結(jié)點(diǎn)位置,其偽碼描述如下:算法1(檢索某一結(jié)點(diǎn)位置nodepos的父結(jié)點(diǎn)位置parvpos算法).按收益優(yōu)先及度約束控制嫁接策略執(zhí)行嫁接操作,算法的偽碼描述如下:算法2(嫁接算法).2.2.2嫁接策略為使嫁接操作能夠處理不同情形的DCMST問題,本文提出以下幾種嫁接策略,它們分別是:1嫁接枝的選擇對考察結(jié)點(diǎn),若所選關(guān)聯(lián)結(jié)點(diǎn)分枝移至考察結(jié)點(diǎn)前后收益大于0,則該分枝可選為嫁接枝.按該策略執(zhí)行嫁接,操作簡便,且總體效果較好.其缺點(diǎn)是,嫁接后某些結(jié)點(diǎn)的分枝數(shù)可能大大超過給定的度約束值,從而增加剪接的負(fù)擔(dān).2prim算法對考察結(jié)點(diǎn),選取與其具有最小邊長的關(guān)聯(lián)結(jié)點(diǎn)作為嫁接枝.按該策略執(zhí)行嫁接,在理想的情形下,通過該策略可生成一棵無度約束的最小生成樹.其缺點(diǎn)主要有:1)針對給定某一度約束值dc,若通過Prim算法得到的無約束生成樹對應(yīng)的度值與dc相差較大,該控制策略往往不能取得好的效果;2)增加算法陷入局部最優(yōu)解的概率.32引入策略對考察結(jié)點(diǎn)新加入的分枝進(jìn)行控制,一般不超過給定的度約束值dc.按該策略執(zhí)行嫁接,可使嫁接后的生成樹基本滿足度約束要求.4順序關(guān)系信息對考察結(jié)點(diǎn),在判斷某一結(jié)點(diǎn)代表的分枝是否作為嫁接枝時(shí),應(yīng)將邊長信息(決定收益)和位置次序關(guān)系信息(決定優(yōu)先關(guān)系)同時(shí)進(jìn)行分析.也就是說,某一結(jié)點(diǎn)代表的分枝移動(dòng)到考察結(jié)點(diǎn)后,即使收益不如其他的分枝但考慮其位置次序關(guān)系,應(yīng)優(yōu)先將該分枝選為嫁接枝.由于在嫁接中需要同時(shí)考察邊長及位置次序關(guān)系,如果處理恰當(dāng),則可有效提高算法的求解精度和收斂速度.5關(guān)聯(lián)采用約束的工藝文獻(xiàn)給出了當(dāng)最大結(jié)點(diǎn)數(shù)為100時(shí),第r條邊選擇的概率值近似為,n為結(jié)點(diǎn)數(shù),r(1≤r≤m)為按邊長排序分配的序號(hào),m為邊的總數(shù).考慮到本文算法中嫁接算子的作用與文獻(xiàn)變異算子作用的差異,本文的處理方法是按邊長排序:針對每一結(jié)點(diǎn)的邊長信息設(shè)定一個(gè)閾值,當(dāng)邊長大于或等于該閾值時(shí),其分配概率為0;當(dāng)邊長小于給定的閾值時(shí),按邊長或以邊長排列分配位置次序,然后分別計(jì)算關(guān)聯(lián)結(jié)點(diǎn)代表的分枝對應(yīng)的概率值.以下分別對它們的概率進(jìn)行分析.當(dāng)按邊長分配概率時(shí),對考察結(jié)點(diǎn)i=1,2,…,n,設(shè)給定的閾值為ri,設(shè)與i關(guān)聯(lián)的某一結(jié)點(diǎn)j構(gòu)成的邊長為len(i,j),定義len(i,j)與ri的距離dis(len(i,j),ri)為因此,結(jié)點(diǎn)j代表的分枝的選擇概率為當(dāng)按以邊長排列分配位置次序時(shí),對考察結(jié)點(diǎn)i=1,2,…,n,設(shè)給定的閾值為ri.由公式(4),計(jì)算出與i關(guān)聯(lián)的結(jié)點(diǎn)j構(gòu)成的邊長為len(i,j)與ri的距離dis(len(i,j),ri),對dis(len(i,j),ri)按遞減排序,以確定與i關(guān)聯(lián)的結(jié)點(diǎn)j構(gòu)成的邊的位置次序rank(i,j),分別對它們分配1,2,…,m值.則結(jié)點(diǎn)j代表的分枝的選擇概率為公式(5)和公式(6)中,j=1,2,…,n且j≠i.在上述策略中,策略1)~策略4)屬于穩(wěn)定控制策略,策略5)屬于非穩(wěn)定控制策略.在算法設(shè)計(jì)中,嫁接操作在一般情形采用上述策略1)和策略3)就能取得較好的效果;當(dāng)求解一些復(fù)雜及特殊情形的DCMST問題,選擇交替使用策略2)、策略4)或策略5).2.3剪切算子和策略2.3.1佳關(guān)聯(lián)控制—剪接算子構(gòu)造嫁接時(shí)產(chǎn)生的生成樹可能包含某些結(jié)點(diǎn)不滿足度約束以及具有較差屬性分枝的情形,均要進(jìn)行剪接操作.判斷一條分枝是否在當(dāng)前位置具有最(較)差屬性的依據(jù)為下列兩種情形之一:1)若該分枝移動(dòng)到另一關(guān)聯(lián)結(jié)點(diǎn)的收益最(較)大;2)若所有考察的分枝分別移動(dòng)收益均小于0,則指移動(dòng)后代價(jià)最小的分枝.算法3以一棵生成樹子結(jié)點(diǎn)分枝進(jìn)行修剪為例說明剪接操作的程序流程,算法的偽碼描述如下:算法3(剪接算法).在剪接過程中,可能遇到的一個(gè)關(guān)鍵問題是沖突.在圖1和圖2的示例中,不失一般性,假定給定度約束值為3.由于序號(hào)為6的結(jié)點(diǎn)有4條分枝,必須剪去結(jié)點(diǎn)6的一條分枝.假定已檢測到結(jié)點(diǎn)7代表的分枝具有最差的屬性,而結(jié)點(diǎn)7與除結(jié)點(diǎn)6以外的最佳關(guān)聯(lián)結(jié)點(diǎn)是結(jié)點(diǎn)3,那么將結(jié)點(diǎn)7代表的分枝插入到結(jié)點(diǎn)3之后就可以.這一插入過程未引起新的不滿足度約束的情形,即不會(huì)引起沖突,其操作如圖1所示.但是,如果結(jié)點(diǎn)7與除結(jié)點(diǎn)6之外只與結(jié)點(diǎn)4結(jié)合具有最好的特性,這時(shí)將引起新的沖突,因?yàn)榻Y(jié)點(diǎn)4已有3條分枝,不能再插入新的分枝,否則引起新的不滿足約束的情形發(fā)生,此時(shí)稱插入后引起了新的沖突.其操作如圖2所示.定義4(沖突及沖突檢測).在對消除不滿足約束情形進(jìn)行剪接或?qū)哂休^差屬性的分枝進(jìn)行剪接操作,若引起新的不滿足約束的情形稱為沖突;將發(fā)現(xiàn)這一沖突現(xiàn)象的過程稱為沖突檢測.定義5(沖突解決).1)當(dāng)沖突出現(xiàn)時(shí),若沖突能在遍歷一個(gè)或若干個(gè)結(jié)點(diǎn)后按收益最大化原則完全解決,稱沖突能在與問題規(guī)模無關(guān)的常數(shù)內(nèi)解決,此時(shí)沖突解決的時(shí)間復(fù)雜度為O(1).2)當(dāng)沖突出現(xiàn)時(shí),若沖突能在遍歷所有結(jié)點(diǎn)分枝后可按收益最大化原則完全解決,稱沖突能在與問題規(guī)模相關(guān)的線性關(guān)系內(nèi)解決,此時(shí)沖突解決的最壞時(shí)間復(fù)雜度為O(n).3)當(dāng)沖突出現(xiàn)時(shí),若沖突在遍歷所有結(jié)點(diǎn)后仍無法按收益最大化原則完全解決,稱沖突只能在與問題規(guī)模相關(guān)的非線性關(guān)系內(nèi)解決,此時(shí)沖突解決的時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間或指數(shù)時(shí)間.由定義5可知,當(dāng)沖突出現(xiàn)時(shí),若沖突能在O(1)和O(n)時(shí)間內(nèi)解決,稱沖突能完全解決.盡管沖突的多項(xiàng)式時(shí)間解決和指數(shù)時(shí)間解決有很大的區(qū)別,但沖突的多項(xiàng)式時(shí)間解決的循環(huán)遞歸將導(dǎo)致沖突的指數(shù)時(shí)間解決情形出現(xiàn),為簡化處理過程,稱這兩種情形為沖突不能完全解決.定義6(沖突的簡化解決).當(dāng)沖突出現(xiàn)時(shí),按收益較大化或代價(jià)較小化原則尋求在至多與問題規(guī)模相關(guān)的線性關(guān)系時(shí)間內(nèi)解決該沖突的過程,稱為沖突的簡化解決.定義7(沖突的有效解決).當(dāng)沖突出現(xiàn)時(shí),按收益較大化原則尋求在至多與問題規(guī)模相關(guān)的線性關(guān)系時(shí)間內(nèi)解決該沖突的過程,稱為沖突的有效解決.定義8(沖突的退化解決).當(dāng)沖突出現(xiàn)時(shí),按代價(jià)最(較)小化的原則尋求在至多與問題規(guī)模相關(guān)的線性關(guān)系時(shí)間內(nèi)解決該沖突的過程,稱為沖突的退化解決.在沖突的解決過程中,使用了一種向前搜索的機(jī)制,這種機(jī)制能對已確定的邊在考慮沖突存在及沖突解決中根據(jù)收益和代價(jià)進(jìn)行重新評價(jià),以確定相應(yīng)的沖突解決方案.2.3.2剪切策略在剪接過程中,由于某些策略與嫁接策略的思想類似,因而對它們僅作簡要說明,分別如下:12優(yōu)先考慮策略對考察結(jié)點(diǎn)的所有分枝,若所選分枝移至另一結(jié)點(diǎn)位置后收益大于0且未引起不能有效解決的沖突,則該分枝可選為剪接枝,執(zhí)行剪接操作.22雙重信息篩選策略對考察結(jié)點(diǎn)的所有分枝,在判斷某一分枝是否作為剪接枝時(shí),應(yīng)將邊長信息和位置次序關(guān)系信息同時(shí)進(jìn)行分析.33減少策略當(dāng)不滿足度約束時(shí),若在剪接中出現(xiàn)不能有效解決的沖突,只能按代價(jià)最(較)小化原則進(jìn)行剪接.2.4基于適應(yīng)值概率的轉(zhuǎn)盤式選擇策略在基本遺傳算法體系的基礎(chǔ)上,結(jié)合嫁接和剪接算子,形成GPOGA算法,其偽碼描述如下:算法4(GPOGA).在算法中采用的選擇策略稱為(μ+λ+λ),即將隨機(jī)選擇的兩個(gè)父個(gè)體、由基本遺傳算子——雜交及變異后產(chǎn)生的新個(gè)體及經(jīng)嫁接和剪接后產(chǎn)生的新個(gè)體共同參與競爭,以選擇兩個(gè)較好的個(gè)體進(jìn)入下一代種群空間.上述算法,根據(jù)情形也可采用基于適應(yīng)值概率的轉(zhuǎn)盤式選擇策略.3算法分析3.1嫁接和剪接算法的局部最優(yōu)性分析本文算法中,若考慮遺傳算子的作用及精英選擇策略,則算法是以概率1收斂到所求問題的最優(yōu)解.單獨(dú)從嫁接和剪接算子的作用來看,它們只是在一定程度上加速或減緩算法的收斂速度.考慮其綜合效果嫁接和剪接操作只能是加速算法的收斂速度,否則,得到的解被原有父個(gè)體替換而被拋棄.因此,本文算法以概率1收斂到問題的全局最優(yōu)解.詳細(xì)的證明過程可參考文獻(xiàn)的有關(guān)定理和結(jié)論.在對DCMST問題求解時(shí),由于嫁接和剪接算子均使用localsearch策略以及嫁接和剪接策略的差異,它們在一定程度上可能使算法陷于局部最優(yōu);當(dāng)陷于局部最優(yōu)時(shí),要跳出這種狀態(tài)一般會(huì)出現(xiàn)沖突,本算法可以有效檢測沖突,并提出了若干有效的解決方法.綜合考慮本文算法各遺傳算子的作用,與沒有加入嫁接和剪接算子的情形相比,算法具有更強(qiáng)的尋優(yōu)能力,同時(shí)算法獲得問題最好解的概率增大.3.2算法的最壞計(jì)算復(fù)雜度該算法每一代計(jì)算主要由雜交、變異、嫁接、剪接及評價(jià)5部分組成.假定結(jié)點(diǎn)數(shù)大小為n,種群規(guī)模為N,度約束值為dc,則雜交操作的時(shí)間復(fù)雜度為O(N×n2),變異操作的時(shí)間復(fù)雜度為O(N×n2),嫁接操作的最壞時(shí)間復(fù)雜度為O(N×n3).而在剪接操作中,考慮到樹、回溯和沖突解決的最壞情形,其最壞時(shí)間復(fù)雜度為O(N×(n×(n-1-dc)×n×n)),而評價(jià)的時(shí)間復(fù)雜度為O(N×n×dc),因此在一代運(yùn)算中,算法的最差時(shí)間復(fù)雜度為在本文所討論的結(jié)點(diǎn)規(guī)模范圍內(nèi),N的取值與n無關(guān),度約束值dc一般為常數(shù)3,因此,通過對測試用例計(jì)算時(shí)間的曲線擬合及分析,可得出本文算法的平均時(shí)間復(fù)雜度為O(na),2.5<a<3.0.我們認(rèn)為,在算法中由于增加嫁接和剪接算子操作,雖然算法的最壞計(jì)算復(fù)雜度理論值可達(dá)O(n4).但這一過程沒有破壞模式定理和隱含并行性定理,上述兩定理在本文算法中的基本遺傳算子(雜交與變異算子)及新算子中均發(fā)揮作用.所不同的是,由于增加了知識(shí)的作用及沖突的解決,使得新算子由一種近似隨機(jī)的搜索變成一種在知識(shí)指導(dǎo)下按一定方向進(jìn)行的搜索.另一方面,評價(jià)算法性能的一個(gè)重要指標(biāo)是評價(jià)次數(shù),通過對non-Euclidean和Euclidean兩大類測試問題的實(shí)驗(yàn)分析,本文算法在得到所求問題相同解精度解的評價(jià)次數(shù)均遠(yuǎn)低于相關(guān)文獻(xiàn)給出的數(shù)據(jù).即使考慮在一代中計(jì)算代價(jià)(或計(jì)算時(shí)間)的增加量,本文算法對所求問題的求解精度和收斂速度方面都有較大提高.4計(jì)算模型的評價(jià)為了驗(yàn)證本文所提算法GPOGA在求解DCMST問題的有效性和正確性,我們在VC環(huán)境下采用C/C++編程,某些圖形曲線根據(jù)計(jì)算數(shù)據(jù)由Matlab繪制輸出.在對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行比較和分析時(shí),本文采用以下幾個(gè)指標(biāo)作為對通過算法得到所求DCMST問題的最好解的精度和算法的性能進(jìn)行評價(jià)的依據(jù),它們分別是:評價(jià)(次)數(shù)(evalutions);最好解偏差(best-gap);平均最好解偏差(average-bestgap).首先,我們對一個(gè)經(jīng)典的9結(jié)點(diǎn)完全圖DCMST問題進(jìn)行求解,該問題在度為3時(shí)的最好解為2256.遺傳操作基本參數(shù)設(shè)置與對比文獻(xiàn)所給參數(shù)設(shè)置基本相同.為避免隨機(jī)性影響,我們進(jìn)行了1000輪測試.得到的實(shí)驗(yàn)結(jié)果為:在度約束為3時(shí)的最好解為2256,最小收斂代數(shù)為1,最大收斂代數(shù)為5,平均收斂代數(shù)為1.52算法在1000輪測試中均收斂到2256,即算法得到該問題最優(yōu)解的概率為100%.這一測試結(jié)果,無論從算法的收斂速度還是算法收斂到最優(yōu)解的概率均優(yōu)于相關(guān)文獻(xiàn)提供的實(shí)驗(yàn)數(shù)據(jù).4.1實(shí)驗(yàn)數(shù)據(jù)及分析我們參照有關(guān)文獻(xiàn)所提方法設(shè)計(jì)了一個(gè)專用的隨機(jī)數(shù)生成器,該生成器按均勻隨機(jī)方式產(chǎn)生之間整數(shù)作為生成non-Euclidean測試用例圖的邊長.在本文的測試實(shí)驗(yàn)中,GPOGA算法的基本參數(shù)設(shè)置相同,只是針對不同的測試問題,最大計(jì)算代數(shù)和計(jì)算輪數(shù)依不同問題有所不同.其基本參數(shù)設(shè)置為:種群大小N為100,交叉概率pc為0.4,變異概率pm為0.2,嫁接及剪切概率pg,pp分別為1.測試問題按上述方法生成結(jié)點(diǎn)規(guī)模為50~500之間、間隔為50的non-Euclidean圖例.對結(jié)點(diǎn)數(shù)為50~250最大計(jì)算代數(shù)max(gen)為100;當(dāng)結(jié)點(diǎn)為300及以上時(shí),max(gen)為20.計(jì)算輪數(shù)max(run)為10.表1為利用GPOGA求解按均勻隨機(jī)方式生成結(jié)點(diǎn)數(shù)為50~500的non-Euclidean圖例問題在度約束值為3時(shí)的實(shí)驗(yàn)數(shù)據(jù).表1中不帶*時(shí)間是當(dāng)結(jié)點(diǎn)數(shù)為50~250程序運(yùn)行所需時(shí)間;帶*是結(jié)點(diǎn)數(shù)為300~500所對應(yīng)的運(yùn)行時(shí)間.表2為GPOGA求解上述測試問題在各種度約束時(shí)的實(shí)驗(yàn)數(shù)據(jù),若當(dāng)度約束為某一值時(shí)已得到與Prim算法得到的解相同,則不再計(jì)算度約束為其他值的情形.對non-EuclideanDCMST問題的實(shí)驗(yàn)數(shù)據(jù)說明及對比分析如下:1)在對結(jié)點(diǎn)數(shù)為50~250的測試問題中,由本文算法得到的最好解偏差最大值為1.97%,最小值為0.08%其平均最好解偏差最大值為2.05%,最小值為0.19%.在與同類或類似文獻(xiàn)提供具有可比性實(shí)驗(yàn)的數(shù)據(jù)對比表明,由本文算法得到的實(shí)驗(yàn)數(shù)據(jù)在所求解問題最好解的精度和算法的收斂速度上均有一定的優(yōu)勢.2)對結(jié)點(diǎn)數(shù)為400及以上的情形,隨機(jī)生成了間隔為20的若干組non-Euclidean圖例,經(jīng)過反復(fù)測試表明實(shí)驗(yàn)結(jié)果表明:隨機(jī)生成non-Euclidean圖例問題由Prim算法得到的無約束時(shí)最佳解對應(yīng)的度值一般在10及10以上,本文算法總能找到度約束為3時(shí)的一棵最好生成樹,它對應(yīng)的目標(biāo)值與通過Prim算法計(jì)算得到的值相等.主要原因是:(1)按上述均勻隨機(jī)產(chǎn)生分布于之間的整數(shù)作為non-Euclidean圖例的邊長,各邊對應(yīng)的結(jié)點(diǎn)位置并不真實(shí)地反映在Euclidean空間中,從而結(jié)點(diǎn)之間的距離只是一種假想的給定值;(2)對每個(gè)結(jié)點(diǎn)均可能產(chǎn)生與其他結(jié)點(diǎn)構(gòu)成含最小權(quán)重的邊.以結(jié)點(diǎn)數(shù)400為例,按等概率均勻隨機(jī)數(shù)方式分布于之間的整數(shù)作為測試圖例的邊長,將分別期望產(chǎn)生約877條邊長為10和11的邊,考慮邊的無向性,每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)構(gòu)成邊長為10和11的邊各有4條之多.從這些具有較小邊長的邊中選擇399條邊構(gòu)成一棵滿足度約束為3的最佳生成樹,使其與Prim算法得到的無約束生成樹具有相同目標(biāo)值的概率幾乎是1.理論分析和實(shí)驗(yàn)測試得出:對分布在其他區(qū)間的均勻隨機(jī)問題,只要結(jié)點(diǎn)數(shù)大小達(dá)到一定規(guī)模,將會(huì)出現(xiàn)類似的實(shí)驗(yàn)現(xiàn)象.4.2eulideandcmt問題測試4.2.1實(shí)驗(yàn)結(jié)果與分析參照文獻(xiàn)按均勻隨機(jī)方式產(chǎn)生之間整數(shù)作為生成測試問題結(jié)點(diǎn)的坐標(biāo)值,以結(jié)點(diǎn)之間的Euclidean距離作為測試用例圖的邊長,生成結(jié)點(diǎn)數(shù)分別為50~500,間隔為50的隨機(jī)問題.GPOGA算法最大計(jì)算代數(shù)取值為:當(dāng)結(jié)點(diǎn)大小為50~300時(shí),最大計(jì)算代數(shù)取值為100,計(jì)算輪數(shù)max(run)為20;當(dāng)結(jié)點(diǎn)數(shù)大小為350及以上時(shí),最大計(jì)算代數(shù)為200,計(jì)算輪數(shù)max(run)為20.文獻(xiàn)給出在度約束為3時(shí),由branch-and-cut算法、ABACUS及CPLEX8.1得到的最好解作為檢驗(yàn)文獻(xiàn)算法找到滿意解的基準(zhǔn).在我們的實(shí)驗(yàn)方案中,通過參考相關(guān)文獻(xiàn),實(shí)現(xiàn)了branch-and-cut算法.同時(shí),在Prim算法基礎(chǔ)上,通過邊邊交換設(shè)計(jì)實(shí)現(xiàn)了一種啟發(fā)式算法(稱為PrimES).將上述兩種算法的最好解作為問題的滿意解,以此作為檢測本文算法成功找到所求問題解的概率,并計(jì)算相應(yīng)解的平均代數(shù)及評價(jià)次數(shù).表3為利用GPOGA求解按文獻(xiàn)方式生成結(jié)點(diǎn)數(shù)為50~500的Euclidean圖例問題在度約束為3時(shí)的實(shí)驗(yàn)數(shù)據(jù).由實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn),在每輪計(jì)算中,由本文算法求解結(jié)點(diǎn)數(shù)為50~200的問題得到最好解與Prim’s解的相對誤差控制在0.2%以內(nèi).表4為GPOGA與文獻(xiàn)所提方法求解結(jié)點(diǎn)數(shù)為50~200在度約束為3時(shí)的對比數(shù)據(jù).從表4對比數(shù)據(jù)看出,由GPOGA得到所求問題滿意解的概率與文獻(xiàn)提供的數(shù)據(jù)相當(dāng);但本文算法收斂到滿意解的平均評價(jià)次數(shù)均小于文獻(xiàn)的實(shí)驗(yàn)數(shù)據(jù),說明本文算法可以快速得到所求問題的(近似)最優(yōu)解.4.2.2實(shí)驗(yàn)結(jié)果及分析為進(jìn)一步檢測算法,我們隨機(jī)選取網(wǎng)絡(luò)資源TSPLIB中的8個(gè)Euclidean的測試問題,所選的8個(gè)用例盡量選取不同類型的數(shù)據(jù),以避免同一類型數(shù)據(jù)的內(nèi)在規(guī)律性.對某些包含小數(shù)的測例數(shù)據(jù),舍去其小數(shù).對Prim算法和本文算法得到的生成樹對應(yīng)邊長和,為保證計(jì)算精度,只將最后計(jì)算結(jié)果的小數(shù)部分舍去.分別為:eil51pr107,ch150,kroA200,gil262,pr299,lin318及pr439.上述8個(gè)測例對應(yīng)Prim算法最佳解對應(yīng)的度值均為4.GPOGA算法的基本參數(shù)設(shè)置同上,對前6個(gè)測例問題,最大計(jì)算代數(shù)max(gen)為100,計(jì)算輪數(shù)max(run)為20;對lin318和pr439問題,max(gen)設(shè)為200,max(run)均為10,實(shí)驗(yàn)測試及統(tǒng)計(jì)數(shù)據(jù)見表5.圖3為采用GPOGA求解ch150問題最好解偏差與平均值偏差隨計(jì)算代數(shù)變化的曲線圖.從圖可以看出由于嫁接及剪接控制策略的交互使用及采用的選擇策略,平均值偏差會(huì)出現(xiàn)一定的波動(dòng).測試表明,這種波動(dòng)不會(huì)影響算法對最優(yōu)解的搜索,也不會(huì)對算法的收斂性產(chǎn)生影響.圖4為種群中個(gè)體的多樣性隨代數(shù)變化的曲線圖.為統(tǒng)計(jì)方便,本文將具有相同目標(biāo)值或適應(yīng)值的個(gè)體認(rèn)為是同一個(gè)體.從曲線圖可以看出,種群中個(gè)體的多樣性基本維持在25%~45%之間.圖5為由GPOGA得到測例eil51在度約束為3時(shí)的最好解取整后為378