遗传算法在事务型问题中的应用研究(刘超英文) 下载本文

遗传算法在事务型问题中的应用

刘超

Genetic Algorithm in transactional Problem

LIUCHAO

武汉职业技术学院 计算机技术与软件工程学院

WuHan Polytechnic of Computer Technology and Software Engineering

摘要:在遗传算法提出之初,我们解决的多是值类运算类型的问题,对染色体基因的编码则以二进制编码为优。但生活中很多问题都不是值类型的,很难用一个具体的数值来确定答案的正确性和最优度。这就需要根据不同的问题类型开发出不同的编码方法来。 关键词:遗传算法;编码;事务类型

Abstract: in the genetic algorithm was first, our solution is the value of multi-class computing

types of problems, on chromosome gene coding, the binary encoding is best. However, many problems in life are not value types, it is difficult to determine a specific numerical answer is correct and the optimal degree. This need to develop different types of problems different encoding methods

Keywords: Genetic Algorithm;coding;service type

遗传算法简称GA(Genetic Algorithm)是一种模拟自然界中遗传和选择机制的寻找最优解的方法。他的基本原理来自于达尔文的生物进化论和盂德尔的基因学说。遗传算法模拟自然界的遗传和进化原则,一步步修订解决问题的方案使之接近完美。

遗传算法的优势在于可以绕过复杂的数学推演,而采用最直接的方式在有限的结果集中搜索更优的结果。遗传算法通过设定一个初始种群,即一个预设的结果。并对这个初始种群进行基因突变和杂交,留下好的基因改变不好的基因,使种群不停的进化,最后得到一个最优的或趋进于最优的结果。

遗传算法求解问题的步骤主要有4个部分组成。 第一步是编码。其主要工作是把问题中的各分量分别进行编码后合并成一个二进制的位串。每个二进制的位串就表示一种解决问题的可能解。

第二步是生成初始种群。遗传算法不能凭空生成解决问题的答案,他只能在已有答案的基础上进行优化,使答案更接近我们的要求。可以通过各种方法,生成一组随机的初始种群的个体,然后按照一定的规则和要求计算出每个个体的适应度。适应度表示出了根据每种个体解决问题,满足我们要求的程度。适应度越高,说明该个体越满足我们的要求。

第三步是选择,即遗传。从每一代种群中选取优良的个体保留到下一代种群中。一般采用的方式是依照适应度给种群中的个体排序,保留适应度较高的一部分个体,淘汰掉适应度低的那部分个体。

第四步是变异和交叉。被淘汰的个体不可以直接保留到下一代种群中,需要进行变异和交叉,改变编码成为一个新的个体后进入下一代种群,然后重新计算适应度和排序。重复第三步和本步骤直到找到满意的个体为止。

从上面的解题步骤可以看出,遗传算法在解决值类型问题时是有很大优势的。对染色体的二进制基因编码方式,既方便进行第四步的变异和交叉,又吻合了计算机内部的二进制运

算。但是,当运用遗传算法解决事务型的问题时,这样的编码方式还一样的好用么?

下面我们以高校排课为例对遗传算法编码方式进行的分析。

高校排课中,一般是连续的2小节课一起上的,根据上课的课程、教师、班级不同把课程分为不同的课程对象,每个对象代表一次大课,上课教师、课程、班级就是课程对象的属性。那么在排课时需要给每个课程对象安排上课时间和上课的教室,并且不能给同一个课程对象安排相同的上课时间和教室。对于有相同教师属性或相同班级属性的课程对象都不能出现在同一个上课时间上,因为同一个教师或班级不可能在同一时间在两个教室上两门课。

