基于特征提取系统的遗传算法在QAP上的应用

针对遗传算法在解QAP时表现出局部搜索能力差、收敛过快的问题,提出一种基于特征提取系统的遗传算法.该算法综合遗传算法较强全局搜索能力和特征提取系统对优秀个体的特征提取能力,并辅以局部搜索,在解QAP时取得了良好的性能.     

Complex university course timetabling

This paper summarizes the work done to solve a complex course timetabling problem at a large university and provides new insights into the overall timetabling process. The first step in the successful solution of this problem was to define a course structure model that allowed application of classical course timetabling methods. Several methods were necessary to solve the complete problem. First, support procedures were needed to detect and correct an infeasible problem where hard constraints were being violated. The resulting timetabling problem was then solved via a search for a complete assignment of times and rooms to classes, taking all hard and soft constraints into account. Methods were also developed for modifying a computed solution in response to changes introduced at a later time while having a minimal impact on existing assignments.     

A hybrid approach using genetic and fruit fly optimization algorithms for QoS-aware cloud service composition

This paper addresses the QoS-aware cloud service composition problem, which is known as a NP-hard problem, and proposes a hybrid genetic algorithm (HGA) to solve it. The proposed algorithm combines two phases to perform the evolutionary process search, including genetic algorithm phase and fruit fly optimization phase. In genetic algorithm phase, a novel roulette wheel selection operator is proposed to enhance the efficiency and the exploration search. To reduce the computation time and to maintain a balance between the exploration and exploitation abilities of the proposed HGA, the fruit fly optimization phase is incorporated as a local search strategy. In order to speed-up the convergence of the proposed algorithm, the initial population of HGA is created on the basis of a heuristic local selection method, and the elitism strategy is applied in each generation to prevent the loss of the best solutions during the evolutionary process. The parameter settings of our HGA were tuned and calibrated using the taguchi method of design of experiment, and we suggested the optimal values of these parameters. The experimental results show that the proposed algorithm outperforms the simple genetic algorithm, simple fruit fly optimization algorithm, and another recently proposed algorithm (DGABC) in terms of optimality, computation time, convergence speed and feasibility rate.     

用演化算法求解高校排课的问题

根据排课问题的有效性约束,建立了基于实际情况的数学模型,提出课元、资源等概念模型。采用演化算法来解决排课问题,根据教师集、班级集、课程集、教室集、时间集、课元集、资源集等概念定义了约束集,再设计了相应的编码和评价方法,采用轮盘选择、单点交叉、随机变异、μ＋λ淘汰等策略进行计算．实验结果表明,用演化算法解决排课问题是可行的。     

优化蚁群算法在排课中的应用策略

针对高校排课面临的问题和挑战,通过分析排课问题的约束条件,将解决排课问题转化为二分图匹配的问题,并给出优化蚁群算法方案,探索高校排课问题的优化策略。     

基于混合蚁群优化的卫星地面站系统任务调度方法

卫星地面站系统任务调度是一个典型的组合优化问题, 优化过程极其复杂. 鉴于此, 提出了一种有效求解该问题的基于蚁群优化算法和导向局部搜索方法的混合优化方法. 该方法将蚁群优化和导向局部搜索有效地结合在一起, 极大地提高了优化绩效. 实例计算结果表明, 该混合方法能有效地求解卫星地面站系统任务调度问题.     

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.     

A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences

The timetabling problem at universities is an NP-hard problem concerned with instructor assignments and class scheduling under multiple constraints and limited resources. A novel meta-heuristic algorithm that is based on the principles of particle swarm optimization (PSO) is proposed for course scheduling problem. The algorithm includes some features: designing an ‘absolute position value’ representation for the particle; allowing instructors that they are willing to lecture based on flexible preferences, such as their preferred days and time periods, the maximum number of teaching-free time periods and the lecturing format (consecutive time periods or separated into different time periods); and employing a repair process for all infeasible timetables. Furthermore, in the original PSO algorithm, particles search solutions in a continuous solution space. Since the solution space of the course scheduling problem is discrete, a local search mechanism is incorporated into the proposed PSO in order to explore a better solution improvement. The algorithms were tested using the timetabling data from a typical university in Taiwan. The experimental results demonstrate that the proposed hybrid algorithm yields an efficient solution with an optimal satisfaction of course scheduling for instructors and class scheduling arrangements. This hybrid algorithm also outperforms the genetic algorithm proposed in the literature.     

An ILP based heuristic for a generalization of the post-enrollment course timetabling problem

We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.     

A hybrid self-adaptive bees algorithm for examination timetabling problems

A hybrid self-adaptive bees algorithm is proposed for the examination timetabling problems. The bees algorithm (BA) is a population-based algorithm inspired by the way that honey bees forage for food. The algorithm presents a type of neighbourhood search that includes a random search that can be used for optimisation problems. In the BA, the bees search randomly for food sites and return back to the hive carrying the information about the food sites (fitness values); then, other bees will select the sites based on their information (more bees are recruited to the best sites) and will start a random search. We propose three techniques (i.e. disruptive, tournament and rank selection strategies) for selecting the sites, rather than using the fitness value, to improve the diversity of the population. Additionally, a self-adaptive strategy for directing the neighbourhood search is added to further enhance the local intensification capability. Finally, a modified bees algorithm is combined with a local search (i.e. simulated annealing, late acceptance hill climbing) to quickly descend to the optimum solution. Experimental results comparing our proposed modifications with each other and with the basic BA show that all of the modifications outperform the basic BA; an overall comparison has been made with the best known results on two examination timetabling benchmark datasets, which shows that our approach is competitive and works well across all of the problem instances.     

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

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

