基于GEP的任務(wù)指派問題的求解算法

朱明放，葉飛躍，丁小未

1.江蘇理工學(xué)院云計算與智能信息處理常州市重點實驗室，江蘇常州 213001

2.江蘇理工學(xué)院計算機工程學(xué)院，江蘇常州 213001

基于GEP的任務(wù)指派問題的求解算法

朱明放1，2，葉飛躍1，2，丁小未2

1.江蘇理工學(xué)院云計算與智能信息處理常州市重點實驗室，江蘇常州 213001

2.江蘇理工學(xué)院計算機工程學(xué)院，江蘇常州 213001

1 引言

指派問題（Task Assignment Problem，TAP）是指這樣一類問題：有若干資源和若干任務(wù)，如何科學(xué)合理地進行資源優(yōu)化和配置，從而產(chǎn)生最大化的經(jīng)濟效益和社會效益或者說完成這些任務(wù)的成本量最小，即，使得指派方案總體效果最佳。這類問題有廣泛的研究和應(yīng)用背景，如一個單位有若干項工作需要分配給若干人（或部門）來完成；學(xué)校有若干班級需要安排在若干教室里上課等[1]。

任務(wù)指派問題是典型的組合優(yōu)化問題，是典型的NP問題之一，從而得到了廣泛的關(guān)注和研究。任務(wù)指派問題的解法主要分為兩類：一類是精確求解算法，如匈牙利法[2]；另一類是啟發(fā)式算法，如遺傳算法[3]、蟻群算法[4]、模擬退火方法[5]、人工蜂群算法[6]、整數(shù)規(guī)劃的方法[7]等。

基因表達(dá)式編程（Gene Expression Programming，GEP）是由葡萄牙科學(xué)家Ferreira C.2001年提出來的一種新型遺傳算法[8]，其特點是將基因型和表現(xiàn)型分離，比傳統(tǒng)的遺傳編程（Genetic Programming，GP）快2～4個數(shù)量級，因而得到了廣泛的研究，已被應(yīng)用到函數(shù)發(fā)現(xiàn)[9]、分類[10]、聚類[11]、關(guān)聯(lián)規(guī)則[12]、時間序列預(yù)測[13]、組合優(yōu)化[14]等數(shù)據(jù)挖掘領(lǐng)域。

本文設(shè)計了基于GEP思想的TAP問題求解算法，并利用C#編程實現(xiàn)了該算法，結(jié)合實例分析表明算法的正確性和有效性。

2 基因表達(dá)式編程概要

2.1 基因表達(dá)式編程算法流程

基因表達(dá)式編程（GEP）是將基因型和表現(xiàn)型分開的一種遺傳算法，也就是在該算法中有2個實體：表達(dá)樹和染色體，GEP進化中，遺傳操作在固定長度的線性編碼的染色體上進行，而個體評價是在染色體解碼得到的表達(dá)樹上進行，即操作和評價相分離[15]。

GEP使用Karva語言對表達(dá)樹和染色體進行互相編、解碼。染色體由若干個基因組成，每個基因由頭部和尾部組成，頭部可以包含是函數(shù)符號和終結(jié)符號，尾部僅有終結(jié)符號。在GEP中，所有的遺傳操作只要保證基因的合法結(jié)構(gòu)，它就能解碼為合法的程序[16]。

GEP基本算法流程見圖1所示。

圖1 GEP算法基本流程圖

正是GEP基因結(jié)構(gòu)性和簡單線性編碼，使得GEP的遺傳算子比較豐富，主要有：變異、逆串、插串、根插串、基因插串、單點重組、2點重組、基因重組等八大算子。其遺傳算子的具體技術(shù)細(xì)節(jié)詳解文獻[8]。

2.2 GEP多基因家族結(jié)構(gòu)

對于任務(wù)指派問題求解，問題中有兩類信息：資源和任務(wù)，每一類信息在GEP的基因表達(dá)式中用一個多基因（Multi-gene）結(jié)構(gòu)表示，因此對該問題，使用二基因家族（Multi-gene Families）的染色體結(jié)構(gòu)表示。例1是一個簡單例子說明多基因家族問題。

