遗传算法在高职院校排课问题中的研究与应用

- 1 - 遗传算法在排课问题上的应用研究

遗传算法是一种基于自然选择的搜索算法，它可以在一组可能的解决方案中找到一个最优解，因此被广泛应用于基于最优解的问题中。在教育领域，排课是一个重要的问题，也是一个复杂的问题，有关排课的研究已经开展了很多年，但仍存在解决排课问题更有效的方法。因此，基于遗传算法在排课问题上的应用研究是一个值得研究的话题。

首先，本文将介绍遗传算法在排课问题上的应用，它的基本原理是通过不断的进化，以适应性优良的解决方案来解决排课问题。在排课中，遗传算法可用于解决课程安排问题、教室安排问题、课程冲突问题、运行时间问题等。它采用一种基因编码来表示排课问题，通过进行变异、交叉操作等染色体变换来改进排课方案。接下来，将研究以教室排课、课程安排两个方面的应用来深入讨论遗传算法在排课问题上的应用。

在教室排课方面，遗传算法可以实现有效的教室分配。它可以根据不同的课程的教室需求、教师的教室需求以及教室的可用时间来安排课程。其中，教师和教室的需求条件也可以设置不同级别的权重，从而更加细化设置排课条件，实现更有效的教室排课。此外，遗传算法可以考虑到各个教室之间的时间冲突，以及多个教室之间容纳参加课程学生的数量，从而实现更有效的教室排课。

在课程安排方面，遗传算法可以有效的帮助教师安排课程，以满足不同的教育要求，实现教师之间的合理分配和课程之间的平衡。通过编码人口，可以对课程进行编码，从而实现更好的课程安排。例如， - 2 - 可以根据课程的难度、学生的学习需求、教师的专业能力等因素来安排课程，从而实现更有效的课程规划。

此外，遗传算法也可以用于解决课程冲突问题，以及安排课程表的运行时间。当多个课程之间发生冲突时，可以采用遗传算法来解决冲突问题，从而保证排课的效率和准确性。另外，运行时间也可以通过遗传算法来优化，以满足课程表的需求。

本文讨论了遗传算法在排课问题上的应用，主要以教室排课和课程安排两个方面来讨论它的应用，还讨论了它解决课程冲突和运行时间问题的能力。通过这种应用，可以有效地解决排课问题，提高排课效率和准确性。因此，基于遗传算法在排课问题上的应用研究具有重要的现实意义。

遗传算法在排课问题上的应用研究

遗传算法在排课问题上的应用研究

排课问题是一类特定的调度问题，是日常性和生活中常见的问题，具有复杂的决策过程和可行解空间。由于排课问题所考虑到的因素众多，并且约束条件复杂，使得排课问题具有难度大、计算量大、搜索空间大等特点，这使得精确求解排课问题变得极其困难，已有不少学者将遗传算法引入排课问题的研究之中，这也成为当前研究的热点。

遗传算法是一种基于自然选择机制的模拟算法，它是一种仿生算法，是一种用于解决复杂优化问题的有效算法，是一种基于模拟的算法，它可以帮助我们解决复杂的优化问题，包括最大化和最小化目标函数的值，它在处理复杂的优化问题方面表现出了良好的性能。

遗传算法是一种进化算法，它将种群中的每一个个体看作是一个可行解，当满足一定约束条件后，经过一系列的选择、交叉、变异等过程，最终达到最优解。遗传算法在排课问题中可以根据求解目标，采用合适的选择、交叉、变异等进化算子，对种群进行进化，最终达到最优解。 由于排课问题的复杂性，已有不少学者将遗传算法引入排课问题的研究之中，并取得了良好的效果。首先，遗传算法可以快速地搜索出符合约束条件的可行解，其次，在处理复杂的约束条件时，遗传算法可以快速地求得最优解，并可以把结果保持在一定的范围内，最后，遗传算法可以有效的解决排课问题的约束条件，并且可以提高效率。

总之，遗传算法是一种有效的排课算法，它可以有效的处理排课问题的复杂约束条件，并可以快速的搜索出最优解。

关于遗传算法的排课应用研究　王志江　（广东轻工职业技术学院，广东广州５１０３００）　

