李舒明

（福建船政交通職業(yè)學(xué)院 航海學(xué)院，福建 福州 350007）

蟻群算法自20世紀(jì)90年代提出之后，經(jīng)過不斷地改善被應(yīng)用于工作指派、旅游求決、車輛調(diào)度等眾多領(lǐng)域[1]。其仿生學(xué)算法功能被廣泛開發(fā)之后，具有較強的動態(tài)約束能力，不僅可以解決離散域問題，還可以解決連續(xù)域問題，其技術(shù)能力在我國研究領(lǐng)域開發(fā)程度更深，被傳播范圍也更為廣闊[2]。高校實驗室預(yù)約智能化指高校實驗室預(yù)約管理中用計算機(jī)智能手段改進(jìn)人工管理手段的過程。當(dāng)前我國高校實驗室管理過程中，將較多的精力投入到實驗室設(shè)備、技術(shù)、環(huán)境的更新?lián)Q代方面，忽視或很少關(guān)注實驗室設(shè)備管理、設(shè)備調(diào)度、教學(xué)實驗安排等柔性管理領(lǐng)域[3]，從而導(dǎo)致實驗室資源利用效率低下、浪費嚴(yán)重、實驗進(jìn)度遲滯等問題。為改善當(dāng)前我國高校實驗室管理現(xiàn)狀，引入蟻群優(yōu)先排序算法，結(jié)合具體高校實驗室管理結(jié)構(gòu)，實現(xiàn)實驗室預(yù)約智能化。

1 面向蟻群算法的開放式實驗室預(yù)約智能系統(tǒng)優(yōu)化設(shè)計

1.1 系統(tǒng)預(yù)約算法優(yōu)化設(shè)計

蟻群算法優(yōu)先排序原則指出，螞蟻在進(jìn)行最優(yōu)路徑選擇之前首先須形成一個螞蟻個體，螞蟻個體須具有協(xié)作機(jī)制，其次具備信息素遺留能力即螞蟻的記憶能力，最后通過信息素遺留情況，在多個螞蟻協(xié)作的條件下進(jìn)行最短路徑選擇[4]。在遇到路徑破壞情況時，還具有再次協(xié)作進(jìn)行重新最短路徑選擇的再生能力[5]。

根據(jù)蟻群算法原則實驗室預(yù)約過程中，須首先進(jìn)行個體間協(xié)作構(gòu)造，即同類相識進(jìn)行拾起放下過程。以單個學(xué)生進(jìn)行預(yù)約機(jī)制為例，假定學(xué)生A為起始測試對象，則虛擬起始學(xué)生A會按照相似度決定是否拾起另一個隨機(jī)測驗對象，如果兩者不相似則學(xué)生A會在大概率范圍內(nèi)重新轉(zhuǎn)移拾起地點，直到找到相似對象地點。如果二者相似則會進(jìn)行拾起動作，進(jìn)行路徑確認(rèn)并產(chǎn)生信息素進(jìn)行放下動作。再此尋找下一個物體進(jìn)行以上相似度“拾起—放下—拾起”過程[5]。在經(jīng)過數(shù)次迭代過程之后，整個算法才會結(jié)束。如以上分析，若一學(xué)生A在網(wǎng)格r的位置上遇到拾起對象Oi，則Oi與周圍物體的相似度計算公式為

式中：Neighs×s（r）為學(xué)生A在r的位置所能夠涉及到的全部范圍，由于蟻群算法自身的特點限制，圍是一個以r為中心的圓形區(qū)域。d（Oi，Oj）表示學(xué)生A從位置Oi到位置Oj的距離。n表示學(xué)生A在位置r能夠接收到的所有學(xué)生的信息量。α為學(xué)生群體相似度系數(shù)，在相似度計算中，α的值越大則相似度值越大，此時由于對象Oi與對象Oj的區(qū)分度過小，會加大算法的收斂速度，也會造成將本不相似的對象群體歸為一類的現(xiàn)象。反之，則相似度值較小，區(qū)分度較大，收斂速度會提升，也會加大對象群體的區(qū)分水平。在相似度迭代計算中，將拾起概率設(shè)為Pp，放下概率設(shè)為Pd，值在[0，1]，則一個循環(huán)過程中局部相似度計算為

