毕业设计-学分制模式下基于遗传算法.doc

1、 普 通 本 科 毕 业 论 文 (设 计 )题 目: 学分制模式下基于遗传算法的排课系统的设计I摘 要排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为 NP 完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决 NP 问题非常有效。本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法

2、、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。【关键词】学分制模式；排课系统；遗传算法；多目标优化IIDesign of the Course Arrangement System Based on Genetic Algorithms in Credit ModeAbstract：The problem of course arrangement is an optimization problem with multi-constraints and multi-objective, which is actually a timeta

3、ble problem and has been proved to be a NP-completed problem. As a ramdom searching algorithm, the genetic algorithm(GA) using colony searching technology is very suitable for NP-completed problem.This thesis uses GA for the course arrangement system with credit mode. Therough analyzing deeply the f

4、actors and constraints of course arrangement, the optimization objectives of course arrangement are determined first. Then the coding mode for genetic operations is designed and the computation method for reasonable fitness is given. An optimized course table is gotten through the operations of sele

5、ction, recombination and mutation on the initial colony.Based on the object-oriented method, this design makes use of classroom schedule algorithm, genetic fill algorithm and conflict detecting algorithm to arrange course. The experiments are carried out using real data to analyse the influence of a

6、ll parameters on the genetic operations and results.Keywords：Credit Mode; Course Arrangement System; Genetic Alogrithm; Multi-objective OptimizationIII目 录1 引言 .12 遗传算法 .22.1 遗传算法研究的内容 .32.2 遗传算法的基本术语 .42.3 遗传算法的基本思想 .52.4 遗传算法的基本操作 .63 排课系统的需求分析 .83.1 排课系统的业务流程分析 .83.2 排课因素分析 .103.3 排课的约束条件 .114 基于遗

7、传算法的排课算法的描述 .124.1 排课问题的目标分析 .124.2 排课系统中的基本算法 .154.2.1 排课算法的面向对象的应用 .154.2.2 教室调度算法 .174.2.3 基因初始化算法 .184.2.4 冲突检测算法 .194.3 排课问题中遗传算法的设计 .194.3.1 遗传算法的编码 .194.3.2 初始种群的产生 .204.3.3 遗传操作的设计 .204.3.4 适应度函数的设计 .22IV5 实验及结果分析 .225.1 排课系统开发环境 .225.2 参数设置对排课效率的影响 .235.3 结果分析 .266 总结与展望 .27参考文献 .29江西财经大学本科

8、毕业设计11 引言排课问题是高校日常教学工作和其他各项活动的基础。课程表不仅是老师和学生上课的依据，也对学校的其他工作的安排有一定影响。利用计算机辅助排课，是教学管理实现科学化，现代化的重要课题之一。目前高校招生逐年扩张，学生人数不断增加，再加上大多数高校实行学分制，课程开设逐渐向着广度和深度扩展，但学校的教学资源及设备却得不到及时补充，这些都给教务处排课人员造成很大的压力。单纯采用劳动强度大、效率低的手工排课，已成为提高教学管理质量的瓶颈。随着计算机在教学工作中的普及应用，利用计算机进行自动排课已经成为一个重要的研究课题。排课问题不仅是教学管理工作中必需面对的问题，而且也是运筹学中研究的一个

9、问题时间表问题 (TimeTable Problems，简记 TTPS)。排课问题的研究始于 20 世纪 50 年代末，但直到 1963 年，Gotlieb 在他的文章中对排课问题进行了形式化描述并提出了排课问题的数学模型 1，才标志着排课问题的研究进入科学的殿堂。但由于在实践中遇到的困难，人们对排课问题的解是否存在产生了疑问。1976 年，S Even 和 Cooper 等人证明了排课问题是 NP 完全问题2,3，这虽然回答了在排课实践中遇到困难的原因，但同时宣布计算机解决排课问题无法实现，因为计算机难解性理论指出，现代计算机尚未找到解决 NP 完全问题的多项式算法。我国对排课问题的研究始于

