化學實驗室資源優(yōu)化配置的探索與實踐

田景芝， 荊 濤， 鄭永杰， 田志茗， 杜曉昕

(齊齊哈爾大學 a.化學與化學工程學院； b.計算機與控制工程學院， 黑龍江 齊齊哈爾 161006)

0 引 言

高校中化學實驗室無紙化資源管理的普及，電子化網(wǎng)絡(luò)化的管理模式給高校帶來了巨大的變革[1-2]。但隨著學?；瘜W實驗教學體系的不斷發(fā)展完善，實驗資源(如化學藥品、化學儀器和實驗場地)迅速增長，如何根據(jù)教學計劃對這些實驗資源進行智能的優(yōu)化配置成為當前亟待解決的難題[3-4]。在對資源進行合理優(yōu)化配置的時候，需要考慮的制約條件會很多，人工優(yōu)化配置顯然不可行，因此需要找到智能優(yōu)化算法來解決該問題[5-6]。粒子群算法[7]是一種較為新穎的智能仿生算法，成為了學者用來解決優(yōu)化求解問題的研究熱點。本文采用粒子群算法來設(shè)計化學實驗室無紙化資源管理中的優(yōu)化配置算法。

1 優(yōu)化配置問題描述

1.1 問題模型

化學實驗室無紙化資源配置問題是一個六維空間上的組合優(yōu)化問題[8-9]。六維空間定義為PZ(U,L,D,I,T,P)，其中，U為用戶維度，L為課程維度，D為化學藥品維度，I化學儀器維度、T為時間維度和P為實驗室維度。每個維度包含的實體集合如下。

用戶維度集合：U={U1,U2,…,Ux}，Ui表示第i個用戶。

課程維度集合：L={L1,L2,…,Ly}，Li表示第i門課程。

化學藥品維度集合：D={D1,D2,…,Dz}，Di表示第i種化學藥品申請數(shù)目，D*為D的子集即D*?D。

化學儀器維度集合：I={I1,I2,…,Ib}，Ii表示第i種化學儀器申請數(shù)目，I*為I的子集即I*?I。

時間維度集合：T={T1,T2,…,Th}，Ti表示第i個時間段。

實驗室維度集合：P={P1,P2,…,Pv}，Pi表示第i個實驗室。

則將求解問題的六維空間的所有集合元素做笛卡爾積S=U×L×D*×I*×T×P，便可得到該問題的求解空間。求解空間中每一個解記為：

其中max=x*y*z*b*h。

1.2 目標函數(shù)的定義

在解空間中不是所有的解都是需要的，也不是所有的解都是最優(yōu)的[10]，因為這些解是要滿足一些約束條件[11]。本文將其約束條件定義為過濾準則和優(yōu)化規(guī)則。

(1) 過濾規(guī)則(CR)。用戶在某一時間不能同時在多個實驗室上課；實驗室在某一時間不能同時承擔多門課。

輸入：

?

規(guī)則：

CR=

輸出：S1。

(2) 優(yōu)化規(guī)則(OR)。用戶如果連續(xù)更換實驗室，那么其距離不要過遠；用戶不宜連續(xù)進行多次試驗；實驗室、藥品和儀器分布盡可能均勻；獲得資源的等待時間要盡可能小。優(yōu)化準則定義為

min(con(Pi,Pj)∩Mean(D,I,P)∩Wait(D,I,P))

定義1(代價距離) 代價距離采用二維特征矩陣表示，假定用戶從Pi轉(zhuǎn)移到Pj。