局部相似度由拾起概率與放下概率共同決定。在公式（2）中，k1與k2都為閾值常量，且在拾起與放下的過程中都會產(chǎn)生一個隨機(jī)數(shù)R，如果拾起與放下概率的值大于R，則進(jìn)行拾起或放下工作，反之繼續(xù)移動。根據(jù)公式（2）可知，拾起與放下概率與f（Oi）相關(guān)。f（Oi）值大時，Pp值越小，Pd值越大，表明此時易進(jìn)行放下動作，不易進(jìn)行拾起動作。反之f（Oi）值小時，Pd越小，Pp值越大。

在重復(fù)進(jìn)行拾起與放下動作時，由于不同的螞蟻之間的權(quán)值不同，因此在一個緊密預(yù)約周期內(nèi)要盡量避免學(xué)生預(yù)約重復(fù)現(xiàn)象出現(xiàn)。信息素即權(quán)值在每一輪計算中都具有蒸發(fā)過程，即每一輪計算都必須排除前一輪過程中的較差路徑。為避免重復(fù)預(yù)約現(xiàn)象出現(xiàn)，假設(shè)預(yù)約學(xué)生數(shù)為n，信息蒸發(fā)的概率為ρ，規(guī)定0＜ρ＜1，一般情況下將ρ值定位0.5，則第k個學(xué)生在t預(yù)約時刻的信息素量為Δτij，計算結(jié)果為

在學(xué)生未進(jìn)行預(yù)約選擇，在起始時刻時候，則其預(yù)約信息素大小用τ表示，設(shè)置為τ0。則τ0的大小直接決定學(xué)生信息素的遺留能力及學(xué)生個體間的協(xié)作機(jī)制，當(dāng)τ0太小時，（1-ρ）τij值較小，則學(xué)生個體進(jìn)行一次選擇之后所留信息素較少。此時信息素對學(xué)生預(yù)約選擇概率影響較大，學(xué)生進(jìn)行自由選擇的概率將縮小，提高收斂速度。反之當(dāng)τ0值過大時，信息素對學(xué)生個體為構(gòu)造能力影響較小，將不利于后來學(xué)生對先前路徑的優(yōu)劣感知，不利于路徑合理性的構(gòu)建。為確定τ0值的合理性，在具體設(shè)計算法設(shè)計過程中，引入貪婪算法中節(jié)點之間的路徑長度Cn，使τ0=n/Cn。

為增強收斂速度，減少因個人預(yù)約造成的預(yù)約通道擁堵或者稀少問題，提高整個聚類過程的有效性、魯棒性及算法收斂速度[6]。在相似度聚類過程中，對學(xué)生A的觀察半徑及概率轉(zhuǎn)換函數(shù)變量進(jìn)行優(yōu)化控制，采用觀察前后階段半徑發(fā)生先由大變小后由小變大的方法，對收斂速度進(jìn)行改進(jìn)，半徑變化公式為

式中：Tmax為全部計算過程中的迭代次數(shù)，n（t）為局部迭代次數(shù)，s（t+1）表示學(xué)生在進(jìn)行第t+1次迭代使得觀察半徑，Int（）表示向下取整函數(shù)，N和M分別表示觀察半徑的下界與上界M=s（0），算法每迭代一次半徑縮減或增加值為1。

在拾起與放下概率轉(zhuǎn)換過程中，學(xué)生預(yù)約過程之間的距離d（Oi，Oj）采用歐式計算法則。但是在學(xué)生相似度計算過程中，不僅要考慮對象之間的相似度，還需考慮兩個正在使用預(yù)約系統(tǒng)的學(xué)生之間的選擇趨勢是否相似。因此研究在距離控制變量中加入余弦距離計算，使距離線性之間的互補效果更加明顯。距離變量控制為

除了考慮到距離之間的趨勢因素之外，實驗室預(yù)約計算過程中還應(yīng)加入對相似度動作速度的考量。研究設(shè)定前期相似度迭代速度較快后期速度較慢，迭代過程中通過速度的改變，可以在快速的整理對象的分類數(shù)目，提高對象組合的精細(xì)度[8]。速度設(shè)定之后的相似度計算為

