基于隨機微粒群算法的開放實驗室規劃研究

摘? 要：近年來，國家對高校實驗室教學平臺共享的要求逐步提高，如何低能耗開放和規劃實驗室利用是非常有意義的研究。為充分利用隨機微粒群算法的強局部搜索力和單純形法的多樣性，提出了一種改進的基于單純形法的隨機微粒群算法，通過數值實驗證明算法的有效性，并以實驗室電量優化為目標進行仿真，實驗表明本文算法能有效減少電量消耗。

關鍵詞：實驗室規劃;隨機微粒群算法;單純形法

中圖分類號：TP301.6? ? ?文獻標識碼：A

Research on Open Laboratory Planning based on

Stochastic Particle Swarm Optimization

WANG Jianli

（School of Computer Science and Technology， Taiyuan University of Science and Technology， Taiyuan 030024， China）

wangjianli@tyust.edu.cn

Abstract： In recent years， China has gradually increased the requirements for the sharing of university laboratory teaching platforms. How to open and plan laboratory utilization with low energy consumption is a very meaningful research. In order to make full use of the strong local search power of the stochastic particle swarm optimization and the diversity of the simplex algorithm， this paper proposes an improved stochastic particle swarm optimization based on the simplex algorithm. Numerical experiments show the effectiveness of the algorithm. Simulation is carried out with the goal of laboratory power optimization. Experiments show that the proposed algorithm can effectively reduce power consumption.

Keywords： laboratory planning; stochastic particle swarm optimization; simplex algorithm

1? ?引言（Introduction）

高校實驗室是進行實驗教學和科學研究的重要基地，近年來國家要求各高等學校加強專業實驗室、虛擬仿真實驗室、創業實驗室和訓練中心建設，促進實驗教學平臺共享[1]。目前，國內高校普遍存在校級公共實驗室、專業院級實驗室的重復建設，為了更好地管理和規劃開放實驗室，使資源配置和利用率均達到最優，本文提出規劃開放實驗室管理的目標函數，為合理開放實驗室提供了算法參考。

微粒群算法（Particle Swarm Optimization， PSO）作為一種智能優化算法[2-3]，是James Kennedy和Russell Eberhart于1995 年提出的。該算法一經提出被廣泛應用于很多實際優化問題，近幾年被應用于群體動畫行為自動控制[4]、天然氣管道的優化運行[5]、城鄉應急避難場所規劃[6]等。隨機微粒群算法是2004 年曾建潮等提出的一種改進微粒群算法[7]，其基本思想是在基本微粒群算法的基礎上，將基本微粒群進化方程中先前速度項的系數設為0，不保留先前的速度記憶，從而取消原有速度對新微粒的影響，提高局部搜索能力。

單純形法是求解線性規劃問題最常用、最有效的算法之一。單純形法最早由George Dantzig于1947 年提出[8]。單純形法的基本思路是：先找出可行域的一個頂點，根據一定規則判斷其是否最優;若不是最優值，則轉換到與之相鄰的另一頂點，并使目標函數值更優;如此下去，直到找到某最優解為止。

2? 開放實驗室數據分析（Data analysis of open laboratory）

隨著高校實驗室的全面開放，學生會根據自己的需求提出實驗申請，信息中心需為學生提供符合條件的實驗機房。如何合理地規劃機房選取，為學生提供優質實驗條件并最大程度避免資源浪費是一項有益的探索。本文采用結合單純形法改進的隨機微粒群算法對開放實驗室規模進行規劃設計，針對基本實驗學時要求、每種實驗室的利用率、同一類型實驗室內每臺電腦的利用率等多目標約束條件提出規劃函數，實驗仿真求解規劃函數，給出設計規劃開放實驗室的依據。

假定如下數學模型：將全校待安排的機房進行劃分，令其變成M 行、N 列的二維表格，則有M×N 個實驗室單元。假設一共存在K 種實驗室類型，表示單元（i，j），其中i=1，...，M;j=1，...，N;k=1，...，K。規劃實驗室總體目標為某一上機時間段內所有實驗室能耗最低，同時還需滿足以下條件：

（1）學生單門實驗課時數需滿足本學期最小實驗學時要求Cmin;

