基于msm模型的分布式免疫記憶克隆選擇算法

基于msm模型的分布式免疫記憶克隆選擇算法

1基于免疫克隆選擇學的人工免疫記憶算法生物網(wǎng)絡(luò)系統(tǒng)是高度并行的分布式自適應系統(tǒng)。它的高度自適應、自學和噪聲耐受性吸引了越來越多的人工智能科學家的注意。他們借鑒生物循環(huán)系統(tǒng)的模型和機制，構(gòu)建了高性能、高可組織、高魯棒性的人工智能系統(tǒng)。這是人工智能的一個新品種。ais已成為人工智能研究領(lǐng)域的一個新熱點。1958年Burnet等提出的免疫系統(tǒng)克隆選擇學說是生物免疫系統(tǒng)最著名的模型之一.在免疫克隆選擇學說的啟發(fā)下,人工智能領(lǐng)域出現(xiàn)了基于抗體種群進化的克隆選擇算法.L.N.DeCastro構(gòu)造了第一個克隆選擇算法,并成功地用于解決模式識別、數(shù)值優(yōu)化和組合優(yōu)化問題.Kim等人提出了一種動態(tài)克隆選擇算法,并用于解決連續(xù)變化環(huán)境中的異常探測問題.焦李成等人在前人工作的基礎(chǔ)上提出了免疫多克隆策略,取得了良好的效果.和進化算法一樣,克隆選擇算法也是通過編碼來實現(xiàn)與問題無關(guān)的搜索.問題解的編碼稱之為抗體,問題解的優(yōu)劣用抗體的親合度來描述.免疫克隆選擇算法的流程是從一個初始的抗體種群出發(fā),通過克隆操作和免疫基因操作,并以親合度的高低為標準對種群進行迭代進化,直到找到滿意的解為止.收斂速度和種群多樣性之間的矛盾是所有進化類隨機搜索算法都必須面對的.為加快遺傳算法的收斂速度,又不希望以犧牲種群多樣性為代價,研究者開始研究遺傳算法的并行實現(xiàn).受并行遺傳算法的啟發(fā),結(jié)合人工免疫系統(tǒng)自身的特點,本文提出了一種人工免疫系統(tǒng)的分布式模型——塔式主從模型(Tower-likeMaster-SlaveModel,TMSM).在TMSM的基礎(chǔ)上,構(gòu)造了用于解決數(shù)值優(yōu)化問題的分布式免疫記憶克隆選擇算法(DistributedImmuneMemoryClonalSelectionAlgorithm,DIMCSA).仿真結(jié)果表明,DIMCSA適合求解大規(guī)模的復雜優(yōu)化問題.2并行遺傳算法的并行模型目前關(guān)于人工免疫系統(tǒng)并行化模型的研究國內(nèi)外還不多見.然而并行遺傳算法的研究已經(jīng)取得了一定的進展.現(xiàn)有的遺傳算法并行模型主要有:主從式模型,粗粒度模型和細粒度模型.2.1粗粒度并行模型主從式并行模型,結(jié)構(gòu)如圖1(a)所示.該模型是一種單種群進化模型,主進程M執(zhí)行種群的進化操作算子,從進程S分別計算每個染色體的適應度.在主從式模型中主進程和從進程交替工作,且任何一個從進程的滯后和通信故障都會導致整個算法的延誤,因此該模型的效率不高,穩(wěn)定性也較差.粗粒度并行模型,結(jié)構(gòu)如圖1(b)所示.該模型是基于多種群進化的模型,各個子種群進行獨立的進化,子種群間以一定的時間間隔進行個體的遷移.粗粒度模型引起了研究者的廣泛關(guān)注,目前已經(jīng)出現(xiàn)了大量關(guān)于子種群拓撲結(jié)構(gòu),遷移策略,子種群分工策略等方面的研究工作.細粒度并行模型是基于單個種群進化的模型,種群中個體分布在圖1(c)所示的網(wǎng)格上,且規(guī)定網(wǎng)格上的個體只能和與其臨近的個體進行競爭和交叉.隨著研究的深入,又出現(xiàn)了立方體、超立方體網(wǎng)格,智能網(wǎng)格等結(jié)構(gòu)的細粒度并行模型.該模型比粗粒度模型更有利于保護局部子種群自身特質(zhì),但是個體間的通信過頻,通信開銷巨大.2.2tmsm的結(jié)構(gòu)粗粒度并行模型是一種適合分布式實現(xiàn)的并行模型.為了引入免疫系統(tǒng)特性,本文在粗粒度模型基礎(chǔ)上構(gòu)造了適合人工免疫算法的塔式主從式模型(TMSM),如圖2所示.定義1TMSM由一個主種群M和若干個從種群S按圖2中的方式組織而成.定義2從種群S,稱為子種群,由一個抗體種群和一個遷入抗體構(gòu)成.每個子種群和記憶種群中的一個抗體構(gòu)成一一映射,與子種群構(gòu)成映射的記憶抗體稱為子種群的優(yōu)勢代表.子種群和對子種群的操作構(gòu)成子種群進程.定義3主種群M,稱為記憶種群,由各個子種群對應的優(yōu)勢代表抗體構(gòu)成.記憶種群進程除了包括記憶種群和對記憶種群的操作之外,還完成對子種群進程之間的個體遷移調(diào)度.2.3tmsm的算法原理TMSM體現(xiàn)了免疫系統(tǒng)特性.模型將一個子種群和記憶抗體建立一一映射,子種群分工策略使各子種群對不同區(qū)域的解空間進行搜索,子種群和記憶抗體的對應關(guān)系又將子種群的多樣性延伸到了記憶種群.這種分布式搜索和分布式記憶機制有助于保持抗體種群的多樣性.TMSM的各計算節(jié)點之間既相互獨立又相互聯(lián)系,某個子種群進程的故障不會導致整個算法的中止.TMSM是一種粗粒度的并行,通信大代價小.模型把抗體之間大量的信息交互限制在計算節(jié)點內(nèi)部,節(jié)省了通信開銷.3可行域xn最優(yōu)化問題由目標和約束條件兩個部分構(gòu)成:Minimizef(x)=f(x1,x2,…,xn)(1)Subjectx=(x1,x2,…,xn)∈S?X(2)f(X)為數(shù)值優(yōu)化問題的目標函數(shù),滿足所有約束條件的解空間S稱為可行域,S?Rn表示邊界為xiˉ≤xi≤ˉxi,i=1,2,?,n的n維搜索空間,即:S=[xˉ,ˉx],xˉ=(x1ˉ,x2ˉ,?,xnˉ),ˉx=(ˉx1,ˉx2,?,ˉxn)(3)可行域中的解稱為可行解.在可行域中使目標函數(shù)最小的解為最優(yōu)解.對于最大化問題,可將目標函數(shù)乘以負1,轉(zhuǎn)化為最小化問題求解.對于有復雜約束的數(shù)值優(yōu)化問題,可以通過拉格朗日乘子法或者懲罰函數(shù)的方法將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來處理.3.1抗體的解碼及發(fā)育本文采用了實數(shù)編碼方式,用0到1之間的實數(shù)串表示一個抗體.對于一個m維的數(shù)值優(yōu)化問題,抗體的編碼長度為m.記抗體空間中的任意一個抗體為:A=g1,g2,?,gm?gi∈,i=1,2,?,m,其解碼后對應的函數(shù)變量記為:X=(x1,x2,?,xm).抗體A稱為變量X的編碼,記為:A=e(X);反之,變量X稱為抗體A的解碼,記為:X=e-1(A).抗體的解碼過程如式(4):xi=xiˉ+(ˉxi-xiˉ)×gi,i=1,2,?,m(4)抗體的親合度必須是一個正實數(shù),并且親合度的值越大的抗體,其對應的解的質(zhì)量越好.目標函數(shù)f(X)的值無法保證是常正或者常負的,因此,不能用f(X)直接構(gòu)造抗體的親合度函數(shù).在此,我們引入了一個常負的中間函數(shù)g(X),滿足以下條件:對任意的變量X都有g(shù)(X)≤0,且g(X)和f(X)是一致的,即,對任意的兩變量X1,X2∈S,如果g(X1)>g(X2),那么f(X1)>f(X2).引入了g(X),原來的優(yōu)化問題就轉(zhuǎn)化為:min{g(e-1(A)):A∈Ι},其中I是抗體空間.抗體A與抗原之間的親合度定義為:aff(A)=-g(e-1(A))(5)n個抗體構(gòu)成一個抗體種群,記為A={A1,A2,…,An}.規(guī)模為n的抗體種群構(gòu)成的抗體種群空間可以表示為:Ιn={A:A=(A1,A2,?,An),Ak∈Ι,1≤k≤n}(6)3.2初始記憶種群DIMCSA是基于TMSM且采用了免疫克隆選擇算法流程的多種群異步分布式算法.算法分為子種群進程和記憶種群進程兩個部分.DIMCSA的計算任務由記憶種群發(fā)起,并由記憶種群判斷算法是否停止.整個算法流程的偽碼表示如下:Begin設(shè)定算法終止條件,抗體編碼長度m,給定子種群數(shù)N,子種群規(guī)模S,子種群克隆規(guī)模CS,記憶種群克隆規(guī)模Cm,子種群變異概率PS,子種群重組概率PC和遷移間隔G;停機信號量STOP=FALSE;啟動記憶種群進程;記憶種群進程依次啟動所有的子種群進程,并給子種群進程編號,同時以某種子種群分工策略給各個子種群分配搜索中心;每個子種群進程根據(jù)分配到的搜索中心初始化各自的子種群,并計算初始種子群抗體親合度;每個子種群進程用子種群最優(yōu)抗體初始化與之對應的優(yōu)勢代表,產(chǎn)生初始記憶種群;While(NOTSTOP)記憶種群和每個子種群同時迭代進化;End停機信號量STOP是一個全局信號量,由記憶種群進程控制,一旦STOP的取值為TRUE,記憶種群進程會通知所有的子種群進程停止搜索.遷移間隔G代表了各個子種群進程進行個體遷移操作的間隔為G次迭代.記憶種群進程會在每次迭代結(jié)束的時候判斷算法終止條件是否滿足,如果滿足則將停機信號量置為TRUE,算法停止.3.3物種的重復發(fā)展各個子種群進程分別對各自的抗體種群進行免疫多克隆的進化迭代操作.第i個(i=1,2,…,N)子種群進程操作步驟的偽碼表示如下:3.3.1qj克隆的計算對第i個子種群經(jīng)過第g次迭代后得到的種群SPi(g),i=1,2,…,N中的任意一個抗體aj(g)進行規(guī)模為qj克隆的克隆操作,定義為:Aj=Ij×aj(g),j=1,2,…,S(7)其中Ij為元素為1的qj維行向量.qj是子種群克隆規(guī)模,qj的大小與aj(g)的親合度成正比.3.3.2共感染型抗體pd的變異操作ps算法的免疫基因操作包括重組操作和克隆變異操.抗體aj(g)克隆后的抗體組Aj中的第k個抗體記為Aj[k]?k=1,2,?qj.記該抗體經(jīng)過重組操作后的抗體記為Aj′[k].那么:Aj′[k]={Aj[k],ifk=1CR(Aj[k],aΜ),ifk=2CR(Aj[k],ar(g)),otherwise(8)其中aM為當前的遷入抗體,ar(g)是子種群SΡi(g)中不同于aj(g)的任意抗體,r≠j且r=1,2,…,N.CR(a1(g),a2(g))表示抗體a1(g)和抗體a2(g)以某種方式進行重組得到的兩個新抗體中的任意一個.變異操作是對重組操作后得到的抗體組Aj′中的每一個抗體進行變異概率為PS的按位高斯變異,即隨機改變抗體的m×pS個抗體位,m是抗體編碼長度.變異操作后得到新的抗體組A″j.3.3.3sfg表征克隆選擇操作從A″j和aj(g)中選出一個抗體,記為aj(g+1),加入下一代子種群中.若?aj代表A″j中親合度最大的抗體,aj(g)代表SPi(g)中Aj的克隆父代抗體,那么aj(g+1)可以通過式(9)得到:aj(g+1)={?aj,ifU(0,1)≤pjaj(g),otherwise(9)其中U(0,1)表示0到1之間的隨機實數(shù),pj是一個概率,pj的取值規(guī)則如下:如果aff(aj(g))<aff(?aj),那么:pj=1(10)如果aff(aj(g))≥aff(?aj)且aj(g)不是當前種群中的最優(yōu)抗體,那么:pj=exp(-aff(aj(g))-aff(?aj)α)(11)如果aff(aj(g))≥aff(?aj)且aj(g)是當前種群中的最優(yōu)抗體,那么:pj=0(12)在式(10)～(12)中,aff(aj(g))代表抗體aj(g)的親合度,α>0是一個與抗體種群多樣性有關(guān)的值,一般多樣性越好,a取值越大,反之越小.3.3.4東北部.的刑滿釋放后篩選抗體子種群抗體經(jīng)過G次迭代后,子種群進程在當前子種群中以一定的策略選擇一個抗體提交給記憶種群進程的操作稱為遷出抗體提交操作.本文算法將當前最優(yōu)抗體作為遷出抗體.子種群進程將遷出抗體發(fā)送給記憶種群進程,記憶種群進程收到后將遷出抗體信息加入到遷移調(diào)度任務隊列.3.4重復進化家族的序列記憶種群進程操作步驟的偽碼表示如下:3.4.1任務任務任務的信息和記憶種群抗體遷移任務調(diào)度操作完成兩個方面的任務:用子種群的遷出抗體更新其優(yōu)勢代表;給子種群分配一個遷入抗體并發(fā)送給子種群進程.記憶種群進程收到子種群的遷出抗體信息后,會將該信息加入到遷移調(diào)度任務隊列的隊尾.遷移調(diào)度任務隊列中保存的數(shù)據(jù)結(jié)構(gòu)包括發(fā)起調(diào)度任務的子種群編號id(id=1,2,?,Ν),子種群提交的遷出抗體?aid和遷出抗體的親合度aff(?aid).記憶種群經(jīng)過第g次迭代后得到的種群記為ΜΡ(g)?ΜΡ(g)中的第i個抗體是編號為i的子種群對應的優(yōu)勢代表,記為ΜΡ[i],i=1,2,?,Ν.在更新優(yōu)勢代表的操作如式(13):ΜΡ[id]={?aid,ifaff(?aid)≥aff(ΜΡ[id])ΜΡ[id],otherwise(13)在給編號為id的子種群指派遷入抗體的操作中,記憶種群進程隨機產(chǎn)生一個自然數(shù)j,滿足j≠id,j=1,2,…,N,然后將ΜΡ[j]作為編號為id的子種群的遷入抗體發(fā)送給這個子種群進程.3.4.2記憶抗體的變異記憶種群進程在記錄抗體子種群優(yōu)勢抗體的同時,也在頻繁自我進化.記憶成熟算子對記憶種群中最優(yōu)的T%個抗體進行單克隆選擇進化,即克隆、變異和選擇的迭代過程.T的值反映了記憶種群進行記憶成熟操作抗體的比例,本文取為10.克隆操作和子種群的克隆操作相同,對記憶種群中的每個抗體ΜΡ[i],i=1,2,?,Ν進行qi克隆,得到qi維的抗體組MP[i].記憶抗體的變異采取方差σ隨迭代次數(shù)k遞減的高斯變異方式.變異操作得到新的抗體組記為MP′[i].克隆選擇操作從MP′[i]中選出一個最優(yōu)的抗體作為下一代記憶抗體替代克隆父代抗體.與子種群的克隆選擇操作不同,這里的克隆選擇是一個擇優(yōu)操作.4記憶成熟操作子種群進程的遷出抗體提交操作總是將子種群最優(yōu)抗體提交給記憶種群進程,且記憶種群進程只有在子種群提交的優(yōu)勢代表優(yōu)于上一代的優(yōu)勢代表時才進行更新.因此,子種群的遷出抗體提交操作不會使記憶種群退化.另外記憶種群進程的記憶成熟操作是完全擇優(yōu)的進化,也保證了記憶種群是不退化的.因此,記憶種群反映了整個系統(tǒng)的進化過程,如果能證明記憶單元中的抗體收斂到最優(yōu)解對應的抗體,那么整個算法就是收斂的.下面通過分析記憶種群的收斂性來說明DIMCSA以概率1收斂.由于記憶種群中的每個記憶抗體只與該抗體的前一代抗體相關(guān),因此,可以用馬爾可夫鏈(MarkovChain)描述每個記憶抗體的進化過程.集合I為抗體空間,則記憶種群空間可以記為:ΙΜΡ={ΜΡ|ΜΡ[i]∈Ι,i=1,2,?,Ν}(14)記優(yōu)化問題最優(yōu)解集合為:B*={a|a∈I,aff(a)=f*=max(aff(a′)),a′∈I}(15)對于記憶抗體種群MP:?(MP)≡|MP∩B*|(16)表示記憶抗體種群MP中包含對應著最優(yōu)解的抗體個數(shù),是一個大于等于零的整數(shù).定義4如果對于記憶種群的任意初始狀態(tài)MP0,經(jīng)過均k次迭代后得到的MP(k)均有:limk→∞p{?(ΜΡ(k))≥1|ΜΡ(0)=ΜΡ0}=1(17)則稱,算法以概率1收斂到最優(yōu)種群集.定理1記憶種群中的每個抗體經(jīng)過一次迭代進化成最優(yōu)抗體的概率大于零.證明記最優(yōu)抗體種群中的任意一個抗體為A?ˉA是每個基因位都和A不同的抗體.那么對于記憶種群中的任意一個抗體ΜΡ[i]?i=1,2,?,Ν,其變異到Α的概率δ都大于等于ˉA變異到Α的概率ˉδ.算法中記憶成熟操作采取方差σ隨迭代次數(shù)k遞減的高斯變異方式,則對于抗體ˉA的第i個抗體基因位ˉAi變異到與Α的第i個抗體基因位Ai相同的概率為pi=(√2πσ)-1exp(-(Ai-ˉAi)2/2σ2)＞0(18)因此ˉA變異到Α的概率:ˉδ=m∏j=1pj>0(19)其中m是抗體編碼長度.故而記憶單元中的每個抗體經(jīng)過一次迭代進化成最優(yōu)抗體的概率δ≥ˉδ＞0.定理1證畢.定理1說明了,DIMCSA采取的免疫單克隆的記憶成熟操作使得記憶種群中的每個抗體都有可能經(jīng)過一次迭代進化成最優(yōu)抗體.定理2DIMCSA是概率1收斂的.證明記憶種群的任意初始狀態(tài)MP0,經(jīng)過k次迭代沒有找到全局最優(yōu)解的概率記為:Ρ0(k)=Ρ{?(ΜΡ(k))=0}=Ρ{ΜΡ(k)∩B*=[ΤΡΡ1542,+3mm。3mm,BΡ#]}(20)那么:Ρ0(k+1)=Ρ{?(ΜΡ(k+1))=0}=Ρ{ΜΡ(k+1)∩B*=[ΤΡΡ1542,+3mm。3mm,BΡ#]}(21)根據(jù)貝葉斯條件概率公式有:Ρ0(k+1)=Ρ{?(ΜΡ(k+1))=0}=Ρ{?(ΜΡ(k+1))=0|?(ΜΡ(k))≠0}×Ρ{?(ΜΡ(k))≠0}+Ρ{?(ΜΡ(k+1))=0|?(ΜΡ(k))=0}×Ρ{?(ΜΡ(k))=0}(22)由于記憶種群中的抗體是不退化的,所以Ρ{?(ΜΡ(k+1))=0|?(ΜΡ(k))≠0}=0(23)將式(23)帶入式(22)可得:Ρ0(k+1)=Ρ{?(ΜΡ(k+1))=0|?(ΜΡ(k))=0}×Ρ{?(ΜΡ(k))=0}=Ρ{?(ΜΡ(k+1))=0|?(ΜΡ(k))=0}×Ρ0(k)(24)記憶種群中的抗體獲得全局最佳抗體有兩種方式,一種是通過記憶種群的免疫操作獲得,設(shè)此種方式的概率為:ΡΙ={ΡΙ(1),ΡΙ(2),?}(25)另一種是通過抗體子種群提交的遷出抗體獲得,設(shè)此種方式的概率為ΡΙΙ={ΡΙΙ(1),ΡΙΙ(2),?}(26)因此:Ρ{?(ΜΡ(k+1))≥1|?(ΜΡ(k))=0}=1-(1-ΡΙ(k+1))(1-ΡΙΙ(k+1))(27)由定理1我們可以得到,P(k)Ι>0.記ζ=minkΡ(k)Ι,;k=1,2,…則由式(27)可知:Ρ{?(ΜΡ(k+1))≥1|?(ΜΡ(k))=0}＞ΡΙ(k+1)≥ζ＞0(28)因此有:Ρ{?(ΜΡ(k+1))=0|?(ΜΡ(k))=0}=1-Ρ{?(ΜΡ(k+1))≠0|?(ΜΡ(k))=0}=1-Ρ{?(ΜΡ(k+1))≥1|?(ΜΡ(k))=0}≤1-ζ＜1(29)由式(24)可知:0≤Ρ0(k+1)≤(1-ζ)×Ρ0(k)≤(1-ζ)2×Ρ0(k-1)?≤(1-ζ)k+1×Ρ0(0)(30)由于limk→∞(1-ζ)k+1=0,0≤Ρ0(0)≤1,所以:0≤limk→∞p0(k)≤limk→∞(1-ζ)k+1Ρ0(0)=0(31)所以:limk→∞p0(k)=0(32)對于記憶抗體的任意初始狀態(tài)MP0,經(jīng)過k次迭代后找到全局最優(yōu)解的概率記為:Ρ1(k)=Ρ{?(ΜΡ(k))=1}=Ρ{ΜΡ(k)∩B*≠[ΤΡΡ1542,+3mm。3mm,BΡ#]}(33)由式(22)可知:P1(k)=1-P0(k)(34)故而:limk→∞Ρ1(k)=limk→∞Ρ{?(ΜΡ(k))≥1}=1-limk→∞Ρ{?(ΜΡ(k))=0}=1-limk→∞Ρ0(k)=1(35)因此,對于記憶抗體的任意初始狀態(tài)MP0有:limk→∞p{?(ΜΡ(k))≥1|ΜΡ(0)=ΜΡ0}=1(36)由定義4可知,DIMCSA以概率1收斂到最優(yōu)種群集.定理2證畢.5x計算本文采用了以下十個標準測試函數(shù):f1(x)=Ν∑i=1x2i;S=[-100,100]n;f(x*)=0(37)f2(x)=Ν∑i=1|xi|+Ν∏i=1|xi|;S=[-10,10]n;f(x*)=0(38)f3(x)=Ν∑i=1(i∑j=1xj)2;S=[-100,100]n;f(x*)=0(39)f4(x)=n∑i=1(|xi+0.5|)2;S=[-100,100]n;f(x*)=0(40)f5(x)=Ν∑i=1ix4i+random[0,1);S=[-1.28,1.28]n;f(x*)=0(41)f6(x)=Ν∑i=1(-xisin(√|xi|));S=[-500,500]n;f(x*)=-418.983×n(42)f7(x)=Ν∑i=1(x2i-10cos(2πxi)+10);S=[-5.12,5.12]n;f(x*)=0(43)f8(x)=-20exp(-0.2√1ΝΝ∑ix2i)-exp(1ΝΝ∑i=1cos(2πxi))+20+e;S=[-30,30]n;f(x*)=0(44)f9(x)=Ν∑i=1x2i4000-Ν∏i=1cos(xi√i)+1;S=[-600,600]n;f(x*)=0(45)f10(x)=1nn∑i=1(x4i-16x2i+5xi);S=[-5,5]n;f(x*)=-78.33236(46)f1～f3是單峰函數(shù),f4是階梯函數(shù).f5是有噪四次函數(shù).f6～f10是多峰函數(shù),其局部最優(yōu)值的個數(shù)隨著問題維數(shù)的增長而增長.5.1多線程仿真并行計算仿真環(huán)境通常為了驗證分布式算法的性能,人們將分布式算法在處理器陣列上或局域網(wǎng)上運行,用算法運行時間作為衡量算法性能的重要指標.這種方法看似合理,但仿真結(jié)果和實驗環(huán)境相關(guān),實際上是有失客觀性的.分布式算法的運行時間由兩個重要部分組成:算法計算時間和網(wǎng)絡(luò)通信時間.前者只取決于分布式算法本身,與網(wǎng)絡(luò)延遲無關(guān);后者不僅和分布式算法有關(guān),還受到通信網(wǎng)絡(luò)狀態(tài)的影響.網(wǎng)絡(luò)開銷大的算法受網(wǎng)絡(luò)狀態(tài)影響大,反之則較小.現(xiàn)有的算法評價機制,都沒有將兩者分離開來考慮.也就是說,當算法的運行環(huán)境有所改變的時候,算法的優(yōu)劣也可能隨之改變.本文采用多線程技術(shù)來模擬分布式的計算資源,構(gòu)造了一種多線程虛擬并行計算仿真環(huán)境(Multi-threadSimulativeParallelComputingSystem,MSPCS),并基于MSPCS設(shè)計了衡量并行算法性能的指標.MSPCS克服了基于處理器陣列和基于局域網(wǎng)的并行仿真系統(tǒng)的缺點,將算法計算時間和網(wǎng)絡(luò)通信時間分開來考慮.相應地,算法性能衡量標準也由兩個部分組成,算法的使用者可以根據(jù)算法運行的網(wǎng)絡(luò)環(huán)境選擇合適的算法.算法在執(zhí)行過程中用親合度評價計數(shù)器數(shù)組AET記錄記憶種群和各個子種群平均抗體親合度的次數(shù).AET規(guī)模為N+1,其中N為子種群個數(shù).AEΤ表示記憶種群線程評價抗體親合度的次數(shù),AEΤ[i]?i=1,2,...,Ν表示第i個子種群線程評價抗體親合度的次數(shù).用計數(shù)器CT記錄算法通信次數(shù).那么,算法的平均親合度評價次數(shù)θ1和平均通信次數(shù)θ2可以分別由式(47)(48)得到:θ1=1Ν+1Ν∑i=0AEΤ[i](47)θ2=1Ν+1CΤ(48)算法總的運行時間可以表示為:T=θ1T1+θ2T2(49)其中,T1是算法計算一次抗體親合度需要的時間代價;T2是分布式算法在實際運行環(huán)境中計算節(jié)點之間進行一次信息傳遞需要的平均時間代價.由式(49)可以看出,在決定算法運行時間的四個因素中,θ1和θ2只與算法的性能有關(guān),T1和T2與問題的規(guī)模和網(wǎng)絡(luò)狀態(tài)有關(guān).因此,本文用θ1和θ2來衡量算法的搜索性能.在實際應用中,使用者根據(jù)實際問題的規(guī)模和算法的具體運行環(huán)境估算出T1和T2,進而決定使用哪種算法更優(yōu).5.2dimcsa算法性能分析為了驗證DIMCSA搜索到全局最優(yōu)解的能力,對十個不同類型的標準測試函數(shù)進行了優(yōu)化實驗,并將實驗結(jié)果和分布式遺傳算法(DGA)進行了比較.目標函數(shù)維數(shù)為30,子種群數(shù)量為10,規(guī)模為2,遷移間隔為1.在DIMCSA中,子種群克隆規(guī)模為15,變異概率為1/m,m為編碼長度,重組概率為1,記憶種群克隆規(guī)模為10.算法的停止條件設(shè)置為當前搜索到的最優(yōu)解達到一定的精度或者迭代次數(shù)達到上限10000次.表1中的數(shù)據(jù)是50次獨立實驗的平均結(jié)果.從表1的實驗結(jié)果可以看出,DIMCSA用較小的計算代價和通信代價找到了質(zhì)量更高的解.DIMCSA比DGA的收斂速度更快,精度更高.5.3局部極小值該組實驗驗證了DIMCSA求解大規(guī)模復雜問題的能力.f6～f9是四個多峰函數(shù),其局部最優(yōu)值的個數(shù)隨著問題維數(shù)