目 录
1 引言 1
2 遗传算法简介 1
2.1 遗传算法的基本术语 2
2.2 遗传算法的基本思想 3
2.3 遗传算法的基本操作 4
3 排课问题的需求分析 5
3.1 排课问题的业务流程分析 5
3.2 排课因素分析 8
3.3 排课的约束条件 9
4 基于遗传算法的排课算法的描述 10
4.1 排课问题的目标分析 10
4.2 排课系统中面向对象的应用及用到的算法 13
4.2.1 排课算法的面向对象的应用 13
4.2.2 教室调度算法 15
4.2.3 基因初始化算法 16
4.2.4 冲突检测算法 17
4.3 排课问题中遗传算法的设计 17
4.3.1 遗传算法的编码 17
4.3.2 初始种群的产生 18
4.3.3 遗传操作的设计 18
4.3.4 适应度函数的设计 20
5 实验及结果分析 20
5.1 排课系统开发环境 20
5.2 实例说明及参数设置对排课效率的影响 20
5.3 结果分析 23
5.3.1 排课结果分析 23
5.3.2 与人工排课的比较 24
6 结束语 25
参考文献 26
利用上述术语，我们可以更好的描述遗传算法。遗传算法是从代表问题可能潜在解集的一个种群(population)开始的，而一个种群则由经过基因(Gene)编码(coding)的一定数目的个体(individual)（或染色体）组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（基因型）是某种基因组合决定的。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度(fitness)大小挑选(selection)个体，并借助于自然遗传学的遗传算子(geneticoperators)进行组合交叉(crossover)和变异(mutation)，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码(decoding)可以作为问题近似最优解。遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与临域等。计算开始时，随机地初始化一定数目的个体(父个体1、父个体2、父个体3、父个体4、…、父个体N)形成初始种群，并计算每个个体的适应度函数，第一代(初始代)就产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组(交叉)而产生子代，所有的子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代(子个体1、子个体2、子个体3、子个体4、……)。这一过程循环执行，直到满足优化准则为止[8]。遗传算法的过程如图2-1所示。
2.3 遗传算法的基本操作
遗传算法包括三个基本操作：选择、交叉和变异。这些基本操作又有许多不同的方法，下面我们简要进行介绍：
(1) 选择(selection)
遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算[3]。
① 选择是用来确定重组或交叉个体，以及被选个体将产生多少子代个体。首先计算个体适应度，具体有以下算法：
(a) 按比例的适应度计算(proportional fitness assignment)
(b) 基于排序的适应度计算(rank-based fitness assignment)
② 适应度计算之后是实际的选择，按照适应度进行父代个体的选择。可以挑选以下的算法：
(a) 轮盘赌选择(roulette wheel selection)
(b) 随机遍历抽样(stochastic universal sampling)
(c) 局部选择(local selection)
(d) 截断选择(truncation selection)
(e) 锦标赛选择(tournament selection)
(2) 交叉或重组基因(crossover/recombination)
遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法[3]。
基因重组是结合来自父代交配种群中的信息产生新的个体。依据个体编码表示方法的不同，可以有以下的算法：
① 实值重组(real valued recombination)
(a) 离散重组(discrete recombination)
(b) 中间重组(intermediate recombination)
② 二进制交叉(binary valued crossover)
(a) 单点交叉(single-point crossover)
(b) 多点交叉(multiple-point crossover)
(c) 均匀交叉(uniform crossover)
(d) 洗牌交叉(shuffle crossover)
(e) 缩小代理交叉(crossover with reduced surrogate)
(3) 变异(mutation)
遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体[3]。
交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化。依据个体编码表示方法的不同，可以有以下的算法：
① 实值变异
② 二进制变异
3 排课问题的需求分析
排课系统的设计必需建立在对排课流程的详细分析的基础之上。由于各学校自身情况、采用的教学模式(学分制或学年制)的不同，导致各学校排课流程存在差异，本文以江西财经大学为分析对象，设计出适合学分制模式下的高校排课算法[9,10]。
