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

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

關(guān)鍵詞：實驗室規(guī)劃;隨機微粒群算法;單純形法

中圖分類號：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）

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

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

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

2? 開放實驗室數(shù)據(jù)分析（Data analysis of open laboratory）

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

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

（1）學(xué)生單門實驗課時數(shù)需滿足本學(xué)期最小實驗學(xué)時要求Cmin;

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

設(shè)某一上課時段內(nèi)單臺電腦能耗函數(shù)為，某一種實驗室某一上課時段學(xué)時數(shù)為，實驗室能耗約束目標函數(shù)表示為：

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

3? ?算法（Algorithm）

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

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

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

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

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

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

Step4：混合全部微粒，將最優(yōu)值作為全局最優(yōu)值。

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

3.2? ?測試函數(shù)

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

（1）F1：Rastrigin函數(shù)

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

（2）F2：Griewank函數(shù)

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

3.3? ?實驗方法

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

3.3.1? ?實驗數(shù)據(jù)分析

Rastrigin函數(shù)更新周期、達優(yōu)次數(shù)、進化代數(shù)的關(guān)系如圖1（a）、圖1（b）所示，Griewank函數(shù)更新周期、達優(yōu)次數(shù)、進化代數(shù)的關(guān)系如圖1（c）、圖1（d）所示。

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

3.3.2? ?收斂性及結(jié)果分析

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

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

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

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

4.1? ?實驗室規(guī)劃基礎(chǔ)數(shù)據(jù)分析

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

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

4.2? ?實驗方法和實驗結(jié)果

參數(shù)選取：c1=c2=1.8，種群數(shù)num初始值設(shè)定為500，進化代數(shù)設(shè)定為3，000 代，k值取5。

使用SM-SPSO算法求解函數(shù)最優(yōu)值按照如下流程運行：

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

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

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

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

Step5：對其他組粒子重復(fù)Step2—Step4，完成所有粒子尋優(yōu)。

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

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

5? ?結(jié)論（Conclusion）

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

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

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

參考文獻（References）

[1] 劉宏炳.中醫(yī)藥學(xué)實驗教學(xué)平臺資源共享優(yōu)化模型建設(shè)與探索[J].新疆醫(yī)學(xué)，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] 楊亮.群體動畫行為自動控制的微粒群優(yōu)化算法[J].現(xiàn)代電子技術(shù)，2020，43（19）：106-110.

[5] 林棋.微粒群進階算法在天然氣管道優(yōu)化運行中的應(yīng)用[J].石油工業(yè)技術(shù)監(jiān)督，2020，36（8）：33-39.

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

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

2004：10-25.

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

作者簡介：

王建麗（1983-），女，碩士，實驗員.研究領(lǐng)域：最優(yōu)化理論及其應(yīng)用.