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

计算机科学２００３Ｖ０１．３０Ｎ９

１２

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

陈卫东李吉桂

（华南师范大学计算机系广州５１０６３１）

ＰｅｒｓｏｎｉｆｉｃａｔｉｏｎＡｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅＵｎｉｖｅｒｓｉｌｙＴｉｍｅｔａｂｌｉｎｇＰｒｏｂｌｅｍ

ＣＨＥＮ

（Ｄｅｐｔ．。ｆＣｏｍｐｕｔｅｒ

Ｗｅｉ—Ｄｏｎｇ

Ｌ１Ｊｉ。“Ｇｕｉ

５１０６３１）

Ｓｃｉｅｎｃｅ，ＳｏｎｔｈＣｈ／ｎａＮｏｍａ／Ｕｎｉｖｅｒｓｉｔｙ．Ｇｕａｎｇｚｈｏｕ

Ａｂｓｔｒａｃｔａｎｄ

ＦｏｒｔｈｅｕｎｉｖｅｒｓｉｔｙｔｉｍｅｔａｂｌｉａｇｐｒｏｂｌｅｍｔｈａｔｉｓＮＰ－ｈａｒｄ，ｓｏｍｅＤｅｗｓｔｒａｔｅｇｉｅｓｏｆｔａｃｋｌｉｎｇｉｔ

ａｌｇｏｒｉｔｈｍｓ

ｂａｓｅｄ

ｏｒＬ

ａｒｅ

ｐｒｏｐｏｓｅｄ．

ｋｎｏｗｎ

ａ，ｔ

ｔｗｏｈｅｕｒｉｓｔｉｃ

ｐｅｒｓｏｎｉｔｉｃａｔｉｏｎ

ｓｔｒａｔｅｇｉｅｓ

ａｒｅ

ｐｒｅｓｅｎｔｅｄ．ｗｈｉｃｈｏｔｌｔｐｅｒｆｏｒｍ

ｏｕｆ

ｔｈｅ

ｓｔｒａｉｇｈｔｆｏｒｗａｒｄｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｓｉｎｔｈｅｑｕａｌｉｔｙｏｆｓｏｌｕｔｉｏｎ．Ｔｈｅｐｒａｃｔｉｃａｌ．

ｅｘｐｅｒ如ｅｎｔａｌ

ｒｅｓｕｌｔｓｓｈｏｗｔｈａｔ

ａｌｇｏｒｉｔｈｍｓ

Ｋ。＂。‘ｄ５

Ｔｉｍ。‘８６１ｉ“８ ＮＰＩｈａ‘妇３＇№。“№‘ｉ。“ｔＨ。“ｒｉｓｔｉ。８１９０ｒｉ‘ｈｍ８下１７ｊ

Ｂ

１引言

高校排课问题是典型的ＮＰ一难问题ｏ］，即在Ｐ≠ＮＰ的假设下，找不到一个算法能保证在多项式时间内得到最优解。因此，为了实际应用的需要，对于这类问题，往往利用问题的一些启发式知识来探求能快速求其近似最优解的算法，即启发式算法。目前求解排课同题的启发式算法大致可分为两大类：一类是构造型算法，另一类是改进型算法。构造型算法一般是按照某种次序逐步安排每门课程进而得到一张合法课表，常使用的是一种称之为直接启发式算法ｏ］。它们一般是模拟人工排课的经验，基本策略都是。优先安排受限制最多的课程”，而差别仅在于赋予“受限制最多”的含义不同。改进型算法则一般是在【合法）课表上进行改进使得课表更加合理．如繁忌搜索、模拟退火算法、造传算法０４。’等现代优化算法．但这些算法有时需要在预先产生的若干个初始合法课表上进行工作。相比之下，直接启发式算法，简单、宣接、快速．其启发式知识往往是针对具体同题的特点提出的，虽然通用性较差，但是如果启发式知识得当．则往往能快速地得到较好的解．而现代优化算法尽管具有通用性和理论上的全局最优性，但是往往收敛慢。在实用的系统中大都是采用直接启发式算法。