（2）同一類型的實驗室課時數盡量均衡。

設某一上課時段內單臺電腦能耗函數為，某一種實驗室某一上課時段學時數為，實驗室能耗約束目標函數表示為：

采用基于隨機微粒群算法規劃理論將規劃方案視為優化目標，將學生上機申請看作一個粒子群，對原始粒子群按照目標函數及其約束條件進行適當的評價，并經過不斷地更新，直到使其適應度達到最合適或者滿足進化代數為止。

3? ?算法（Algorithm）

3.1? ?改進的隨機微粒群算法

隨機微粒群算法（Stochastic Particle Swarm Optimization， SPSO）進化過程中每個粒子的更新方程為下式：

這種進化方式保證了全局收斂性。為充分利用隨機微粒群算法的強局部搜索力和單純形法的多樣性，同時提高隨機微粒群算法的進化速度和質量，本文提出了一種改進的基于單純形法的隨機微粒群算法（Simplex Method-Stochastic Particle Swarm Optimization， SM-SPSO），該算法的流程描述如下：

Step1：初始化算法基本參數，給隨機微粒群每個粒子的位置和速度賦初值。

Step2：奇數種群使用隨機微粒群算法進行進化，對于每代進化的微粒，將其當前適應值與之前的最優值進行比較，取其優者保留，如此進化R代。

Step3：偶數種群使用單純形法進化R代。

Step4：混合全部微粒，將最優值作為全局最優值。

Step5：判讀是否滿足精度要求，若是，退出程序;否則，其余較好微粒隨機分配給兩個子種群，重復Step2—Step5。

3.2? ?測試函數

為了說明SM-SPSO算法的有效性，本文選擇了兩個典型的多峰測試函數進行測試。

（1）F1：Rastrigin函數

在時達到全局極小值，在范圍內大約存在10 個局部極小值。

（2）F2：Griewank函數

在時達到全局極小值，局部極小值范圍為：

3.3? ?實驗方法

仿真實驗中，Rastrigin函數和Griewank函數的維數先取5 維實驗，再升至10 維。設置初始種群數為30 個粒子，迭代精度要求取值為0.01，進化3，000 代，c1、c2各取1.8，都分別進行50 次運算。統計收斂率和平均收斂代數，并分析結果。

3.3.1? ?實驗數據分析

Rastrigin函數更新周期、達優次數、進化代數的關系如圖1（a）、圖1（b）所示，Griewank函數更新周期、達優次數、進化代數的關系如圖1（c）、圖1（d）所示。

更新周期如果設置得太大，算法的全局搜索性能會嚴重下降;更新周期如果設置得太小，算法的通信代價會大大增加，所以綜合考慮設置算法更新周期為20。這樣在c1、c2和R取值相同的情況下，兩個函數平均收斂代數對比如圖2（a）、圖2（b）所示，平均收斂率對比如圖2（c）、圖2（d）所示。

3.3.2? ?收斂性及結果分析

本文提出的改進的隨機微粒群算法是隨機微粒群算法的分種群雙運行，只是進化過程中對較好微粒進行了混合、篩選，再重新分配，粒子更新仍然按照隨機微粒群算法的進化方程來更新，更新過程保存的全局極值點是比原先的極值點下降的，所以改進算法是一種保證全局收斂的算法。

分析圖1數據可以得出：對于Rastrigin函數和Griewank函數，本文提出的算法更新周期增加時，兩個函數的達優次數均比較穩定。更新周期對進化代數的影響包括：兩個函數5 維時隨著更新周期的增大，進化代數易隨之波動;但10 維時隨著更新周期增大，進化代數趨于穩定。

分析圖2數據，對于Rastrigin函數和Griewank函數，本文提出的改進的隨機微粒群算法在選取5 維、10 維時，兩個函數的平均收斂代數、平均收斂率均優于基本隨機微粒群算法，此數值實驗結果表明了算法的有效性。

4? ?改進隨機微粒群算法實驗室規劃分析（Laboratory?? ?planning analysis for improved stochastic? ? particle swarm optimization）

4.1? ?實驗室規劃基礎數據分析

