基于GEP的任务指派问题的求解算法

朱明放，叶飞跃，丁小未

1.江苏理工学院云计算与智能信息处理常州市重点实验室，江苏常州 213001

2.江苏理工学院计算机工程学院，江苏常州 213001

基于GEP的任务指派问题的求解算法

朱明放1，2，叶飞跃1，2，丁小未2

1.江苏理工学院云计算与智能信息处理常州市重点实验室，江苏常州 213001

2.江苏理工学院计算机工程学院，江苏常州 213001

1 引言

指派问题（Task Assignment Problem，TAP）是指这样一类问题：有若干资源和若干任务，如何科学合理地进行资源优化和配置，从而产生最大化的经济效益和社会效益或者说完成这些任务的成本量最小，即，使得指派方案总体效果最佳。这类问题有广泛的研究和应用背景，如一个单位有若干项工作需要分配给若干人（或部门）来完成；学校有若干班级需要安排在若干教室里上课等[1]。

任务指派问题是典型的组合优化问题，是典型的NP问题之一，从而得到了广泛的关注和研究。任务指派问题的解法主要分为两类：一类是精确求解算法，如匈牙利法[2]；另一类是启发式算法，如遗传算法[3]、蚁群算法[4]、模拟退火方法[5]、人工蜂群算法[6]、整数规划的方法[7]等。

基因表达式编程（Gene Expression Programming，GEP）是由葡萄牙科学家Ferreira C.2001年提出来的一种新型遗传算法[8]，其特点是将基因型和表现型分离，比传统的遗传编程（Genetic Programming，GP）快2～4个数量级，因而得到了广泛的研究，已被应用到函数发现[9]、分类[10]、聚类[11]、关联规则[12]、时间序列预测[13]、组合优化[14]等数据挖掘领域。

本文设计了基于GEP思想的TAP问题求解算法，并利用C#编程实现了该算法，结合实例分析表明算法的正确性和有效性。

2 基因表达式编程概要

2.1 基因表达式编程算法流程

基因表达式编程（GEP）是将基因型和表现型分开的一种遗传算法，也就是在该算法中有2个实体：表达树和染色体，GEP进化中，遗传操作在固定长度的线性编码的染色体上进行，而个体评价是在染色体解码得到的表达树上进行，即操作和评价相分离[15]。

GEP使用Karva语言对表达树和染色体进行互相编、解码。染色体由若干个基因组成，每个基因由头部和尾部组成，头部可以包含是函数符号和终结符号，尾部仅有终结符号。在GEP中，所有的遗传操作只要保证基因的合法结构，它就能解码为合法的程序[16]。

GEP基本算法流程见图1所示。

图1 GEP算法基本流程图

正是GEP基因结构性和简单线性编码，使得GEP的遗传算子比较丰富，主要有：变异、逆串、插串、根插串、基因插串、单点重组、2点重组、基因重组等八大算子。其遗传算子的具体技术细节详解文献[8]。

2.2 GEP多基因家族结构

对于任务指派问题求解，问题中有两类信息：资源和任务，每一类信息在GEP的基因表达式中用一个多基因（Multi-gene）结构表示，因此对该问题，使用二基因家族（Multi-gene Families）的染色体结构表示。例1是一个简单例子说明多基因家族问题。

例1有6个人员和6项任务，每个人完成不同的任务时工作成本不同，我们的问题是，每人安排一项任务，怎样安排使得完成整个任务的成本最小？

显然，该问题共有6!种按排方案，是典型的NP问题。我们对人员用数字1～6表示，任务用字母A-F表示。图2（a）中是GEP解决该问题时一个二基因家族染色体表示，即图2（b）表示的工作指派方案的信息表示。图2（b）表示该染色体解码对应的表达树，即图2（a）染色体的解码信息，表达了一种任务指派方案。

图2 染色体表示及其表达树

需要指出，染色体的编码是随机生成，只要保证染色体的合法结构，即串的前6位表示人员信息，后6位表示任务信息，且每种信息是一种排列即可，则每个染色体都能正确地表示一个合法程序，即正确的任务指派方案。

3 主要遗传算子设计

第2章介绍的GEP基本的流程和多基因家族的编码。本章介绍本GEP算法设计中选择操作、逆串操作、插串操作和适应度函数的设计问题。

3.1 选择算子设计

GEP像其他遗传算法一样引入随机选择方法模拟自然选择过程，其中轮盘赌方法是一个简单的实现模拟自然选择的方式，为了保证进化过程不至于破坏已经获得的最好解，在轮盘赌的基础上加了保持最优解的策略。实现方法是对种群的各个个体进行适应性评价，计算出适应度函数值，然后定义各个个体的选择概率为个体的适应度函数值与所有适应度函数值的累加和。算法描述如图3所示。

图3 选择算子算法描述

3.2 其他遗传算子设计

算法主要使用了两个遗传操作：逆串（inversion）操作和插串（insertion）操作。逆串操作是指染色体中选择两点，把这两点间的串的顺序倒置的操作；插串算子是选择一个待插入的基因位和一个基因串片断，将该片断插入到待插入的基因位，原来位置的基因串依次后退的遗传操作。例2对这两种操作做简单说明。

例2设父辈染色体如例1所示。即P=632451EDFCBA。

逆串操作：随机选择一个基因家族，如第一个基因家族；再随机生成0～5之间的两个随机数，如2，4，将第2～4位之间基因逆置，得到S=635421EDFCBA。

插串操作：随机选择一个基因家族，如第一个基因家族；再随机生成0～5之间随机数，如2，4，第三步随机生成0～2（两个随机数的最小值）之间随机数，如1，将第2～4位之间基因插入到1开始的基因位置，其他基因依次后移，得到S=624531EDFCBA。

