勤務系統執勤自動化排班研究

摘 要： 在開發的武警勤務管理系統中，應用自適應遺傳算法對勤務執勤的自動化排班進行了研究。根據武警勤務特點建立了一系列的約束條件模型，設計了相應的目標函數，適應度函數和遺傳算子，最終在勤務系統自動化排班中取得了較為理想的效果。

關鍵詞： 遺傳算法； 自適應遺傳算法； 人員排班； 勤務管理系統

中圖分類號： TN911?34； TP18 文獻標識碼： A 文章編號： 1004?373X（2015）07?0107?03

0 引 言

在武警系統日常的管理工作中，士兵的執勤排班是一個十分常見的現實問題。但是在實際的管理工作中大多數的排班方式仍舊采用傳統的人工排班方式，即根據管理人員的經驗來進行士兵的排班。此種排班方式缺點十分明顯，不僅效率低下而且極容易出錯，并且難以兼顧到公平與效率的原則，不利于武警系統管理的科學化。

從理論上說，人員排班問題其實是一個組合優化的問題，其具有高度的非線性，并且當問題規模較龐大的時候，此類問題會變得十分復雜。解決此類問題常采用的方法有遺傳算法（GA）[1]，模擬退火算法（SA）[2]和蟻群算法（ACO）[3]等，本文在開發武警勤務管理系統中，運用了自適應遺傳算法解決了武警勤務管理系統中的士兵排班問題，并取得了比較理想的效果。

1 自適應遺傳算法

1.1 遺傳算法

遺傳算法（Genetic Algorithms，GA）是在1975年由美國密歇根大學的J.Holland教授提出的，而后經由DeJong、Goldberg等人歸納總結所形成的一類模擬進化算法[4?5]。它的基本思想是模擬自然界的遺傳機制和生物進化論，從而形成的一種過程搜索最優解的算法。現在被人們廣泛地應用于人工智能[6]、社會科學[7]、自動控制[8]、信號處理[9]、組合優化[10]和計算機科學等領域。

1.2 自適應遺傳算法

遺傳控制參數中的交叉概率[Pc]和變異概率[Pm]的選擇是影響GA性能和行為的關鍵因素，直接影響算法的收斂性。由于在標準遺傳算法（Simple Genetic Algorithms，SGA）中，[Pc]和[Pm]采用固定值，所以在求解復雜優化問題的時候就會存在收斂速度慢和早熟現象等缺點[11?12]，因此，遺傳算法的實現方式還有待于進一步的改進。

針對SGA存在的問題，本研究采用Srinvivas等提出的一種改進的自適應遺傳算法（Adaptive Genetic Algorithms，AGA）[13]，它的基本思想是引入式（1）、式（2）所示的自適應調整函數，能使遺傳控制參數[Pc]和[Pm]能夠隨著個體適應度的大小和群體的分散程度自動調整。它的原理是：當群體有陷入局部最優解的趨勢時，就相應地提高遺傳控制參數[Pc]和[Pm；]而當群體在解空間發散時，就相應地降低它們的值。而且，當個體的適應度接近當代種群中的最大適應度時，就認為該個體性能良好，對其采用較低的[Pc]和[Pm，]以此來盡可能的保留住它的優良模式，而當個體的適應度值低于當代種群的平均適應度時，就認為該個體性能不佳，將對其采用較大的[Pc]和[Pm，]以此來加快個體的更新速度。

