基于公共池自適應遷移策略的并行遺傳算法

蔣然

摘 要： 分析了傳統(tǒng)粗粒度并行遺傳算法的局限性，針對其遷移固定不變及無效遷移造成的通信開銷大等缺點，將公共池與自適應遷移策略相結(jié)合，提出了一種適合在多核計算機上運行的基于公共池自適應遷移策略的并行遺傳算法。該算法根據(jù)當前的進化狀態(tài)自適應地進行遷移，并利用公共池淡化了子種群間交換個體時的拓撲結(jié)構(gòu)。對復雜非線性函數(shù)求極值的仿真結(jié)果表明，該算法與傳統(tǒng)并行遺傳算法相比，收斂速度快，求解精度高，得到最優(yōu)解的進化代數(shù)提前，并行效率明顯提升。

關(guān)鍵詞： 粗粒度； 并行遺傳算法； 公共池； 自適應遷移策略； 函數(shù)優(yōu)化

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2016）10-43-04

Parallel genetic algorithm based on adaptive migration strategy of sharing pool

Jiang Ran

（Faculty of Information Engineering， Yangzhou Ploytechnic College， Yangzhou， Jiangsu 225000， China）

Abstract： The limitations of traditional coarse grained parallel genetic algorithm are analyzed. Aiming at the disadvantages of high communication overhead caused by fixed or invalid migration， a parallel genetic algorithm is proposed， which is suitable for running on multi-core computers and based on the adaptive migration strategy of sharing pool. According to the current state of evolution， the proposed algorithm can adapt to the migration， and the sharing pool is used to dilute the topological structure of the individual exchange between the sub populations. Simulation results for extreme value of complex nonlinear function show that， compared with the traditional parallel genetic algorithm， the algorithm is fast convergence， high precision， early to obtain the evolutionary generation of optimal solution， and significantly improves the parallel efficiency.

Key words： coarse grained； parallel genetic algorithm； sharing pool； adaptive migration strategy； function optimization

0 引言

并行遺傳算法（Parallel Genetic Algorithms，PGA）是將并行計算機的高速并行性和遺傳算法的天然并行性相結(jié)合的一種算法。目前并行遺傳算法模型分為主從式模型、粗粒度模型、細粒度模型和混合模型[1]。其中粗粒度模型是應用最廣且適應性最強的并行遺傳算法模型。

1 研究現(xiàn)狀

國內(nèi)外學者對粗粒度模型的研究，主要集中在遷移拓撲、遷移規(guī)模和遷移策略等問題上[2]。近幾年相關(guān)的研究包括：蔡明頔、胡振興等人提到的通過對交叉算子的修正，以及多個小規(guī)模種群并行優(yōu)化求解的方案[3-4]；劉晉勝等人提出的采用八個不同策略為并行遺傳算法的分支遺傳操作進行群體尋優(yōu)等[5-6]。

根據(jù)這些研究分析可知，一方面，如果粗粒度模型中各子種群之間遷移間隔小，則有利于提高解的精度和收斂速度，但會明顯地增大通信及同步開銷，如果遷移間隔較大，雖然降低了通信及同步開銷，但不利于提高解的精度和收斂速度。針對這個問題，本文提出一種自適應遷移策略，即各個子種群中執(zhí)行個體遷移時，并不是固定不變地移遷，而是根據(jù)當前的進化狀態(tài)動態(tài)、有條件地遷移；此外，本文提出公共池的概念，應用公共池的方式來代替各子種群間個體遷移時的拓撲結(jié)構(gòu)。因此，將本文算法稱為基于公共池自適應遷移策略的并行遺傳算法（Parallel Genetic Algorithm Based on Adaptive Migration Strategy of Sharing Pool，簡稱AMSPPGA算法）。

2 AMSPPGA算法

2.1 AMSPPGA算法的選擇算子

AMSPPGA算法的選擇算子總共選出k個個體，其過程描述為：首先計算種群中每一個個體的適應值，然后按適應值從大到小排序，從中選取前s（s

2.2 AMSPPGA算法的交叉淘汰算子

在AMSPPGA算法中，交叉淘汰算子采用文獻[7]提出的多父體雜交算子的思想。多父體雜交算子的思想如下[7]：考慮函數(shù)優(yōu)化問題，其中，，記D中的M個點為，記所生成的子空間為，其中aj滿足條件：。

在AMSPPGA算法中，借鑒多父體雜交算子的思路，結(jié)合算法特點，交叉淘汰算子設計過程如下[8]：

Step1：；

Step2：如果則轉(zhuǎn)到Step8；

Step3：隨機生成，并使aj滿足：，并且；