例1有6個人員和6項任務(wù)，每個人完成不同的任務(wù)時工作成本不同，我們的問題是，每人安排一項任務(wù)，怎樣安排使得完成整個任務(wù)的成本最小？

顯然，該問題共有6!種按排方案，是典型的NP問題。我們對人員用數(shù)字1～6表示，任務(wù)用字母A-F表示。圖2（a）中是GEP解決該問題時一個二基因家族染色體表示，即圖2（b）表示的工作指派方案的信息表示。圖2（b）表示該染色體解碼對應(yīng)的表達(dá)樹，即圖2（a）染色體的解碼信息，表達(dá)了一種任務(wù)指派方案。

圖2 染色體表示及其表達(dá)樹

需要指出，染色體的編碼是隨機生成，只要保證染色體的合法結(jié)構(gòu)，即串的前6位表示人員信息，后6位表示任務(wù)信息，且每種信息是一種排列即可，則每個染色體都能正確地表示一個合法程序，即正確的任務(wù)指派方案。

3 主要遺傳算子設(shè)計

第2章介紹的GEP基本的流程和多基因家族的編碼。本章介紹本GEP算法設(shè)計中選擇操作、逆串操作、插串操作和適應(yīng)度函數(shù)的設(shè)計問題。

3.1 選擇算子設(shè)計

GEP像其他遺傳算法一樣引入隨機選擇方法模擬自然選擇過程，其中輪盤賭方法是一個簡單的實現(xiàn)模擬自然選擇的方式，為了保證進化過程不至于破壞已經(jīng)獲得的最好解，在輪盤賭的基礎(chǔ)上加了保持最優(yōu)解的策略。實現(xiàn)方法是對種群的各個個體進行適應(yīng)性評價，計算出適應(yīng)度函數(shù)值，然后定義各個個體的選擇概率為個體的適應(yīng)度函數(shù)值與所有適應(yīng)度函數(shù)值的累加和。算法描述如圖3所示。

圖3 選擇算子算法描述

3.2 其他遺傳算子設(shè)計

算法主要使用了兩個遺傳操作：逆串（inversion）操作和插串（insertion）操作。逆串操作是指染色體中選擇兩點，把這兩點間的串的順序倒置的操作；插串算子是選擇一個待插入的基因位和一個基因串片斷，將該片斷插入到待插入的基因位，原來位置的基因串依次后退的遺傳操作。例2對這兩種操作做簡單說明。

例2設(shè)父輩染色體如例1所示。即P=632451EDFCBA。

逆串操作：隨機選擇一個基因家族，如第一個基因家族；再隨機生成0～5之間的兩個隨機數(shù)，如2，4，將第2～4位之間基因逆置，得到S=635421EDFCBA。

插串操作：隨機選擇一個基因家族，如第一個基因家族；再隨機生成0～5之間隨機數(shù)，如2，4，第三步隨機生成0～2（兩個隨機數(shù)的最小值）之間隨機數(shù)，如1，將第2～4位之間基因插入到1開始的基因位置，其他基因依次后移，得到S=624531EDFCBA。

逆串遺傳算子的算法描述見圖4所示。插串操作同樣的方法可以設(shè)計，這里因篇幅限制，略去。

圖4 逆串算子算法描述

3.3 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)是進化計算的關(guān)鍵問題，它給定了進化計算的進化的方向和速度。TAP問題是一個組合優(yōu)化問題，目標(biāo)確定一個最優(yōu)指派方案。常有兩種方法確定這類問題適應(yīng)度函數(shù)。

第一種使用公式（1）確定個體的適應(yīng)度。

其中fi為個體i的適應(yīng)度值，Tg為當(dāng)前進化代中成本最大的個體的成本值，Ti為當(dāng)前代個體i的成本值。

第二種采用公式（2）確定個體適應(yīng)度。

其中M為預(yù)先指定的一個大數(shù)，為固定值。fi，Ti和第一種評價函數(shù)代表的意義同公式（1）相同。這種方法的不足是，需要預(yù)先指定M的值，而確定M的值，需要預(yù)先的經(jīng)驗和知識。這里使用公式（1）作為適應(yīng)度函數(shù)。