由于蟻群算法更新規(guī)則往往只是加強每次迭代最短路徑時的信息素濃度，而信息素濃度的增加會造成算法只對出局部最優(yōu)解進(jìn)行計算，因此需要將每次迭代的最優(yōu)解結(jié)果充分利用，才可以找到局部與全局最優(yōu)解之間的關(guān)聯(lián)。所以在本次研究中引入最優(yōu)解控制參數(shù)中的自適應(yīng)動態(tài)因子σ（σ∈（0,1）），其主要對單次迭代最優(yōu)解信息素濃度的更新比重進(jìn)行自適應(yīng)控制，加大優(yōu)秀路徑的信息素濃度，進(jìn)而更好的顯示路徑信息。全局更新每次迭代完成后的最優(yōu)路徑信息素濃度的規(guī)則為

式中：τij（t+1）為示第t+1次迭代時在節(jié)點i和節(jié)點j之間路徑上的信息素強度。自適應(yīng)動態(tài)因子其中：γ表示控制反正切函數(shù)形狀的參數(shù)表示目前能夠通過搜索到的局部最優(yōu)路徑的平均長度；Lmin表示當(dāng)前全局最優(yōu)解；表示本次目前能夠通過搜索到的局部最優(yōu)路徑的長度。σ的反正切函數(shù)為

結(jié)合式（9）、式（10）來看反正切函數(shù)f（x）具有平滑的輸出曲線，范圍在［0,1］之間。若Llocalmin值越高且搜索路徑越長時，σ值越靠近0；反之，σ值越靠近1。在不同參數(shù)γ下f（x）與經(jīng)典蟻群算法的σ曲線對比，如圖1所示。

圖1 動態(tài)因子函數(shù)曲線圖Fig.1 Curve of dynamic factor function

1.2 系統(tǒng)預(yù)約流程優(yōu)化設(shè)計

實驗室預(yù)約過程中，由于用戶對實驗室設(shè)備資源的不熟悉，會造成部分設(shè)備使用過度，而部分設(shè)備長期閑置的現(xiàn)象[6]。為提高設(shè)備使用效率，提高用戶對設(shè)備資源的合理利用。按照設(shè)備信息狀況對實驗室設(shè)備預(yù)約系統(tǒng)進(jìn)行兩種模式流程設(shè)計并優(yōu)化[6]。

一種流程是針對在一個周期內(nèi)（一周），設(shè)備使用頻率不足設(shè)備使用最高負(fù)荷。則表明在此周期內(nèi)，可根據(jù)具體使用設(shè)備情況，在保留原設(shè)備預(yù)約安排的前提下，進(jìn)行空余時間篩選并安排新的預(yù)約請求，直接生成到結(jié)果計算中，設(shè)計流程如圖2所示。

圖2 預(yù)約模式一流程圖Fig.2 Flow chart of reservation mode 1

如圖2所示，用戶在登錄界面之后，變會進(jìn)入預(yù)約請求界面，可進(jìn)行最近一周期內(nèi)實驗預(yù)約請求。在用戶進(jìn)行預(yù)約篩選之前，計算機(jī)系統(tǒng)會對當(dāng)前已經(jīng)存在的預(yù)約請求和空余時間進(jìn)行計算并生成結(jié)果。若當(dāng)前預(yù)約時間小于設(shè)備可使用時間，則根據(jù)用戶意愿則進(jìn)入預(yù)約界面并形成預(yù)約結(jié)果。保證下一位預(yù)約用戶正常選擇同時也可保證系統(tǒng)的穩(wěn)定性與準(zhǔn)確性。

若一個周期內(nèi)設(shè)備使用量高于設(shè)備可使用時間，則需要對用戶請求進(jìn)行合理配置。在系統(tǒng)開始之前根據(jù)設(shè)備一周期可使用時間進(jìn)行容量設(shè)定[7]。在具體預(yù)約操作過程中，以最大預(yù)約數(shù)為界限，按照預(yù)約時間先后順序，對超出使用容量的客戶進(jìn)行攔截。并按照最優(yōu)路徑計算方法，對攔截客戶進(jìn)行最優(yōu)預(yù)約結(jié)果進(jìn)行處理。具體操作流程如圖3所示。

圖3 預(yù)約模式二流程圖Fig.3 Flow chart of reservation mode 2

如圖3所示，對于第二種預(yù)約模式中被攔截的用戶進(jìn)行重新路徑計算，按照周期內(nèi)實驗次數(shù)最少，設(shè)備利用最小，可使用率較高原則，進(jìn)行重新預(yù)約安排。蟻群計算最優(yōu)計算結(jié)果如圖4所示。

