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

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

中圖分類號：TP301.6? ? ?文獻(xiàn)標(biāo)識碼：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）

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

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

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

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

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

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

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

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

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

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

3? ?算法（Algorithm）

3.1? ?改進(jìn)的隨機(jī)微粒群算法

隨機(jī)微粒群算法（Stochastic Particle Swarm Optimization， SPSO）進(jìn)化過程中每個(gè)粒子的更新方程為下式：

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

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

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

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

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

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

3.2? ?測試函數(shù)

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

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

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

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

在時(shí)達(dá)到全局極小值，局部極小值范圍為：

3.3? ?實(shí)驗(yàn)方法

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

3.3.1? ?實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

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

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

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

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

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

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

4.2? ?實(shí)驗(yàn)方法和實(shí)驗(yàn)結(jié)果

參數(shù)選?。篶1=c2=1.8，種群數(shù)num初始值設(shè)定為500，進(jìn)化代數(shù)設(shè)定為3，000 代，k值取5。

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

Step1：將粒子按照同一實(shí)驗(yàn)室種類k值分類。

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

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

Step4：按照SM-SPSO算法開始進(jìn)化。

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

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

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

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

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

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

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

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

[1] 劉宏炳.中醫(yī)藥學(xué)實(shí)驗(yàn)教學(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] 楊亮.群體動(dòng)畫行為自動(dòng)控制的微粒群優(yōu)化算法[J].現(xiàn)代電子技術(shù)，2020，43（19）：106-110.

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

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

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

2004：10-25.

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

作者簡介：

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