【34页】【毕业设计】学分制模式下基于遗传算法的排课系统的设计.doc源文档全文在线看
1、手机端页面文档仅支持阅读 15 页,超过 15 页的文档需使用电脑才能全文阅读。
在对固体物质进行退火处理时,常先将它加温使其粒子可自由运动,以后随着温度的逐渐下降,粒子逐渐形成低能态晶格。
若在凝结点附近的温度下降速率足够慢,则固体物质定会形成最低能量的基态。
优化问题也存在类似过程。
模拟退火法被用来解决许多实际应用中的优化问题,取得了不错的效果,用其解决排课问题,现在还江西财经大学本科毕业设计处在模型实验阶段,还有许多问题要解决。
禁忌搜索的思想最早由于年提出,它是对局部领域搜索的种扩展,是种全局逐步寻优算法,是对人类智力过程的种模拟。
禁忌搜索算法通过引入个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。
文献中提出了结合网络流算法与禁忌搜索算法的优势,求解排课问题的方案,虽然得出了可行解,但结果不够理想,很多优化因素没有考虑。
蚁群算法是随着仿生学的发展而发展起来的,它是由意大利学者在世纪年代初提出的,它通过模拟蚁群觅食的过程中寻找最短路径的方法来求解优化问题。
文献提出了基于二部图的排课模型,并揉合蚁群算法三个不同模型的优点,提出种面向排课问题的改进型蚁群算法,但是问题求解复杂,操作繁琐。
上述算法都是定程度上的启发搜索算法,但是搜索过程的启发信息依赖于实际情况,排课问题求解只能针对个别的实际问题,且没有引入目标优化技术,更不用说人性化方面的考虑。
正是因为如此,具有智能性并行性和高鲁棒性的遗传算法迅速应用于排课问题,并得到了很快的发展。
本文正是在上述背景下展开的,在分析和实践的过程中,针对江西财经大学排课问题的具体情况,结合排课问题中常见的约束及优化目标,采用了种适应于排课问题的编码方法,并将遗传算法应用到课表的优化,以此获得最终的排课方案。
遗传算法遗传算法,是模拟生物在自然环境中的遗传和进化过程而形成的种自适应全局优化概率搜索算法。
它出现在世纪年代,最早是由美国密执安大学的教授与其同事学生研究形成的个比较完整的理论和方法,在系列研究工作的基础上,年代由进行归纳总结,形成了遗传算法的基本框架。
经过余年的发展,计算机智能已经成为人工智能研究的个重要方向,以及后来人工生命研究的兴起,使遗传算法受到广泛关注。
从年在美国卡内基梅隆大学召开的第届国际遗传会议到年月,的创刊,遗传算法作为系统优化自适应和学习的高性能计算和建模方法的研究日趋成熟。
遗传算法是种借鉴生物界自然选择和进化机制发展起来的高度并行随机自适应的搜索算法。
其主要特点是群体搜索策略和种群中个体之间的信息交换。
由于其具有健壮性,特别适合于处理传统搜索算法解决不好的复杂的和非线江西财经大学本科毕业设计性问题。
简单的讲,它使用了群体搜索技术,从而产生新代的种群,并逐步使种群进化到近似最优解的状态。
遗传算法是多学科结合与渗透的产物,从产生至今已广泛地运用于包括工程设计制造业人工智能计算机科学生物工程石油勘探自动控制社会科学商业和金融等各个领域。
遗传算法研究的内容遗传算法的研究主要集中在编码方法适应函数遗传算子遗传算法参数选择全局收敛性和搜索效率的数学基础欺骗问题收敛性分析局部收敛及混合遗传算法等。
本文在将遗传算法应用到排课问题中时,对遗传算法的编码适应函数的设计遗传算子遗传算法参数的选择等进行了分析。
编码方法遗传算法的编码在许多问题的求解中,对算法的性能有很重要的影响。
简单二进制编码的采用得到了早期理论结果定理最小字母表原理的支持,但仍有很多不足之处。
灰色编码可用于克服二进制编码映射的不连续问题。
动态参数编码的提出是为了克服搜索效率与表示精度间的矛盾,同时对克服过早收敛现象也有所帮助。
此外,多值编码实值编码区间值编码编码对称编码以及将以往的合成编码分解成多个相对编码的编码策略等多种编码方法也都被证明各有优缺点。
这些编码方法的提出是启发式的,缺乏个理论基础来判断各种编码方法的好坏并指导它们的设计。
为解决二进制编码带来的组合爆炸和遗传算法的早熟收敛问题,提出了十进制编码。
根据教授提出的编码应该有利于交叉变异操作的编码原则,本文设计了适用于排课问题的编码模型。
适应函数的设计在遗传算法中,适应度值是用来区分群体中个体好坏的标志。
遗传算法正是根据适应值对个体进行选择的。
在实际操作中,适应函数的设计对算法的收敛性及收敛速度的影响较大。
本文根据排课问题的求解目标,并考虑系统与排课者的交互,设计了合理的适应度函数。
遗传算子遗传算法的三个算子分别是选择交叉和变异。
选择体现适者生存的原理,通过适应值选择优质个体而抛弃劣质个体。
杂交能使个体之间的遗传物质进行交换从而产生更好的个体。
变异能恢复个体失去的或未开发的遗传物质,以防止个体在形成最优解过程中过早收敛。
选择策略是遗传算法中的很重要的个环节。
由于其对遗传搜索过程具有较大的影响,很多人早就意识到它在遗传算法中的重要性。
所以近年来,不同江西财经大学本科毕业设计的遗传策略相继被提出。
等人概括了种选择策略。
首先引入了选择算子的收敛模型,随后,他和又作了扩展,并提出取代时间概念,可以对各种选择策略此时遗传操作所用的时间为衡量遗传效率的标准。
江西财经大学本科毕业设计每次实验我们进行次测试,最终取平均值作为此次实验的遗传效率值。
具体见表。
表种群规模对排课效率的影响单位秒编号实验实验二实验三平均值由上表可以看出,当种群规模增大时,最优个体达到定的适应度所需的时间越短,遗传算法的效率越高。
但是并不是说种群规模越大越好,种群越大,种群的交叉,变异所用的时间就越多。
经过多次测试,本文取种群规模为。
交叉概率对排课效率的影响交叉操作是产生新个体的重要操作,交叉概率决定了交叉操作的频率。
交叉概率越大,则频率越高。
当交叉频率很高时,可以很快地收敛到最优解区域。
般选择较大的交叉概率,以尽量产生优秀的个体。
但交叉频率过高时,可能造成种群早熟,得到局部最优解。
本文分别测试了交叉概率为时,遗传效率的大小。
结果如表所示。
表交叉概率对排课效率的影响单位秒编号实验实验二实验三平均值从表可以看出,交叉概率越大,遗传效率越高。
排课问题在充分交叉的情况下,可明显提高效率。
所以本文取交叉概率为。
变异概率对排课效率的影响在自然界中,生物产生变异基因突变的概率是很小的,正是因为如此,种江西财经大学本科毕业设计群在世代相传。
同样,为了维持种群的稳定性,遗传操作中变异概率不能设置过大。
但是当变异概率设置过小,却会导致全局搜索难于进行,因为缺少变异,种群往往在局部搜索,很难跳出来。
这就使得些资源难以得到利用,这样往往排不出课表或课表质量较差。
本文测试了交叉概率为时,遗传效率的大小。
表交叉概率对排课效率的影响单位秒编号实验实验二实验三平均值从表可以看出,过低的变异概率导致遗传效率较低,过大的变异概率导致种群的遗传效率严重下降。
本文取。
遗传代数对排课结果的影响遗传代数决定遗传操作的次数,遗传代数越大,遗传操作所用的时间相应增加。
如果遗传代数过小,种群还没有收敛到最优解就结束。
当遗传代数过高时,种群可能会出现大量同个体,种群几乎停止进化,甚至可能出现退化。
本文测试了遗传代数为时,所得出的最优课表的适应度值,如表所示。
表遗传代数对排课结果的影响编号实验实验二实验三实验四平均值从表可以看出,遗传代数并不是越大越好。
本文取遗传代数为。
江西财经大学本科毕业设计结果分析根据表的参数的设置,本文进行了次测试,结果如表所示。
表遗传操作结果表编号初始种群最大适应度值最优课表适应度值遗传操作耗时平均值从表可以看出,通过设计的排课算法对初始解进行优化,适应度平均提高了,适应度有明显的进化趋势,说明本文设计的染色体编码和适应度函数能够较好的反映排课的需求。
与传统的人工排课方式的比较如下相似方面无冲突性指课程表必须满足所有硬性约束。
无论是人工编排的课程表还是排课系统自动编排的课程表都不存在冲突问题,即没有同时间个教师上门以上课程个班级同时上门以上课程个教室同时间上门以上课程的冲突,且教室容量类型,课程安排的校区都符合教学任务书的要求。
无冲突性是个课程表必须满足的首要条件。
课程的日组合优度高周上课次数大于的课在周内分散安排,不管是对于教师还是学生来说都是有必要的。
教师在进行每节课的教学之前需要深入领会教学大纲的精神仔细研究教材内容恰当安排教学过程和认真编写教案。
过于连续的课程安排会使得这些工作受到很大的影响,进而影响到教师课堂讲解。
同样,对于学生来说,每次教学内容学习完毕后,学生需要时间来消化学习内容,进步理解和巩固所学知识。
过于连续的课程安排会使学生疲于应付新的知识,又由于进度太快,前面知识掌握不牢,造成无法掌握新知识。
另方面,连续的课程安排之后是相对的空闲,这使学生对新学习的知识缺乏巩固。
因此,课程的日组合优度是个课程表优劣的关键因素,这点,不管是人工编排的课程表还是系统编排的课程表江西财经大学本科毕业设计都具备了。
人性化根据老师的具体要求对课表进行编排,体现排课过程中人性化的考虑。
不管是人工排课还是排课系统排课,都会考虑老师的特殊要求。
例如,在本文中,我们考虑了如果时间段老师不能上课,则该时间不给其安排课程。
差异方面效率差异人工排课跟计算机系统排课最大的差异在于效率,在个拥有上万名学生,几千门课程的学校,要想排出个合理可行的课表,往往需要教务处工作人员忙碌十几天甚至个月。
而利用计算机系统排课,在设置好相应参数后,只需要几分钟最多几小时就可以排出可行的优化的课表。
且减少了人力的消耗。
时间安排对称方面的差异人工排课时,对周上课次数大于的课程的多次安排往往采用时间对称的方式。
如周学时为的课程,安排在周节周三节周五节或周节周三节周五节。
自动排课系统会尽量朝对称方面优化,但是结果往往会是周的节周三节周五节。
节次优度方面的差异人工排课时,会尽量给课程安排较好的时
