蔣然

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

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

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：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）是將并行計(jì)算機(jī)的高速并行性和遺傳算法的天然并行性相結(jié)合的一種算法。目前并行遺傳算法模型分為主從式模型、粗粒度模型、細(xì)粒度模型和混合模型[1]。其中粗粒度模型是應(yīng)用最廣且適應(yīng)性最強(qiáng)的并行遺傳算法模型。

1 研究現(xiàn)狀

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

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

2 AMSPPGA算法

2.1 AMSPPGA算法的選擇算子

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

2.2 AMSPPGA算法的交叉淘汰算子

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

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

Step1：；

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

Step3：隨機(jī)生成，并使aj滿足：，并且；

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

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

Step6：；

Step7：轉(zhuǎn)到Step2；

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

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

2.3 AMSPPGA算法的遷移算子

種群間個(gè)體的遷移算子決定著各子種群以什么樣的方式與其他種群中的個(gè)體交換。本文對遷移算子進(jìn)行改進(jìn)，用公共池的方式來代替各子種群間個(gè)體遷移時(shí)的拓?fù)浣Y(jié)構(gòu)。

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

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

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

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

2.4 AMSPPGA算法的遷移準(zhǔn)則

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

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

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

2.5 AMSPPGA算法具體描述

AMSPPGA算法具體描述如下。

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

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

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

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

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

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

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

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

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

Schaffer函數(shù)為：

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)（References）：

[1] 馮小丹，婁自婷，王文元.并行遺傳算法的研究及應(yīng)用進(jìn)展[J].

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

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

報(bào)，2007.35（1）：56-59

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

師范大學(xué)自然科學(xué)學(xué)報(bào)，2013.29（3）：13-15

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

刊，2013.12（2）：33-35

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

機(jī)測量與控制，2011.19（2）：1188-1190

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

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

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

新算法[J].武漢大學(xué)學(xué)報(bào)（自然科學(xué)版），1999.45（5）：771-775

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

理工大學(xué)，2009

[9] 嚴(yán)曉明.粗粒度并行遺傳算法遷移算子的一種改進(jìn)[J].福建

師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2013.29（1）：42-47

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

算法[J].武漢理工大學(xué)學(xué)報(bào)，2011.33（7）：138-142