云環境下多群體協作粒子群優化框架的研究

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

關鍵詞：粒子群優化；種群；群體；云計算

1 引言

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

2 多群體協作并行粒子群優化算法

2.1 并行粒子群優化算法

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

2.2 Multi-Swarm Cooperative PSO（MS-CPSO）

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

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

2.3 并行多群體協作PSO

可以想象在復雜異構的云環境中，將來執行粒子群優化算法的集群基本上分數不同的自治域，將并行機制與細顆粒度的粒子群優化算法合并構造出的多群體并行協作粒子群優化算法（Parallel Multi-swarm Cooperative PSO，PMCPSO）[4]成為關鍵所在。

3 云環境下分層并行多種群協作PSO框架

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

如圖2所示，該框架分為三層：主程序層（Master-program layer），云層（Mid-cloud layer），集群層（Inner-cluster layer）。

圖2 C-LPMCPSO框架結構圖

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

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

4 C-LPMCPSO性能研究

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

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

圖3 在C-LPMCPSO框架上最優化Rosenbrock問題的實驗結果圖

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

5 結束語

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

參考文獻

[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]網格中執行SLA的并行多群體協作PSO框架[J].計算機工程，VOL.34，NO.21，pp.190-192，2008-11

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