蟻群算法下的開放式高校實驗室預約系統(tǒng)優(yōu)化

李舒明

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 基于蟻群算法的開放式高校實驗室預約系統(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名學生進行50次路徑選擇評測。最終生成貪心算法、HGS算法、GRE算法和蟻群算法的對比結果如圖6所示。

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

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

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

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

圖7 四種規(guī)模下不同算法的對比結果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ī)模對比結果，圖7（b）為110×98和350×487規(guī)模對比結果。從圖7中可以看出，無論是哪種規(guī)模下，相較于其他三種算法蟻群分析算法的計算時間都較短。規(guī)模分別為8×6，55×49，110×98和350×487時，蟻群算法的計算時間分別為7、52、110、340 s。相較于其他三種算法，計算時間平均縮短分別為2、28.67、93.33、310 s。極大程度上縮短計算時間，并且隨著規(guī)模的不斷擴大，蟻群算法在計算時間方面的優(yōu)勢就更為明顯。表明在蟻群算法指導下，高校實驗室預約智能系統(tǒng)的設計具有較強的合理性。

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

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

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

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

3 結論

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