图着色算法解决考试时间安排问题的优化

时间表问题是将有限的时间资源分配给多个对象的资源分配问题,它是一类具有多约束条件的组合优化问题。时间表问题已经被证明是一个NP完全问题。大学考试时间安排问题是时间表问题的一个应用,利用改进的图着色算法来处理大学考试的时间安排问题能够最大程度上使考试时间安排得更加人性化、合理化。实验测试表明,基于所给出的算法实现的考试时间安排系统具有良好的可行性、实用性和优越性。     

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

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

改进罚函数法与蝙蝠算法在约束优化中的应用

设计了一种基于自适应罚函数法和改进蝙蝠算法的约束优化问题求解方法。提出了一种自适应罚函数法,该处理方法综合考虑了约束违反的情况和进化过程的特点,如果某个约束违反的次数越多,则证明该约束越强,赋予惩罚系数越大;种群中的不可行解的数量越多,为保持种群的多样性,则约束应该取较小的值,即惩罚系数取较小的值。提出了一种改进的蝙蝠算法,利用混沌的遍历性特点产生初始种群,增强了初始种群的多样性和种群的质量;在考虑了脉冲响度的蝙蝠算法局部搜索中,融入了交叉操作;为防止算法在后期陷入局部最优解,引进了变异操作,保证了群体的多样性。将自适应罚函数法与改进的蝙蝠算法融合起来求解约束优化问题,4个复杂的标准测试函数和2个工程实际问题证明了该约束优化求解方法的可行性和有效性。     

带时间窗的多车型需求可拆分揽收配送问题

研究了一种带时间窗的多车型需求可拆分揽收配送问题（Multi-Vehicle Split Pickup and Delivery Problem with Time Windows,MVSPDPTW）。针对这个问题以执行任务车辆行驶路径总长度最小为目标函数,建立了一个混合整数线性规划模型。提出了一种高效禁忌模拟退火（Tabu Simulated Annealing,TSA）算法,在算法中设计了两种新的邻域搜索算子,分别用于修复违反容量约束以及换车操作,多种算子配合的方式扩大了邻域搜索范围,避免算法陷入局部最优。此外在算法中加入了禁忌机制以及违反约束惩罚机制,实现了搜索空间的有效裁剪,提高了算法的全局寻优能力。最后基于Solomon数据集和构造的仿真数据集等对算法进行了大量仿真实验,实验验证了该算法的有效性。     

采用增强学习算法的排课模型

时间表问题是典型的组合优化和不确定性调度问题。课表问题是时间表问题的一种形式,分析了排课问题的数学模型，并研究了用增强学习(Reinforcement Leaming)算法中的Q学习(Q-Leaming)算法和神经网络技术结合解决大学课表编排问题，给出了一个基于该算法的排课模型，并对其排课效果进行了分析和探讨。     

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

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

三峡-葛洲坝联合调度系统闸室编排快速算法

三峡—葛洲坝两坝联合调度系统是用于提高三峡—葛洲坝航道通航能力的一套系统。两坝联合调度的计划编排是一个与闸室编排相耦合的时间表问题。闸室编排可以用二维Packing模型来描述,是一个典型NP完全问题。提出一种基于分步降维思想的启发式快速编排算法,该算法把闸室编排二维Packing问题降到一维求解,有效解决三峡-葛洲坝联合调度的计划编排中与闸室编排相耦合的时间表问题。该算法在实际工程应用中取得了良好的效果,有效地提高了闸室面积利用率。     

分组遗传算法优化大学考试时间表

大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模,而寻优的操作有可能会破坏时间表的硬约束条件,从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发,对用图着色模型得到的已经满足了硬约束条件的初始考试时间表,用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间,并且还大大减少了寻优的计算量。     

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

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

求解约束优化问题的改进自适应mu约束处理技术

针对当前的约束处理技术存在易陷入局部最优解、难以满足等式约束和多控制参数的问题,在mu约束处理技术的基础上,以梯度下降法和多目标拥挤距离为理论依据,设计反映种群约束违反度分布信息的omega参数,它可以自适应地调节约束违反度阈值mu的松弛进而有效地解决约束问题.此外,改进了mu阈值比较准则以提高种群的多样性.经对CEC2017的标准约束优化问题(Constraint optimization problems,COP)进行求解,并与其他先进算法相比较,结果表明,改进的mu约束处理技术能够高效地处理含等式约束的COP.     

An Iterative local-search framework for solving constraint satisfaction problem