4 實驗分析與研究

4.1 實驗數(shù)據(jù)及參數(shù)

本實驗程序用VS2010環(huán)境下C#編寫。

設(shè)某單位有6人計劃安排6項任務(wù)，每人完成且只完成一項任務(wù)，各人的完成每項任務(wù)的成本見表1。現(xiàn)使用本程序求解該問題。

表2給出實驗參數(shù)，進化中選擇函數(shù)是具有精英保持策略的輪盤賭算法。

表1 任務(wù)指派成本矩陣

表2 進化參數(shù)

4.2 實驗結(jié)果及分析

按表2的進化參數(shù)，獨立運行程序100次，每次均得到的最小代價約是22。圖5是一次運行的成本變化曲線。

任務(wù)指派方案為：426315EDFBAC，即4-E，2-D，6-F，3-B，1-A，5-C。

該次運行的平均適應(yīng)度函數(shù)值的變化曲線如圖6所示。分析圖5，在前20代系統(tǒng)快速收斂，在100代左右收斂到滿意的近似解，如103代時，最小代價值為23。在120代時系統(tǒng)趨于穩(wěn)定。

圖5 TAP進化過程

圖6是運行過程中適應(yīng)度變化情況，為了清晰，圖中每隔10代取樣一次繪制的圖形。觀察到系統(tǒng)進化過程仍保持較高的基因多樣性，所以系統(tǒng)是健康強壯的。

圖6 適應(yīng)度的變化曲線

對于本實例，資源數(shù)量和任務(wù)數(shù)量均為6，規(guī)模較小，采用精確求解的匈牙利方法計算求解，以檢驗解的正確性。按照文獻[1]給出的匈牙利解法的具體算法步驟，獲得和本文算法完全相同的結(jié)果。匈牙利解法是建立在一系列的矩陣操作的基礎(chǔ)上，計算復(fù)雜，而且在確定任務(wù)指派方案后，再計算這種方案的成本。可見，本文算法是TSP問題求解的有效途徑。

5 結(jié)束語

GEP是遺傳算法發(fā)展的新階段，它繼承了GAs線性定長編碼的優(yōu)點，又繼承GP對復(fù)雜問題的表達(dá)能力，從而在基因編碼問題上使用了簡單編碼可以應(yīng)對復(fù)雜的問題。

本文介紹了GEP模型的工作原理，針對TAP問題進行了基于GEP的算法設(shè)計，用C#加以實現(xiàn)，進行實驗研究，說明GEP能高效解決TAP問題。下一步將進一步完善系統(tǒng)，擴大應(yīng)用，同時將該算法推廣到不平衡任務(wù)指派的問題求解中去，獲得更為廣闊的應(yīng)用。將該工作推廣到實際生產(chǎn)活動中去。

[1]鄭燁，王明杰，樊娟.基于匈牙利法的企業(yè)員工任務(wù)分配問題研究[J].統(tǒng)計與決策，2011（5）：182-185.

[2]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Research Logistic Quarterly，1955，2：83-97.

[3]黃江波.一種自適應(yīng)遺傳算法及其應(yīng)用[J].微電子學(xué)與計算機，2010，27（9）：193-196.

[4]張群，薛雨石.蟻群算法在機隊指派問題中的應(yīng)用[J].中國管理信息化，2011，14（13）：79-80.

[5]趙越.模擬退火算法求解指派問題新探[J].吉林建筑工程學(xué)院學(xué)報，2011，28（4）：61-63.

[6]孫曉雅，林焰.改進的人工蜂群算法求解任務(wù)指派問題[J].微電子學(xué)與計算機，2012，29（1）：23-26.

[7]任先海，楊樂平，朱彥偉.基于整數(shù)規(guī)劃的在軌服務(wù)任務(wù)指派問題研究[J].裝備指揮技術(shù)學(xué)院學(xué)報，2008，19（2）：52-56.

[8]Ferreira C.Gene Expression Programm-ing：a new adaptive algorithm for solving problems[J].Complex Systems，2001，13（2）：87-129.

