Guided Local Search
International series in management science/operations research/International series in operations research & management sciencePublished 1 January 2010
Christos Voudouris, Edward Tsang, Abdullah Alsheddy
Citations212
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This chapter describes the principles of Guided Local Search (GLS) and Fast Local Search and surveys their applications and provides guidance for implementing and using GLS and FLS.
Abstract
Combinatorial explosion is a well-known phenomenon that prevents complete algorithms from solving many real-life combinatorial optimization problems. In many situations, heuristic search methods are needed. This chapter describes the principles of Guided Local Search (GLS) and Fast Local Search (FLS) and surveys their applications. GLS is a penalty-based metaheuristic algorithm that sits on top of other local search algorithms, with the aim to improve their efficiency and robustness. FLS is a way of reducing the size of the neighbourhood to improve the efficiency of local search. The chapter also provides guidance for implementing and using GLS and FLS. Four problems, representative of general application categories, are examined with detailed information provided on how to build a GLS-based method in each case.
Keywords
Computer ScienceEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
IEEE Transactions on Evolutionary ComputationMOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition
9,561 Citations2007Qingfu Zhang, Hui Li
Experimental results have demonstrated that MOEA/D with simple decomposition methods outperforms or performs similarly to MOGLS and NSGA-II on multiobjective 0-1 knapsack problems and continuous multiobjectives optimization problems.
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
INFORMS Journal on ComputingTabu Search—Part II
5,643 Citations1990Fred Glover
The elements of staged search and structured move sets are characterized, which bear on the issue of finiteness, and new dynamic strategies for managing tabu lists are introduced, allowing fuller exploitation of underlying evaluation functions.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Tabu Search
2,936 Citations1997Fred Glover, Manuel Laguna
This book explores the meta-heuristics approach called tabu search, which is dramatically changing the authors' ability to solve a host of problems that stretch over the realms of resource planning, telecommunications, VLSI design, financial analysis, scheduling, spaceplanning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management,mineral exploration, biomedical analysis, environmental conservation and scores of other problems.
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
Elsevier eBooksFoundations of Constraint Satisfaction
1,616 Citations1993
Introduction to the C SP CSP solving - an overview chapter fundamental concepts of the CSP chapter problem reduction chapter basic search strategies for solving CSPs search orders in searching in C SPs exploitation of problem specific features stochastic search methods.
Operations ResearchA Method for Solving Traveling-Salesman Problems
1,532 Citations1958G. A. Croes
A method of solution for the traveling-salesman problem that is applicable to both symmetric and asymmetric problems with random elements, and does not use subjective decisions, so that it can be completely mechanized.
Foundations of artificial intelligenceHandbook of Constraint Programming
1,493 Citations2006
Researchers from other fields should find in this handbook an effective way to learn about constraint programming and to possibly use some of the constraint programming concepts and techniques in their work, thus providing a means for a fruitful cross-fertilization among different research areas.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
1,468 Citations1989David S. Johnson, C. Aragon +2 more
This paper discusses annealing and its parameterized generic implementation, describes how this generic algorithm was adapted to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm.
A new method for solving hard satisfiability problems
1,183 Citations1992Bart Selman, Hector J. Levesque +1 more
A greedy local search procedure called GSAT is introduced for solving propositional satisfiability problems and its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks.
Annals of Operations ResearchA user's guide to tabu search
910 Citations1993Fred Glover, Éric D. Taillard +1 more
This presentation demonstrates that a well-tuned implementation of tabu search makes it possible to obtain solutions of high quality for difficult problems, yielding outcomes in some settings that have not been matched by other known techniques.
Artificial IntelligenceMinimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
830 Citations1992Steven Minton, Mark Johnston +2 more
A theoretical analysis is presented both to explain why this heuristic approach to solving large-scale constraint satisfaction and scheduling problems works well on certain types of problems and to predict when it is likely to be most effective.
Parallel ComputingRobust taboo search for the quadratic assignment problem
827 Citations1991Éric D. Taillard
An adaptation of taboo search to the quadratic assignment problem is discussed in this paper, which is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations.
INFORMS Journal on ComputingThe Reactive Tabu Search
806 Citations1994Roberto Battiti, Giampietro Tecchiolli
An algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search, and it is shown that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant.
Operations ResearchThe Traveling-Salesman Problem
670 Citations1956Merrill M. Flood
The traveling-salesman problem is that of finding a permutation P of the integers from 1 through n that minimizes the quantity A where the aαβ are a given set of real numbers.
Journal of Global OptimizationQAPLIB – A Quadratic Assignment Problem Library
655 Citations1997Rainer E. Burkard, Stefan E. Karisch +1 more
A collection of electronically available data instances for the Quadratic Assignment Problem are described, indicating whether or not the problem is solved to optimality and the best known bounds for the problem are supplied.
Artificial IntelligencePartial constraint satisfaction
609 Citations1992Eugene C. Freuder, Richard J. Wallace
A general model of partial constraint satisfaction is proposed and standard backtracking and local consistency techniques for solving constraint satisfaction problems can be adapted to cope with, and take advantage of, the differences between partial and complete constraint satisfaction.
Computers & Operations ResearchA genetic algorithm for the generalised assignment problem
511 Citations1997P.C. Chu, J. E. Beasley
Computational results show that the genetic algorithm heuristic is able to find optimal and near optimal solutions that are on average less than 0.01 % from optimality.
INFORMS Journal on ComputingFast Algorithms for Geometric Traveling Salesman Problems
469 Citations1992Jon Jouis Bentley
Efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets and three local optimizations are described, which are able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours.
INFORMS Journal on ComputingTabu Search Applied to the Quadratic Assignment Problem
461 Citations1990Jadranka Skorin‐Kapov
This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP), and suggests that good tabu list sizes increase with dimension of the problem.
European Journal of Operational ResearchGuided local search and its application to the traveling salesman problem
395 Citations1999Christos Voudouris, Edward Tsang
Comparisons are made with some of the best TSP heuristic algorithms and general optimization techniques which demonstrate the advantages of GLS over alternative heuristic approaches suggested for the problem.
European Journal of Operational ResearchQuadratic assignment problems
382 Citations1984Rainer E. Burkard
Lecture notes in computer scienceLocal optimization and the Traveling Salesman Problem
376 Citations2005David S. Johnson
This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
An Introduction to Variable Neighborhood Search
342 Citations1999Pierre Hansen, Nenad Mladenović
A relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process, is examined, which leads to a new metaheuristic, which is widely applicable.
Annals of Operations ResearchModels and solution techniques for frequency assignment problems
329 Citations2007Karen Aardal, Stan P.M. van Hoesel +3 more
Location ScienceComparison of iterative searches for the quadratic assignment problem
323 Citations1995Éric D. Taillard
This paper compares some of the most efficient heuristic methods for the quadratic assignment problem and shows that no one method is better than all the others.
DIMACS series in discrete mathematics and theoretical computer scienceThe quadratic assignment problem: A survey and recent developments
306 Citations1994Pãnos M. Pardalos, Franz Rendl +1 more
This paper surveys some of the most important techniques, applications, and methods regarding the quadratic assignment problem.
Domain-independent extensions to GSAT: solving large structured satisfiability problems
296 Citations1993Bart Selman, Henry Kautz
This work presents three strategies that dramatically improve GSAT's performance on formulas with a high degree of asymmetry, thereby significantly extending the applicability of the GSAT algorithm.
Computers & Operations ResearchAn efficient variable neighborhood search heuristic for very large scale vehicle routing problems
292 Citations2005Jari Kytöjoki, Teemu Nuortio +2 more
An efficient variable neighborhood search heuristic for the capacitated vehicle routing problem to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands is presented.
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
280 Citations2002Bernd Freisleben, P. Merz
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP) and the results indicate that it is possible to arrive at high quality solutions in reasonable time.
SpringerReferenceEfficient Exploration in Reinforcement Learning
263 Citations2012
It is proved that for all finite deterministic domains, reinforcement learning using a directed technique can always be performed in polynomial time, demonstrating the important role of exploration in reinforcement learning.
Operations ResearchThe Theory of Search
262 Citations1957B. O. Koopman
This is Part III, concluding the series of three papers on The Theory of Search, where the material was first presented by the author at the fall meeting of the Operations Research Society of America in 1953, where it was treated as a natural extension of his paper, The Optimum distribution of effort.
Computers & Operations ResearchActive guided evolution strategies for large-scale vehicle routing problems with time windows
223 Citations2004David Mester, Olli Bräysy
A new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows, which combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure.
INFORMS journal on computingGuided Local Search for the Three-Dimensional Bin-Packing Problem
222 Citations2003Oluf Faroe, David Pisinger +1 more
A heuristic algorithm based on guided local search that iteratively decreases the number of bins, each time searching for a feasible packing of the boxes, finding better solutions than do heuristics from the literature.
Annals of Operations ResearchCombining simulated annealing with local search heuristics
217 Citations1996Olivier Martin, Steve W. Otto
A meta-heuristic to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space.
Lecture notes in economics and mathematical systemsPareto Local Optimum Sets in the Biobjective Traveling Salesman Problem: An Experimental Study
213 Citations2004Luís Paquete, Marco Chiarandini +1 more
This article studies Pareto local optimum sets for the biobjective Traveling Salesman Problem applying straightforward extensions of local search algorithms for the single objective case and indicates the existence of several clusters of near-optimal solutions that are separated by only a few edges.
European Journal of Operational ResearchA guided local search metaheuristic for the team orienteering problem
194 Citations2008Pieter Vansteenwegen, Wouter Souffriau +2 more
Guided local search (GLS) is used to improve two of the proposed heuristics of the literature and an extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space.
European Journal of Operational ResearchA guided local search heuristic for the capacitated arc routing problem
181 Citations2003Patrick Beullens, Luc Muyldermans +2 more
A new local search algorithm for the capacitated arc routing problem (CARP) is presented that outperforms the existing heuristics for the CARP and often detects an optimal solution within limited computation time.
European Journal of Operational ResearchA Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints
179 Citations2007Emmanouil E. Zachariadis, Christos D. Tarantilis +1 more
A metaheuristic algorithm is proposed which incorporates the rationale of Tabu Search and Guided Local Search and employs a memory structure to record the loading feasibility information of the Capacitated Vehicle Routing Problem with two-dimensional loading constraints.
Journal of HeuristicsSolving Vehicle Routing Problems Using Constraint Programming and Metaheuristics
178 Citations2000Bruno De Backer, Vincent Furnon +3 more
A method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems, and has coupled its local search method with a meta-heuristic to avoid the search being trapped in local minima.
European Journal of Operational ResearchFast neighborhood search for two- and three-dimensional nesting problems
149 Citations2006Jens Egeblad, Benny K. Nielsen +1 more
A new heuristic solution method for two-dimensional nesting problems based on a simple local search scheme in which the neighborhood is any horizontal or vertical translation of a given polygon from its current position is presented.
Journal of Global OptimizationA Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems
147 Citations1998Yi Shang, Benjamin W. Wah
This paper derives new approaches for applying Lagrangian methods in discrete space, shows that an equilibrium is reached when a feasible assignment to the original problem is found and presents heuristic algorithms to look for equilibrium points, and proposes a new discrete Lagrange-multiplier-based global-search method (DLM) for solving satisfiability problems.
Operations Research LettersFast local search and guided local search and their application to British Telecom's workforce scheduling problem
137 Citations1997Edward Tsang, Chris Voudouris
A fast local search (FLS) algorithm which helps to improve the efficiency of hill climbing and a guided local search algorithm which was developed to help local search to escape local optima and distribute search effort are reported.
Journal of the Operational Research SocietyHeuristic algorithms for the multiple-choice multidimensional knapsack problem
133 Citations2004Mhand Hifi, Mustapha Michrafy +1 more
Several heuristics for approximately solving the multiple-choice multidimensional knapsack problem (noted MMKP), an NP-Hard combinatorial optimization problem, are proposed.
Expert Systems with ApplicationsA hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service
133 Citations2007Emmanouil E. Zachariadis, Christos D. Tarantilis +1 more
A hybrid solution approach is proposed incorporating the rationale of two well-known metaheuristics which have proven to be effective for routing problem variants, namely tabu search and guided local search to achieve a vast exploration of the search space.
Computers & Operations ResearchTabu search performance on the symmetric traveling salesman problem
130 Citations1994J.R. Knox
The performance of tabu search is compared to the K-OPT procedure using six test problems drawn from the literature and some factors which influence the performance oftabu search are provided.
European Journal of Operational ResearchAnt colony optimization for solving an industrial layout problem
125 Citations2007Yasmina Hani, Lionel Amodeo +2 more
ACO_GLS, a hybrid ant colony optimization approach coupled with a guided local search, applied to a layout problem, shows that it performs better for small instances, while its performance is still satisfactory for large instances.
Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)New Ideas in Optimisation
121 Citations1999Dave Corne, Marco Dorigo +1 more
OpenGrey (Institut de l'Information Scientifique et Technique)GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement
119 Citations1994Andrew Davenport, Edward Tsang +2 more
Although GENET has been designed to be implemented on VLSI hardware, empirical evidence is presented to show that even when simulated on a single processor GENET can outperform existing iterative improvement techniques on hard instances of certain constraint satisfaction problems.
Frequency Assignment Problems
102 Citations1999Robert Murphey, Pãnos M. Pardalos +1 more
Of special interest here are land cellular mobile systems, where an enormous amount of research has been done and nearly 100 references to works just in cellular dynamic channel assignment are found.
Journal of HeuristicsA Constraint Programming Framework for Local Search Methods
99 Citations1999Gilles Pesant, Michel Gendreau
A novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of localSearch methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure.
Journal of HeuristicsTabu Search for Frequency Assignment in Mobile Radio Networks
99 Citations1998Jin‐Kao Hao, Raphaël Dorne +1 more
Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances, and it is compared with other methods based on simulated annealing, constraint programming and graph coloring algorithms.
INFORMS journal on computingA Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities
99 Citations2007Christos D. Tarantilis, Emmanouil E. Zachariadis +1 more
The proposed algorithmic framework was successfully applied to benchmark instances in the literature, generating several new best solutions and developed new classes of VRPIRF benchmark instances with diverse problem characteristics.
Transportation Research Part E Logistics and Transportation ReviewA vehicle routing problem with backhauls and time windows: a guided local search solution
97 Citations2004Yingjie Zhong, Michael H. Cole
Guided Local Search for the Vehicle Routing Problem with Time Windows
93 Citations1999Philip Kilby, Patrick Prosser +1 more
Partial Constraint Satisfaction Problems and Guided Local Search
87 Citations1996Chris Voudouris
The stochastic search method of Guided Local Search (GLS) is examined and the effectiveness of the method is demonstrated on instances of the Radio Link Frequency Assignment Problem (RLFAP), which is a real-world Partial CSP.
Journal of Automated ReasoningGuided Local Search for Solving SAT and Weighted MAX-SAT Problems
72 Citations2000Patrick Mills, Edward Tsang
This paper presents empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compares them with the results of other local search algorithms for the SATproblem.
DIMACS series in discrete mathematics and theoretical computer scienceA GRASP for satisfiability
71 Citations1996Maurício G. C. Resende, Thomas A. Feo
ConstraintsA Comparison of Traditional and Constraint-based Heuristic Methods on Vehicle Routing Problems with Side Constraints
59 Citations2000Philip Kilby, Patrick Prosser +1 more
This paper uses a constraint-based toolkit for solving vehicle routing problems to study the effect of different heuristic techniques, and shows that as the size of the solution space is decreased through addition of side constraints, certain conventional techniques fail while constraint directed techniques continue to perform acceptably.
Computational Biology and ChemistryFast and high precision algorithms for optimization in large-scale genomic problems
52 Citations2004David Mester, Yefim Ronin +2 more
High performance and high precision of the employed algorithm named guided evolution strategy (GES) allows verification of the obtained multilocus orders based on different computing-intensive approaches (e.g., bootstrap or jackknife) for detection and removing unreliable marker loci, hence, stabilizing the resulting paths.
Annals of Operations ResearchPath assignment for call routing: An application of tabu search
52 Citations1993Charles A. Anderson, Kathryn Fraughnaugh +2 more
An implementation of tabu search that solves the path assignment problem, which is the problem of routing video data through an undercapacitated telecommunications network, and its results compare very favourably with those from other methods.
Annals of Operations ResearchApplying an Extended Guided Local Search to the Quadratic Assignment Problem
46 Citations2003Patrick Mills, Edward Tsang +1 more
This paper presents empirical results of applying several extended versions of GLS to the QAP, and shows that these extensions can improve the range of parameter settings within which Guided Local Search performs well.
IOS Press , Ohmsha [distributor] eBooksSat2000: Highlights of Satisfiability Research in the Year 2000
46 Citations2000Ian Gentles, Hans van Maaren +1 more
This book is devoted to various disciplines in Satisfiability research and aims to give the reader an impression of the state of the art of this research in the Year 2000.
Solving constraint satisfaction problems using neural networks
45 Citations1991C. J. Wang, Edward Tsang
Lecture notes in computer scienceiOpt: A Software Toolkit for Heuristic Search Methods
44 Citations2001Christos Voudouris, Raphaël Dorne +2 more
The iOpt Toolkit attempts to address issues by providing problem modelling facilities well-matched to heuristic search operations, a generic framework for developing scheduling applications, and a logically structured heuristicsearch framework allowing the synthesis and evaluation of a variety of algorithms.
BT Technology JournalGuided Local Search — an Illustrative Example in Function Optimisation
42 Citations1998Chris Voudouris
It is demonstrated that the potential applications of GLS are not limited to optimisation problems of discrete nature but also to difficult continuous Optimisation problems.
Journal of SchedulingEmpowerment scheduling for a field workforce
36 Citations2011Abdullah Alsheddy, Edward Tsang
The model is applied to solve a workforce scheduling problem which involves scheduling a multi-skilled workforce to geographically dispersed tasks and maintains fairness by incorporating an automatic market-like mechanism that controls the violation cost of each employee’s request.
Guided Pareto Local Search based frameworks for biobjective optimization
36 Citations2010Abdullah Alsheddy, Edward E. P. K Tsang
The potential of GPLS to be an effective searching technique that can be a central part of a multi-phase or hybrid frameworks is demonstrated by achieving state-of-the-art results.
Perspectives in neural computingA Generic Neural Network Approach For Constraint Satisfaction Problems
34 Citations1992Edward Tsang, C. J. Wang
A neural network approach for solving CSPs which aims at providing prompt responses, which lends itself to the VLSI implementation of parallel processing architectures and the limited number of cycles required by GENET to find the solutions for the tested problems gives hope for solving large C SPs in a fraction of the time required by conventional methods.
Operations ResearchFeature Article—The Process of Search Planning: Current Approaches and Continuing Problems
31 Citations1983Lawrence D. Stone
The purpose of this article is to present an approach to search planning that encompasses both objective and subjective methods and provides for compromises between theoretically optimal plans and operationally feasible ones.
ConstraintsStochastic Local Search Algorithms for Graph Set T-colouring and Frequency Assignment
26 Citations2007Marco Chiarandini, Thomas Stützle
This article presents an experimental study of local search algorithms for solving general and large size instances of the graph set T-colouring problem and investigates systematically different models and search strategies in the algorithms and determines the best choices for different types of instance.
Journal of the Operational Research SocietyA guided tabu search for the heterogeneous vehicle routeing problem
19 Citations2007Christos D. Tarantilis, Emmanouil E. Zachariadis +1 more
The proposed algorithm called guided tabu search (GTS) is based on tabuSearch controlled by a continuous guiding mechanism that modifies the objective function of the problem to diversify the conducted search and help it overcome local optima encountered.
Artificial IntelligenceA Lagrangian reconstruction of GENET
19 Citations2000Kenneth M.F. Choi, Jimmy H. M. Lee +1 more
The guided genetic algorithm and its application to the generalized assignment problem
18 Citations2002TL Lau, Edward Tsang
The Guided Genetic Algorithm is a hybrid of genetic algorithm (GA) and meta-heuristic search algorithm, Guided Local Search (GLS), which builds on the framework and robustness of GA, and integrating GLS's conceptual simplicity and effectiveness to arrive at a flexible algorithm well meant for constraint optimization problems.
International Journal of Artificial Intelligence ToolsSolving the Processor Configuration Problems with a Mutation-Based Genetic Algorithm
17 Citations1997TL Lau, Edward Tsang
This paper presents a Genetic Algorithm (GA) approach to the Processor Configuration Problem that uses a mutation-based GA, a function that produces schemata by analyzing previous solutions, and an efficient data representation.
Journal of HeuristicsGuided Local Search for Final Placement in VLSI Design
12 Citations2003Oluf Faroe, David Pisinger +1 more
A new heuristic is presented for the general cell placement problem where the objective is to minimize total bounding box netlength and it is possible to focus the search on appropriate sub-neighbourhoods, thus reducing the time complexity considerably.
International Journal of Artificial Intelligence ToolsA FRAMEWORK FOR INTEGRATING ARTIFICIAL NEURAL NETWORKS AND LOGIC PROGRAMMING
11 Citations1995Jimmy H. M. Lee, Vincent Tam
This paper presents a general framework for integrating artificial neural networks and logic programming so as to provide an efficient and yet expressive programming environment for solving CSP’s, and proposes PROCLANN, a novel constraint logic programming language that retains the simple and elegant declarative semantics of constraint Logic programming.
A Cascadable VLSI Design for GENET
11 Citations1994Changjiang Wang, Edward Tsang
This paper presents a VLSI design for a competitive neural network model, known as GENET, for solving Constraint Satisfaction Problems (CSP), a mathematical abstraction of the problems in many AI application domains.
Empowerment Scheduling: A Multi-objective Optimization Approach Using Guided Local Search
10 Citations2011Abdullah Alsheddy
This thesis describes the development of a new efficient empowerment scheduling model, called EmS, for FWS, which is strongly linked to the management literature on empowerment from which the requirements are derived and which is competitive with state-of-the-art MOO metaheuristics.
Lecture notes in computer scienceApproximation algorithms for channel assignment in cellular radio networks
9 Citations1989Hans Ulrich Simon
This paper explores the possibility of finding optimal or nearly optimal channel assignments in polynomial time and relates this problem to ‘graph-coloring’ and, if the network is assumed as cellular, to ’packing in the plane’.
BT Technology JournaliSchedule — An Optimisation Tool-Kit Based on Heuristic Search to Solve BT Scheduling Problems
9 Citations2003Raphaël Dorne, Chris Voudouris +3 more
The aim of this paper is to present the iSchedule capabilities as well as to illustrate their use on a particular scheduling problem, the vehicle routing problem, which is of interest to BT in its field service operations.
Parsing natural language using guided local search
9 Citations2002Michael Daum, Wolfgang Menzel
An application of guided local search to the problem of natural language parsing is presented and the resulting algorithm is compared to competing techniques within the framework of weighted constraint dependency grammars.
Computer NetworksGuided local search as a network planning algorithm that incorporates uncertain traffic demands
8 Citations2007Gilberto Flores Lucio, Martin J. Reed +1 more
The results show that the GLS+FLS outperforms the GA and SA techniques in terms of both solution quality and optimisation speed but even more importantly GLS-FLS has significantly reduced parameterisation time.
P-GLS-II
7 Citations2011Nasser Tairan, Qingfu Zhang
A new framework is proposed to improve the performance as well as overcome the limitations in P-GLS, which applies two new different penalization strategies that increase favouring common features based on their occurrences in the agents' local optimal solutions during the search.
Lecture notes in computer scienceSelf-Guided Genetic Algorithm
7 Citations2008Shih-Hsin Chen, Pei‐Chann Chang +1 more
Self-Guided GA is proposed, which is one of the algorithms in the category of evolutionary algorithm based on probabilistic models (EAPM), and it could be a break-through in the branch of EAPM.
A Family of Stochastic Methods For Constraint Satisfaction and Optimisation
7 Citations2001Edward Tsang
A family of stochastic algorithms for constraint satisfaction and optimisation, developed with hardware implementation in mind, and applied to a non-trivial number of satisfiability and Optimisation problems and achieved world-class results is reported.
Semantics for using Stochastic Constraint Solvers in Constraint Logic Programming.
7 Citations1998Peter J. Stuckey, Vincent Tam
This paper proposes a number of models for integrating finitedomain stochastic constraint solvers into constraint logic programming systems to solve constraint-satisfaction problems efficiently, and describes an example system implemented using a modified neural network simulator, GENET, as a constraint solver.
Solving Vehicle Routing Using IOPT
6 Citations2007Raphaël Dorne, Patrick Mills +1 more
The overall conclusion of this work is the toolkit allows the user to maximize reuse of his code, significantly reduce his development time, focus his attention on the design rather than the coding, and exchange problem models or algorithms in a very easy and simple way using XML files within his community.
Ship Technology ResearchOptimization of Surface Utilization Using Heuristic Approaches
4 Citations2005Yves Langer, Maud Bay +6 more
Digital library of Zielona Gora (University of Zielona Góra)GUIDED LOCAL SEARCH FOR QUERY REFORMULATION USING WEIGHT PROPAGATION
4 Citations2006Issam A. R. Moghrabi
A new technique for query reformulation that assesses the relevance of retrieved documents using weight propagation is proposed, and the experimental results reveal the effectiveness of the new technique.
IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesObjective Function Adjustment Algorithm for Combinatorial Optimization Problems
3 Citations2006Hiroki Tamura
Simulation results based on some TSPLIB benchmark problems showed that the objective function adjustment algorithm could find better solutions than Local Search, Guided Local Search and Tabu Search.
OpenAIR@RGU (Robert Gordon University)Distributed guided local search for solving binary DisCSPs.
2 Citations2005Muhammed Basharu, Inés Arana +1 more
The Distributed Guided Local Search (Dist- GLS) algorithm for solving Distributed Constraint Satisfaction Problems is introduced, based on the centralised Guided local Search algorithm extended with additional heuristics in order to enhance its efficiency in distributed scenarios.
…