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

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

0 引 言

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

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

1.1 問(wèn)題模型

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

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

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

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

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

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

實(shí)驗(yàn)室維度集合：P={P1,P2,…,Pv}，Pi表示第i個(gè)實(shí)驗(yàn)室。

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

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

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

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

(1) 過(guò)濾規(guī)則(CR)。用戶在某一時(shí)間不能同時(shí)在多個(gè)實(shí)驗(yàn)室上課；實(shí)驗(yàn)室在某一時(shí)間不能同時(shí)承擔(dān)多門(mén)課。

輸入：

?

規(guī)則：

CR=

輸出：S1。

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

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

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

(θ∈(0,1),A

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

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

定義2(均衡度) 解空間的均衡度為化學(xué)藥品均衡度、化學(xué)儀器均衡度和實(shí)驗(yàn)室均衡度之和即

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

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

化學(xué)藥品均衡度定義為：

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

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

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

化學(xué)儀器均衡度定義為：

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

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

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

實(shí)驗(yàn)室均衡度定義為：

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

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

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

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

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

方程的解為：

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

2 基于改進(jìn)粒子群的問(wèn)題求解算法

2.1 模型的實(shí)例化

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

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

s.t.S∈CR

2.2 粒子群的改進(jìn)

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

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

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

(3)

2.3 算法的實(shí)現(xiàn)

步驟1：對(duì)每個(gè)粒子的位置、速度和公告板進(jìn)行初始化。

步驟2：通過(guò)式(1)計(jì)算每個(gè)粒子的適應(yīng)度值。

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)分析

3.1 優(yōu)化前后實(shí)驗(yàn)分析

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

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

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

3.2 性能對(duì)比分析

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

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

圖1 運(yùn)行時(shí)間對(duì)比

由圖1可知，本文算法平均運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)低于遺傳算法，這說(shuō)明了本文算法在對(duì)化學(xué)實(shí)驗(yàn)室無(wú)紙化資源優(yōu)化配置中是快速的。

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

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

圖3 代價(jià)距離對(duì)比

圖4 均衡度對(duì)比

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

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

4 結(jié) 語(yǔ)

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

[1] 王 睿．優(yōu)化實(shí)驗(yàn)室資源配置，提高實(shí)驗(yàn)室使用效能[J]．實(shí)驗(yàn)室研究與探索，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] 盛蘇英，堵 俊，吳 曉．高校實(shí)驗(yàn)室信息化管理的研究與實(shí)踐[J]．實(shí)驗(yàn)室研究與探索，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] 董振旗，陳桂明，白志成，等．加強(qiáng)儀器設(shè)備管理提高教學(xué)保障效能[J]．實(shí)驗(yàn)室研究與探索，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] 蔡海燕，劉 昭．實(shí)驗(yàn)室信息化管理初探[J].實(shí)驗(yàn)室研究與探索，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ī)藥院校實(shí)驗(yàn)室資源配置模式的探索[J]．實(shí)驗(yàn)室研究與探索，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] 馬書(shū)剛，楊建華．虛擬組織服務(wù)資源的優(yōu)化配置模型[J]．計(jì)算機(jī)工程與應(yīng)用，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īng)學(xué)習(xí)的多目標(biāo)粒子群優(yōu)化算法[J]．計(jì)算機(jī)應(yīng)用研究，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] 魏國(guó)強(qiáng)，景 琳．多應(yīng)急點(diǎn)資源優(yōu)化調(diào)度模型研究[J]．統(tǒng)計(jì)與決策，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] 胡飛虎，耿澤飛，陳慧敏，等．多資源組合多目標(biāo)應(yīng)急調(diào)度問(wèn)題的研究[J]．微計(jì)算機(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] 孫 敏，潘 郁．多資源復(fù)雜網(wǎng)絡(luò)的應(yīng)急調(diào)度研究[J]．運(yùn)籌與管理，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] 劉士新．項(xiàng)目?jī)?yōu)化調(diào)度理論與方法[M]．北京：機(jī)械工業(yè)出版社，2006：26-58．

[12] 張于賢，于 明，葉冰冰．基于開(kāi)排隊(duì)理論的生產(chǎn)線設(shè)備資源優(yōu)化配置[J]．系統(tǒng)科學(xué)學(xué)報(bào)，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] 張 凱，趙國(guó)榮，姜 靜．資源約束項(xiàng)目調(diào)度問(wèn)題的粒子群優(yōu)化算法求解[J]．海軍航空工程學(xué)院學(xué)報(bào)，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]．計(jì)算機(jī)應(yīng)用，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] 王華秋，曹長(zhǎng)修．并行混沌粒子群優(yōu)化研究及應(yīng)用[J]．計(jì)算機(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] 崔海波，曾 熠．基于改進(jìn)遺傳算法的資源優(yōu)化配置研究[J]．計(jì)算機(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ā)展的強(qiáng)大動(dòng)力。教育要發(fā)展，根本靠改革。要以體制機(jī)制改革為重點(diǎn)，鼓勵(lì)地方和學(xué)校大膽探索和試驗(yàn)，加快重要領(lǐng)域和關(guān)鍵環(huán)節(jié)改革步伐。創(chuàng)新人才培養(yǎng)體制、辦學(xué)體制、教育管理體制，改革質(zhì)量評(píng)價(jià)和考試招生制度，改革教學(xué)內(nèi)容、方法、手段，建設(shè)現(xiàn)代學(xué)校制度。加快解決經(jīng)濟(jì)社會(huì)發(fā)展對(duì)高質(zhì)量多樣化人才需要與教育培養(yǎng)能力不足的矛盾、人民群眾期盼良好教育與資源相對(duì)短缺的矛盾、增強(qiáng)教育活力與體制機(jī)制約束的矛盾，為教育事業(yè)持續(xù)健康發(fā)展提供強(qiáng)大動(dòng)力。

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