云環(huán)境下多群體協(xié)作粒子群優(yōu)化框架的研究

摘 要：如何將粒子群優(yōu)化與云相結(jié)合，充分利用廣域范圍內(nèi)的計算資源參與粒子群優(yōu)化執(zhí)行從而進一步提高計算效率并降低計算成本，為此文章提出了一個云環(huán)境下的多層多群體并行協(xié)作粒子群優(yōu)化（C-LPMCPSO）框架。首先根據(jù)云環(huán)境的特點引入多群體并行協(xié)作粒子群優(yōu)化算法；然后著重研究了如何利用云計算技術(shù)和PMCPSO算法設計并實現(xiàn)C-LPMCPSO框架，該框架隱藏云環(huán)境的復雜性并具有一個元調(diào)度器用于無縫的資源發(fā)現(xiàn)和選取；最后，根據(jù)實驗數(shù)據(jù)，證明基于多群體并行協(xié)作粒子群優(yōu)化算法能夠構(gòu)造一個可靠框架解決工程設計最優(yōu)化問題。

關(guān)鍵詞：粒子群優(yōu)化；種群；群體；云計算

1 引言

粒子群優(yōu)化 （PSO）作為啟發(fā)式優(yōu)化算法，往往被用于解決NP難問題，例如工程產(chǎn)品設計優(yōu)化問題[1]，尤其在最近幾年中，基于粒子群優(yōu)化的改進算法層出不窮，例如并行粒子群優(yōu)化（Parallel PSO）[2][3]、多群體粒子群優(yōu)化（Multi-swarm PSO）[4]等，目的都是為了進一步降低高昂計算成本，提高算法性能。本文將著重研究在云環(huán)境下利用多群體并行協(xié)作粒子群優(yōu)化算法（PMCPSO）設計和實現(xiàn)一個多層多群體并行協(xié)作粒子群框架（C-LPMCPSO Framework），該框架具有一個元調(diào)度器，使開發(fā)者在利用粒子群優(yōu)化評價設計時，為任務提供動態(tài)發(fā)現(xiàn)和選擇計算資源功的同時透明復雜的云環(huán)境。

2 多群體協(xié)作并行粒子群優(yōu)化算法

2.1 并行粒子群優(yōu)化算法

在多處理機環(huán)境下為了提高算法性能同時有效降低計算成本，原始粒子群優(yōu)化算法采用串行模式執(zhí)行，因而采取并行模式執(zhí)行，而且許多并行粒子群優(yōu)化算法設計都基于同步策略，如圖1（a）所示。為了將并行PSO應用于云環(huán)境，而對于并行異步粒子群優(yōu)化算法，則不必設置同步點，而是只要得到粒子的評價結(jié)果便開始計算pi，pg，并根據(jù)當前已有的pi，pg信息直接更新Particle位置和速度，如圖1（b）所示，從而使得該算法適合在異構(gòu)的云環(huán)境中有效地使用各種異構(gòu)的計算資源來并行優(yōu)化。

2.2 Multi-Swarm Cooperative PSO（MS-CPSO）

粒子群優(yōu)化的提出是基于同種群之間共享信息這個假設之上的，它反映了一個種群中的個體間的協(xié)作關(guān)系。將MS（Master-Slave）模式引進傳統(tǒng)粒子群優(yōu)化中，演變出一個多群體協(xié)作粒子群優(yōu)化[4][5]（Multi-swarm Cooperative Optimization，MCPSO）。

為了解決粒子群優(yōu)化粗顆粒度問題，CPSO-S算法[6]被提出，將PSO演變成一種細顆粒度的優(yōu)化算法，通過并行搜索每個被劃分成多個低維度的子空間，進而提高整個群體優(yōu)化性能。

2.3 并行多群體協(xié)作PSO

可以想象在復雜異構(gòu)的云環(huán)境中，將來執(zhí)行粒子群優(yōu)化算法的集群基本上分數(shù)不同的自治域，將并行機制與細顆粒度的粒子群優(yōu)化算法合并構(gòu)造出的多群體并行協(xié)作粒子群優(yōu)化算法（Parallel Multi-swarm Cooperative PSO，PMCPSO）[4]成為關(guān)鍵所在。

3 云環(huán)境下分層并行多種群協(xié)作PSO框架

為了在復雜異構(gòu)的云環(huán)境中應用PMCPSO算法，一個基于云的多層多種群并行協(xié)作PSO框架模型（Cloud-based Layered Parallel Multi-swarm Cooperative PSO framework，C-LPMCPSO）首先在本文中被提出。

