基于拟人策略的高校排课算法

《基于拟人策略的高校排课算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据计算机科学2003V01．30N912基于拟人策略的高校排课算法¨陈卫东李吉桂(华南师范大学计算机系广州510631)PersonificationAlgorithmsfortheUniversilyTimetablingProblemCHENWei—DongL1Ji。“Gui(Dept．。fComputerScience，SonthCh／naNoma／University．Guangzhou510631)AbstractFortheuniversitytimetabliagproblemthatisNP-hard，someDewstrategiesofta

2、cklingitareproposed．andtwoheuristicalgorithmsbasedorLpersoniticationstrategiesarepresented．whichotltperformtheknownstraightforwardheuristicalgorithmsinthequalityofsolution．Theexper如entalresultsshowthatoufalgorithmsa，tpractical．K。"。‘d5Tim。‘861i“8·NPIha‘妇3'№。“№‘i。“tH。“risti。8190ri‘hm8下17

3、jB1引言高校排课问题是典型的NP一难问题o]，即在P≠NP的假设下，找不到一个算法能保证在多项式时间内得到最优解。因此，为了实际应用的需要，对于这类问题，往往利用问题的一些启发式知识来探求能快速求其近似最优解的算法，即启发式算法。目前求解排课同题的启发式算法大致可分为两大类：一类是构造型算法，另一类是改进型算法。构造型算法一般是按照某种次序逐步安排每门课程进而得到一张合法课表，常使用的是一种称之为直接启发式算法o]。它们一般是模拟人工排课的经验，基本策略都是。优先安排受限制最多的课程”，而差别仅在于赋予“受限制最多”的含义不同。改进型算法则一般是在【合法)课表上进

4、行改进使得课表更加合理．如繁忌搜索、模拟退火算法、造传算法04。’等现代优化算法．但这些算法有时需要在预先产生的若干个初始合法课表上进行工作。相比之下，直接启发式算法，简单、宣接、快速．其启发式知识往往是针对具体同题的特点提出的，虽然通用性较差，但是如果启发式知识得当．则往往能快速地得到较好的解．而现代优化算法尽管具有通用性和理论上的全局最优性，但是往往收敛慢。在实用的系统中大都是采用直接启发式算法。我们给出的启发式算法吸收了构造型和改进型这两类算法的特点。包含有两个算法：Exp】oring算法从教果上相当于是一个局部搜索算法，它在构造课表的过程中同时也对课表进行了

5、局部优化．所得课表的质量明显高于直接启发式算法所得的课表；Learning算法是在前者的基础上引入了拟人策略来跳出。局部黯阱”的搜索算法，进一步提高了漂表的质量。鉴于UTTP的约束多样性和目标模糊性，本文首先给出了UTTP的一个数学描述，将约束条件进行量化，确定了优化目标。接着描述了传统的直接启发式算法。然后制定了几个新的求解策略，由此得出两个基于拟人策略的排课算法一并将它们与直接启发式算法进行了比较。实验结果表明我们的算法求解速度快、效果好。2问题的数学描述根据我国高校的典型情况。约定高校排课问题具有如下特点：一门课程的教学可包含多个自然班级；每个班级上课的课室不

6、固定；--f3课程可根据周学时多次授课．每次授课的时间连堂1、2或3节；同一教师可以讲授多门不同的课程等等。为了方便，将每次授课所包含的几个要素组成的4元组(课程，班级列表．教师，周学时)称作课元．将一周内可供安排的每节上课时间称作时间片，由时间片和课室构成的序偶(时间片，课室)称作时空片。将课室相同，时间在同一个上午、下午或晚上且连续的若干个时空片的集合称作时空片簇。因此排课的任务即是为给定的每个课元合理地分配时空片簇。“合理地”体现为排课方案满足一定的约束条件。一般包括以下三个层次：1)硬约束条件，主要包括：(·)按课元周学时分配大小相当的时空片簇．且课室类型(

7、如体育馆)和容量满足课元的要求f(ii)每个时空片最多只能分配给一个课元，(iii)每个自然班在同一个时间片内最多只能有一门必修课；(Iv)每个教师在同～个时间片内最多只能有一门课；(v)属于同一门课程的不同课元不能安排在同一天；(vi)其它必须满足的条件(比如．由于某种原因要求某些特定时间不能排课等)。2)优化约柬条件。旨在使课程的安排尽可能合理、科学，倒如：(I)同一门课程的多个课元的时间要间隔均匀．而课室则尽可能相同；(．i)尽可能给重点课程的课元分配好的时间片和好的课室；(iii)尽可能将文理科课程的课元、主副课程的课元交错安排；(iv)尽可能满足每个课