圖4 預(yù)約模式二過程優(yōu)化計算過程流程圖Fig.4 The flow chart of the optimization calculation process of reservation mode 2

如圖4所示，按照相似度原則分別對設(shè)備數(shù)量、使用時間、損耗程度進(jìn)行控制。在具體的預(yù)約程序中設(shè)備數(shù)量與時間是一一對應(yīng)的關(guān)系，因此首先對時間和設(shè)備量進(jìn)行控制。從預(yù)約信息的第一條開始，對預(yù)約設(shè)備損耗進(jìn)行計算。計算每一條預(yù)約信息之前都需要對該預(yù)約進(jìn)行計算與否判斷，若無計算則進(jìn)入計算流程，若已計算則進(jìn)入下一條預(yù)約記錄，直至所有預(yù)約記錄計算完成為止。通過對預(yù)約設(shè)備損耗程度的累計結(jié)果與可使用損耗累計結(jié)果對比判斷預(yù)約請求并生成結(jié)果。按照以上操作流程對實驗室設(shè)備管理智能化流程實現(xiàn)如圖5所示。

圖5 開放式實驗室預(yù)約智能管理程序設(shè)計流程圖Fig.5 Flow chart of design of intelligent management program for open laboratory appointment

如圖5所示開發(fā)式高校實驗室預(yù)約智能系統(tǒng)，不僅涉及前臺用戶的管理設(shè)計，更為重要的是后臺運行控制設(shè)計[7]。在最優(yōu)路徑幾率型蟻群算法控制下，算法模型的建構(gòu)可以實現(xiàn)后臺參數(shù)的最優(yōu)計算參數(shù)設(shè)定，在流程模型的優(yōu)化設(shè)計可以為前臺用戶提供更為快捷的預(yù)約服務(wù)、查詢服務(wù)、監(jiān)護(hù)服務(wù)、設(shè)備錄入及更新服務(wù)，極大提高整個開放式高校實驗室預(yù)約智能系統(tǒng)使用效率。

2 基于蟻群算法的開放式高校實驗室預(yù)約系統(tǒng)評測

2.1 系統(tǒng)優(yōu)化路徑評測

在殘留信息的相對重要程度取值為3，期望值的取值為1，信息素的揮發(fā)系數(shù)，信息素更新常數(shù)為5，信息素更新時間控制在[1，5]之間。分別選取規(guī)模為8×6，55×49，110×98，350×487條件下，對12名學(xué)生進(jìn)行50次路徑選擇評測。最終生成貪心算法、HGS算法、GRE算法和蟻群算法的對比結(jié)果如圖6所示。

圖6 幾種算法最優(yōu)解及誤差對比分析結(jié)果Fig.6 Optimal solutions and error comparison analysis results of several algorithms

從圖6（a）為各種算法在不同規(guī)模下的最優(yōu)解對比，圖6（b）為各種算法在不同規(guī)模下的偏差對比。從5（a）中可以看出，在小規(guī)模測試結(jié)果中，各種算法結(jié)果不存在較大差別，甚至結(jié)果基本一致，都能夠得到與已知最優(yōu)解一致的答案。但是隨著規(guī)模的增大，蟻群算方法的最優(yōu)解分別為2.87、2.12、3.28，相對于其他三種算法而言，其最優(yōu)解相對于已知最優(yōu)解而言，偏差趨勢明顯提高，偏差度顯著降低。圖6（b）中從誤差對比結(jié)果分析可得規(guī)模為55×49時，誤差率為4.4%；規(guī)模為110×98時，誤差率為6.1%；規(guī)模為350×487時，誤差率為9.0%。平均誤差率降低6.5%左右。相比于其他幾種算法誤差率平均降低7.5%。誤差率顯著降低，提高系統(tǒng)計算精準(zhǔn)度，能夠為高校實驗室預(yù)約智能提供良好的設(shè)計效果。

2.2 系統(tǒng)運行時間評測

對高校實驗室預(yù)約智能系統(tǒng)進(jìn)行有效評測，除要考慮系統(tǒng)運行的精準(zhǔn)度之外，一個重要參數(shù)就是計算時間的評測。較短的計算時間可以直接提高系統(tǒng)的使用效率，增強系統(tǒng)流程度，減小系統(tǒng)因計算量過大而導(dǎo)致的崩潰現(xiàn)象，提高學(xué)生使用感受。在原有參數(shù)不變情況下對個算法計算時間進(jìn)行對比分析，結(jié)果如圖7所示。

