本站原创摘 要：指派问题是一种特殊的组合优化问题.遗传算法适于群体问题优化.通过构造合适的适应度函数,设计良好的染色体编码,选择合理的遗传操作,文章提出的改进策略有效地实现了指派问题的求解.
Abstract：Assignmentproblemisaspecialkindofbinatorialoptimizationproblems.Geicalgorithmsissuitableforoptimizationofpopulationproblems.Byconstructingasuitablefitnesunction,designinggoodchromosomecode,selectingreasonablegeicoperations,thispaperputorwardanimprovedstrategywhicheffectivelyrealizesthesolvingforassignmentproblem.
关 键 词：指派问题；遗传算法；染色体；适应度
Keywords：assignmentproblem；geicalgorithms；chromosomes；fitness
中图分类号：G623.5文献标识码：A文章编号：1006-4311（2013）04-0324-02
0引言
指派问题是一种特殊的0-1整数规划问题,目前对于小规模指派问题,匈牙利法是一种常用的简单有效的解决方式；而对于大规模指派问题,则因为计算量过大,因而运算较为困难.基于生物群体遗传进化操作的遗传算法,则很适合群体规模较大问题的优化处理.因此将规模较大的指派问题应用遗传算法进行求解,就会较为简便快捷.
1遗传算法
1.1遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[1],它是一种多学科融合交叉的产物.遗传算法通过合理的编码机制和进化机制,广泛应用于近似最优化、生产调度、图形分割及自动控制等领域.
1.2遗传算法基本步骤[2]
①初始化.设置初始种群、最大迭代次数及迭代计数器.
②适应度评价.对当前种群计算其个体适应度.
③进化操作.主要是通过选择、交叉、变异、倒位等算子作用产生下一代群体.
④终止条件判断.如果已经求得最优解,则终止；否则重复以上两个步骤.
2指派问题的遗传算法实现
2.1指派问题模型描述人们日常生活和工作中,经常会遇到这类问题：有n个任务需要n个人去完成,每个人完成每个任务的效率不尽相同,要求一个人只能完成其中一个任务,一个任务只能由一个人完成.要求合理分配之后,所达到的总体效率最好,这就是指派问题.
那么,根据优化模型理论,当目标为极大值时,指派问题的数学模型[3]如下：
Maxz等于cx（1）
x等于1i等于1,2,等,n（2）
x等于1j等于1,2,等,n（3）
x等于0,1（4）
其中,当指派第i个人去完成第j个任务时,x等于1；否则x等于0.c表示第i个人去完成第j个任务的效率；约束条件（2）表示：第i个人只能完成一项任务；约束条件（3）表示：第j个任务只能由一个人完成.
2.2指派问题的遗传算法设计遗传算法[4]设计是完成遗传运算的具体方法,涵盖了决策变量的基因型与表现型之间的编码和解码,个体适应度函数构造,遗传算子构建,控制参数设置等过程.
2.2.1指派问题适应度函数针对指派问题在求解目标函数为极大值时的情况和考虑指派问题可行解的非负性前提下,其个体适应度与目标函数值是成正比.因此,指派问题的适应度函数构建为如下所示：
F等于cx
其中,x表示第i个人是否去做第j个任务.c表示第i个人完成第j个任务的效率.
F越大,表示个体适应度越好,其可行解越好,能够以较大概率遗传到下一代.当F取值最大时,则表示已经达到最优解.
2.2.2指派问题染色体编码染色体[5]编码质量是影响遗传算法计算效率和准确度的重要因素.考虑到指派问题的特殊约束性质：即每人只能完成其中一个任务且每个任务只能由一人完成.针对决策变量x的取值,其基因型编码不采取通常的0-1二进制编码,而采用常用的十进制编码.并且,每个基因块只有两个基因位,分别表示决策变量的行下标取值和列下标取值.当问题规模为n时,则指派问题决策变量染色体编码表示为：
在这种染色体编码十进制表示方式下,对于每个个体,其染色体的n个基因块在处理时按照如下规则进行：
①各代群体每个染色体中各基因块第一位分别赋予固定值：范围为0到n-1,即R11等于0,R21等于1,等Rn1等于n-1.其目的是保证决策变量选取位于不同行.
②各代群体每个染色体中各基因块第二位分别赋予无重复随机值：范围为0到n-1,即R12、R22等Rn2每次取0到n-1的随机全排列值.目的是保证决策变量选取位于不同列.
通过这种方式进行指派问题染色体编码,可以只对基因块中第二位编码进行随机产生,提高了搜索效率.同时,由于是十进制编码,各个基因块的值组合可以直接定位于效率矩阵中的对应元素位置,加快运算效率.
2.2.3指派问题遗传算子改进策略一般情况下,遗传算法遗传过程和进化过程主要是通过选择、交叉、变异及倒位等遗传算子组合运算完成群体迭代.考虑指派问题组合优化的特殊性：即可行解必须位于不同行不同列,已在决策变量染色体编码中进行了约束限制,那么,在遗传进化过程中,无需再对种群群体进行变异操作和倒位操作.因此,通过优化染色体编码,在遗传进化过程中仅通过选择和交叉策略实现种群迭代,有效地提高了运算效率,加快了最优解的获得.
3算法仿真
控制参数的设置是否合理对于遗传算法而言,关系到其优化效率.在此,我们设置种群规模为80；交叉概率为Pc等于0.6,各基因块位置不变的情况随机配对基因块第二位（此时也就相当于包含了变异运算）；选择运算根据目标极大化特点,采用赌[6]策略进行优化选择.
仿真验证时,我们只需输入效率矩阵阶数和对应效率矩阵的各个元素值则可获得最优解.
检测设效率矩阵阶数为5,对应的效率矩阵如下所示：
12913117814138991412161217121115810710817
经过运算之后得到的最优解为[0：2------1：1------2：3------3：0------4：4],其适应度为F等于77.
4结束语
在指派问题中,对于阶数越高的效率矩阵而言,运用此改进的遗传算法进行求解,效果越明显,效率也越高.如果目标函数是极小值情况,只要通过函数变换,转化为极大值则可.通过仿真验证,这种通过优化染色体编码和减少遗传算子作用相结合的改进策略,对于大规模指派问题求解十分有效.