10、 20 世纪 80 年代初期，所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统。吴金荣把排课问题化成整数规划来解决 4，但计算量很大，而且仅仅适用于规模很小的排课问题。何永太、胡顺仁等人试图用图论中的染色问题来求解排课问题 5,6，但染色问题本身也是排课问题。基于专家系统的求解算法将专家系统知识引入排课问题的求解 7，能有效组织排课过程中的知识。但由于实际排课问题存在各种各样的限制条件与特殊要求，至今没有一个有效地普遍适用的排课算法。随着现代智能优化技术的出现和发展，模拟退火算法、禁忌搜索算法、蚁群算法、遗传算法等被应用到排课问题中。模拟退火算法(Simulated Anneal

11、ing)是 Kirkpatrick 等人于 1983 年首先提出的，它是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题间的相似性。在对固体物质进行退火处理时，常先将它加温使其粒子可自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能量的基态。优化问题也存在类似过程。模拟退火江西财经大学本科毕业设计2法被用来解决许多实际应用中的优化问题，取得了不错的效果，用其解决排课问题 8，现在还处在模型实验阶段，还有许多问题要解决。禁忌搜索的

12、思想最早由 Glover 于 1986 年提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。文献9中提出了结合网络流算法与禁忌搜索算法的优势，求解排课问题的方案，虽然得出了可行解，但结果不够理想，很多优化因素没有考虑。蚁群算法是随着仿生学的发展而发展起来的，它是由意大利学者 M.Dorigoz 在 20 世纪 90 年代初提出的，它通过模拟蚁群觅食的过程中寻找最短路径的方法来求解优化问题。文献10提出了

13、基于二部图的排课模型，并揉合蚁群算法 AS、ACS、MMAS 三个不同模型的优点，提出一种面向排课问题的改进型蚁群算法，但是问题求解复杂，操作繁琐。上述算法都是一定程度上的启发搜索算法，但是搜索过程的启发信息依赖于实际情况，排课问题求解只能针对个别的实际问题，且没有引入目标优化技术，更不用说人性化方面的考虑。正是因为如此，具有智能性、并行性和高鲁棒性的遗传算法迅速应用于排课问题，并得到了很快的发展。本文正是在上述背景下展开的，在分析和实践的过程中，针对江西财经大学排课问题的具体情况，结合排课问题中常见的约束及优化目标，采用了一种适应于排课问题的编码方法，并将遗传算法应用到课表的优化，以此获得最