我们给出的启发式算法吸收了构造型和改进型这两类算法的特点。包含有两个算法：Ｅｘｐ】ｏｒｉｎｇ算法从教果上相当于是一个局部搜索算法，它在构造课表的过程中同时也对课表进行了局部优化．所得课表的质量明显高于直接启发式算法所得的课表；Ｌｅａｒｎｉｎｇ算法是在前者的基础上引入了拟人策略来跳出。局部黯阱”的搜索算法，进一步提高了漂表的质量。

鉴于ＵＴＴＰ的约束多样性和目标模糊性，本文首先给出了ＵＴＴＰ的一个数学描述，将约束条件进行量化，确定了优化目标。接着描述了传统的直接启发式算法。然后制定了几个新的求解策略，由此得出两个基于拟人策略的排课算法一并将它们与直接启发式算法进行了比较。实验结果表明我们的算法求解速度快、效果好。

特点：一门课程的教学可包含多个自然班级；每个班级上课的课室不固定；－－ｆ３课程可根据周学时多次授课．每次授课的时间连堂１、２或３节；同一教师可以讲授多门不同的课程等等。

为了方便，将每次授课所包含的几个要素组成的４元组（课程，班级列表．教师，周学时）称作课元．将一周内可供安排的每节上课时间称作时间片，由时间片和课室构成的序偶（时间片，课室）称作时空片。将课室相同，时间在同一个上午、下午或晚上且连续的若干个时空片的集合称作时空片簇。因此排课的任务即是为给定的每个课元合理地分配时空片簇。“合理地”体现为排课方案满足一定的约束条件。一般包括以下三

个层次：

１）硬约束条件，主要包括：（ ）按课元周学时分配大小相当的时空片簇．且课室类型（如体育馆）和容量满足课元的要求ｆ（ｉｉ）每个时空片最多只能分配给一个课元，（ｉｉｉ）每个自然班在同一个时间片内最多只能有一门必修课；（Ｉｖ）每个教师在同～个时间片内最多只能有一门课；（ｖ）属于同一门课程的不同课元不能安排在同一天；（ｖｉ）其它必须满足的条件（比如．由于某种原因要求某些特定时间不能排课等）。

２）优化约柬条件。旨在使课程的安排尽可能合理、科学，倒如：（Ｉ）同一门课程的多个课元的时间要间隔均匀．而课室则尽可能相同；（．ｉ）尽可能给重点课程的课元分配好的时间片和好的课室；（ｉｉｉ）尽可能将文理科课程的课元、主副课程的课元交错安排；（ｉｖ）尽可能满足每个课元教学的合理要求．比如对多媒体课室的要求；等等．

３）特殊约束条件。主要是指班级、教师个人提出的一些特殊的合理要求．比如。住在校外的教师、老教师需要在上课的时间和地点方面酌情关照等等．

设Ｃ是所有课元的集合，ＴＲ是所有时空片的集合，由ＴＲ可导出所有时空片簇的集合。将问题的解定义为给每个课元按照其周学时效分配互不相交的对空片簇的方案．满足了全部硬约束条件的解就是可行解（即一张课表）．最优解为最大程度满足优化约束条件和特殊约束条件的可行解（即一张最满意的课表）。

将所有的优化约束条件和特殊约束条件依次编号为１－２，…．Ｓｆ并对它们赋予相应的权重ｗ．≥０（１≤ｉ≤ｓ）．为了在数量

２问题的数学描述

根据我国高校的典型情况。约定高校排课问题具有如下

＊）国家自然科学基金资助项目（１０２０１００９）；广东省自然科学基金资助硬目（０２１０７２）．脒卫东讲师．主要研究方向：计算复杂性理论、算法设计与分析．幸古桂教授ｔ主要研究方向：入工智能．

１７２

万方数据　

上体现这些约束条什的满足情况，我们引入两个概念。

定义２．１设ｔ是可行解，ｉＣ－Ｃ是课元，定义函数

ｉ

