基因表达式编程的任务指派问题求解算法设计与实现
摘要：任务指派问题是典型的组合优化问题，得到了广泛的研究。基于基因表达式编程的思想，设计了任务指派问题求解的算法，并用C#实现了该算法。结合人力资源任务分配的实例进行了实验分析和研究，获得了人员与岗位配置的最优解。实验表明算法设计是正确性和有效性，因而为企业人员安排提供参考依据。关键词：TAP问题；基因表达式编程；逆串算子中图分类号: TP301.6 文献标识码: AThe Design and Implementation of Task Assigned ProblemBased on Gene Expression ProgrammingZHU Ming-fang1,2, Ye Fei-yue1,2,PAN Yu1,2 , DING Xiao-wei2,(1. KeyLaboratory of Cloud Computing & Intelligent Information Processing ofChangzhou City, Jiangsu Teachers University of Technology, Changzhou, 213001,China；(2. 2. School of Computer Engineering, Jiangsu Teachers Universityof Technology, Changzhou， 213001,China)Abstract: Task assignmentproblem (TAP) is one kind of classic combinatorial optimization problem whichhas been gained extensive research. Designed an algorithm of TAP based on geneexpression programming (GEP) and implemented it with C# will be presented this paper.At last the analysis and study of experiment is presented, which by a livingexample of people resource assignment. The results indicate this algorithm is correctnessand effectiveness, so provides a reference frame of TAP for some enterpriseunits.Keyword: task assignment problem; geneexpression programming; inversion1 引言任务指派问题(Task Assignment Problem, TAP)是指这样一类问题：有若干资源和若干任务，如何科学合理的进行资源优化和配置，从而产生最大化的经济效益和社会效益或者说完成这些任务的成本量最小，即使得指派方案总体效果最佳。这类的问题有广泛的研究和应用背景，如一个单位有若干项工作需要分配给若干人（或部门）来完成；学校有若干班级需要安排在若干教室里上课等[1]。任务指派问题是典型的组合优化问题，是典型的NP问题之一，从而得到了广泛的关注和研究，有众多的研究方法解决这类问题，其中有匈牙利法[1]、蚁群算法[2]、模拟退火方法[3]、基于整数规划的方法[4]等。基因表达式编程(Gene Expression Programming,GEP) 是由葡萄牙科学家FerreiraC. 2001年提出来的一种新型遗传算法[5],其特点是将基因型和表现型分离，比传统的遗传编程(GeneticProgramming, GP)快2～4个数量级[5]，因而得到了广泛的关注和研究，已经被广泛应用到数据挖掘的各个领域[6]。本文设计了基于GEP思想的TAP问题求解算法，并利用C#编程实现了该算法，同时，通过实例表明算法正确性和有效性。论文余下部分的组织结构如下：第二节阐述了GEP解决TAP问题时染色体结构和遗传操作；第三节说明了算法设计的整体思路；第四节结合实例，说明算法的运行效率；最后第五节是的结论和下一步工作。2 基因表达式编程概要2.1 基因表达式编程算法流程基因表达式编程(GEP)是将基因型和表现型分开的一种遗传算法，也就是在该算法中有2个实体：表达树和染色体，GEP进化中，遗传操作在固定长度的线性编码的染色体上进行，而个体评价是在染色体解码得到的表达树上进行，即操作和评价相分离。GEP使用Karva语言对表达树和染色体进行互相编、解码。染色体由若干个基因组成，每个基因由头部和尾部组成，头部可以包含是函数符号和终结符号，尾部仅有终结符号。在GEP中，所有的遗传操作只要保证基因的合法结构，它就能解码为合法的程序[10]。GEP基本算法流程见图1所示。正是GEP基因结构性和简单线性编码，使得GEP的遗传算子比较丰富，主要有：变异、逆串、插串、根插串、基因插串、单点重组、2点重组、基因重组等八大算子。其算法的具体技术细节详解文献[5]。2.2 GEP多基因家族结构对于任务指派问题求解，问题中有两类信息：资源和任务，每一类信息在GEP的基因表达式中用一个多基因（Multi-gene）结构表示，因此对该问题，使用二基因家族(Multi-geneFamilies)的染色体结构表示。例1是一个简单例子说明多基因家族问题。例2 有6个人员和6项任务，每个人完成不同的任务时工作成本不同，我们的问题是，每人安排一项任务，怎样安排使得完成整个任务的成本最小？显然，该问题共有6！种按排方案，是典型的NP问题。我们对人员用数字1-6表示，任务用字母A-F表示。图2(a)中是GEP解决该问题时一个二基因家族染色体表示，即图2(b)表示的工作指派方案的信息表示。图2(b) 表示该染色体解码对应的表达树，即图2(a)染色体的解码信息，表达了一种任务指派方案。需要指出，染色体的编码是随机生成，只要保证染色体的合法结构，即串的前6位表示人员信息，后6位表示任务信息，且每种信息是一种排列即可，则每个染色体都能正确的表示一个合法程序，即正确的任务指派方案。3 主要算法设计第2节介绍的GEP基本的流程和多基因家族的编码。本节介绍本算法设计中选择操作、逆串操作、插串操作和适应度函数的设计问题。3.1 选择算子设计GEP像其它遗传算法一样引入随机选择方法模拟自然选择过程，其中轮盘赌方法是一个简单的实现模拟自然选择的方式，为了保证进化过程不至于破坏已经获得的最好解，在轮盘赌的基础上加了保持最优解的策略。实现方法是对种群的各个个体进行适应性评价，计算出适应度函数值，然后定义各个个体的选择概率为个体的适应度函数值与所有适应度函数值的累加和。算法描述如图3所示。带有精英选择的选择算法1For i=1 to size //size为种群规模2计算Fi //Fi是i个体适应度函数值3F=sum(Fi) //F适应度函数值之和4Fi值最大的个体到下一代第1位置5P1=F1/F6For i=2 to size //计算累积概率7Pi=Pi-1+Fi/F8For i=2 to size9产生0～1之间随机数r10//根据r值范围，确定被选中的个体11If r<p1 then 选中第一个个体复制12Else if r>=pj-1 and r<pj then13选择第j个个体复制到第i位置图3 选择算子算法描述3.2 遗传算子设计本算法主要使用了两个遗传操作：逆串（inversion）操作和插串（insertion）操作。逆串操作是指染色体中选择两点，把这两点间的串的顺序倒置的操作；插串算子是选择一个待插入的基因位和一个基因串片断，将该片断插入到待插入的基因位，原来位置的基因串依次后退的遗传操作。例2对这两种操作做简单说明。例2 设父辈染色体如例1所示。即P= 632451EDFCBA。逆串操作：随机选择一个基因家族，如第一个基因家族；再随机生成0~5之间的两个随机数，如2，4，将第2~4位之间基因逆置，得到S=635421 EDFCBA ;插串操作：随机选择一个基因家族，如第一个基因家族；再随机生成0~5之间随机数，如2，4，第三步随机生成0~2（两个随机数的最小值）之间随机数，如1，将第2~4位之间基因插入到1开始的基因位置，其他基因依次后移，得到S=624531EDFCBA 。逆串遗传算子的算法描述见图4所示,插串操作同样的方法可以设计，这里因篇幅限制，略去。逆串遗传操作算法1For i=1 to size //size为种群规模2{产生0～1随机数r3If r<pinv then //pinv为逆串率4{ p=random(0,1) //随机选择0或15If p==0 then//在第一基因家族6{产生0~L/2-1之间随机数r1，r27//L为染色体长度，设r1<r28将r1~r2之间基因取逆放在原位置9}else10{产生L/2~L之间随机数r1，r211//设r1<r212将r1~r2之间基因取逆放在原位置13}14} }图4 逆串算子算法描述3.3 适应度函数设计适应度函数确定，是进化计算的关键问题，它给定了进化计算的进化的方向和速度。TAP问题是一个组合优化问题，目标确定一个最优指派方案。常有2种方法确定这类问题适应度函数。第一种使用公式(补充：软件开发 , C# ,上一个：传说中的WCF：群聊天程序
下一个：RDLC 用ashx调用打印的例子
