遗传算法的探究与应用

《遗传算法的探究与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、遗传算法的探究与应用摘要：随着全国各大高校的扩招，如何正规、科学、合理地安排好课程、教师、教室等诸多资源进行排课已经成为学校教务管理的重点与难点。随着人T智能领域的不断完善与发展，遗传算法山于其超群的并行搜索能力，以及在解决优化问题中体现出來的高度健壮性，迅速被应用于求解组合优化的排课问题。关键词：遗传算法；排课系统；优化中图分类号：TP301近些年來，伴随着“数字化校园计划”快速并逐步的向深入发展，传统高校中的教学管理模式也面临着重大的转变。有效运用计算机作为日常教学和教务的辅助管理已经成为各个高校实现数字化校园的工作垂点。遗传算法(Genetic

2、AlgorithmGA)是一类借鉴生物界的进化规律演化而来的高度并行、随机、自适应的搜索算法。S.even等人在1975年的研究证明了排课问题是NP-Complete问题［1］,非“枚举法”之外不能找出最优可行解。国内外，已有众多学者将遗传算法的原理应用于排课系统之屮，如，乔树青将遗传算法的运行区分为多种不同的机制应用于排课系统之中［2］；石慧运用基因对交叉遗传算法求解多校区排课问题［3］。但是山于约束条件过于宽泛，计算结果常常无法收敛于全局最优解。本文尝试利用遗传算法的原理对排课系统进行优化求解。1遗传算法描述遗传算法不同于传统的搜索算法［4］o遗

3、传算法依据编码方式以及初始条件随机生成一组解，这组解被称为种群(Population)。构成种群的每个解都被称为染色体(Chromosonie)。染色体通常是一组数据，这组数据被用来作为表示问题的解的代码，其木身不一定是一组可行解［5］。这些染色体在后续的迭代过程中部分会不断的进入到下一代的染色体Z中这被称为遗传。在每一代种群中用适应度值(Fitness)來表示染色体的优劣程度，并利用适应度函数来対一组染色体进行适应度的测量。测量后根据选择算法进行选择是否遗传到子代之中。由此生成的下一代染色体称为后代(Offspring)o后代是还有可能是通过父代交

4、叉和变异产生的个体。新一代形成中，根据适配值的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数，适配值高的染色体被选中的概率较高。据此，经过若干代之后，算法可能收敛于最好的染色体，它很可能就是问题的最优解或较优解。2排课问题分析及算法设计从数学角度来讲排课问题，实质上是在时间、班级、教师以及教室和课程的5维空间上，以教学计划中的各种要求所产生一些约束条件的组合规划问题［6］。所需要采取的就是对排课问题中的各个维度上的对象按照各个约束条件解决对象间的冲突。在解决冲突之前，首先由理清一下四种关系：(1)课程与教师Z间的映射，即每门课程的任教的教师有

5、哪些。(1)课程与的互斥关系，即在拓扑关系图中以时间描述的先后顺序。(2)课程与班级之间的映射，即需要学习木门课程的班级有哪些。（4）课程与时间的映射，即课程不能被安排在相同的时间段（更复杂的逻辑关系）。经过对高校排课系统的需求分析知道，若将教室维度加上很难在冇限的时间和空间存储条件下进行求解，并且在需求方对于教室安排并不是必须的，因此我们假设教室资源充足的前提下进行排课算法的设计。2.1个体表示在系统中笔者使用BYTE类型的三维数组来表示染色体个体（记为P）o其中第一维度（记为I维度）为班级编号classListSize,第二维度（记为J维度）为教

6、师编号teacherListSize,第三维（记为K维度）度为时间片编号timeSliceTotal。个体中存的值则为教师授课程编号。个体表示I班级在K时间上J教师所教授的第P门课程。如图1：byte[][][]chromosome二newbyte[classListSize][teacherListSize][timeSliceTotal]；图1染色体个体数据结构定义2.2评价函数评价根据班级所有相同课程的时间间隔度量值ti＞班级教师教授课程的时间间隔度量值tj、班级主干课程重要度度量值之和Sumi.班级上课教师的要求与课程安排符合程度度量值Sum

7、j,在此足义排课系统状态的评价特征特征向量X={ti,tj,Sumi,Sumj}0在域X上存在一个集合P,设存在一个数x与aPi（x）e[0,1]（xeX）——对应。定义个体差异度为nki=max{aPi,-aPk}/min{aPi,-aPk}o定义适应度函数为，n为特征值个数（n二4）。2.3选释算法选择算法选用轮盘赌算法，依据评价分值进行选择下一代种群轮。其中轮盘赌算法是依据个体的分值在整体分值总和中所占的比例，并使这个比例为该个体被选中的比率。然后通过设置伪随机数来进行个体选择并重复多次。2.4交叉算子与变异交叉运算是产牛新个体的主要方法[7]

8、,它是遗传算法的全局搜索能力的核心因素。为了保证排课系统自动生成的课表的合法性，不能直接使用单点交叉和双点交