《毕业设计学分制模式下基于遗传算法》由会员分享，可在线阅读，更多相关《毕业设计学分制模式下基于遗传算法（34页珍藏版）》请在金锄头文库上搜索。
1、. . . . . 普通本科毕业论文(设计)题 目: 学分制模式下基于遗传算法的排课系统的设计 学习好帮手摘 要排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法
2、、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。【关键词】学分制模式；排课系统；遗传算法；多目标优化Design 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 timetabl
3、e 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 fac
4、tors 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 select
5、ion, 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 all
6、 parameters on the genetic operations and results.Keywords：Credit Mode; Course Arrangement System; Genetic Alogrithm; Multi-objective Optimization目 录1 引言12 遗传算法22.1 遗传算法研究的内容32.2 遗传算法的基本术语42.3 遗传算法的基本思想52.4 遗传算法的基本操作63 排课系统的需求分析83.1 排课系统的业务流程分析83.2 排课因素分析103.3 排课的约束条件114 基于遗传算法的排课算法的描述124.1 排课问题的目标分
7、析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 适应度函数的设计225 实验及结果分析225.1 排课系统开发环境225.2 参数设置对排课效率的影响235.3 结果分析266 总结与展望27参考文献29 学习好帮手. . . . .1 引言排课问题是高校日常教学工作和其他各项活动的基础。课程表不仅是老师和学生上课的依据，也对学校的其他工作的安
8、排有一定影响。利用计算机辅助排课，是教学管理实现科学化，现代化的重要课题之一。目前高校招生逐年扩张，学生人数不断增加，再加上大多数高校实行学分制，课程开设逐渐向着广度和深度扩展，但学校的教学资源及设备却得不到及时补充，这些都给教务处排课人员造成很大的压力。单纯采用劳动强度大、效率低的手工排课，已成为提高教学管理质量的瓶颈。随着计算机在教学工作中的普及应用，利用计算机进行自动排课已经成为一个重要的研究课题。排课问题不仅是教学管理工作中必需面对的问题，而且也是运筹学中研究的一个问题时间表问题 (TimeTable Problems，简记TTPS)。排课问题的研究始于20世纪50年代末，但直到196
9、3年，Gotlieb在他的文章中对排课问题进行了形式化描述并提出了排课问题的数学模型1，才标志着排课问题的研究进入科学的殿堂。但由于在实践中遇到的困难，人们对排课问题的解是否存在产生了疑问。1976年，S Even和Cooper等人证明了排课问题是NP完全问题2,3，这虽然回答了在排课实践中遇到困难的原因，但同时宣布计算机解决排课问题无法实现，因为计算机难解性理论指出，现代计算机尚未找到解决NP完全问题的多项式算法。我国对排课问题的研究始于20世纪80年代初期，所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统。吴金荣把排课问题化成整数规划来解决4，但计算量很大，而且仅仅适用于规模
10、很小的排课问题。何永太、胡顺仁等人试图用图论中的染色问题来求解排课问题5,6，但染色问题本身也是排课问题。基于专家系统的求解算法将专家系统知识引入排课问题的求解7，能有效组织排课过程中的知识。但由于实际排课问题存在各种各样的限制条件与特殊要求，至今没有一个有效地普遍适用的排课算法。随着现代智能优化技术的出现和发展，模拟退火算法、禁忌搜索算法、蚁群算法、遗传算法等被应用到排课问题中。模拟退火算法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是基
11、于物理中固体物质的退火过程与一般优化问题间的相似性。在对固体物质进行退火处理时，常先将它加温使其粒子可自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能量的基态。优化问题也存在类似过程。模拟退火法被用来解决许多实际应用中的优化问题，取得了不错的效果，用其解决排课问题8，现在还处在模型实验阶段，还有许多问题要解决。禁忌搜索的思想最早由Glover于1986年提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则
12、来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。文献9中提出了结合网络流算法与禁忌搜索算法的优势，求解排课问题的方案，虽然得出了可行解，但结果不够理想，很多优化因素没有考虑。蚁群算法是随着仿生学的发展而发展起来的，它是由意大利学者M.Dorigoz在20世纪90年代初提出的，它通过模拟蚁群觅食的过程中寻找最短路径的方法来求解优化问题。文献10提出了基于二部图的排课模型，并揉合蚁群算法AS、ACS、MMAS三个不同模型的优点，提出一种面向排课问题的改进型蚁群算法，但是问题求解复杂，操作繁琐。上述算法都是一定程度上的启发搜索算法，但是搜索过程的启发信息依赖于实际情况，排课问
13、题求解只能针对个别的实际问题，且没有引入目标优化技术，更不用说人性化方面的考虑。正是因为如此，具有智能性、并行性和高鲁棒性的遗传算法迅速应用于排课问题，并得到了很快的发展。本文正是在上述背景下展开的，在分析和实践的过程中，针对江西财经大学排课问题的具体情况，结合排课问题中常见的约束及优化目标，采用了一种适应于排课问题的编码方法，并将遗传算法应用到课表的优化，以此获得最终的排课方案。2 遗传算法遗传算法(Genetic Algorithm, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它出现在20世纪60年代，最早是由美国密执安大学的John Hollan
14、d教授与其同事、学生研究形成的一个比较完整的理论和方法，在一系列研究工作的基础上，80年代由Goldberge进行归纳总结，形成了遗传算法的基本框架。经过20余年的发展，计算机智能已经成为人工智能研究的一个重要方向，以及后来人工生命研究的兴起，使遗传算法受到广泛关注。从1985年在美国卡内基梅隆大学召开的第一届国际遗传会议(International Conference on Genetic Algorithms：ICGAs，85)，到1997年5月，IEEE的Transaction on Evolutionaly Computation创刊，遗传算法作为系统优化、自适应和学习的高性能计算和
15、建模方法的研究日趋成熟3。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应的搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。简单的讲，它使用了群体搜索技术，从而产生新一代的种群，并逐步使种群进化到近似最优解的状态。遗传算法是多学科结合与渗透的产物，从产生至今已广泛地运用于包括工程设计、制造业、人工智能、计算机科学、生物工程、石油勘探、自动控制、社会科学、商业和金融等各个领域。2.1 遗传算法研究的内容遗传算法的研究主要集中在编码方法、适应函数、遗传算子、遗传算法参数选择、全局收敛性和搜索效率的数学基础、欺骗问题、收敛性分析、局部收敛及混合遗传算法等8。本文在将遗传算法应用到排课问题中时，对遗传算法的编码、适应函数的设计、遗传算子、遗传算法参数的选择等
