摘 要： 在開發(fā)的武警勤務(wù)管理系統(tǒng)中，應(yīng)用自適應(yīng)遺傳算法對勤務(wù)執(zhí)勤的自動化排班進行了研究。根據(jù)武警勤務(wù)特點建立了一系列的約束條件模型，設(shè)計了相應(yīng)的目標(biāo)函數(shù)，適應(yīng)度函數(shù)和遺傳算子，最終在勤務(wù)系統(tǒng)自動化排班中取得了較為理想的效果。

關(guān)鍵詞： 遺傳算法； 自適應(yīng)遺傳算法； 人員排班； 勤務(wù)管理系統(tǒng)

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

0 引 言

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

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

1 自適應(yīng)遺傳算法

1.1 遺傳算法

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

1.2 自適應(yīng)遺傳算法

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

針對SGA存在的問題，本研究采用Srinvivas等提出的一種改進的自適應(yīng)遺傳算法（Adaptive Genetic Algorithms，AGA）[13]，它的基本思想是引入式（1）、式（2）所示的自適應(yīng)調(diào)整函數(shù)，能使遺傳控制參數(shù)[Pc]和[Pm]能夠隨著個體適應(yīng)度的大小和群體的分散程度自動調(diào)整。它的原理是：當(dāng)群體有陷入局部最優(yōu)解的趨勢時，就相應(yīng)地提高遺傳控制參數(shù)[Pc]和[Pm；]而當(dāng)群體在解空間發(fā)散時，就相應(yīng)地降低它們的值。而且，當(dāng)個體的適應(yīng)度接近當(dāng)代種群中的最大適應(yīng)度時，就認為該個體性能良好，對其采用較低的[Pc]和[Pm，]以此來盡可能的保留住它的優(yōu)良模式，而當(dāng)個體的適應(yīng)度值低于當(dāng)代種群的平均適應(yīng)度時，就認為該個體性能不佳，將對其采用較大的[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]為整個群體中最大的適應(yīng)度值；[favg]為每一代群體的平均適應(yīng)度值；[f]為要交叉的兩個體中較大個體的適應(yīng)度值；[f]為要變異個體的適應(yīng)度值。

2 士兵排班的AGA算法設(shè)計

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

2.1 個體編碼

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

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

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

2.2 基本模型

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

目標(biāo)函數(shù)：

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

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

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

式中：[F2（x）]為每個人（小組）一個排班周期[T]內(nèi)在[k]個崗位上工作負荷均等的子函數(shù)，如公式（5）所示；[Da，][Db，]…，[Dk]為一個周期[T]內(nèi)每人（小組）在[k]個崗位上的理論值班總數(shù)；[F2]取極小化表示每個人（小組）一周期內(nèi)在[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） 一個排班周期每人（小組）執(zhí)勤天數(shù)上限[Workmin]與下限[Workmax，]如式（6）所示：

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

（2） 一個排班周期內(nèi)每人（小組）連續(xù)執(zhí)勤小于[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） 一個排班周期內(nèi)每人（小組）連休天數(shù)不超過[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 適應(yīng)度函數(shù)

在遺傳算法中，適應(yīng)度函數(shù)是用于區(qū)分群體中個體好壞的惟一標(biāo)準(zhǔn)，它的值總是非負的，并且在任何情況下都希望它的值越大越好。在本研究中，適應(yīng)度函數(shù)構(gòu)造如式（9）所示：

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

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

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

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

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

3 應(yīng)用效果分析

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

圖1 士兵排班表

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

4 結(jié) 論

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

參考文獻

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

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

[3] 倪慶劍，邢漢承，張志政，等.蟻群算法及其應(yīng)用研究進展[J].計算機應(yīng)用與軟件，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] 景興建，土越超，談大龍.理性遺傳算法及其在多機器人運動防調(diào)中的應(yīng)用[J].自動化學(xué)報，2002，28（6）：955?961.

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

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

[11] 羅志軍.遺傳算法的全局收斂性的齊次有限馬爾柯夫鏈分析[J].系統(tǒng)工程與電子技術(shù)，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] 王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

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