晏妮

（陜西安康職業(yè)技術學院 陜西 安康725000）

基于共享存儲的并行狹義遺傳算法

晏妮

（陜西安康職業(yè)技術學院 陜西 安康725000）

遺傳算法具有簡單、易算且方便分布并行處理等特點，基于這種優(yōu)勢，遺傳算法被廣泛應用于眾多領域范圍內(nèi)，比如機器學習、工業(yè)控制等。為解決高難度的非線性及其相關問題，采用基于共享存儲的并行狹義遺傳算法，可以有效實現(xiàn)對數(shù)據(jù)級的并行操作，具有較強的并行度，其只需較少的通訊開銷就能獲得比原先更高的運行效率，至少提高至50%以上。文中詳細闡述了基于共享存儲的并行狹義遺傳算法，仿真實驗驗證了其正確性和高效性。

共享存儲；并行狹義遺傳算法；非線性；探究

遺傳算法擁有廣泛的發(fā)展前景，且應用范圍極廣，是一種全局優(yōu)化的搜索算法，常常應用于解決許多復雜的問題中，究其本質(zhì)，遺傳算法就是一種模式的運算，具有簡單、易算且方便分布并行處理等特點。而基于共享存儲的并行狹義遺傳算法更是將這些優(yōu)勢得到了進一步提高，使其被廣泛應用于工業(yè)控制、作曲等諸多方面，實現(xiàn)了高效率運行。

1 并行狹義算法的簡要概述

狹義遺傳算法具有一定的局部收斂性，屬于遺傳算法的一種，但這種方法的搜索并不是一個Markov過程。所謂Markov過程，通常用以下方式表達：設{X(t),t∈T}，對任意n個不同的t1＜t2＜…＜tn-1＜tn,則有 P(X(tn)≤xn|X(tn-1)=xn-1,… X(t1)= x1=P(X(tn)≤xn|X(tn-1)=xn-1），則稱 X(t)為馬爾可夫（Markov）過程，簡稱馬氏過程。但這種狹義的遺傳算法的搜索率十分高，且收斂過程的穩(wěn)定性也十分高，同時在搜索過程中具有較強的可控制性。但無論是粗粒度還是細粒度的并行遺傳算法，都具有很低的運行效率。究其原因，這主要是因為并行遺傳算法的運行效率都不太高，且他們在實現(xiàn)并行方面，都只能實現(xiàn)控制并行的功能，卻不能實現(xiàn)對數(shù)據(jù)的并行。而狹義遺傳算法卻能夠實現(xiàn)對數(shù)據(jù)的并行且具有很小的通訊開銷，同時還具有較高的運行效率。

2 基于共享存儲的并行狹義遺傳算法的模型分析

通常情況下，并行狹義遺傳算法的模型需要滿足以下條件，第一，需要進行一次利用基于個體進化的狹義遺傳算法，對一個給定的區(qū)域[G,K]進行搜索，且搜索的是一個并行任務，在搜索的過程中，每一個并行任務都會產(chǎn)生一個并行進程進而完成搜索任務。第二，每一個并行進程都需要一個處理器資源，這個處理器資源通過申請就可以得到，如果處理器資源的申請通過就可以在有限的時間內(nèi)完成任務。第三，一個并行進程最多只能允許在一個處理器資源上運行。第四，每一個并行進程在申請?zhí)幚砥髻Y源時，如果資源能夠滿足既可以在限制的時間內(nèi)完成任務。第五，處理器資源都具有一定的有限性。第六，利用個體進化的狹義遺傳算法所得到的求解，可將其歸納為有限個子任務，也可以說是有限個并行進程。所以，針對以上條件，就需要設置一個等待隊列的進程，也可以說是公共存儲區(qū)，該共享隊列主要用來保存局部最優(yōu)解。一般情況下，共享隊列應存放在處理器上面，并且要求是一個被激活的處理器。如圖1所示。

由于一個并行進程最多只能允許在一個處理器資源上運行，當一個資源處理器產(chǎn)生了兩個新的搜索任務時，其中有一個搜所任務在處理器上運行，那么另一個搜索任務就必須申請其他處理器之后，再在相應的處理器上運行，這樣才能確保運行的順利進行。所以，系統(tǒng)中的每一個處理器都會產(chǎn)生一定的任務，并將其傳遞到其他系統(tǒng)中的處理器，進而產(chǎn)生局部最優(yōu)解，而這些最優(yōu)解會迅速傳遞到第一個被激活的處理器資源上，因此，這樣才能得到全局最優(yōu)解。

圖1 系統(tǒng)處理器之間通訊示意圖Fig.1 Communication between the system processor schematic

3 基于共享存儲的并行狹義遺傳算法的實現(xiàn)

當在任意一個處理器上設立一個公共隊列Q的過程中，其目的就是為了存儲搜索的局部最優(yōu)結果，那么，基于共享存儲的并行狹義遺傳算法是如何實現(xiàn)的呢？具體分析如下。

3.1 并行狹義遺傳算法的探索進程和開發(fā)進程之間的關系

如圖2所示，由于并行狹義遺傳算法主要是用于探索空間的，一旦算法開始，就會啟動n個并行進程算法進行探索空間，這一過程就被稱為探索進程。因此，每一個并行進程都有一個相對應的群體進行操作，設置一個模式變量，其主要就是用來存放模式，并確保它們能夠初始化為不同的群體。這時，就要求距離函數(shù)滿足下述條件：h(P)＜h(P)時，其中11i0i代表的是探索進程的符號，且1≤i≤n。如果隨機選取一個探索進程并將其模式變量取出，如果為空，則并行探索進程處于剛啟動的狀態(tài)，因為只有剛啟動時，并行進程才會出現(xiàn)這種可能。這時，將提取的模式直接加入到本地模式變量中，這樣在和遠程讀取的模式進行空間交配，最終產(chǎn)生兩個新模式，并隨機存入本地和遠程模式變量中，然后繼續(xù)執(zhí)行進程，直至出現(xiàn)最優(yōu)解，然后將其提交給開發(fā)進程，并讀取本地模式變量，并用它來將本地群體進行初化，繼續(xù)上述步驟，直至收到終止信號，結束本進程?；诳臻g交配的特殊性，各探索進程分別對不同的子空間進行搜索，所以，采用過大的變異和交叉概率是不適宜的，只有采用適宜的變異和交叉概率，才能有效實現(xiàn)搜索的可達性。

圖2 探索進程和開發(fā)進程之間的關系Fig.2 Explore the relationship between the process and the development process

通常情況下，開發(fā)進程的操作群體空間在剛開始的時候，確保相應的個體，而這些個體都是由n個探索進程所提供。一旦群體滿了之后，這時就要采用最小的淘汰法對探索進程中提交的個體進行相應的接收。更重要的一點是，由于n個探索進程分別在n個不同的模式空間之中進行搜索功能，這在一定程度上就已經(jīng)保證了所提交的個體分別是不同子空間中的最優(yōu)個體，這樣才能使開發(fā)進程對具有多樣性的個體進行操作，使其得到有效保障。所以，這樣的開發(fā)進程適宜采用小變異概率和交叉概率進行運算，從而避免群體中已積累有用信息的多樣性較優(yōu)個體遭到破壞。

3.2 基于共享存儲的并行狹義遺傳算法的操作步驟

對一個給定的區(qū)域[G,K]內(nèi)進行搜索操作，便會產(chǎn)生一個進程，而這些進程便會執(zhí)行以下操作：

1)一旦給定的區(qū)域[G,K]進行搜索任務時，產(chǎn)生一個進程，而每個進程會相應產(chǎn)生一個初始群體M,M滿足{a1,a2,a3…,am}.

