Hybrids of Constructive Metaheuristics and Constraint Programming: A Case Study with ACO
A long-standing problem in combinatorial optimization with metaheuristics has been how to handle hard constraints effectively. Integrating metaheuristic methods with Constraint Programming (CP), an exact technique for solving hard constraints, promises a
- PDF / 599,510 Bytes
- 33 Pages / 595.276 x 841.89 pts (A4) Page_size
- 78 Downloads / 169 Views
Introduction Evolutionary metaheuristics are widely used for combinatorial optimization and achieve a competitive performance in many practically relevant applications. However, real-world problems are often subject to hard constraints and handling these with evolutionary metaheuristics is generally not easy. Constraint handling in evolutionary methods has thus been the subject of extensive research. In this chapter we will discuss a new approach to handling hard constraints in metaheuristics by hybridizing these with Constraint Programming, an exact technique for solving hard constraints. From a conceptual perspective our hybridization is important for two reasons: (1) It introduces declarative problem models into metaheuristics. This opens a way to fine-tune the function of the metaheuristics for a new problem domain in a systematic way. Such fine-tuning normally has to be performed in an ad-hoc fashion by programming problem-specific repair methods, new neighbourhood functions etc. The hybrid approach allows us to adapt some of this functionality automatically and systematically by re-defining the declarative problem model. (2) It introduces automatic learning of search strategies B. Meyer: Hybrids of Constructive Metaheuristics and Constraint Programming: A Case Study with ACO, Studies in Computational Intelligence (SCI) 114, 151–183 (2008) c Springer-Verlag Berlin Heidelberg 2008 www.springerlink.com
152
Bernd Meyer
into CP. To cope with very large feasible spaces, the CP method requires us to design and implement problem-specific search strategies. In realistic cases, this task represents a significant development effort and requires considerable CP programming expertise. This has recently prompted leading CP researchers to declare ease-of-use as the next big challenge for CP systems [47, 56]. A hybridization of CP with metaheuristics is certainly not the “magic bullet” for the ease-of-use problem, but it can help to automate the problem of finding a search strategy to some degree. 1.1 Constraint Handling in Metaheuristics Traditionally, three types of approaches have been used for constraint handling in metaheuristics: penalty-based relaxation techniques, multi-phase methods, and repair techniques [14]. Relaxation techniques allow the search to use infeasible solutions and simply modify the objective function by a penalty based on the amount of constraint violation. Multi-phase methods attempt to split the search into phases that try to find feasible subspaces and phases that try to optimize feasible solutions (Section 3.4 will discuss this in more detail). Repair techniques attempt to explicitly modify infeasible solutions to make them feasible. Arguably, penalty-based relaxation is the most widely used way to handle constraints in Evolutionary Algorithms. For this the objective function f (x) that is to be minimized is modified into a Lagrangian (an auxiliary objective function) fˆ(x) = f (x) + λ · g(x) where g(x) is a positive function measuring the amount of constraint violation and the Lagrange multipliers λ
Data Loading...