設單個學生的申請為隨機微粒群算法的微粒，每個微粒設置為6 維微粒，指標分別為學號、課程名、申請時間、申請實驗室類型、實驗機器號、能耗值，即：stu=（stu0，stu1，stu2，stu3，stu4，stu5）T。

初始微粒隨機分配，假設實驗學校第k 種實驗室，擁有i個實驗房間，每個實驗房間有j 臺實驗儀器，某一門課要求的最少課時數量為Cmin;某一學期需要進行該項實驗學生數目為num，取種群規模為取整INT（num/（i×j×k））。實驗室規劃要求能耗函數值越低越好，課程課時數函數需大于規定課時數，選擇的實驗函數需是學校K（K≥0）種實驗室之一，由以上分析得到該實驗室規劃的多目標優化函數定義：

4.2? ?實驗方法和實驗結果

參數選?。篶1=c2=1.8，種群數num初始值設定為500，進化代數設定為3，000 代，k值取5。

使用SM-SPSO算法求解函數最優值按照如下流程運行：

Step1：將粒子按照同一實驗室種類k值分類。

Step2：對于每一類粒子，按照初始種群的num倍數分組。

Step3：選取一組隨機初始化粒子的stu4、stu5屬性參數。

Step4：按照SM-SPSO算法開始進化。

Step5：對其他組粒子重復Step2—Step4，完成所有粒子尋優。

Step6：判斷k值是否為0，若為0則退出程序;若不為0則k值減1，重復Step2—Step6。

選取24 個計算機實驗機房為例，每個機房有45 臺電腦可供使用，設定單日申請機房用量500 人，初始微粒隨機分布如圖3（a）所示，優化運算后微粒分布如圖3（b）所示。從圖中可以看出，以實驗室機房能耗最低化為目標函數進行微粒進化后，可以大大提高機房利用率。以單臺電腦開機12 小時耗能2.76 度電計算，每天至少節約1，117.8 度電。

5? ?結論（Conclusion）

（1）通過求解Rastrigin函數和Griewank函數表明：改進

的并行隨機微粒群算法的收斂率隨進化代數的增加而增加，單純形法的優化快速性在改進算法中得以體現。實驗結果表明：對同一個測試函數，在其維數、進化代數均相同的情況下，由于全部初始點均隨機產生，因此算法多樣性好。在進化的過程中，因為很好地結合了單純形法和隨機微粒群算法的特點，新算法的收斂速度和收斂率均明顯優于基本隨機微粒群算法。據此說明改進算法是保證全局收斂的有效算法。

（2）通過構造開放實驗室能耗多目標優化函數，并使用改進隨機微粒群算法求解該優化函數，仿真實驗表明了算法的有效性，為規劃開放實驗室、優化實驗室資源、提高設備利用率提供了一種參考。

參考文獻（References）

[1] 劉宏炳.中醫藥學實驗教學平臺資源共享優化模型建設與探索[J].新疆醫學，2020，8（5）：879-882.

[2] KANEMASA M， AIYOSHI E. Algorithm tuners for PSO methods and genetic programming techniques for learning tuning rules[J]. IEEE Trans on Electrical and Electronic Engineering， 2014， 9（4）：407-411.

[3] SUGIHARA K， TANAKA H. Interval evaluation in the analytic hierarchy process by possibility analysis[J]. Computational Intelligence， 2001， 17（3）：567-579.

[4] 楊亮.群體動畫行為自動控制的微粒群優化算法[J].現代電子技術，2020，43（19）：106-110.

[5] 林棋.微粒群進階算法在天然氣管道優化運行中的應用[J].石油工業技術監督，2020，36（8）：33-39.

[6] 黃揚飛.基于微粒群算法對城鄉應急避難場所規劃的研究[J].地震工程學報，2020，42（1）：236-241.

[7] 曾建潮，介婧，崔志華.微粒群算法[M].北京：科學出版社，

2004：10-25.

[8] 夏桂梅，曾建潮.一種基于單純形法的隨機微粒群算法[J].計算機工程與科學，2007，29（1）：90-92.

作者簡介：

王建麗（1983-），女，碩士，實驗員.研究領域：最優化理論及其應用.