In this article, we introduce a new solving framework based on using alternatively two local-search algorithms to solve constraint satisfaction and optimization problems. The technique presented is based on the integration of local-search algorithm as a mechanism to diversify the search instead of using a build on diversification mechanisms. Thus, we avoid tuning the multiple parameters to escape from a local optimum. This technique improves the existing methods: it is generic especially when the given problem can be expressed as a constraint satisfaction problem. We present the way the local-search algorithm can be used to diversify the search in order to solve real examination timetabling problems. We describe how the local-search algorithm can be used to assist any other specific local-search algorithm to escape from local optimality. We showed that such framework is efficient on real benchmarks for timetabling problems.     

Extending GENET with lazy arc consistency

Many important applications, such as graph coloring, scheduling and production planning, can be solved by GENET, a local search method which is used to solve binary constraint satisfaction problems (CSPs). Where complete search methods are typically augmented with consistency methods to reduce the search, local search methods are not. We propose a consistency technique, lazy arc consistency, which is suitable for use within GENET. We show it can improve the efficiency of the GENET search on some instances of binary CSPs, and does not suffer the overhead of full arc consistency     

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

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

Genetic based discrete particle swarm optimization for Elderly Day Care Center timetabling

The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.     

Modelling and Solving Employee Timetabling Problems

Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a fixed period of time, typically a week. We present a general definition of employee timetabling problems (ETPs) that captures many real-world problem formulations and includes complex constraints. The proposed model of ETPs can be represented in a tabular form that is both intuitive and efficient for constraint representation and processing. The constraint networks of ETPs include non-binary constraints and are difficult to formulate in terms of simple constraint solvers. We investigate the use of local search techniques for solving ETPs. In particular, we propose several versions of hill-climbing that make use of a novel search space that includes also partial assignments. We show that, on large and difficult instances of real world ETPs, where systematic search fails, local search methods perform well and solve the hardest instances. According to our experimental results on various techniques, a simple version of hill climbing based on random moves is the best method for solving large ETP instances.     

A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling

The post enrolment course timetabling problem (PECTP) is one type of university course timetabling problems, in which a set of events has to be scheduled in time slots and located in suitable rooms according to the student enrolment data. The PECTP is an NP-hard combinatorial optimisation problem and hence is very difficult to solve to optimality. This paper proposes a hybrid approach to solve the PECTP in two phases. In the first phase, a guided search genetic algorithm is applied to solve the PECTP. This guided search genetic algorithm, integrates a guided search strategy and some local search techniques, where the guided search strategy uses a data structure that stores useful information extracted from previous good individuals to guide the generation of offspring into the population and the local search techniques are used to improve the quality of individuals. In the second phase, a tabu search heuristic is further used on the best solution obtained by the first phase to improve the optimality of the solution if possible. The proposed hybrid approach is tested on a set of benchmark PECTPs taken from the international timetabling competition in comparison with a set of state-of-the-art methods from the literature. The experimental results show that the proposed hybrid approach is able to produce promising results for the test PECTPs.     

An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach

In this paper we consider the no-wait job shop problem with a makespan objective. This problem has usually been addressed by its decomposition into a sequencing and a timetabling problem. Here, first we focus on the timetabling problem and take advantage of the symmetry of the problem in order to suggest a new timetabling procedure. Secondly, we suggest embedding this timetabling into a recent metaheuristic named complete local search with memory.     

A Generic Framework for Constrained Optimization Using Genetic Algorithms

In this paper, we propose a generic, two-phase framework for solving constrained optimization problems using genetic algorithms. In the first phase of the algorithm, the objective function is completely disregarded and the constrained optimization problem is treated as a constraint satisfaction problem. The genetic search is directed toward minimizing the constraint violation of the solutions and eventually finding a feasible solution. A linear rank-based approach is used to assign fitness values to the individuals. The solution with the least constraint violation is archived as the elite solution in the population. In the second phase, the simultaneous optimization of the objective function and the satisfaction of the constraints are treated as a biobjective optimization problem. We elaborate on how the constrained optimization problem requires a balance of exploration and exploitation under different problem scenarios and come to the conclusion that a nondominated ranking between the individuals will help the algorithm explore further, while the elitist scheme will facilitate in exploitation. We analyze the proposed algorithm under different problem scenarios using Test Case Generator-2 and demonstrate the proposed algorithm's capability to perform well independent of various problem characteristics. In addition, the proposed algorithm performs competitively with the state-of-the-art constraint optimization algorithms on 11 test cases which were widely studied benchmark functions in literature.     

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

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

基于PBIL算法的高校自动排考系统

提出了一种基于PBIL的高校自动排考算法,重点论述了如何优化目标函数与排考约束条件之间的关系,并对PBIL基因选择算法提出了改进。通过实际的测试应用,基于PBIL算法的自动排考系统能够较好地满足学分制下的自动排考需求,对附加约束条件具有较强的适应性,能够满足各个学校的不同排考需求。