ｒ．ｉ，ｔ）一ＷｌＸｌ＋Ｗ２Ｘ：＋…＋Ｗ。Ｘ。

（１）

并称ｆ（１ｔｔ）为课元ｉ在可行解ｔ中的不满意度。其中，Ｘ．∈｛０，１｝（１≤】≤５）表示在ｔ中课元ｉ的安排是否违反了第ｊ个约束条件，若违反，Ｘ．；１，否则ｘ，一０。

定义２．２设ｔ是可行解，定义评价函数‘罚函数）：

Ｅ（ｔ）一厶Ⅲ“ｌ，ｔ）

（２）

并称Ｅ（ｔ）为可行解ｔ的不满意度。

由于排课问题的模型没有定式，考虑到我国高校的实情，我们参照许多文献的做法，取（２）式作为我们的目标函数口５“。于是我们可以对高校排课问题作如下形式描述：

［ｕＴＴＰ］

ｒａｉｎ，￡日＃＿Ｅ（ｔ）

（３）

满足【３）式的可行解ｔ即为相对于权重ｗ，，ｗ∥“，ｗ．的

最优解．简称为最优解。

对于权重ｗ，≥ｏ（１≤－≤ｓ）的确定．一般来说．优化约束条件的权重较大．而特殊约束条件的权重较小。当然，人们在实施排课时，若需要优化标准侧重于某个条件．则可以人为地赋予该条件较大的权重，使得产生的课表可以满足实际要求。使用启发式算法来求解（３）式，就是求取尽可能使Ｅ（ｔ）达到较小值的可行解ｔ。

５传统的直接启发式算法

直接启发式算法，一般是首先根据备课元的约束性赋予以优先权，然后按照课元的优先权次序来依次给每个课元安排其“理想”的时空片簇，直到得到整张课表。这里结合ＵＴＴＰ（３）式来描述直接启发式算法。它们通常要采用如下两个策略：优先权策略和最佳分配策略。

５

１优先权策略

课元一般具有属性：类型、周学时、班级数、教师、所属课程包含的课元个数等。根据这些属性可以给课元赋以优先权．比如可采用属性的线性组合来确定每个课元的优先权。

一般地，课元的优先权值越大，课元的约束就越多，从而可供其选择的满意的时空片簇就少．所以应该优先安排。优先权策略就是，按照课元的优先权由大到小依次来培课元安排

时空片簇。

５．２最佳分配策略

定义５．１在任一时刻，称由所有已被“合法”安排了时空片簇（即满足硬约束条件）的课元子集ｃｍ在ＴＲ中形成的部分课表ＴＲ（ｃ。ｕｂ）（它同时也表示了剩余时空片集）为系统在此时刻的格局。所有课元均已被安排了时空片簇的格局称为目标格局（即可行解）。剩余课元中尚有课元可合法安排的非目标格局为活格局．否则称为死格局。

定义５．２在某活格局ＴＲ（ｃｍ）下，对于课元ｃ∈Ｃ—Ｃｍ，称ＴＲ（Ｃｍ）中每一个能合法安排下Ｃ的空闲时空片簇为课元ｃ的可行时空片簇。

定义５．５在某活格局ＴＲ（Ｃ．“）下．考虑课元ｃ∈ｃ—ｃ舢的安排。设Ｆｓ≠０是该格局下课元ｃ的可行时空片簇集。对于任意的ｔｓ∈ＦＳ，定义课元ｃ对ｔｓ的不满意度为：

ｇ（ｃ，ｔｓ．ＴＲ（ＣＩｕｂ））一Ｗ１Ｘ１＋Ｗ２Ｘ２＋…＋Ｗ。Ｘ．

ｆ，４）

其中ｗ，（１≤ｊ≤ｓ）为评价函数Ｅ（ｔ）中的权值．Ｘｉ∈｛０，１）表示在部分课表ＴＲ（Ｃ。ｎ）中若将ｔ３分配给ｃ后ｃ的安排是否满足第ｊ个约束条件，若不满足，则Ｘ，一１，否则Ｘｊ＝０。