［摘要］　随着高等院校招生规模逐渐扩大，各高校教躺｝课面临着紧张的资源分配和使用问题，本文通过排课　过程中遇到资源问题分析，对遗传排课算法处理排课问题提出建议，在面对繁杂的排课约束条件、排课规则中能排出　满意度高的课程表。　［关键词］　遗传算法；排课；研究　随着我国教育事业的快速发展，高校的办学规模逐步扩　大，教师和课室资源的紧张问题日益突显，手工排课不易于充　分利用资源的缺点更加突显，不能够高效的利用资源，在处理　复杂的排课问题就要花费更加大量的时间，而且准确性不高，　容易产生问题和冲突，影响教学质量。遗传算法的自组织性、　自适应性、并行性等为解决这个问题提供有效的方案。　１、排课问题　１．１课室资源。在班级和人数的增加的情况下，课室资源　显得紧张，更加需要充分的提高教室的利用的效率。在课室　资源中有三个要素：课室类型，课室上课时间，课室上课学　生人数。在对课室进行分析的时候，结合不同学校的数据中　可以得到：如计算机实验室【ｌ　Ｊ＿外语教学的语音室等课室需要　优先的满足安排。在安排课室的时候要尽量的按照班级的人　数安排课室，先把小的课室安排，然后再安排大的课室。为　了让课室资源从分的使用，在遗传算法基因变异的时候可以　使用课室的空闲时间进行变异，提高利用率。解决冲突问题，　排课过程中是一定不能出现冲突问题的，所以课室资源在安　排的时候一定要满足硬约束，同一个时间一间课室只能有一　位老师在上课。　１．２教学计划。目前各高校的专业分类增多，教学计划专　业课程的设置也随之增加，其中课程可以分为专业课程和基础　课程两大类。在各高校中都需要优先合理的安排，使得专业的　教学效果更加好。在教室资源无法满足的情况下，基础课程的　时间安排需要进行灵活的安排，如安排在晚上时间。目前许多　学生缺乏体育锻炼的意识，在高校增多体育课程安排，也需要　考虑安排在体育课程之前的课程和之后的课程最好不安排专　业课程，基础公共课程比较合适，体育运动后身体会有恢复的　过程，精力比较难集中。　１．３班级课表。在班级课表中，各门课程合理的均匀分布，　一天最好不要安排整天的课程，这样学生会觉得很疲劳，学习　的效果不理想。专业课程和基础课程分开间隔安排，让学生能　够有充足的时间对知识进行消化，完成课程作业。在部分建设　规模比较大的院校，不同课室会形成区域的分布情况，有分公　共教学区域、专业课室区域、实训课室区域等，就要充分考虑　到学生在两节课程的电间时间能否足够更换不同类型的课室，　保证能够准时上课。　１．４教师课表。在资源不足的情况下，老师的教学任务会　加重，为了使老师能够以更好的精神状态进行教学活动，教师　尽量不要安排连续上课，每天四节课程比较合适。尽量不要安　排一位老师同一天上两门以上的不同的课程，让老师能有更加　充足的备课时间。目前许多高校都有建立了分校区，部分老师　承担了不同校区的上课任务，特别是要乘坐交通工具往返的情　况，这部分老师的课程就要特殊安排课程，保证老师有充足的　精力进行教学。　２、遗传算法　遗传算法自１９６９年由Ｈｏｌｌａｎｄ教授提出后，经过几十年科　学家的不断研究，已成功在计算机科学、机械化设计、通信技　术、人工智能等方面广泛应用。多次召开的遗传算法的国际学　术会议和研讨会，也促进的遗传算法的快速发展。近年来由于　各高校政策性的扩招，在校生人数不断增加，带来了许多教学　上的改革、新教学模式的普及应用，配套的教学资源的不足等　等的原因，遗传算法在应用于排课问题也遇到了许多新的问　题，是目前遗传算法的一个研究课题。　２．１编码。随着信息化的脚步进程，目前许多高校各部门　都实现了信息化的平台，在信息化的过程中为了统一性，都会　制定同一标准的编码方式，使得各个平台直接的信息交流更加　顺畅。通常使用的二进制、格雷码编码方式显得复杂不容易读　懂，而采用十进制编码能够更加直观、简单易懂的对问题进行　表述，特别是对排课中的年份、专业、系别要素等等的要素表　示能更加直观、详细、易懂。　２．２种群。种群是对问题进行编码后，多个染色体随机组　成群体，每个染色体代表着一个问题的解，一般的种群大小取　２０～１００［　。目前高校的专业分类越来越多，课程设置越来越细，　可以采取分类进行种群初始化，【３ｌ使用分类种群可以在处理课　表的时候把主要对场地限制性比较高的课程和课室资源不足　的课室类型进行优先安排，课室充足的类型再安排。　２．３适应度函数。适应度作为一个评判的标准，适应度会　影响到算法的收敛度，在求解不同的问题的时候设置不同适应　度。课程的改革是的评价适应度函数条件更多，排课问题中一　般采取罚函数方法建立适应度函数。　２．４，算子。算子【　］是遗传算法里最重要的操作，算子有选　择、交叉、变异三个方面的操作。选择操作一般使用轮盘赌的　方式实现，使适应度较高的个体容易被保留，使适应度较低的　个体容易被淘汰。交叉算子是在两个染色体上通过交换自身的　基因片段，产生新的个体，通常的交叉方式有单点交叉、多点　交叉、算数交叉等。在排课中资源紧张情况，使用单点交叉，　算子的交叉可以定位设置在时间的交叉。变异操作是在种群中　为了防止陷入局部最优解，在染色体的基因上进行随机的改　变，一般的变异概率都设置比较低。在资源不足的情况下，可　以考虑在已经安排了课室的染色体上对时间进行变异。　在高校的资源紧张的环境下，给排课算法增加了难度，各　高校的资源分布也有各自的实际情况，遗传算法在应用与排课　中需要充分结合分析学校的具体资源数据，通过对数据的统计　分析，具体设置遗传算法的参数，得到符合实际情况可行性更　高的课表。　参考文献　…金民锁．基于遗传算法的实验室排课系统设计与实现Ｕ】＿实验室　研究与探索，２０１０，２９（３），６６￣６９．　１２］许琦．基于遗传算法的高校排课问题的研究【Ｄ１．华南理工大学，　２０１２．　［３］涂井先．基于辅助种群分类的遗传算法Ｕ１广东工业大学学报，　２０１２，２９（１）：３９￣４２．　【４１成伟．基于遗传算法的排课系统的设计与实现［Ｄ】湖南大学，　２Ｏ１１　１３４作者简介：王志江（１９８５一），男，研究实习员，广东轻工职业技术学院艺术设计学院。