圖7 四種規(guī)模下不同算法的對比結(jié)果Fig.7 Comparison results of different algorithms at four scales

由于不同規(guī)模條件下規(guī)模計算所需時間差距較大，因此將8×6，55×49，110×98和350×487規(guī)模按照兩兩對比形式分開對比，以更加清晰的比較四種算法計算時間差距。圖7（a）為8×6和55×49規(guī)模對比結(jié)果，圖7（b）為110×98和350×487規(guī)模對比結(jié)果。從圖7中可以看出，無論是哪種規(guī)模下，相較于其他三種算法蟻群分析算法的計算時間都較短。規(guī)模分別為8×6，55×49，110×98和350×487時，蟻群算法的計算時間分別為7、52、110、340 s。相較于其他三種算法，計算時間平均縮短分別為2、28.67、93.33、310 s。極大程度上縮短計算時間，并且隨著規(guī)模的不斷擴(kuò)大，蟻群算法在計算時間方面的優(yōu)勢就更為明顯。表明在蟻群算法指導(dǎo)下，高校實驗室預(yù)約智能系統(tǒng)的設(shè)計具有較強的合理性。

2.3 系統(tǒng)運行效應(yīng)評測

相較于系統(tǒng)運行路徑與時間的優(yōu)勢，蟻群算法不僅能夠?qū)崿F(xiàn)局部區(qū)域優(yōu)化，更為重要的是它能夠在實現(xiàn)局部優(yōu)化的基礎(chǔ)上，進(jìn)一步實現(xiàn)全局優(yōu)化。不僅能夠?qū)崿F(xiàn)離散域的優(yōu)化，更能夠?qū)崿F(xiàn)連續(xù)性的系統(tǒng)優(yōu)化。在原有參數(shù)不變的情況下，選取貪心算法與蟻群算法進(jìn)行對比分析，結(jié)果如圖8所示。

圖8 貪心算法與蟻群算法50最優(yōu)路徑選擇對比結(jié)果Fig.8 Comparison results of optimal path selection between greedy algorithm and ant colony algorithm 50

圖8（a）、（b）分別為貪心算法和蟻群算法對學(xué)生和教師50次最優(yōu)路徑選擇中的其中一次迭代仿真結(jié)果。從圖8（a）中可以看出，基于貪心算法的最優(yōu)解大于470，而優(yōu)化設(shè)計后的蟻群算法最優(yōu)解小于460。從圖8（b）中可以看出，基于貪心貪心算法的最優(yōu)解大于520，而優(yōu)化設(shè)計后的蟻群算法最優(yōu)解小于510。并且兩幅圖都表現(xiàn)出，蟻群算法的曲線都率先實現(xiàn)節(jié)點轉(zhuǎn)折。這表明蟻群算法相較于貪婪算法而言，能夠優(yōu)先跳出局部最優(yōu)，進(jìn)而實現(xiàn)全局最優(yōu)目標(biāo)。

3 結(jié)論

高校實驗室預(yù)約智能化系統(tǒng)建構(gòu)的合理性，不僅能夠極大程度上減少設(shè)備損耗、提高設(shè)備使用效率，還能夠降低人工成本、提高學(xué)生的實驗?zāi)芰?，從而增強高校教學(xué)實力?；诖搜芯恳胂伻核惴ǎ瑢︻A(yù)約系統(tǒng)的預(yù)約算法及流程進(jìn)行優(yōu)化設(shè)計，建立起高校實驗室預(yù)約智能管理系統(tǒng)并對其進(jìn)行了效用評測。結(jié)果表明，經(jīng)過優(yōu)化設(shè)計后的高校實驗室預(yù)約系統(tǒng)，其計算偏差在規(guī)模分別為55×49，110×98，350×487時，誤差率分別為4.4%、6.1%、9.0%。平均誤差率在6.5%左右，相比于其他幾種算法誤差率平均降低7.5%，極大提高了系統(tǒng)計算精準(zhǔn)度。同時相比于其他三種算法平均計算時間分別降低2、28.67、93.33、310 s，極大提高了系統(tǒng)計算時間。除此之外還能夠?qū)崿F(xiàn)較高程度的全局優(yōu)化能力，驗證了系統(tǒng)建構(gòu)的合理性。