遗传算法与禁忌搜索算法的混合策略在VRPTM问题上的应用

该文探讨了如何将基于遗传算法和禁忌搜索算法的混合策略应用于求解有时间窗的车辆路径(VRPTM)问题,给出了相应的应用算法。实验结果表明,这种将禁忌搜索作为变异操作的混合策略对VRPTM问题是行之有效的,其优化性能优于简单的遗传算法。     

求解车间调度问题的2阶段混合粒子群优化算法

针对车间调度问题,提出了一种2阶段混合粒了群算法(TS-HPSO).该算法在第1阶段为每个粒子设置较大的惯性系数w,同时去掉了粒子的社会学习能力,从而保证每个微粒在局部范围内充分搜索.第2阶段的混合粒子群算法以第1阶段每个粒子找到的最好解作为初始解,同时以遗传算法中的变异操作保证粒了多样性;为保证算法的寻优能力,对全局gbest进行贪婪邻域搜索.计算结果证明了本算法的有效性.     

Enhanced hybrid metaheuristic algorithms for optimal sizing of steel truss structures with numerous discrete variables

The advent of modern computing technologies paved the way for development of numerous efficient structural design optimization tools in the recent decades. In the present study sizing optimization problem of steel truss structures having numerous discrete variables is tackled using combined forms of recently proposed metaheuristic techniques. Three guided, and three guided hybrid metaheuristic algorithms are developed by integrating a design oriented strategy to the stochastic search properties of three recently proposed metaheuristic optimization techniques, namely adaptive dimensional search, modified big bang-big crunch, and exponential big bang-big crunch algorithms. The performances of the proposed guided, and guided hybrid metaheuristic algorithms are compared to those of standard variants through optimum design of real-size steel truss structures with up to 728 design variables according to AISC-LRFD specification. The numerical results reveal that the hybrid form of adaptive dimensional search and exponential big bang-big crunch algorithm is the most promising algorithm amongst the other investigated techniques.     

多目标混合遗传算法求解流水车间调度问题

为高效地求解多目标流水车间调度问题,提出了一种多目标混合遗传算法,此算法将局部搜索融入进化计算中,采用非劣解并行局部搜索策略,并依据基于Pareto支配关系的个体排序数和密度值进行适应度赋值,以加速算法的收敛,保持群体多样性.仿真结果表明,新算法能够有效地解决多目标流水车间调度问题.     

A hybrid genetic algorithm for feature subset selection in rough set theory

Rough set theory has been proven to be an effective tool to feature subset selection. Current research usually employ hill-climbing as search strategy to select feature subset. However, they are inadequate to find the optimal feature subset since no heuristic can guarantee optimality. Due to this, many researchers study stochastic methods. Since previous works of combination of genetic algorithm and rough set theory do not show competitive performance compared with some other stochastic methods, we propose a hybrid genetic algorithm for feature subset selection in this paper, called HGARSTAR. Different from previous works, HGARSTAR embeds a novel local search operation based on rough set theory to fine-tune the search. This aims to enhance GA’s intensification ability. Moreover, all candidates (i.e. feature subsets) generated in evolutionary process are enforced to include core features to accelerate convergence. To verify the proposed algorithm, experiments are performed on some standard UCI datasets. Experimental results demonstrate the efficiency of our algorithm.     

一种改进的混合遗传算法研究

标准遗传算法的求泛能力优于它的求精能力,在求解GA-困难问题时求解精度难以控制,本文由此提出了一种改进的ε-混合遗传算法。本算法在每代找出最优个体之后,以该最优个体为初始出发点在一个固定半径的区域内进行局部搜索,以搜索结果代替最差个体或其它个体,然后再进入下一代操作。算法大大提高了求解精度,同时也提高了稳定定性。     

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 new hybrid algorithm for university course timetabling problem using events based on groupings of students

In this paper, a new hybrid algorithm (NHA) combining genetic algorithm with local search and using events based on groupings of students is described to solve the university course timetabling problem. A list of events such as lectures, tutorials, laboratories and seminars are ordered and mutually disjoint groups of students taking them are formed in such a way that once a student is selected in any group, he is excluded from further selection in other groups. The union of all the events taken by all the students of each group is formed. The number of events in each group is termed as its group size whose upper bound is restricted by the total number of timeslots and can be reduced to the maximum number of events per student. The above process of forming groups is repeated till the size of each group is reduced within this bound by not choosing those events which are common for all the students in the group. Now, the genetic algorithm with local search (GALS) is applied on a number of benchmark problems. The experimental results show that our algorithm, NHA, is able to produce promising results when compared with the results obtained by using GALS and other existing algorithms.     

An effective hybrid algorithm for university course timetabling

The university course timetabling problem is an optimisation problem in which a set of events has to be scheduled in timeslots and located in suitable rooms. Recently, a set of benchmark instances was introduced and used for an ‘International Timetabling Competition’ to which 24 algorithms were submitted by various research groups active in the field of timetabling. We describe and analyse a hybrid metaheuristic algorithm which was developed under the very same rules and deadlines imposed by the competition and outperformed the official winner. It combines various construction heuristics, tabu search, variable neighbourhood descent and simulated annealing. Due to the complexity of developing hybrid metaheuristics, we strongly relied on an experimental methodology for configuring the algorithms as well as for choosing proper parameter settings. In particular, we used racing procedures that allow an automatic or semi-automatic configuration of algorithms with a good save in time. Our successful example shows that the systematic design of hybrid algorithms through an experimental methodology leads to high performing algorithms for hard combinatorial optimisation problems.