2)對所產(chǎn)的初始群體M中的a1,a2,a3…,am都要進行適應度的評估。

3)一旦對群體M執(zhí)行操作后，群體M已煥然一新，成為被更新后的種群M。

4)做出準確的判斷，即群體M是否達到穩(wěn)定的狀態(tài)。如果已經(jīng)達到穩(wěn)定的狀態(tài)，就會得到局部最優(yōu)個體R，其作用主要有3項，首先，主要是為了調(diào)用基于個體化的狹義遺傳算法，進而得到子區(qū)域[R1,R2];其次，是將當前局部最優(yōu)解及其對應的子區(qū)域[R1,R2]，將其加入到共享隊列Q中，最后重新確定搜索區(qū)域，同時執(zhí)行并行遺傳操作。完成下文第6個步驟。如果群體M沒有進化達到穩(wěn)定的狀態(tài)，則進行交叉操作，按照第5個步驟進行。

5)執(zhí)行交叉操作，并轉入第2個操作，即對所產(chǎn)的初始群體M中的每一個個體都要進行適應度的評估。

6)重新確定搜索區(qū)域，同時執(zhí)行并行遺傳操作。其中，并行遺傳操作主要可分為四種情況進行，第一種情況是，當G= R1時，則將原來的分區(qū)[G,K]轉變?yōu)樾碌膮^(qū)域[R2,K]，這樣就可以在搜索過程中產(chǎn)生一個在當前處理器上運行的新進程。第二情況是，當K=R2時，就可以將原來的分區(qū)[G,K]轉變?yōu)樾碌膮^(qū)域[G,R1]，這樣就可以在新區(qū)域搜索任務中產(chǎn)生新的進程，并在處理器資源上運行。第三種情況是，當G=R1且K=R2時，則證明區(qū)域[G,K]已經(jīng)完成搜索任務。第四種情況是，當G≠R1且K≠R2，則原來的區(qū)域[G,K]已經(jīng)邊變?yōu)樾碌腫G,R1]和[R2,K]，這樣就可以在新區(qū)域搜索任務中產(chǎn)生新的進程，這樣就可以申請?zhí)幚砥髻Y源，如果能夠得到滿足通過就可以在處理器資源上運行，進而執(zhí)行并行遺傳搜索，如果沒有得到滿足，則該進程就會處于等待隊列狀態(tài)，另外，對于新區(qū)域[G,R1]的搜索也會產(chǎn)生一個進程，并讓該進程在當前處理器上運行。

