Guided local search is a metaheuristic search method. A meta-heuristic method is a method that sits on top of a local search algorithm to change its behavior.
Guided local search builds up penalties during a search. It uses penalties to help local search algorithms escape from local minima and plateaus. When the given local search algorithm settles in a local optimum, GLS modifies the objective function using a specific scheme (explained below). Then the local search will operate using an augmented objective function, which is designed to bring the search out of the local optimum. The key is in the way that the objective function is modified.
The method in its current form was developed by Dr Christos Voudouris and detailed in his PhD Thesis [1]. GLS was inspired by and extended GENET, a neural network architecture for solving Constraint Satisfaction Problems, which was developed by Chang Wang, Edward Tsang and Andrew Davenport. Both GLS's and GENET's mechanism for escaping from local minima resembles reinforcement learning.
Overview
Solution features
To apply GLS, solution features must be defined for the given problem. Solution features are defined to distinguish between solutions with different characteristics, so that regions of similarity around local optima can be recognized and avoided. The choice of solution features depends on the type of problem, and also to a certain extent on the local search algorithm. For each feature a cost function is defined.
Each feature is also associated with a penalty (initially set to 0) to record the number of occurrences of the feature in local minima.
The features and costs often come directly from the objective function. For example, in the traveling salesman problem, “whether the tour goes directly from city X to city Y” can be defined to be a feature. The distance between X and Y can be defined to be the cost. In the SAT and weighted MAX-SAT problems, the features can be “whether clause C satisfied by the current assignments”.
At the implementation level, we define for each feature an Indicator Function indicating whether the feature is present in the current solution or not. is 1 when solution exhibits property , 0 otherwise.
Selective penalty modifications
GLS computes the utility of penalising each feature. When the local search algorithm returns a local minimum x, GLS penalizes all those features (through increments to the penalty of the features) present in that solution which have maximum utility, , as defined below.
The idea is to penalise features that have high costs, although the utility of doing so decreases as the feature is penalised more and more often.
Searching through an augmented cost function
GLS uses an augmented cost function (defined below), to allow it to guide the local search algorithm out of the local minimum, through penalising features present in that local minimum. The idea is to make the local minimum more costly than the surrounding search space, where these features are not present.
The parameter λ may be used to alter the intensification of the search for solutions. A higher value for λ will result in a more diverse search, where plateaus and basins are searched more coarsely; a low value will result in a more intensive search for the solution, where the plateaus and basins in the search landscape are searched in finer detail. The coefficient is used to make the penalty part of the objective function balanced relative to changes in the objective function and is problem specific. A simple heuristic for setting is simply to record the average change in objective function up until the first local minimum, and then set to this value divided by the number of GLS features in the problem instance.
Extensions of guided local search
Mills (2002) has described an extended guided local search (EGLS) which utilises random moves and an aspiration criterion designed specifically for penalty based schemes. The resulting algorithm improved the robustness of GLS over a range of parameter settings, particularly in the case of the quadratic assignment problem. A general version of the GLS algorithm, using a min-conflicts based hill climber (Minton et al. 1992) and based partly on GENET for constraint satisfaction and optimisation, has also been implemented in the Computer-Aided Constraint Programming project.
Tabu search is a class of search methods which can be instantiated to specific methods. GLS can be seen as a special case of Tabu search.
By sitting GLS on top of genetic algorithm, Tung-leng Lau introduced the guided genetic programming (GGA) algorithm. It was successfully applied to the general assignment problem (in scheduling), processors configuration problem (in electronic design) and a set of radio-link frequency assignment problems (an abstracted military application).
Choi et al. cast GENET as a Lagrangian search.
Bibliography
Alsheddy, A., Empowerment scheduling: a multi-objective optimization approach using Guided Local Search, PhD Thesis, School of Computer Science and Electronic Engineering, University of Essex, 2011
Choi, K.M.F., Lee, J.H.M. & Stuckey, P.J., A Lagrangian Resconstruction of GENET, Artificial Intelligence, 2000, 123(1-2), 1-39
Davenport A., Tsang E.P.K., Kangmin Zhu & C J Wang, GENET: A connectionist architecture for solving constraint satisfaction problems by iterative improvement, Proc., AAAI, 1994, p.325-330
Lau, T.L. & Tsang, E.P.K., Solving the processor configuration problem with a mutation-based genetic algorithm, International Journal on Artificial Intelligence Tools (IJAIT), World Scientific, Vol.6, No.4, December 1997, 567-585
Lau, T.L. & Tsang, E.P.K., Guided genetic algorithm and its application to radio link frequency assignment problems, Constraints, Vol.6, No.4, 2001, 373-398
Lau, T.L. & Tsang, E.P.K., The guided genetic algorithm and its application to the general assignment problems, IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI'98), Taiwan, November 1998
Mills, P. & Tsang, E.P.K., Guided local search for solving SAT and weighted MAX-SAT problems, Journal of Automated Reasoning, Special Issue on Satisfiability Problems, Kluwer, Vol.24, 2000, 205-223
Mills, P. & Tsang, E.P.K. & Ford, J., Applying an Extended Guided Local Search on the Quadratic Assignment Problem, Annals of Operations Research, Kluwer Academic Publishers, Vol.118, 2003, 121-135
Minton, S., Johnston, M., Philips, A.B. & Laird, P., Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence (Special Volume on Constraint Based Reasoning), Vol.58, Nos.1-3 1992, 161-205
Tsang, E.P.K. & Voudouris, C., Fast local search and guided local search and their application to British Telecom's workforce scheduling problem, Operations Research Letters, Elsevier Science Publishers, Amsterdam, Vol.20, No.3, March 1997, 119-127
Voudouris, C., Tsang, E.P.K., Partial Constraint Satisfaction Problems and Guided Local Search, Proceedings of the Second International Conference on the Practical Application of Constraint Technology (PACT'96), pp 337-356, London, UK, 1996
Voudouris, C., Guided Local Search—An illustrative example in function optimisation, BT Technology Journal, Vol.16, No.3, July 1998, 46-50
Voudouris, C., Tsang, E., Solving the Radio Link Frequency Assignment Problems using Guided Local Search, In Proceedings of NATO symposium on Frequency Assignment, Sharing and Conservation in Systems (AEROSPACE), AGARD, paper No. 14, Aalborg, Denmark, 5-7 October 1998
Voudouris, C. & Tsang, E.P.K., Guided local search joins the elite in discrete optimisation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 57, 2001, 29-39
Voudouris, C. & Tsang, E.P.K., Guided local search, in F. Glover (ed.), Handbook of metaheuristics, Kluwer, 2003, 185-218
Voudouris, C., Tsang, E.P.K. & Alsheddy, A., Guided local search, Chapter 11, in M. Gendreau & J-Y Potvin (ed.), Handbook of Metaheuristics, Springer, 2010, 321-361
Voudouris, C., Tsang, E., Alsheddy, A., Guided Local Search, Wiley Encyclopedia of Operations Research and Management Science, Wiley, 2010
Voudouris, C., Tsang, E., Alsheddy, A., Effective Application of Guided Local Search, Wiley Encyclopedia of Operations Research and Management Science, Wiley, 2010
↑ Voudouris, C, Guided local search for combinatorial optimisation problems, PhD Thesis, Department of Computer Science, University of Essex, Colchester, UK, July, 1997
Related Research Articles
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.
Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem-specific branching heuristic.
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.
Column generation or delayed column generation is an efficient algorithm for solving large linear programs.
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region.
In mathematical optimization, the active-set method is an algorithm used to identify the active constraints in a set of inequality constraints. The active constraints are then expressed as equality constraints, thereby transforming an inequality-constrained problem into a simpler equality-constrained subproblem.
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.
Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch.
In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem. Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal. This fact is called weak duality.
In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency.
In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name local search.
In mathematical optimization, constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.
Distributed constraint optimization is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized.
Penalty methods are a certain class of algorithms for solving constrained optimization problems.
In mathematical optimization and computer science, a feasible region,feasible set, or solution space is the set of all possible points of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.
Multi-objective optimization or Pareto optimization is an area of multiple-criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective is a type of vector optimization that has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives.
Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