显然，若从格局ＴＲ（ｃ，“）最后能到达一目标格局ＴＲ（Ｃ），则有ｇ（ｃ．ｔｓ，ＴＲ（Ｃ。ｎ））≤ｆ（ｃ，ＴＲ（Ｃ））。

最佳分配策略就是将满足ｍｌｍ．∈陌｛ｇ（ｃ，ｔｓ．ＴＲ（‰））｝

万　

方数据的ｔｓ分配给课元ｃ。

５

５算法描述

根据上面的两个策略，对直接启发式算法描述如下。

ｐｒｏｃｅｄｕｒｅＨｅｕｒｉｓｔｉｃ

ｉｎｐｕｔ：课元集ｃ，时空片集ＴＲｏｕｔｐｕｔ课表ＴＲ（Ｃｍ）

ｂｅｇｉｎ

确定每个课元的优先杈值．并将课元按照其忧先权值由太到小

设初始格局为ＴＲ（ｃ“ｂ）．其中ＣＩｕｂ—ａＦａｉｌＳｅｔ＝ｏ∥算法中不能安排的谭元集

ｆｏ”１ｔｏｌＣｌ

ｄｏ

１．在课表ＴＲ（Ｃｍ）中获职课元ｃ的可行时空片簇集ＦＳ２．若ＦＳ＝ｏ．将ｃ加入ＦａｉｌＳｅｔ中

３．若Ｆｓ≠ｏ．将满足ｍｉｎｉ。ＥＦｓ｛ｇ（ｃ，ｔｓ．ＴＲ（ｃ眦ｂ））｝的ｔｓ分配给课元ｃ．并更新格局ＴＲ（ｃＩ。ｂ）

ｅｎｄｆｏｒ

ｅｎｄ．

当然，算法中可能会遇到某课元无法安排的情况。一些文献口１中采用的办法就是，在遇到这种情况时算法就进行一定限度的回期，即调整一十或者多个课元的安排．给它们换一个较满意的可行时空片簇．直到当前课元能安排下为止。

通过实验我们发现，Ｈｅｕｒｉｓｔｉｃ算法的结果对于课元优先次序很敏感。即，排课结果往往会因课元的优先次序不同而差别较大。下面给出的Ｅｘｐｌｏｒｉｎｇ算法能在较大程度上消除这种敏感性，而Ｌｅａｒｎｉｎｇ算法具有学习的能力，它能够学习到课元的某种优先次序。

４基于拟人策略的启发式算法

为了避免盲目搜索，提高所得解的质量．我们在Ｈｅｕｒｉｓｔｉｃ算法的基础上针对ＵＴＴＰ提出了如下三个新的排课策略。

４．１靠边策略

在某活格局ＴＲ（Ｃ。ｎ）下，考虑课元ｃ∈ｃ—ｃｍ的安排，其周学时为ｐ。在部分课表ＴＲ（ｃｍ）中任意大小为ｐ的空闲时空片簇都有可能是其可行时空片簇。例如．某个最大空闲时空片簇如图１所示．

１

２

３

４

５

图１

其大小为５。假定ｐ一２．对于课元ｃ而盲，实际上它对应４个大小为２的空闲时空片簇：１－２、ｚ一３、３—４、４ ５．我们仅考虑靠边的两个空闲时空片簇１—２和４－５．这就是时空片簇的靠边策略。即，在某格局下，从部分谭表中的所有最大空闲时空片簇的靠边于时空片簇中获取当前课元的可行时空片簇。

直观上看，采用靠边策略一方面可以缩小搜索范围，另一方面可以使得时空片的剩余空间更好利用，为后面课元的安排留下更多的机会。

４．２前景探测策略

在某活格局ａ—ＴＲ（ｃ。。）下．考虑课元ｃ∈Ｃ—Ｃｍ的安排。设Ｆｓ≠ａ是该格局下课元ｃ的可行时空片簇集．对于任意的ｔＳ∈ＦＳ，新括局ＴＲ（Ｃ岫）ＵＩｃ卜ｔｓ｝（在ＴＲ（ｃ讪）中将课元ｃ安排在ｔｓ处后所得的新课表）均可能是格局ａ的后继格局。用ｈ（ｃ，ｔｓ，ａ）来度量每个新格局的前景：