[9]朱明放，唐常杰，陳安龍，等.基于樸素基因表達(dá)式編程挖掘緊致函數(shù)[J].電子科技大學(xué)學(xué)報：自然科學(xué)版，2010，39（2）：284-288.

[10]Duan Lei，Tang Changjie，Tang Liang，et al.An effective microarraydataclassifierbasedongeneexpression programming[C]//Proceeding of the 5th Int’l Conf on Natural Computation，2009：523-527.

[11]陳瑜，唐常杰，葉尚玉，等.基于基因表達(dá)式編程的自動聚類方法[J].四川大學(xué)學(xué)報：工程科學(xué)版，2007，39（6）：107-112.

[12]曾濤，唐常杰，朱明放，等.基于人工免疫和基因表達(dá)式編程的多維復(fù)雜關(guān)聯(lián)規(guī)則挖掘方法[J].四川大學(xué)學(xué)報：工程科學(xué)版，2006，38（5）：136-142.

[13]朱明放，王宏濤，任艷玲.基于基因表達(dá)式編程的私人汽車擁有量建模和預(yù)測[J].計算機應(yīng)用研究，2010，27（3）：958-960.

[14]朱明放.基于基因表達(dá)式編程的TSP問題求解[J].計算機工程與應(yīng)用，2008，44（23）：53-55.

[15]唐常杰，張?zhí)鞈c，左劼，等.基于基因表達(dá)式編程的知識發(fā)現(xiàn)-沿革、成果和發(fā)展方向[J].計算機應(yīng)用，2004，24（10）：7-10.

[16]Zuo Jie，Tang Changjie，Zhang Tianqing.Mining predicate association rule by Gene Expression Programming[C]// LNCS 2419：Proc of the 3rd International Conf for Web Information Age 2002（WAIM02）.Berlin：Springer-Verlag，2002：92-103.

ZHU Mingfang1，2,YE Feiyue1，2,DING Xiaowei2

1.Key Laboratory of Cloud Computing&Intelligent Information Processing of Changzhou City,Jiangsu University of Technology,Changzhou,Jiangsu 213001,China
2.School of Computer Engineering,Jiangsu University of Technology,Changzhou,Jiangsu 213001,China

Task Assignment Problem（TAP）is one kind of classic combinatorial optimization problem which has been gained extensive research.Design an algorithm of TAP based on Gene Expression Programming（GEP）and implement it with C#.The analysis and study of experiment is presented,which by a living example of people resource assignment.The results indicate this algorithm is correctness and effectiveness,so provide a reference frame of TAP for some enterprise units.

Task Assignment Problem;Gene Expression Programming;inversion

任務(wù)指派問題是典型的組合優(yōu)化問題，得到了廣泛的研究。基于基因表達(dá)式編程的思想，設(shè)計了任務(wù)指派問題求解的算法，并用C#實現(xiàn)了該算法。結(jié)合人力資源任務(wù)分配的實例進行了實驗分析和研究，獲得了人員與崗位配置的最優(yōu)解。實驗表明算法設(shè)計是正確和有效的，從而為企業(yè)人員安排提供參考。

TAP問題；基因表達(dá)式編程；逆算子

A

TP301.6

10.3778/j.issn.1002-8331.1212-0332

ZHU Mingfang,YE Feiyue,DING Xiaowei.Solving algorithm of task assigned problem using gene expression programming.Computer Engineering and Applications,2014,50（22）：50-53.

國家自然科學(xué)基金（No.61142007）；常州市云計算與智能信息處理重點實驗室項目（No.CM20123004）；江蘇省“青藍(lán)工程”項目（No.KYQ10007）。

朱明放（1970—），男，博士，副教授，主要研究方向為數(shù)據(jù)挖掘，進化計算；葉飛躍（1960—），男，教授，主要研究方向為數(shù)據(jù)挖掘；丁小未（1991—），男，本科生。

2012-12-27

2013-02-28

1002-8331（2014）22-0050-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-19,http://www.cnki.net/kcms/detail/11.2127.TP.20130319.1424.007.html