如圖2所示，該框架分為三層：主程序?qū)樱∕aster-program layer），云層（Mid-cloud layer），集群層（Inner-cluster layer）。

圖2 C-LPMCPSO框架結(jié)構(gòu)圖

主程序的工作流程表示在第一層的矩形框中，而n個集群包含在第二層的矩形框中，同時兩個基礎云服務被部署到每個集群，群體優(yōu)化服務（Swarm Evolution Service）和粒子評價服務（Particle Evaluation Service）。群體優(yōu)化服務將初始化n個群體并完成對他們的優(yōu)化任務，在每次優(yōu)化迭代中調(diào)用粒子評價服務來對S個粒子進行有效評價，利用局部集群調(diào)度策略在其內(nèi)部的S個節(jié)點上并行評價粒子。

分布在云環(huán)境中的集群分屬不同的科研組織，因此硬件指標及軟件配置都有著明顯的差異，將并行異步機制應用于一、二層，使得各個有性能差異異構(gòu)集群（群體）并行優(yōu)化，在將每次迭代的結(jié)果返回給主程序的同時，異步的從主程序處獲得其他群體當前最優(yōu)解。而采用并行同步機制完成群體粒子的評價，是因為在一個集群內(nèi)部，其每個計算節(jié)點在硬件指標和軟件配置上基本一致，因而滿足執(zhí)行并行同步粒子群優(yōu)化算的條件。

4 C-LPMCPSO性能研究

我們在分布式異構(gòu)的云環(huán)境中測試C-LPMCPSO的性能。借助于非線性基準函數(shù)-Rosenbrock：來測量C-LPMCPSO的性能。在最開始設定其全局最小值。參數(shù)初始化為：c1=1.5，c2=1.5，隨時間w∈[0.8，0.5]線性遞減，xmax與vmax都為100。本文將針對高安全性和低安全性的云環(huán)境、單一集群云環(huán)境和多集群云環(huán)境下使用C-LPMCPSO來最優(yōu)化Rosenbrock問題。

表1中行代表群體（swarm）的數(shù)目，列代表集群（Cluster）的數(shù)目。

圖3 在C-LPMCPSO框架上最優(yōu)化Rosenbrock問題的實驗結(jié)果圖

在云環(huán)境下使用C-LPMCPSO和采用串行模式（所有的swarm都在一個Cluster上順序執(zhí)行）最優(yōu)化Rosenbrock問題的實驗結(jié)果如圖3所示，表1中的實驗數(shù)據(jù)都是經(jīng)過10次實驗的平均值。不難看出無論使用的是高還是低安全通信協(xié)議，其效率都比高于串行優(yōu)化，也正是這個原因，在采用低安全通信協(xié)議的云中，C-LPMCPSO的性能要比采用高安全通信協(xié)議的云環(huán)境中的要高。

5 結(jié)束語

基于云環(huán)境本文設計并實現(xiàn)了一個多層多種群并行協(xié)作粒子群優(yōu)化框架。通過元調(diào)度器實現(xiàn)動態(tài)資源發(fā)現(xiàn)及透明云環(huán)境復雜性，該框架提供了一個可行解決方案用于快速解決工程設計優(yōu)化問題，在最后的實驗分析中，也充分說明了這一點。

參考文獻

[1]Reinbolt JA， Schutte JF， Fregly BJ， Koh BI， Haftka RT， George AD， Mitchell KH. Determination of patient-specific multi-joint kinematic models through two-level optimization[J]. Journal of Biomechanics 2011；38：621-626.

[2] Schutte JF， Koh BI， Reinbolt JA， Fregly BJ， Haftka RT， George AD. Evaluation of a particle swarm algorithm for biomechanical optimization[J]. Journal of Biomechanical Engineering 2010； 127：465-474.

[3]Schutte JF， Reinbolt JA， Fregly BJ， Haftka RT， George AD. Parallel global optimization with particle swarm algorithm[J]. International Journal for Numerical Methods in Engineering 2009； 61：2296-2315.

[4]網(wǎng)格中執(zhí)行SLA的并行多群體協(xié)作PSO框架[J].計算機工程，VOL.34，NO.21，pp.190-192，2008-11

作者簡介：祁超，男，陜西三原人，蒙古族，陜西師范大學，副教授，主要研究方向：計算機網(wǎng)格。