从新格局ＴＲ（ｃ。ｂ）Ｕ｛ｃ—ｔｓ）出发，使用最佳分配策略依次对ｃ一（ｃｌ“Ｕ｛ｃ））中的课元进行排课，若最后能达到一且标格局（可行解），该可行解的不满意度印为ｈ（ｅ，ｔｓ，口）；若最终到达的是一死格局，则ｈ（ｃ，ｔｓ，ａ）一Ｗｏ＊ＪＦａｉｌＳｅｔＩ，其中

１７３

ＦａｉｌＳｅｔ是该死格局中未能安排的课元集，ｗ。是比任何可行解的不满意度都大的一个数。其搜索过程如图２所示。

前景探测策略就是在当前格局ａ下，选择前罱最佳的那十新格局作为下一个格局，即将满足ｍｉｎ“Ｆｓ（ｈ（ｃ．ｓｔ，ａ）｝的ｔｓ分配给课元ｃ。

目标榕

图Ｚ

该策略是从搏弈中受到启发得来的一种拟人策略，它模拟对弈者的经验，每次从当前的格局走向下一个格局之前．总是要向前看若干步。从效果上看，该策略叉可视作是一种局部搜索策略，因为在其搜索过程中实际上可能探测到许多可行解，它选择往更好的可行解方向继续搜索。其效果显然比最佳分配策略要好．下面的定理２表明了这一点。

４．５学习簟略

学习策略就是，根据前景探测策略，若得到一个可行解ＴＲ（Ｃ），则按照（１）式来计算每个课元在这张课表中的不满意度ｆ（ｃ，ＴＲ（Ｃ）），然后挑选出最不满意的课元；若不能得到一个可行解．而是刊达一个死格局，则认为其中未能安排的课元是最不满意的课元。对最不满意的课元增加其优先权值，然后再应用前景探测策略进行下一轮排课，如图３所示。

匿３学习策略模型

前景探测策略可看作是一个局部搜索策略，使用它到达一目标格局或死格局时相当于到达了局部极小值点。学习策略就是如何从局部极小跳到前途可能更好的地方。因此。该策略能比前景探测策略具有更大的搜索范围。这种策略实质上也是一种拟人的策略．通过实验，我们发现直接启发式算法及前景探测策略的排课结果都对课元的优先权次序敏感。使用学习策略，通过若干回合的学习就可以很自然地得到能使算法有较好结果的课元的某种优先次序。

基于上面的策略，我们得到两个基于拟人策略的排课算法．其描述如下。

４４

Ｅｘｐｌｏｒｉｎｇ算法

瓣，ｅｄ：ｕ课ｒｅ元Ｅ集ｘｐｌ。ｏｒ，辞≤斧蟹警ｌｊ彭翟凳譬嚣冀；｝雾警备由大到小排序

Ｏｕｔｐｕｔ：课表ＴＲ（Ｃ“Ｏ

ｂｅｇｉｎ

１７４

万　

方数据设初始格局为一ＴＲ（Ｃ，ｎ）．其中ｃ，ｎ—ｏ

ＦａｉｌＳｅｔ一０／／算法中不能安排的课元集

ｆｏｒｃ一１ｔＯｌＣｌ

ｄｏ

１．在课表ＴＲ（Ｃ“ｂ）中用靠边策略来获得课元ｃ的可行时空片簇集ＦＳ

２若ＦＳ＝ｏ，将ｃ加入ＦａｉｌＳｅｔ中

３若ＦＳ≠ｏ，将满足ｒａｉｎ幔Ｆｓ｛ｈ（ｃ，ｔｓ．ａ））的ｔｓ分配给谭元ｃ，井更新格局ａ—ＴＲ（ｃ，“）

ｅｎｄｆｏｒｅｎｄ

４５

Ｌｅａｒｎｉｎｇ算法

ｅｎｄ

４

８算法分析