(θ∈(0,1),A

根據(jù)特征矩陣可以求出實驗室間的距離為

其中:如果在同一個教學樓將其距離級別定義為A;在同一個校區(qū)的不同教學樓距離級別定義為B;在不同校區(qū)距離級別定義為C;N為Pi所在教學樓樓層最大數(shù);α為Pi所在的樓層數(shù);β為Pj所在樓層數(shù);這里設(shè)置A=0，B=1，C=2。代價距離越大,表示連續(xù)更換的實驗室間距離越遠。

定義2(均衡度) 解空間的均衡度為化學藥品均衡度、化學儀器均衡度和實驗室均衡度之和即

Mean(D,I,P)=Mean(D)+Mean(I)+Mean(P)

均衡度越小說明資源的均勻分布程度越好。

化學藥品均衡度定義為：

Mean(D)=13(z/x-Num(Ui1)()2+

z/y-Num(Li2)()2+z/h-Num(Ti5)()2)

其中,Num()用于統(tǒng)計D在U,L,T三個維度的每個分量上的總數(shù)。

化學儀器均衡度定義為：

Mean(I)=13(b/x-Num(Ui1)()2+

b/y-Num(Li2)()2+b/h-Num(Ti5)()2)

其中，Num()用于統(tǒng)計I在U,L,T三個維度的每個分量上的總數(shù)。

實驗室均衡度定義為：

Mean(P)=13(v/x-Num(Ui1)()2+

v/y-Num(Li2)()2+v/h-Num(Ti5)()2)

其中，Num()用于統(tǒng)計P在U,L,T三個維度的每個分量上的總數(shù)。

定義3(等待時間) 此處基于馬爾可夫排隊網(wǎng)絡(luò)[12]定義等待時間：

每一種資源的等待時間求解如下(以資源的個數(shù)為6為例)，求解方程為：

方程的解為：

其中，λ,a1,d1,a2,d2由抽樣及并行皮爾遜檢驗法獲得。

2 基于改進粒子群的問題求解算法

2.1 模型的實例化

本文采用粒子群算法[13-15]來求解化學實驗室無紙化資源優(yōu)化配置問題，需將粒子群算法進行實例化。其中Si=(Ui1,Li2,D,i3,Ii4,Ti5,Pi6)表示粒子群算法的第i粒子，適應度函數(shù)的定義要參照過濾準則和優(yōu)化準則，具體定義如下：

MIN(Con(Pi,Pj)∩Mean(D,I,P)∩Wait(D,I,P))

s.t.S∈CR

2.2 粒子群的改進

由于粒子算法如不加以改進，容易陷入局部極值，求解性能惡劣。因此本文對粒子群算法進行了改進，改進的思想主要來自于遺傳算法變異的思想，通過對那些陷入局部極值的粒子進行變異操作，可以使其跳出局部極值點，從而收斂于全局最優(yōu)解。

高斯分布是概率論和數(shù)理統(tǒng)計中一類重要的分布，高斯變異就是在粒子個體的任意一個分量上加上一個服從高斯分布的隨機擾動項。

本文對粒子Si=(Ui1,Li2,D,i3,Ii4,Ti5,Pi6)進行高斯變異，定義如下：

(3)

2.3 算法的實現(xiàn)

步驟1：對每個粒子的位置、速度和公告板進行初始化。

步驟2：通過式(1)計算每個粒子的適應度值。

步驟3：設(shè)置公告板1，公告板1記錄粒子經(jīng)過的最好位置，如果粒子的適應度值優(yōu)于公告板，則公告板1的值更新為當前粒子的適應度值。

步驟4：設(shè)置公告板2，公告板2記錄粒子群中粒子經(jīng)歷過的最好位置，如果新的粒子群中存在這樣的粒子，它的適應度值優(yōu)于當前公告板2的值，則公告板2的值更新為當前粒子的適應度值。

步驟5：更新每一個粒子的速度和位置。

步驟6：如果公告板2連續(xù)2次迭代過程中沒有改變或者變化很小(<β)，則轉(zhuǎn)向步驟7；否則轉(zhuǎn)向步驟8。

步驟7：將當前粒子群中最差粒子用公告板2中的最優(yōu)粒子取代得到了新的粒子群狀態(tài)，對新粒子群中最優(yōu)粒子按式(3)進行高斯變異，對變異后的最優(yōu)粒子和公告板2上的最優(yōu)粒子比較，取二者最優(yōu)的替換公告板2。

步驟8：判斷是否達到了是否已達到的最大迭代次數(shù)MaxIteration或最小準則，若不滿足，轉(zhuǎn)向步驟3；否則轉(zhuǎn)向步驟 9。

步驟 9： 算法終止，輸出公告板2中粒子和函數(shù)值。

3 仿真實驗分析

3.1 優(yōu)化前后實驗分析

這部分仿真實驗主要對采用本文算法優(yōu)化前后資源配置情況的對比分析，化學實驗室無紙化資源配置任務(wù)數(shù)為60、70、80、90、100、110、120、130、140、150、160學時，從資源利用率、資源請求等待時間和資源均衡度三個方面對比如表1所示。

表1 優(yōu)化前后資源配置對照表

由表1可知，通過本文的優(yōu)化配置算法可以大大提高資源的利用率和減小申請資源的等待時間。

3.2 性能對比分析

遺傳算法是最成熟以及應用最廣泛的尋優(yōu)算法，這部分仿真實驗主要是從優(yōu)化配置的運行時間、適應度值、代價距離和均衡度這四個方面，和遺傳算法[16]進行比較。仿真試驗中對于遺傳算法的控制參數(shù)設(shè)定為：種群規(guī)模為20，個體串長度為22，雜交概率為0.9，變異概率為0.01，最大遺傳代數(shù)為100；對于改進的粒子群算法控制參數(shù)設(shè)定為：種群規(guī)模為20，最大迭代次數(shù)為50。

化學實驗室無紙化資源配置任務(wù)數(shù)為60、90、160時，兩種算法各測20組數(shù)據(jù)取平均值，得到了平均運行時間見圖1，得到了平均適應度值見圖2。

圖1 運行時間對比

由圖1可知，本文算法平均運行時間遠遠低于遺傳算法，這說明了本文算法在對化學實驗室無紙化資源優(yōu)化配置中是快速的。

由圖2可知，本文算法的平均適應度值要遠遠高于遺傳算法，適應度函數(shù)可知，適應度函數(shù)值越低代表越接近最優(yōu)解。這也說明了本文算法在對化學實驗室無紙化資源優(yōu)化配置中是高效的。

此外任務(wù)書數(shù)從60離散變化到160學時，針對優(yōu)化準則中的代價距離和均衡度兩參數(shù)的對比結(jié)果如圖3和圖4所示。

圖3 代價距離對比

圖4 均衡度對比

由圖3可知，本文算法在進行資源配置時候，會使連續(xù)更換實驗室的距離很小，優(yōu)化配置性能遠遠高于遺傳算法。

由圖4可知，遺傳算法隨著任務(wù)書的逐漸增大，其均衡度會驟然變大，性能下降。而本文算法在人數(shù)很大的情況下，其均衡度依然變化緩慢，說明本文算法性能更優(yōu)。

4 結(jié) 語

在高?；瘜W實驗室無紙化資源優(yōu)化配置問題中，首先進行了數(shù)學建模，將該優(yōu)化問題抽象為一個六維解空間內(nèi)求最優(yōu)解的問題，提出了過濾準則和優(yōu)化準則及其相關(guān)定義，定義了適應度函數(shù)，采用粒子群算法進行最優(yōu)解的求解，設(shè)計出了基于粒子群的化學實驗室無紙化資源優(yōu)化配置算法。經(jīng)過仿真實驗證明，該算法具有運行速度快，性能高效等優(yōu)點。該算法具有很高的理論價值和實用價值，具有很高推廣空間。

[1] 王 睿．優(yōu)化實驗室資源配置，提高實驗室使用效能[J]．實驗室研究與探索，2011，30(10)：400-402．

WANG Rui. Optimizing the Configuration of Laboratory Resources and Improving the Efficiency of Laboratory Applications[J]. Research and Exploration in Laboratory, 2011, 30(10): 400-402.

[2] 盛蘇英，堵 俊，吳 曉．高校實驗室信息化管理的研究與實踐[J]．實驗室研究與探索，2012，31(12)：184-187.

SHENG Su-ying, DU Jun, WU Xiao. Laboratory Information Management in Colleges and Universities[J]. Research and Exploration in Laboratory, 2012, 31(12): 184-187.

[3] 董振旗，陳桂明，白志成，等．加強儀器設(shè)備管理提高教學保障效能[J]．實驗室研究與探索，2007，26(1)：128-130．

DONG Zhen-qi, CHEN Gui-ming, BAI Zhi-cheng,etal. Strengthening the Management of Instrument and Equipment to Enhance the Efficiency of Teaching Support[J]. Research and Exploration in Laboratory, 2007, 26(1) : 128-130.

[4] 蔡海燕，劉 昭．實驗室信息化管理初探[J].實驗室研究與探索，2010，29(9)：168-170．

CAI Hai-yan, LIU Zhao. Discussion on the Information Management of Laboratory[J]. Research and Exploration in Laboratory, 2010,29(9):168-170.

[5] 劉婷婷，張孝良，曹 萍．醫(yī)藥院校實驗室資源配置模式的探索[J]．實驗室研究與探索，2010，29(1)：156-158．

LIU Ting-ting, ZHANG Xiao-liang, CAO Ping. Exploration on Resources’ Configuration Pattern of Medical Universities[J]. Research and Exploration in Laboratory, 2010, 29(1): 156-158.

[6] 馬書剛，楊建華．虛擬組織服務(wù)資源的優(yōu)化配置模型[J]．計算機工程與應用，2012，48(23)：224-229.

MA Shu-gang, YANG Jian-hua. Optimal service resource allocation model for virtual organization. Computer Engineering and Applications[J]. Computer Engineering and Applications, 2012, 48(23): 224-229.

[7] 尹 呈，郭觀七，李文彬，等．基于自適應學習的多目標粒子群優(yōu)化算法[J]．計算機應用研究，2012，29(9)：3232-3235．

YIN Cheng，GUO Guan-qi，LI Wen-bin,etal. Multi-objective particle swarm optimization algorithm based on self-adaptive learning[J]. Application Research of Computers, 2012, 29(9):3232-3235.

[8] 魏國強，景 琳．多應急點資源優(yōu)化調(diào)度模型研究[J]．統(tǒng)計與決策，2010(2)：10-12．

WEI Guo-qiang, JING Ling. Research the Optimization Scheduling Model of Multi-Emergency Resources [J]. Statistics and Decision, 2010(2): 10-12.

[9] 胡飛虎，耿澤飛，陳慧敏，等．多資源組合多目標應急調(diào)度問題的研究[J]．微計算機信息，2009，25(7)：9-10．

HU Fei-hu, GENG Ze-fei, CHEN Hui-min,etal. Research of Multi-Resource Combinatorial and Multi-Objective Scheduling Problem in Emergency Systems[J]. Microcomputer Information, 2009, 25(7): 9-10.

[10] 孫 敏，潘 郁．多資源復雜網(wǎng)絡(luò)的應急調(diào)度研究[J]．運籌與管理，2009，18(6)：165-169．

SUN Min, PAN Yu. Multi-resource Emergency Scheduling Based on Complex-network[J]. Operations Research and Management Science, 2009, 18(6): 165-169.

[11] 劉士新．項目優(yōu)化調(diào)度理論與方法[M]．北京：機械工業(yè)出版社，2006：26-58．

[12] 張于賢，于 明，葉冰冰．基于開排隊理論的生產(chǎn)線設(shè)備資源優(yōu)化配置[J]．系統(tǒng)科學學報，2012，20(3)：75-78．

ZHANG Yu-xian, YU Ming, YE Bing-bing. Optimum Distribution of Equipment Resources in Production Line Based on Open Queuing Network[J]. Journal of Systems Science, 2012, 20(3): 75-78.

[13] 張 凱，趙國榮，姜 靜．資源約束項目調(diào)度問題的粒子群優(yōu)化算法求解[J]．海軍航空工程學院學報，2009，24 (5 )：578 -582．

ZHANG Kai, ZHAO Guo-rong, JIANG Jing. Particle Swarm Optimization Algorithm for Resource-Constrained Project Scheduling Problem[J]. Journal of Naval Aeronautical and Astronautical University, 2009, 24 (5): 578-582.

[14] 劉軍民，高岳林．混沌粒子群優(yōu)化算法[J]．計算機應用，2008，28(2)：322-325．

LIU Jun-min, GAO Yue-lin. Chaos particle swarm optimization algorithm [J]. Computer Applications, 2008, 28(2): 322-325.

[15] 王華秋，曹長修．并行混沌粒子群優(yōu)化研究及應用[J]．計算機仿真，2005，22(11)： 98-101．

WANG Hua-qiu, CAO Chang- xiu. Research and Application of Parallel Chaos Particle Swarm Optimization[J]. Computer Simulation, 2005, 22(11): 98-101.

[16] 崔海波，曾 熠．基于改進遺傳算法的資源優(yōu)化配置研究[J]．計算機仿真，2008，25(6)：173-176．

CUI Hai-bo, ZENG Yi. Scheduling Resources Based on Improved Genetic Algorithm[J]. Computer Simulation, 2008, 25(6): 173-176.

把改革創(chuàng)新作為教育發(fā)展的強大動力。教育要發(fā)展，根本靠改革。要以體制機制改革為重點，鼓勵地方和學校大膽探索和試驗，加快重要領(lǐng)域和關(guān)鍵環(huán)節(jié)改革步伐。創(chuàng)新人才培養(yǎng)體制、辦學體制、教育管理體制，改革質(zhì)量評價和考試招生制度，改革教學內(nèi)容、方法、手段，建設(shè)現(xiàn)代學校制度。加快解決經(jīng)濟社會發(fā)展對高質(zhì)量多樣化人才需要與教育培養(yǎng)能力不足的矛盾、人民群眾期盼良好教育與資源相對短缺的矛盾、增強教育活力與體制機制約束的矛盾，為教育事業(yè)持續(xù)健康發(fā)展提供強大動力。

——摘自《國家中長期教育改革和發(fā)展規(guī)劃綱要》