Search

This paper presents a new hybrid metaheuristic between a greedy randomized adaptive search procedure (GRASP) and an evolutionary/iterated local search (ELS/ILS), using Tabu list to solve the two-echelon location routing problem (LRP-2E). The GRASP uses in turn three constructive heuristics followed by local search to generate the initial solutions. From a solution of GRASP, an intensification strategy is carried out by a dynamic alternation between ELS and ILS. In this phase, each child is obtained by mutation and evaluated through a splitting procedure of giant tour followed by a local search. The tabu list, defined by two characteristics of solution (total cost and number of trips), is used to avoid searching a space already explored. The results show that our metaheuristic clearly outperforms all previously published methods on LRP-2E benchmark instances. Furthermore, it is competitive with the best meta-heuristic published for the single-echelon LRP. [ABSTRACT FROM AUTHOR]

The article presents a solution approach for a curriculum-based timetabling problem, a complex planning problem found in many universities. With regard to the true nature of the problem, we treat it as multi-objective optimization problem, trying to balance several aspects that simultaneous have to be taken into consideration. A solution framework based on local search heuristics is presented, allowing the planner to identify compromise solutions. Two different aggregation techniques are used and studied. First, a weighted sum aggregation, and second, a reference point based approach. Experimental investigations are carried out for benchmark instances taken from track 3 of the International Timetabling Competition ITC 2007. After having been invited to the finals of the competition, held in August 2008 in Montréal, and thus ranking among the best five approaches world-wide, we here extend our work towards the use of reference points. [ABSTRACT FROM AUTHOR]

In this paper, we study the perturbation operator of Iterated Local Search. To guide more efficiently the search to move towards new promising regions of the search space, we introduce a Critical Element-Guided Perturbation strategy (CEGP). This perturbation approach consists of the identification of critical elements and then focusing on these critical elements within the perturbation operator. Computational experiments on two case studies–graph coloring and course timetabling–give evidence that this critical element-guided perturbation strategy helps reinforce the performance of Iterated Local Search. [ABSTRACT FROM AUTHOR]

Many instances of NP-hard problems can be solved efficiently if the treewidth of their corresponding graph is small. Finding the optimal tree decompositions is an NP-hard problem and different algorithms have been proposed in the literature for generation of tree decompositions of small width. In this chapter we present a new iterated local search algorithm to find good upper bounds for treewidth of an undirected graph. The iterated local search algorithm consists from the construction phase, and includes the mechanism for perturbation of solutions, and the mechanism for accepting of solutions for the next iteration. In the construction phase the solutions are generated by the heuristics which search for good elimination ordering of nodes of graph based on moving of only vertices that produce the largest clique in the elimination process. We proposed and evaluated different perturbation mechanisms and acceptance criteria. The proposed algorithm is tested on DIMACS instances for vertex colouring, and is compared with the existing approaches in the literature. The described algorithm has a good time performance and for several instances improves the best existing upper bounds for the treewidth. [ABSTRACT FROM AUTHOR]

The problem of curriculum-based course timetabling is studied in this work. In addition to formally defining the problem, we present a hybrid solution algorithm (Adaptive Tabu Search–ATS), which is aimed at minimizing violations of soft constraints. Within ATS, a new neighborhood and a mechanism for dynamically integrating Tabu Search with perturbation (from Iterated Local Search) are proposed to ensure a continuous tradeoff between intensification and diversification. The performance of the proposed hybrid heuristic algorithm is assessed on two sets of 11 public instances from the literature. Computational results show that it significantly improves the previous best known results on two problem formulations. [ABSTRACT FROM AUTHOR]

Many problems in AI can be stated as search problems and most of them are very complex to solve. One alternative for these problems are local search methods that have been widely used for tackling difficult optimization problems for which we do not know algorithms which can solve every instance to optimality in a reasonable amount of time. One of the most popular methods is what is known as iterated local search (ILS), which samples the set of local optima searching for a better solution. This algorithm΄s behavior is achieved by some mechanisms like perturbation which is a key aspect to consider, since it allows the algorithm to reach a new solution from the set of local optima by escaping from the previous local optimum basis of attraction. In order to design a good perturbation method we need to analyze the local optima structure such that ILS leads to a good biased sampling. In this paper, the local optima structure of the Quadratic Assignment Problem, an NP-hard optimization problem, is used to determine the required perturbation size in the ILS algorithm. The analysis is focused on verifying if the set of local optima has the ˵Big Valley (BV)″ structure, and on how close local optima are in relation to problem size. Experimental results show that a small perturbation seems appropriate for instances having the BV structure, and for instances having a low distance among local optima, even if they do not have a clear BV structure. Finally, as the local optima structure moves away from BV a larger perturbation is needed. [ABSTRACT FROM AUTHOR]