关于算法的时间和空间复杂度．有如下结果：定理４—１

Ｈｅｕｒｉｓｔｉｃ算法、Ｅｘｐｌｏｒｉｎｇ算法、Ｌｅａｒｎｉｎｇ算法

的时间复杂度分别为Ｏ（咖２）、Ｏ（一ｍ３）、Ｏ（ｎ。ｍ’＊

ＭＡＸＴＲＩＥＳ）。空间复杂度均为Ｏ（ｎ十ｍ）．其中，ｍ是课室个数，ｎ是课元个散，ＭＡＸＴＲＩＥＳ是Ｌｅａｒｎｉｎｇ算法中的迭代次

数。

证明：在某格局下确定某课元ｃ的可行时空片簇时．时空片簇个数为Ｏ（ｍ），而判断一个时空片簇是否可行需要时间Ｏ（ｍ），因此获得ｃ的所有可行时空片簇需要时间０【ｍ２）。计算ｇ的时间为ｏ（ｍ），从而对ｃ应用最佳分配策略需要时间ｏ【ｍ２）。因此Ｈｅｕｒｉｓｔｉｃ算法的计算时间为Ｏ（ｎｍ２）。对于ｃ的每个可行时空片簇ｔｓ．计算ｈ（ｃ，ｔｓ，ｎ）时．要在余下的所有课元上应用最佳分配策略并最后计算所得结果Ｅ（ＴＲ（ｃｍ）），需要时间Ｏ（ｎｍ２）。因此Ｅｘｐｌｏｒｉｎｇ算法中一个格局的变迁需要的时间为Ｏ（ｎｍ３），而算法运行过程中格局的变迁次数不超过Ｏ（ｎ）．因此Ｅｘｐｏｒｉｎｇ算法的时间复杂度为Ｏ（ｎ。ｍ’）。由此容易得到Ｌｅａｒｎｉｎｇ算法的时间复杂度为Ｏ（ｎ２ｍ’＊ＭＡＸＴＲＩＥＳ）。在存储空间方面，三个算法的都需要空间ｏ（ｎ）来存储课元，ｏ（ｍ）来存储时空片集．而其它数据的存储空问不会超过０（ｎ＋ｍ），故共需存储空间Ｏ（ｎ－［－ｍ）。

口

我们的算法仅在同题的解空间的一个极小部分进行有针对性的搜索，故对于算法的解质量，不易从理论上作出定量分析。但由于Ｌｅａｒｎｉｎｇ算法的搜索范围包含了Ｅｘｐｌｏｒｉｎｇ算法的搜索范围．而Ｅｘｐｌｏｒｉｎｇ算法的搜索范围叉包含了Ｈｅｕｒｉｓｔｉｃ算法的搜索范围．故有如下结果：

定理２

Ｅｘｐｌｏｒｉｎｇ算法所得解的质量不低干Ｈｅｕｒｉｓｔｉｃ

算法所得解的质量ＩＬｅａｒｎｉｎｇ算法所得解的质量不低于Ｅｘｐｌｏｒｉｎｇ算法所得解的质量．

５，算例硬评论

目前已经对一个系的最近两个学期的排课任务的实例使用ｃ语言编程在ＩＢＭＰＣ一５８６机上进行了自动排课。其中一十实例的描述见图４（ａ）。

我们对于三个算法的性能通过实验进行了比较，结果见图４（ｂ）．算法中ｗ。（１≤ｉ≤５）是按照一定比例确定的，且满足

对于任何可行解ｔ有Ｅ（ｔ）＜ｗ。，具体值见表５。可以看出，对于解的质量，Ｌｅａｒｎｉｎｇ算法要优于Ｅｘｐｌｏｒｉｎｇ算法．而Ｅｘｐｌｏｒｉｎｇ算法则明显要优于Ｈｅｕｒｉｓｔｉｃ算法。从实验中我们还发现，即使课元优先次序不是按预先给定的课元优先权值

得到，而是随机的或者是某种自然次序（比如年级次序）．通过若干次学习．仍然能够得到一种使得算法有较好结果的课元优先次序，这说明我们的Ｌｅａｒｎｉｎｇ算法具有这种学习能力。