7)當全部分區(qū)域被搜索后就會將隊列Q中的內(nèi)容輸出，這樣就能夠得到公共隊列中的最有個體，也就是全局的最優(yōu)解。

3.3 并行狹義遺傳算法具有較高的運行效率

通常情況下，基于共享存儲的并行狹義遺傳算法一般會根據(jù)實際情況，采用自動區(qū)域劃分的方法,這樣就可以讓不同區(qū)域的遺傳尋優(yōu)過程分布到不同的處理器上進行并行執(zhí)行過程。因此，在進行區(qū)域劃分之后，各個子區(qū)域之間應滿足下述內(nèi)容：

1)Di∩Dj=Φ，?i，j{1,2，…，m}，且i≠j；這主要是考慮到具體實現(xiàn)時的可操作性，則算法存在著邊界相交。

3)每個分區(qū)上都只有一個極值點，即每個子區(qū)域都是單峰值區(qū)域，其中{D1，D2，…Dm}為D的一個劃分。因此，時間順序來說，各個區(qū)域之間的依賴關系屬于一種二叉樹結構。如圖3所示。

圖3 自動區(qū)域劃分和各個區(qū)域之間的關系Fig.3 Automatic zoning and relationship between the various regions

所以，對各個子區(qū)域之間的遺傳搜索可以并行地完成，這種并行操作是數(shù)據(jù)級的并行。另外，并行算法中唯一的通訊開銷是在各進程之間傳遞一次初始值和返回搜索后的局部最優(yōu)解，因此通訊開銷小。而利用CGA或GGA實現(xiàn)的并行算法需要不斷地交換不同子群體或鄰域之間的個體或最優(yōu)個體，或者需要不斷地分配初始遺傳子群體并收集遺傳搜索結果。顯然，CGA或GGA的并行算法的通訊開銷比RGA的并行算法的通訊開銷大得多。綜上所述，基于共享存儲的并行狹義遺傳算法具有較高的運行效率。

4 結束語

綜上所述，正是基于共享存儲的并行狹義遺傳算法具有較高的并行度，以及高運行效率，不僅使數(shù)據(jù)級的并行操作成為現(xiàn)實，同時還使得它被廣泛應用于各個行業(yè)，為電子科技領域做出了重要貢獻。

[1]王竹榮,巨濤,馬凡.多核集群系統(tǒng)下的混合并行遺傳算法研究[J].計算機科學,2011(7):194-199. WANG Zhu-rong,JU Tao,MA Fan.Genetic algorithm hybrid multi-core parallel cluster system under[J].Computer Science,2011(7):194-199.

[2]肖海林,王鵬,聶在平.基于遺傳算法的多基站協(xié)作通信功率分配方案[J].電子科技大學學報,2014(1):26-30,41. XIAO Hai-lin,WANG Peng,NIE Zai-ping.Based on genetic algorithm base collaborative communication power allocation scheme[J].University of Electronic Science and Technology, 2014(1):26-30,41.

[3]苗乾坤.面向共享存儲系統(tǒng)的計算模型及性能優(yōu)化[J].中國科學技術大學,2010(5):15-21. MIAO Qian-kun.Model and performance optimization for shared storage system [J].University of Science and Technology of China,2010(5):15-21.

[4]鄭金華,蔡自興.基于共享存儲的并行RGA的設計與實現(xiàn)[J].高技術通訊,2000(3):23-27. ZHENG Jin-hua,CAI Zi-xing.Design and implementation of shared memory parallelism based on RGA [J].High-tech Communications,2000(3):23-27.

[5]馬利平,葛海波，歐陽磊.基于共享存儲器的多處理機并行快速通信[J].電子設計工程，2011（7）：65-67. MA Li-ping,GE Hai-bo,OUYANG Lei.Based on shared memory multiprocessor parallel fast communication[J]. Electronic Design Engineering，2011（7）：65-67.

[6]白東玲，郭紹永.一種改進的混合遺傳算法求解0_1背包問題[J].電子設計工程，2013(14)：9-11. BAI Dong-ling,GUO Shao-yong.An improved hybrid genetic algorithm 0_1 knapsack problem [J].Electronic Design Engineering，2013(14)：9-11.

Narrow parallel genetic algorithm based on shared storage

YAN Ni
（Shaanxi Ankang Vocational and Technical College,Ankang 725000,China）

The genetic algorithm is simple,easy to calculate and easy distribution of parallel processing,etc.,based on this advantage,genetic algorithms are widely used in many fields within the range,such as machine learning,industrial control.In order to solve difficult nonlinear and related issues,narrow parallel genetic algorithm based on shared storage,you can effectively achieve data-level parallelism,with a strong degree of parallelism,which requires less communication overhead can be obtained higher efficiency than the original,at least to more than 50%increase.This paper elaborates on shared memory parallel narrow genetic algorithms,simulation results verify the correctness and efficiency.

Shared memory;parallel narrow genetic algorithm;nonlinear;inquiry

TN99

A

1674－6236（2015）07-0074-03

2014-06-10 稿件編號：201406070

晏 妮(1983—)，女，陜西安康人，碩士，高級講師。研究方向：計算機教學。