一种遗传算法求解指派问题改进策略

《一种遗传算法求解指派问题改进策略》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种遗传算法求解指派问题改进策略　　摘要：指派问题是一种特殊的组合优化问题。遗传算法适于群体问题优化。通过构造合适的适应度函数，设计良好的染色体编码，选择合理的遗传操作，文章提出的改进策略有效地实现了指派问题的求解。Abstract：Assignmentproblemisaspecialkindofcombinatorialoptimizationproblems.Geneticalgorithmsissuitableforoptimizationofpopulationproblems.Byconstructingasuitablefitness

2、function，designinggoodchromosomecode，selectingreasonablegeneticoperations，thispaperputsforwardanimprovedstrategywhicheffectivelyrealizesthesolvingforassignmentproblem.关键词：指派问题；遗传算法；染色体；适应度Keywords：assignmentproblem；geneticalgorithms；chromosomes；fitness中图分类号：G623.5文献标识码：A文章编号：1

3、006-4311（2013）04-0324-020引言6指派问题是一种特殊的0-1整数规划问题，目前对于小规模指派问题，匈牙利法是一种常用的简单有效的解决方式；而对于大规模指派问题，则因为计算量过大，因而运算较为困难。基于生物群体遗传进化操作的遗传算法，则很适合群体规模较大问题的优化处理。因此将规模较大的指派问题应用遗传算法进行求解，就会较为简便快捷。1遗传算法1.1遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[1]，它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和进化机制，广泛应用于近

4、似最优化、生产调度、图形分割及自动控制等领域。1.2遗传算法基本步骤[2]①初始化。设置初始种群、最大迭代次数及迭代计数器。②适应度评价。对当前种群计算其个体适应度。③进化操作。主要是通过选择、交叉、变异、倒位等算子作用产生下一代群体。④终止条件判断。如果已经求得最优解，则终止；否则重复以上两个步骤。2指派问题的遗传算法实现2.1指派问题模型描述6人们日常生活和工作中，经常会遇到这类问题：有n个任务需要n个人去完成，每个人完成每个任务的效率不尽相同，要求一个人只能完成其中一个任务，一个任务只能由一个人完成。要求合理分配之后，所达到的总体效率最好，这

5、就是指派问题。那么，根据优化模型理论，当目标为极大值时，指派问题的数学模型[3]如下：Maxz=■■c■x■（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]设计是完成遗传运算的具体方法，涵盖了决策变量的基因型与表现型之间的编码和解码，个体适应度函数构造，遗传算子构建，控

6、制参数设置等过程。2.2.1指派问题适应度函数针对指派问题在求解目标函数为极大值时的情况和考虑指派问题可行解的非负性前提下，其个体适应度与目标函数值是成正比。因此，指派问题的适应度函数构建为如下所示：F=■■c■x■其中，x■表示第i个人是否去做第j个任务。c■表示第i个人完成第j个任务的效率。6F越大，表示个体适应度越好，其可行解越好，能够以较大概率遗传到下一代。当F取值最大时，则表示已经达到最优解。2.2.2指派问题染色体编码染色体[5]编码质量是影响遗传算法计算效率和准确度的重要因素。考虑到指派问题的特殊约束性质：即每人只能完成其中一个任务且

7、每个任务只能由一人完成。针对决策变量x■的取值，其基因型编码不采取通常的0-1二进制编码，而采用常用的十进制编码。并且，每个基因块只有两个基因位，分别表示决策变量的行下标取值和列下标取值。当问题规模为n时，则指派问题决策变量染色体编码表示为：在这种染色体编码十进制表示方式下，对于每个个体，其染色体的n个基因块在处理时按照如下规则进行：①各代群体每个染色体中各基因块第一位分别赋予固定值：范围为0到n-1，即R11=0，R21=1，…Rn1=n-1。其目的是保证决策变量选取位于不同行。②各代群体每个染色体中各基因块第二位分别赋予无重复随机值：范围为0到

8、n-1，即R12、R22…Rn2每次取0到n-1的随机全排列值。目的是保证决策变量选取位于不同列。6通过这种方式进行指派问