Step4：對選擇算子選擇出來的k個個體：生成一個新個體：即；

Step5：令為種群P（t）中最差的個體，如果優(yōu)于，則用替換；

Step6：；

Step7：轉(zhuǎn)到Step2；

Step8：交叉淘汰算子結(jié)束。

在交叉淘汰算子中，RI為替換、淘汰個體的數(shù)量，其值大小決定了算法替換、淘汰壓力的大小。

2.3 AMSPPGA算法的遷移算子

種群間個體的遷移算子決定著各子種群以什么樣的方式與其他種群中的個體交換。本文對遷移算子進行改進，用公共池的方式來代替各子種群間個體遷移時的拓撲結(jié)構(gòu)。

首先對遷移算子的初始條件作說明：設粗粒度并行遺傳算法的子種群數(shù)為m，每個種群中的個體總數(shù)都為n，第i個子種群在進化代數(shù)為j時的最佳個體為，該個體的適應度值為[9]。

算法設置一個公共池，用來接收各子種群的最佳和最差適應度個體，在公共池中維護兩個數(shù)組。一個數(shù)組存儲各子種群傳來的最佳適應度個體，其數(shù)據(jù)元素為結(jié)構(gòu)體形式，q為子種群號，也對應著數(shù)組的下標，其中，存儲第q個種群的最佳個體值；另一個數(shù)組存儲各子種群傳來的最差適應度個體，數(shù)據(jù)元素為結(jié)構(gòu)體形式，其他含義同上。

設當前的子種群號為s，進化代數(shù)為gen，具體的遷移算子步驟為：選擇當前子種群中適應度值最佳（最差）的個體（），并將該個體的適應度值（）與公共池中最佳（最差）個體數(shù)組中相應種群號的（）比較，如果大于（小于），就表示本次得到了比上次與公共池交互時更好（更差）的個體，此時分別用（）和（）替換種群s在公共池中的（）和（）的值；否則不替換。

利用公共池方式可以先存儲所有子種群的遷移個體，然后再進行比較、處理操作。相比于按拓撲結(jié)構(gòu)指定的次序來進行傳遞兩個子種群中的最優(yōu)及最差個體，這樣做更有利于最優(yōu)個體向各個子種群擴散，并且減少了因為無效遷移造成的通信及同步開銷，同時在公共池中用兩個數(shù)組分別來存放各子種群中的最優(yōu)及最差個體，可以使得公共池的維護更方便。

2.4 AMSPPGA算法的遷移準則

在AMSPPGA算法中，各個子種群中執(zhí)行個體遷移時，并不是固定不變地移遷，而是根據(jù)當前的進化狀態(tài)動態(tài)、有條件地遷移。為了便于描述AMSPPGA算法的遷移準則，給出以下定義。

在公式1中，n為種群大小，為適應值函數(shù)，為種群P的所有個體偏離中心點的距離平方之和，相似度能夠體現(xiàn)出在當前代時種群中各個個體的之間的差異程度。從公式⑴可知：當較大時，表明種群中個體差異程度較大，即表明種群中個體呈現(xiàn)多樣性；當較小時，表明種群中個體差異程度較小，即表明種群中個體即將收斂[10]。

AMSPPGA算法的遷移準則如下，首先利用公式⑴計算出當前種群個體的相似度，當種群個體相似度小于時，表明個體差異較小，此時從公共池中接受一個使本子種群的個體相似度達到最大的個體，隨機替換一個個體，以增大種群個體的多樣性。當種群個體相似度大于時，表明個體差異較大，此時從公共池中接受一個最優(yōu)的個體，以便發(fā)揮優(yōu)良個體的導向作用，加快收斂。

2.5 AMSPPGA算法具體描述

AMSPPGA算法具體描述如下。

Step 1：初始化子種群數(shù)目m，子種群中的個體數(shù)目n等算法的運行參數(shù)。

Step 2：創(chuàng)建m個子線程，讓m個子線程并行地對各個子種群執(zhí)行初始化，利用本文2.1中的思路進行選擇算子操作，利用本文2.2中的思路進行交叉淘汰算子操作。

Step 3：每一個子種群計算本代中個體的適應值，利用本文2.3小節(jié)的思想和步驟生成遷移算子。

Step 4：利用本文2.4小節(jié)的遷移思想和遷移準則執(zhí)行遷移操作。

Step 5：判斷接受來的新個體是否存在于本子種群中，以及是否比最差個體好來決定是否淘汰最差個體。

Step 6：令為種群q中最差的個體，為種群q中最優(yōu)的個體。如果等于，則轉(zhuǎn)到Step 7，否則轉(zhuǎn)到 Step 3。