14、终的排课方案。2 遗传算法遗传算法(Genetic Algorithm, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它出现在 20 世纪 60 年代，最早是由美国密执安大学的 John Holland 教授与其同事、学生研究形成的一个比较完整的理论和方法，在一系列研究工作的基础上，80 年代由 Goldberge 进行归纳总结，形成了遗传算法的基本框架。经过 20 余年的发展，计算机智能已经成为人工智能研究的一个重要方向，以及后来人工生命研究的兴起，使遗传算法受到广泛关注。从 1985 年 在 美 国 卡 内 基 梅 隆 大 学 召 开 的 第 一 届

15、 国 际 遗 传 会 议(International Conference on Genetic Algorithms： ICGAs， 85)， 到 1997 年 5 月 ， IEEE的 Transaction on Evolutionaly Computation 创刊，遗传算法作为系统优化、自适应和学习的高性能计算和建模方法的研究日趋成熟 3。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随江西财经大学本科毕业设计3机、自适应的搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。简单的讲，它

16、使用了群体搜索技术，从而产生新一代的种群，并逐步使种群进化到近似最优解的状态。遗传算法是多学科结合与渗透的产物，从产生至今已广泛地运用于包括工程设计、制造业、人工智能、计算机科学、生物工程、石油勘探、自动控制、社会科学、商业和金融等各个领域。2.1 遗传算法研究的内容遗传算法的研究主要集中在编码方法、适应函数、遗传算子、遗传算法参数选择、全局收敛性和搜索效率的数学基础、欺骗问题、收敛性分析、局部收敛及混合遗传算法等 8。本文在将遗传算法应用到排课问题中时，对遗传算法的编码、适应函数的设计、遗传算子、遗传算法参数的选择等进行了分析 11。(1) 编码方法遗传算法的编码在许多问题的求解中，对算法的

17、性能有很重要的影响。简单二进制编码的采用得到了 Holland 早期理论结果（Schema 定理、最小字母表原理）的支持，但仍有很多不足之处。灰色编码可用于克服二进制编码映射的不连续问题。动态参数编码的提出是为了克服搜索效率与表示精度间的矛盾，同时对克服过早收敛现象也有所帮助。此外，多值编码、实值编码、区间值编码、Delta 编码、对称编码以及将以往的合成编码分解成多个相对独立编码的独立编码策略等多种编码方法也都被证明各有优缺点。这些编码方法的提出是启发式的，缺乏一个理论基础来判断各种编码方法的好坏并指导它们的设计。为解决二进制编码带来的“组合爆炸” 和遗传算法的早熟收敛问题，提出了十进制编码

18、。根据 Holland 教授提出的编码应该有利于交叉变异操作的编码原则 4，本文设计了适用于排课问题的编码模型。(2) 适应函数的设计在遗传算法中，适应度值是用来区分群体中个体好坏的标志。遗传算法正是根据适应值对个体进行选择的。在实际操作中，适应函数的设计对算法的收敛性及收敛速度的影响较大。本文根据排课问题的求解目标，并考虑系统与排课者的交互，设计了合理的适应度函数。(3) 遗传算子遗传算法的三个算子分别是选择、交叉和变异。选择体现“适者生存”的原理，通过适应值选择优质个体而抛弃劣质个体。杂交能使个体之间的遗传物质进行交换从而产生更好的个体。变异能恢复个体失去的或未开发的遗传物质，以防止个体在

19、形成最优解过程中过早收敛。江西财经大学本科毕业设计4 选择策略是遗传算法中的很重要的一个环节。由于其对遗传搜索过程具有较大的影响，很多人早就意识到它在遗传算法中的重要性。所以近年来，不同的遗传策略相继被提出。Potts 等人概括了 23 种选择策略。Goldberg 首先引入了选择算子的收敛模型，随 后 ， 他 和 Deb 又 作 了 扩 展 ， 并 提 出 取 代 时 间 概 念 ，可 以 对 各 种 选 择 策 略 之 间 选 择 压 力 进 行 定 量 分 析 。 Muhlenbein 和 Schlierkamp-Vossen 讨论了选择强度在收敛分析中的应用。Back 对选择压力进行推

20、广。后来为解决模式里有太大的变动或遗传算法欺骗问题，有人提出了具有破坏性选择的遗传算法。 交叉操作使不同个体间的基因相互交换。Potts 概括了 17 种交叉方法。吴少岩等研究了交叉算子与其探索子空间之间的关系，并提出了设计良好算子的指导性原则，并构造出一种启发式交配算子。 变异是一种防止早熟的操作。Potts 总结的变异技术有管理变异，变化的变异概率和单值运算。本文根据这些相关算子设计原则，设计了有利于排课操作的遗传算子。(4) 参数的选择遗传算法的群体规模、收敛判据、交叉概率和变异概率都对排课算法的效率有很大影响，但这些参数的设置还缺少相应的理论指导。由于参数选择关系到算法的精度、可靠性和

21、计算时间等诸因素，并影响到结果的质量和系统性能，因此参数选择的研究受到重视。本文各参数的设置主要是建立在实验的基础上。2.2 遗传算法的基本术语既然遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机算法，那么我们先分析几个生物学的基本概念与术语，这对理解和运用遗传算法是非常重要的 13。(1) 染色体(chromosome)生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子基因组成。遗传因子(Gene) DNA 或 RNA 长链结构中占有一定位置的基本遗传单位，也称为基因。生物的基因数量根据物种的不同多少不一，小的病毒只含有几个基因，而高等动植物的基因却数

22、以万计。(2) 个体(individual)指染色体带有特征的实体，在问题简化的情况下可用染色体代替。(3) 种群(population)染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小江西财经大学本科毕业设计5或种群的规模。有时个体的集合也称为个体群。(4) 进化(evolution)生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。(5) 适应度(fitness)在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种将获得更多的繁

23、殖机会，而对生存环境适应程度较低的物种，其繁殖的机会就会相对较少，甚至逐渐灭绝。(6) 选择(selection)指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。正如达尔文描述的，适者生存。(7) 复制(reproduction)细胞在分裂时，遗传物质 DNA 通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。(8) 交叉(crossover)有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组(recombination

24、)，俗称“杂交” 。(9) 变异(mutation)在细胞进行复制时可能以很小的概率产生某些复制差错，从而使 DNA 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。(10) 编码(coding)DNA 中遗传信息在一个长链上按一定的模式排列，即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。(11) 解码(decodi ng)编码的逆过程，即从遗传子型到表现型的映射。2.3 遗传算法的基本思想通过以上分析，我们可以更好的描述遗传算法。遗传算法是从代表问题可能潜在解集的一个种群(population)开始的，而一个种群则由经过基因(Gene)编码(coding)的一定数目的个体 (individual)（或染色体）组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（基因型）是某种基因组合决定的。初始种群产生