[Pc=Pc1-（Pc1-Pc2）（fmax-f）fmax-favg，f≥favgPc1，f

[Pm=Pm1-（Pm1-Pm2）（fmax-f）fmax-favg，f≥favgPm1，f

式中：[fmax]為整個群體中最大的適應度值；[favg]為每一代群體的平均適應度值；[f]為要交叉的兩個體中較大個體的適應度值；[f]為要變異個體的適應度值。

2 士兵排班的AGA算法設計

武警勤務排班主要是指士兵的站崗執勤，其執勤排班以士兵承包的形式實現，每天每個崗哨的執勤由指定的幾個士兵組成一個小組來負責（如四包一，五包一等）。其約束條件見2.2節。

2.1 個體編碼

編碼就是把一個問題的可行解從它的解空間轉換到遺傳算法所能處理的搜索空間的操作[14]。目前流行的幾種常用的編碼方式有二進制編碼法，浮點數編碼法，格雷碼編碼法，符號編碼法等。根據本研究的實際情況采用了實數編碼法進行編碼。

基因：[Xij=R，若為休息1，若為1號崗位2，若為2號崗位?k，若為k號崗位][i=1，2，…，nj=1，2，…，T]

現假設有[n]個士兵（小組）。排班周期設為[T，]那么 [（Xi1，Xi2，Xi3，…，XiT）]為第[i]個士兵（小組）在一個工作周期[T]內執勤情況。

2.2 基本模型

針對邏輯變量[Xij，][i=1，]2，[…，][n，]定義了邏輯與運算：[∧]，若[∧]兩邊值相等則整體為1，否則為0。

目標函數：

[F（x）=min[W1F1（x）+W2F2（x）]] （3）

式中：[F1（x）]為士兵（小組）輪休的子適應度函數，如式（4）所示；[Df]為一個工作周期[T]內休息的總天數；[F1]取極小化表示執勤排班的染色體應盡量滿足排班周期內的輪休要求。

[F1（x）=i=1nj=1TXij∧R-Df2] （4）

式中：[F2（x）]為每個人（小組）一個排班周期[T]內在[k]個崗位上工作負荷均等的子函數，如公式（5）所示；[Da，][Db，]…，[Dk]為一個周期[T]內每人（小組）在[k]個崗位上的理論值班總數；[F2]取極小化表示每個人（小組）一周期內在[k]個崗位上的工作總量盡量接近[Da，][Db，][Dc，]…，[Dk，]到達負荷均衡。

[F2（x）=i=1nj=1TXij∧1-Da2+j=1TXij∧2-Db2+j=1TXij∧3-Dc2+…+j=1TXij∧k-Dk2] （5）

主要約束條件如下：

（1） 一個排班周期每人（小組）執勤天數上限[Workmin]與下限[Workmax，]如式（6）所示：

[Workmin≤T-j=1T[Xij∧R]≤Workmax，i=1，2，…，n] （6）

（2） 一個排班周期內每人（小組）連續執勤小于[m]天，如式（7）所示：

[[Xij∧R]+[Xi（j+1）∧R]+[Xi（j+2）∧R]+[Xi（j+3）∧R]+…+ [Xi（j+m-1）∧R]>0，i=1，2，…，n；j=1，2，…，31-m] （7）

（3） 一個排班周期內每人（小組）連休天數不超過[w]天，如式（8）所示：

[[Xij∧R]+[Xi（j+1）∧R]+[Xi（j+2）∧R]+[Xi（j+3）∧R]+…+ [Xi（j+m-1）∧R]≤w，i=1，2，…，n；j=1，2，…，31-m] （8）

2.3 適應度函數

在遺傳算法中，適應度函數是用于區分群體中個體好壞的惟一標準，它的值總是非負的，并且在任何情況下都希望它的值越大越好。在本研究中，適應度函數構造如式（9）所示：

[Fit（f（x））=11+c+f（x）] （9）

式中：[f（x）]為目標函數值，[f（x）>0，][c≥0，][c+f（x）≥0，][c]為目標函數界限的保守估計值。

在人員優化組合中，約束優化問題的處理通常采用懲罰函數法。在本研究中采用靜態懲罰法，即對于每個約束，都建立若干級的違約級；對于每個違約級和每個約束，建立一個固定的懲罰系數，再結合初始適應度函數，重新建立評估公式，見式（10）：[f（x）=F（x）×（1-i=1nribi）] （10）

式中：[F（x）]為原目標函數值；[ri]表示[n]個限制條件相應的懲罰系數；[bi]是裁決變量，[bi]=1表示進行第[i]個限制條件的懲罰，[bi]=0表示該搭配滿足第[i]個限制條件，無需懲罰。

本文采用遺傳算法中最常用的輪盤賭法對個體進行選擇。設群體大小為[n，]個體[i]的適應度為[fi，]則個體被選中的概率[Pi=fii=1nfi，]因此，個體的適應度越大，被選中的概率越高。

3 應用效果分析

根據武警中隊排班的實際要求，取排班周期[T=30，]士兵小組數[n=5，]負責執勤崗位數[k=3，][Da=7，][Db=7，][Dc=7，][Df=9，]種群規模為100，停止標準為ε=0.000 1，[Pc]和[Pm]中：[Pc1=0.9，][Pc2=0.6，][Pm1=0.1，][Pm2=]0.001，士兵排班表如圖1所示。

圖1 士兵排班表

圖1中的橫坐標為日期數，縱坐標為士兵小組的序號，1，2，3分別代表1，2，3號崗位，R代表休息。根據實際的執勤排班中的各種約束條件分析可得，圖中結果基本滿足實際需求，兼顧到了效率與公平原則，使士兵執勤排班更加公平化與人性化。

4 結 論

本研究將自適應遺傳算法運用在了武警勤務系統的自動化排班上，解決了士兵執勤的自動化排班問題。通過實際應用結果表明，利用自適應遺傳算法解決此問題是行之有效的，并取得了較為理想的效果。

參考文獻

[1] 馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012，29（4）：1201?1206.

[2] 王銀年，葛洪偉.求解TSP問題的改進模擬退火遺傳算法[J].計算機工程與應用，2010，46（5）：44?47.

[3] 倪慶劍，邢漢承，張志政，等.蟻群算法及其應用研究進展[J].計算機應用與軟件，2008，25（8）：12?16.

[4] HOLLAND J. Adaptation in natural and artificial systems [M]. Michigan， USA： The University of Michigan， 1975.

[5] GOLDBERG D E. Genetic algorithms in search， optimization and machine learning [M]. MA： Addison?Wesley， 1989.

[6] DAVIS J J. Training product unit neural network with genetic algorithms [J]. IEEE Expert， 1993， 8（5）： 26?33.

[7] BAUER R J. Genetic algorithms and investment strategies [R]. New York： Wiley， 1994.

[8] 景興建，土越超，談大龍.理性遺傳算法及其在多機器人運動防調中的應用[J].自動化學報，2002，28（6）：955?961.

[9] 吉根林.遺傳算法研究綜述[J].計算機應用與軟件，2004，21（2）：69?73.

[10] 錢志勤，滕弘飛，孫治國.人機交互的遺傳算法及其在約束布局優化中的應用[J].計算機學報，2001，24（5）：553?558.

[11] 羅志軍.遺傳算法的全局收斂性的齊次有限馬爾柯夫鏈分析[J].系統工程與電子技術，2000，22（1）：73?76.

[12] RUDOLPH G. Convergence properties of canonical genetic algorithms [J]. IEEE Transactions on Neural Networks， 1994， 5（1）： 96?101.

[13] 王小平，曹立明.遺傳算法：理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

[14] 張超群，鄭建國，錢潔.遺傳算法編碼方案比較[J].計算機應用研究，2011，28（3）：819?822.