Ｅ（．）

班级数目

２２５０４８７４２３９２３４８３６０ｌ－５８

教师数目

课程数日

课元敷目课程周总学时数

每个班级的周平均学时教每位教师周平均学时数

课室数量

可用时空片总数

可用时空片数，课程周总学时教

（ａ）

图４（ａ）一个实例的描述。（ｂ）对三种算法解的比较。其中０一可用时空片散／课程周总学时数．其值是为了比较算法的性能

按照一种自然的时间先后顺序减少可用时空片效而得。图中每个点代表两个算倒的结果敢平均。其中Ｌｅａｒｎｉｎｇ算法的参数ＭＡＸＴＲＩＥＳ＝５０。

将我们的算法的解与人工排课的结果相比较，结果见表５。可见ｔＥｘｐｌｏｒｉｎｇ算法、Ｌｅａｒｎｉｎｇ算法的效果不逊色于人工，

而且速度快（执行Ｅｘｐｌｏｒｉｎｇ算法约２秒钟），而人工排课则需要一周多的时间。

表５对于图４（ａ）描述的实例 手工排课蛄秉与Ｅｘｐｌｏｒｉｎｇ算法、Ｌｅａｒｎｉｎｇ算法鲒果的比较

约束条件

（优化约束条件和特殊约束条件）同课程的多个课元时间间隔应均匀同课程的多个课元的课室应该相同

多媒体要求应该满足课程类型搭配要均匀重点课程要有好时间片（指上午）

某些时段最好不要排课

班级日负荷均衡教师日负荷均衡好时间片要充分利用好课室要充分利用剩余时空片集中“碎片”要少教师的特殊要求应该满足

其它若干约束条件

１５４

６３１５１４

２８３．５３．５

６６４０３４４

５４５２９６

Ｓ１５２７３

８

６

６３７

权值百分比

（％）

２

８

手工排课结果中违反某约束的次数（Ｅ一２６３４）

３４

Ｅｘｐｌｏｒｉｎｇ算法结果中违反某约束的欢数（Ｅ＝１９５７）

３２

Ｌｅａｒｎｉｎｇ算法结果中违反某约束的次数（Ｅ＝１８４１）

２５２０６２４４０

１．４１

４１５１７

／／，

三个结果均是可行解．Ｅ是其评价函数值。其中Ｌｅａｒｎｉｎｇ算法的参数ＭＡｘＴＲＩＥＳ＝５０。

我们实现的系统具有交互性能，可全自动排课．也可在排课过程中手工排课和自动排课交互进行。通过调整模型中的参数．可得到符合不同要求的课表。由于系统可提供人工干预的机会．能灵括地处理一些特殊的排课要求，因此具有良好的适应性和实用性。当然，算法结束时可能会出现有课元未能安排的情况，此时可通过加大迭代次数或增加时空片来解决。

ＮＰ－ｃｏｍｐｌｅｔｅｎｅｓｓ．Ｓａｎ

１９７９

Ｆｒａｎｃｉｓｃｏ：Ｗ．Ｈ

Ｆｒｅｅｍａｎａｎｄ

Ｃｏｍｐａｎｙ．

黄文奇．金人超．求解ＳＡＴ问题的拟物拟＾算法一ｓ。Ｉａｒ－中国科学（Ｅ辑）．１９９７ Ｚ７（２）；１７９～１８６

黄文奇，等解Ｐａｃｋｉｎｇ及ＣＮＦ－ＳＡＴ问题的拟物拟人方法．华中理工大学学报。１９９８，２６（４）：５～７

黄文奇．许如初．支持求解圆形Ｐａｃｋｉｎｇ问题的两十拟人策略中国科学（Ｅ辑）．１９９８ｔ２９（４）：３４７～３５２ＦｅｒｍｎｄｅｓＣ，ｅｔａｌＨｉ窖ｈｓｃｈｏｏｌ

ｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ

Ａｐｐｌｉｅｄ

