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.     

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

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

基于GENET的时间表问题自动求解算法

构造大学考试时间表自动生成系统是一个知名的问题．本文用约束满足问题模型来描述大学考试时间表问题,并提出了一个基于GENET的局部搜索算法来解该问题．该算法采用一些问题相关的策略来提高局部搜索效率．实验结果表明,将“强约束违反”转化为“弱约束违反”的方法能大大地提高算法性能,使该算法优于GENET和演化算法。     

非二元约束满足问题求解

在约束满足问题(CSP)的研究中，大部分工作集中在二元约束，但处理实际问题时，常常会遇到非二元约束的情况．该文在概要地讨论了两类求解非二元约束问题方法的基础上，研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法，并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法，以典型例子给出了实现系统的运行结果．     

一阶逻辑中约束求解的局部搜索法*

以一阶谓词逻辑为基础,讨论约束满足问题.着重研究一阶逻辑公式可满足性的局部搜索法,并与命题逻辑中的可满足性过程加以比较.以皇后问题和哈密顿回路问题为例,说明基于一阶逻辑的方法能处理较大的问题实例.     

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

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

Constraint Solving for Proof Planning

Proof planning is an application of AI planning to theorem proving that employs plan operators that encapsulate mathematical proof techniques. Many proofs require the instantiation of variables; that is, mathematical objects with certain properties have to be constructed. This is particularly difficult for automated theorem provers if the instantiations have to satisfy requirements specific for a mathematical theory, for example, for finite sets or for real numbers, because in this case unification is insufficient for finding a proper instantiation. Often, constraint solving can be employed for this task. We describe a framework for the integration of constraint solving into proof planning that combines proof planners and stand-alone constraint solvers. Proof planning has some peculiar requirements that are not met by any off-the-shelf constraint-solving system. Therefore, we extended an existing propagation-based constraint solver in a generic way. This approach generalizes previous work on tackling the problem. It provides a more principled way and employs existing AI technology.     

Constraint Solving and Programming: What Next?

In this paper we advocate for more flexible and user-friendly constraint solving environments, as well as for constraint programming languages which have great expressive power while maintaining a formal semantics based on few crucial concepts. We cite some of our work in these directions and we hint at subjects of our future research.     

基于实例化次数的约束求解方法研究

启发式是约束满足问题领域的重要研究课题,有效的启发式方法可以极大地提高问题的求解效率.在求解约束满足问题时,发现变量实例化失败次数与值实例化成功次数反映了变量和值与已实例化集合之间的关系,将实例化次数加以利用可以对问题求解效率有很大的影响.据此,提出了实例化次数的权值统计方法,并将其与现有启发式方法相结合,提出了实例化次数启发式及其相应的约束求解算法MAC_Try,并证明了其在一个分支上的最坏时间复杂度是O(ned3).大量实验结果表明,新的MAC_Try方法在求解效率上明显优于国际上流行的MAC3rm方法.     

A Glimpse of Constraint Satisfaction

Constraint satisfaction has become an important field in computer science. This technology is embedded in millions of pounds of software used by major companies. Many researchers or software engineers in the industry could have benefited from using constraint technology without realizing it. The aim of this paper is to promote constraint technology by providing readers with a fairly quick introduction to this field. The approach here is to use the well known 8-queens problem to illustrate the basic techniques in constraint satisfaction (without going into great details), and leave interested readers with pointers to further study this field.     

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

对排课问题做出了形式化描述,提出了一种用于排课的混合启发式算法,该算法合并使用了模拟退火和迭代局部搜索两种算法。先依据图着色算法产生初始可行解,然后应用模拟退火算法寻找最优解,为使算法更好地跳出局部最优,实现全局搜索,在模拟退火算法应用过程中,迭代使用两个邻域,标准邻域和双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.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches

Conventional techniques for the constraint satisfaction problem (CSP)have had considerable success in their applications. However,there are many areas in which the performance of the basic approachesmay be improved. These include heuristic ordering of certain tasksperformed by the CSP solver, hybrids which combine compatible solutiontechniques and graph based methods which exploit the structure of theconstraint graph representation of a CSP. Also, conventionalconstraint satisfaction techniques only address problems with hardconstraints (i.e. each of which are completely satisfied or completelyviolated, and all of which must be satisfied by a validsolution). Many real applications require a more flexible approachwhich relaxes somewhat these rigid requirements. To address theseissues various approaches have been developed. This paper attempts asystematic review of them.     

When Ants Attack: Ant Algorithms for Constraint Satisfaction Problems

We describe an ant algorithm for solving constraint problems (Solnon 2002, IEEE Transactions on Evolutionary Computation 6(4): 347–357). We devise a number of variants and carry out experiments. Our preliminary results suggest that the best way to deposit pheromone and the best heuristics for state transitions may differ from current practice     

Temporal Constraint Satisfaction Techniques in Job Shop Scheduling Problem Solving

We describe a restriction of Dechter, Meiri and Pearl's TCSPs (Temporal Constraint Satisfaction Problems) sufficiently expressive to represent any job shop scheduling problem. A solver based on the restriction is then described, which is similar to Ladkin and Reinefeld's qualitative interval network solver; except, however, that the filtering method used during the search is not path consistency but either ULT (Upper-Lower Tightening) or LPC (Loose Path- Consistency), which are both less effective but have the advantage of getting rid of the so-called fragmentation problem.     

Random Constraint Satisfaction: Flaws and Structure

A recent theoretical result by Achlioptas et al. shows that many models of random binary constraint satisfaction problems become trivially insoluble as problem size increases. This insolubility is partly due to the presence of flawed variables, variables whose values are all flawed (or unsupported). In this paper, we analyse how seriously existing work has been affected. We survey the literature to identify experimental studies that use models and parameters that may have been affected by flaws. We then estimate theoretically and measure experimentally the size at which flawed variables can be expected to occur. To eliminate flawed values and variables in the models currently used, we introduce a flawless generator which puts a limited amount of structure into the conflict matrix. We prove that such flawless problems are not trivially insoluble for constraint tightnesses up to 1/2. We also prove that the standard models B and C do not suffer from flaws when the constraint tightness is less than the reciprocal of domain size. We consider introducing types of structure into the constraint graph which are rare in random graphs and present experimental results with such structured graphs.     

一种并行工程约束分解方法

在并行工程产品开发过程中,往往按照问题的结构特点将较大规模的问题分解成一些子问题,并希望通过求解子问题来获得原问题的解。实际中,分解得到的子问题之间往往不是完全独立的,一般的简单分解方法只能有限地降低求解难度和简化问题规模。如何进一步分解各个子问题间的关系,使各个子问题的设计结果不但满足原问题的总体要求而且还能由此获得优化的总体设计结果是一个重要问题。该文给出了分解的意义,提出了基于约束的优化分解方法。     

最先失败原则的约束传播算法

约束满足问题是人工智能研究领域的重要问题.而弧相容算法是求解约束满足问题的重要工具.在弧相容算法中应用启发式规则已经证明是一种很有效的方式.本文提出一个基于最先失败原则的约束传播算法,该算法在搜索过程中更早地发现含有空域的变量并提前进行回溯,从而提高问题求解效率.同时,在"明月1.0"架构下实现了该算法,实验结果表明使用最先失败原则的弧相容算法要比原来的算法效率上提高了约40%.