基于演化算法的一类时间表问题的自动求解

本文给出了一种有效的基于演化算法的求解大学的时间表总理２（编排课程和考试）即在很强的资源约束条件下将一些事件（课程或考试）安排到时间段和空间位置的总理２的方法,此方法有杉直接的时间表编码表示和启发式深化算子,并通过惩罚函数保证对约束条件的满足,计算实验表明方法在求解大学考试时间表问题中是有效的。     

时间表问题算法综述

时间表问题属于一类特殊的调度问题,是NP-难问题,具有广泛的应用领域和很大的应用价值。本文分析了时间表问题的数学模型,并对解决时间表问题的多种算法及其优缺点进行了探讨。     

基于遗传算法求解时间表问题

基于遗传算法求解时间表问题,通过具体时间表问题的描述和分析,定义了一个新颖的染色体编码方式,然后基于该编码,进一步分析并设计了遗传操作—交叉和变异。算法运行结果显示该方法是可行的。     

时间表问题的人工免疫算法研究

本文针对时间表问题提出了一种模拟人类免疫系统的人工免疫算法(AIA)。首先讨论了便于TTP问题描述的数据模型和适应度函数。通过注射疫苗生成满足一定约束的抗体,用扩增操作和变异操作对抗体进行改变,再利用基于浓度的群体更新选择适当的抗体,进入下一轮考察。最后对符合约束条件的抗体进行切片操作,分别生成教师课表、学生课表和教室课表。     

解“时间表问题”（TTP）的启发式算法

本文给出了一种解“时间表问题”的启发式算法，从整个时间表的生成过程来说，它是一种并行和无回溯的方法，从一天的时间表生成来说，它是一种改进的Ｔａｂｕ查代方法。该算法不能保证在任何情况下都能获得可行的时间表，但能保证所获得的时间表是最优的或较优的。     

基于动态度的回溯算法求解大值域约束满足问题

针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域与动态度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容（MAC）技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明：在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。     

一个约束可满足性问题的演化算法求解

约束可满足性问题是一大类常出现于现实应用中的复杂问题,因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题．基于演化算法的框架进行求解。我们采用矩阵的表示方式．并设计了相应的杂交和变异算予。实验表明．演化算法能高效地解决该问题。     

启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

两种改进的模拟退火算法求解大值域约束满足问题

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB模型（Revised B）是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这一类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA（Revised Simulated Annealing Algorithm）和GSA（Genetic-simulated Annealing Algorithm）。将这两种算法用于求解RB模型的随机实例,数值实验结果表明：在进入相变区域时,RSA和GSA算法依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。     

改进求解约束满足问题粗粒度弧相容算法

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.     

Decomposing and Solving Timetabling Constraint Networks

The binary version of the school timetabling (STT) problem is a real‐world example of a constraint network that includes only constraints of inequality. A new and useful representation for this real‐world problem, the STT_Grid, leads to a generic decomposition technique. The paper presents proofs of necessary and sufficient conditions for the existence of a solution to decomposed STT_Grids. The decomposition procedure is of low enough complexity to be practical for large problems, such as a real‐world high school.
To test the decomposition approach, a typical high school was analyzed and used as a model for generating STT_Grids of various sizes. Experiments were conducted to test the difficulty of large STT networks and their solution by decomposition. The experimental results show that the decomposition procedure enables the solution of large STT_Grids (620 variables for a real school) in reasonable time. The constraint network of a typical STT_Grid is sparse and belongs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJumping and ForwardChecking) do not terminate in reasonable times for STT_Grids that are larger than 300 variables.     

混合启发式算法在排课问题上的应用

对排课问题做出了形式化描述,提出了一种用于排课的混合启发式算法,该算法合并使用了模拟退火和迭代局部搜索两种算法。先依据图着色算法产生初始可行解,然后应用模拟退火算法寻找最优解,为使算法更好地跳出局部最优,实现全局搜索,在模拟退火算法应用过程中,迭代使用两个邻域,标准邻域和双Kempe链邻域。实验结果表明,此算法能够很好地提高解的质量。     

A Survey of Automated Timetabling

The timetabling problem consists in scheduling a sequence of lectures between teachers and students in a prefixed period of time (typically a week), satisfying a set of constraints of various types. A large number of variants of the timetabling problem have been proposed in the literature, which differ from each other based on the type of institution involved (university or school) and the type of constraints. This problem, that has been traditionally considered in the operational research field, has recently been tackled with techniques belonging also to Artificial Intelligence (e.g., genetic algorithms, tabu search, and constraint satisfaction). In this paper, we survey the various formulations of the problem, and the techniques and algorithms used for its solution.     

基于约束逻辑程序设计的排课算法研究

课程安排问题是典型的组合优化和不确定调度问题。采用约束逻辑程序设计的研究方法,结合课程安排自身的特点,通过约束推理找到最优的课程安排结果。约束逻辑程序设计综合了人工智能中一致性算法和启发式搜索算法,采用约束推理方法,能非常好地处理各种冲突,并且能快速地排出合理的课程。     

基于基因算法解析排课问题

高等院校由于课程的多样性及教学资源的紧缺,加剧了课务编排的难度,排课问题是一个NP完全问题,算法的计算机时间是呈指数增长的。基因算法借鉴生物界自然选择和自然遗传机制,使用群体搜索技术,尤其是用于处理传统搜索方法难以解决的复杂和非线性问题,为此,使用基因算法从整体解的质量上来分析,力图从全局来分析问题、解决问题。     

基于智能规划的时间表问题研究

时间表问题TTP（Timetabling Problem)是一类应用非常广泛的研究课题，目前也出现了各种各样的解决时间表问题的方法，本文简要分析了近几十年时间表问题研究的历史和技术现状，提出基于智能规划方法的时间表问题解决方案，并且我们用SQL语言实现了这一解决方案，通过对学校课程表的模拟实验证明该方法具有较大的实用价值。     

Timetabling through Constrained Heuristic Search and Genetic Algorithms

Hybrid genetic algorithms are presented that use constrained heuristic search and genetic techniques for the timetabling problem (TP). The TP is an NP-hard problem for which a general polynomial time deterministic algorithm is not known. The paper describes the classification of constraints and the constraint ordering to obtain the minimization of backtracking and the maximization of parallelism. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited to this kind of problem, since there exists an easy way to assess a good timetable, but not a well structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solution. The evaluation function and the genetic operators are well separated from the domain-specific parts, such as the knowledge of the problem and the heuristics, i.e. from the timetable builder. The present paper illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favourably with known programs to solve decision problems under logic constraints. The cost of the new algorithm and the quality of the solutions obtained in significant experiments are reported.     

混合算法在大学课程表问题中的应用研究

大学课程袁问题是时间表问题之一,也是一个多因素的优化决策问题.文章提出的混合算法,基于动态规划的思想,对大学课程表问题进行分阶段求解,分别采用遗传算法分配时间,采用最佳适应算法分配场地.实验结果表明,这种方法既保证了课表的质量,又有利于工程上实现和扩展.     

基于图论的高校排考算法

提出了一种基于图论的考场安排算法及一系列优化策略.考场安排足考务管理活动的重要环节,考场安排结果的优劣直接决定了考务活动能否正常顺利的进行.对高校的考场安排问题进行了分析、抽象,通过建立静态冲突图将时间安排转化为图论的图着色问题来解决排考时间的冲突问题并在此基础上提出了多种对结果的优化策略以保证排考结果的合理性.通过在...