ｔｈｅ

ｗｅｅｋｌｙ

１９９９

ｔｉｍｅｔａｂｌｉｎｇｂｙ

参考文献

１

ＡＣＭｓｙｍｐｏｓｉｕｍ∞

ｃｏｍｐｕｔｉｎｇ Ｆｅｂ．１９９９３４４～３５０

Ｓｃｈａｅｒｔ

Ａ

Ａ

Ｓｕｒｖｅｙ

ｏｔＡｕｔｏｍａｔｅｄ

Ｔｉｍｅｔａｂｌｉｎｇ．Ａｒｔｌｉｉｃｌａｌ

７

黄千平．姚自珍．张轶静．使用棋拟遇火算法懈解表问豫．武汉大学学报．８０００（Ｉｏ）：５５９～５６３

ＩｎｔｅｌｌｉｇｅｎｃｅＲｅｖｉｅｗ，１９９９．１３：８７～１２７

２

ＧａｒｅｙＭＲ．Ｊｏｈｎｓｏｎ

ＤＳ

Ｃｏｍｐｕｔｅｒｓ

ａｎｄ

Ｉｎｔｒａｃｔａｂｉｌｉｔｙ—Ａｇｕｍ

ｔｏ

１７５

万方数据　

内容需要下载文档才能查看 内容需要下载文档才能查看

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

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

陈卫东， 李吉桂

华南师范大学计算机系,广州,510631计算机科学

COMPUTER SCIENCE2003,30(12)4次

参考文献(7条)

1.Schaerf A A Survey of Automated Timetabling[外文期刊] 1999

2.GareyMR;Johnson D S Computers and Intractability-A guid to NP-completeness 19793.黄文奇;金人超 求解SAT问题的拟物拟人算法-Solar 1997(02)4.黄文奇 解Packing及CNF-SAT问题的拟物拟人方法 1998(04)

5.黄文奇;许如初 支持求解圆形packing问题的两个拟人策略[期刊论文]-中国科学E辑 1999(04)6.Fernandes C High school weekly timetabling by evolutionary algorithms 1999

7.黄干平;姚自珍;张轶静 使用模拟退火算法解解表问题[期刊论文]-武汉大学学报(自然科学版) 2000(10)

本文读者也读过(10条)

1. 高青 高校排课过程中"人"的问题及解决途径[期刊论文]-中国电力教育2008(18)2. 孙俊逸.成磊 基于两阶段A*算法排课系统设计[期刊论文]-计算机应用2006,26(z2)3. 徐斌 基于UML的高校排课系统分析与设计[期刊论文]-咸宁学院学报2007,27(6)4. 王毅 并行遗传算法在高校排课系统中的应用[期刊论文]-科技创新导报2009(36)

5. 朱冠宇.王乘.席大春 利用遗传算法求解中学课表安排问题[期刊论文]-计算机工程与应用2004,40(27)6. 林洁樱 基于遗传算法的高校排课系统的设计[期刊论文]-科学与财富2010(7)7. 石菁.李洪波 排课算法比较[期刊论文]-福建电脑2007(8)

8. 肖明.曾莉 基于拉丁矩的高校排课算法[期刊论文]-数字技术与应用2010(8)

9. 黄琦.HUANG Qi 基于智能规划的高校排课系统的研究与设计[期刊论文]-泰山学院学报2009,31(3)10. 高成 关于高校排课工作的初步探讨[期刊论文]-世界华商经济年鉴·高校教育研究2008(8)

引证文献(4条)

1.陈永辉.张杰 基于空间分解的TTP算法模型研究[期刊论文]-湖北工业大学学报 2006(4)2.陈卫东 求图符号控制数的启发式算法[期刊论文]-计算机工程 2005(1)

3.陈卫东 求图符号控制数的拟人退火算法[期刊论文]-华南师范大学学报(自然科学版) 2004(3)4.梁平 基于数学模型的计算机排课系统算法研究与分析[学位论文]硕士 2005

本文链接：http://wendang.chazidian.com/Periodical_jsjkx200312051.aspx