从上述排课问题分析中,我们可以发现需要编码的染色体有两个基因:上课时间和上课地点。如果使用二进制编码方式来编码,则可以把上课时间和地点分别表示为两个二进制串,然后组合到一起。前M位表示上课时间,后N位表示上课地点,整个染色体需要M+N位来表示上课的时间和地点安排。但现实中,上课时间和上课地点的取值范围并不能正好用二进制表示完整,一般会有一部分二进制编码是无效的,不表示任何上课时间和上课地点。当我们要将这些无效的数据给剔除出来时,就需要将二进制表示的信息还原为之前表示的上课时间和上课地点的形式,以方便我们做出对比找出无效的数据。这给我们的操作带来了很多的麻烦。而且现实中上课时间和上课地点也不是一个连续的值。星期一的最后一节课与星期二的第一节课实际上是分开的,不能看做是连续的两节课,使用二进制的编码不能对此进行有效的判断。所以有必要找到一种新的编码方式来解决这些问题。

在事务型问题中,我们没有必要按照经典的方式来把染色体表示成一维二进制编码,可以根据具体的问题,设计合适的编码方式。对于上述排课问题,我们可以把染色体设计成二维的二进制编码。上课时间和上课地点做为横纵坐标,将课程对象填如其中,这样就避免了上课时间和上课地点的潜在冲突,不会出现撞车了。在进行交叉和变异时可以按照教师或班级为单位进行,对同一个教师的课程对象进行统一的交叉或变异操作,可以更快的得到满意的结果。改造后的染色体可以以P(TIME,ADRESS)的方式表示。在交叉和变异操作时可以分开进行,TIME和ADRESS分别进行交叉和变异,加快搜索的速度和准确度。

对于教师、班级和课程则不一定要使用二进制编码,因为事务型问题的适应度计算不是简单的数值大小就能表现的。根据情况不同,计算适应度的规则也不相同,采用和原数据相同的编码则有助于适应度的计算。对于排课问题,我们可以把教师、课程名称和班级封装起来做为课程对象的属性,编码采用和数据库中相同的编码方式,方便和数据库的连接减少编码和解码的操作。

计算染色体的适应度时,根据具体的情况设定计算规则。把非数值化的条件数值化,然后将各条件的数值进行合并,最后得出一个综合的适应度。以把同一教师的课连续安排在一起为例,当有同一教师的不同课程时间安排相邻时,增加适应度的值反;反之则减少。那么适应度越高,教师们的课程就越相对集中。同样把上课地点加入适应度的计算,当同一教师的上课地点越少,则相应增加适应度,反之减少。这样把没有量化的标准量化之后,就能很直观的计算出染色体的适应度。

把问题的标准量化,可以使我们很清楚的计算出各染色体的适应度,并保留最优的一部分遗传到下一代。但是现实生活中很多标准量化起来有一定的难度。这个时候我们需要寻找一些其他的方法来判定和保留优秀的个体,这需要针对具体的问题来具体的分析。对于排课问题,我们的要求是同一老师的课尽量安排到一起。这样我们在选择保留的染色体时,可以保留同一教师安排连在一起的课程对象,把分散的染色体重新变异和交叉。这样连在一起的课程就会保留下来,而分开的课程就会不停的改变上课时间和地点直到最后都满足要求或不能改变为止。这种方法避开了计算染色体的适应度,直接保留满足要求的染色体,变异和交叉不满足要求的染色体,直到达到最佳效果。这种方法适用与类似排课这样的排序问题。

综上所述,在运用遗传算法解决问题时,我们不一定要使用一维二进制的编码方式,甚

至不要一定使用二进制编码。根据实际的情况和具体的环境,可以灵活的采用二维或多维的编码方式,也可以使用十进制、字符串等其它编码方式方便与数据库进行无缝交流,减少编码和解码的工作提高效率。保留染色体的方法不一定要计算出适应度,可以根据具体的情况设计更合理的方法,来完成遗传操作,提高准确度和效率。

每一种算法的提出都有一个不断发展和完善的过程。遗传算法诞生之初,多用于解决值类型的问题,使用一维的二进制编码方式能使染色体和计算机内部数据相统一。随着遗传算法在事务型问题中的应用,简单的二进制编码方式已经不能满足事务型问题中丰富多样的表示需求,我们可以根据具体的情况修改它的编码方式和遗传方式,以满足实际的需求。计算机硬件技术的发展也为提高计算机硬件消耗以降低程序设计难度的方案提供了物质基础。相信在不久的将来遗传算法技术在各学科中的研究应用将更为广泛。