Step 7：算法結(jié)束。

3 仿真及結(jié)果分析

采用較為復雜的非線性函數(shù)求極值問題對AMSPPGA算法進行驗證，并與傳統(tǒng)PGA算法進行對比。

Schaffer函數(shù)為：

設公式⑵各自變量x1，x2的取值都在[-100，100]之間，Schaffer函數(shù)為在（0，0）處存在全局極大值點1。AMSPPGA算法采用實數(shù)編碼，參數(shù)設定如下：種群規(guī)模為100，子種群數(shù)為2，最小和最大個體相似度分別為0.1和10.0，最大進化代數(shù)為100，CPU類型為Intel雙核處理器T6570，按照AMSPPGA算法連續(xù)執(zhí)行程序10次，得到表1實驗結(jié)果。結(jié)果表明每次執(zhí)行都能找到問題的全局最優(yōu)解。

將傳統(tǒng)PGA算法與AMSPPGA算法分別在1，2，4核CPU計算機上連續(xù)執(zhí)行程序10次，根據(jù)實驗結(jié)果，兩種算法的并行加速比曲線如圖1所示。

從圖1中可以看出，由于AMSPPGA算法根據(jù)當前的進化狀態(tài)動態(tài)、有條件地遷移，有效地提高了個體遷移的效率，求解問題時AMSPPGA算法的并行加速比明顯高于傳統(tǒng)PGA算法，具有較好的性能。

Schaffer函數(shù)求極值時最優(yōu)解變化情況

從圖2中可以看出，傳統(tǒng)PGA算法當進化到60代時得到最優(yōu)解，AMSPPGA算法在進化25時就得到最優(yōu)解，并且最優(yōu)解的質(zhì)量比傳統(tǒng)PGA算法要高，這是由于本文算法使用了公共池方式，減少了因為無效遷移造成的通信及同步開銷，同時又保證了各子種群之間的優(yōu)良個體有效迅速地傳播，充分發(fā)揮了優(yōu)良個體的導向作用，避免了傳統(tǒng)PGA算法遷移時的盲目性、固定性，提高了傳統(tǒng)PGA算法的全局尋優(yōu)能力，以及求解精度和收斂速度。

4 結(jié)束語

本文針對并行遺傳算法的粗粒度模型這個主要研究熱點，從模型的遷移策略入手進行研究，探討遷移算子作用機制的本質(zhì)，提出了一種基于公共池自適應遷移策略的并行遺傳算法。算法根據(jù)當前的進化狀態(tài)，動態(tài)、有條件地遷移，并利用公共池淡化了子種群間的拓撲結(jié)構(gòu)。實驗結(jié)果表明，本文算法確實有效地提高了個體遷移的效率和算法的收斂速度，減少了因無效遷移造成的通信及同步開銷，得到了更好質(zhì)量的解，并且出現(xiàn)最優(yōu)解的代數(shù)也縮短，算法的并行效率比傳統(tǒng)PGA算法明顯更高。

參考文獻（References）：

[1] 馮小丹，婁自婷，王文元.并行遺傳算法的研究及應用進展[J].

電腦知識與技術(shù)，2014.10（10）：2347-2350

[2] 高家全，何桂霞.并行遺傳算法研究綜述[J].浙江工業(yè)大學學

報，2007.35（1）：56-59

[3] 蔡明頔，么煥民.基于小種群策略的并行遺傳算法[J].哈爾濱

師范大學自然科學學報，2013.29（3）：13-15

[4] 胡振興，李汪根.基于小種群策略的并行遺傳算法[J].軟件導

刊，2013.12（2）：33-35

[5] 劉晉勝，彭志平，周靖.一種多策略并行遺傳算法研究[J].計算

機測量與控制，2011.19（2）：1188-1190

[6] 劉晉勝，彭志平，周靖.一種多策略并行遺傳算法研究及其收

斂性分析[J].計算機測量與控制，2011.19（8）：2022-2025

[7] 郭濤，康立山，李艷.一種求解不等式約束下函數(shù)優(yōu)化問題的

新算法[J].武漢大學學報（自然科學版），1999.45（5）：771-775

[8] 郭肇祿.一種基于自適應遷移策略的并行遺傳算法[D].江西

理工大學，2009

[9] 嚴曉明.粗粒度并行遺傳算法遷移算子的一種改進[J].福建

師范大學學報（自然科學版），2013.29（1）：42-47

[10] 李偉，黃穎，李康順.一種基于自適應遷移策略的并行遺傳

算法[J].武漢理工大學學報，2011.33（7）：138-142