基于遗传算法的高校排课系统的应用研究

【摘要】排课问题是一个有约束的、多目标的组合优化问题,并且已经被证明为一个NP完全问题. 遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法,是一种非常有效的解决NP完全的组合问题的方法. 本文将遗传算法应用于排课问题的求解,结合高校实际的排课情况,对遗传算法进行了深入的研究分析. 针对排课问题研究了染色体编码方式以及种群的初始化,提出了基于优先级的贪婪算法,并引入权的概念. 通过实验表明,改进的遗传算法明显优于传统的遗传算法.

【关键词】排课问题;遗传算法;基因编码;贪婪算法

高校的教务管理中,排课表工作非常复杂,通常是手工操作要花费大量的精力,且效率低下,教学资源也很难充分利用因此,这是一个急需解决又非常棘手的问题.由于高校教学单位和课程众多,且相互交叉,教师和教室又严重短缺,很难用手工制定出准确、统一、高效、合理的课表.另一方面教学管理的信息化不可能建立在手工操作的基础上,而理论研究和软件技术的成熟己为我们提供了计算机自动排课的重要手段,编制出一套完备、高效、准确、实用的排课表程序己成为可能.

排课管理的主要任务是把全校各系或各授课部门的课进行汇总,然后根据教学计划和教学资源制订全校的公共课,各院系的公共基础课和各班级的专业课课表,以充分满足专业教学的要求,并优化配置各种教学资源,使教学工作科学、高效、顺利的进行。利用遗传算法求解排课问题,其搜索过程带有自组织的智能性、并行性和鲁棒性,且操作简单,可以更少地依赖于实际情况,实现课表的优化,对于具有复杂约束条件的高校排课提供了一种较好的解决方法.

1 排课问题[1][2]

排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合,以使教学正常进行. 这里约束条件主要为避免冲突.所谓冲突,它所包含的内容很广泛,几乎发生在所有两个或多个排课涉及因素之间.而避免冲突也是排课问题中要解决的核心问题.只有在满足全部约束条件和避免所有冲突的基础上,才能保证整个教学计划合理正常进行.课程的安排要满足一定的约束,约束通常被分为两种类型,一种称为硬约束,是排课中必须满足的.