逆串遗传算子的算法描述见图4所示。插串操作同样的方法可以设计，这里因篇幅限制，略去。

图4 逆串算子算法描述

3.3 适应度函数设计

适应度函数是进化计算的关键问题，它给定了进化计算的进化的方向和速度。TAP问题是一个组合优化问题，目标确定一个最优指派方案。常有两种方法确定这类问题适应度函数。

第一种使用公式（1）确定个体的适应度。

其中fi为个体i的适应度值，Tg为当前进化代中成本最大的个体的成本值，Ti为当前代个体i的成本值。

第二种采用公式（2）确定个体适应度。

其中M为预先指定的一个大数，为固定值。fi，Ti和第一种评价函数代表的意义同公式（1）相同。这种方法的不足是，需要预先指定M的值，而确定M的值，需要预先的经验和知识。这里使用公式（1）作为适应度函数。

4 实验分析与研究

4.1 实验数据及参数

本实验程序用VS2010环境下C#编写。

设某单位有6人计划安排6项任务，每人完成且只完成一项任务，各人的完成每项任务的成本见表1。现使用本程序求解该问题。

表2给出实验参数，进化中选择函数是具有精英保持策略的轮盘赌算法。

表1 任务指派成本矩阵

表2 进化参数

4.2 实验结果及分析

按表2的进化参数，独立运行程序100次，每次均得到的最小代价约是22。图5是一次运行的成本变化曲线。

任务指派方案为：426315EDFBAC，即4-E，2-D，6-F，3-B，1-A，5-C。

该次运行的平均适应度函数值的变化曲线如图6所示。分析图5，在前20代系统快速收敛，在100代左右收敛到满意的近似解，如103代时，最小代价值为23。在120代时系统趋于稳定。

图5 TAP进化过程

图6是运行过程中适应度变化情况，为了清晰，图中每隔10代取样一次绘制的图形。观察到系统进化过程仍保持较高的基因多样性，所以系统是健康强壮的。

图6 适应度的变化曲线

对于本实例，资源数量和任务数量均为6，规模较小，采用精确求解的匈牙利方法计算求解，以检验解的正确性。按照文献[1]给出的匈牙利解法的具体算法步骤，获得和本文算法完全相同的结果。匈牙利解法是建立在一系列的矩阵操作的基础上，计算复杂，而且在确定任务指派方案后，再计算这种方案的成本。可见，本文算法是TSP问题求解的有效途径。

5 结束语

GEP是遗传算法发展的新阶段，它继承了GAs线性定长编码的优点，又继承GP对复杂问题的表达能力，从而在基因编码问题上使用了简单编码可以应对复杂的问题。

本文介绍了GEP模型的工作原理，针对TAP问题进行了基于GEP的算法设计，用C#加以实现，进行实验研究，说明GEP能高效解决TAP问题。下一步将进一步完善系统，扩大应用，同时将该算法推广到不平衡任务指派的问题求解中去，获得更为广阔的应用。将该工作推广到实际生产活动中去。

[1]郑烨，王明杰，樊娟.基于匈牙利法的企业员工任务分配问题研究[J].统计与决策，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]黄江波.一种自适应遗传算法及其应用[J].微电子学与计算机，2010，27（9）：193-196.

[4]张群，薛雨石.蚁群算法在机队指派问题中的应用[J].中国管理信息化，2011，14（13）：79-80.

[5]赵越.模拟退火算法求解指派问题新探[J].吉林建筑工程学院学报，2011，28（4）：61-63.

[6]孙晓雅，林焰.改进的人工蜂群算法求解任务指派问题[J].微电子学与计算机，2012，29（1）：23-26.

[7]任先海，杨乐平，朱彦伟.基于整数规划的在轨服务任务指派问题研究[J].装备指挥技术学院学报，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]朱明放，唐常杰，陈安龙，等.基于朴素基因表达式编程挖掘紧致函数[J].电子科技大学学报：自然科学版，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]陈瑜，唐常杰，叶尚玉，等.基于基因表达式编程的自动聚类方法[J].四川大学学报：工程科学版，2007，39（6）：107-112.

[12]曾涛，唐常杰，朱明放，等.基于人工免疫和基因表达式编程的多维复杂关联规则挖掘方法[J].四川大学学报：工程科学版，2006，38（5）：136-142.

[13]朱明放，王宏涛，任艳玲.基于基因表达式编程的私人汽车拥有量建模和预测[J].计算机应用研究，2010，27（3）：958-960.

[14]朱明放.基于基因表达式编程的TSP问题求解[J].计算机工程与应用，2008，44（23）：53-55.

[15]唐常杰，张天庆，左劼，等.基于基因表达式编程的知识发现-沿革、成果和发展方向[J].计算机应用，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

任务指派问题是典型的组合优化问题，得到了广泛的研究。基于基因表达式编程的思想，设计了任务指派问题求解的算法，并用C#实现了该算法。结合人力资源任务分配的实例进行了实验分析和研究，获得了人员与岗位配置的最优解。实验表明算法设计是正确和有效的，从而为企业人员安排提供参考。

TAP问题；基因表达式编程；逆算子

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.

国家自然科学基金（No.61142007）；常州市云计算与智能信息处理重点实验室项目（No.CM20123004）；江苏省“青蓝工程”项目（No.KYQ10007）。

朱明放（1970—），男，博士，副教授，主要研究方向为数据挖掘，进化计算；叶飞跃（1960—），男，教授，主要研究方向为数据挖掘；丁小未（1991—），男，本科生。

2012-12-27

2013-02-28

1002-8331（2014）22-0050-04

CNKI网络优先出版：2013-03-19,http://www.cnki.net/kcms/detail/11.2127.TP.20130319.1424.007.html