Abstract
Working on artificial intelligence, one of the tasks we can carry on is optimization of the possible solutions of a problem. Optimization problems appear. In optimization problems we search for the best solution, or one good enough, to a problem among a lot of alternatives. Problems we try to solve are usual in daily living. Every person constantly works out optimization problems, e.g. finding the quickest way from home to work taking into account traffic restrictions. Humans can find efficiently solutions to these problems because these are easy enough. Nevertheless, problems can be more complex, for example reducing fuel consumption of a fleet of plains. Computational algorithms are required to tackle this kind of problems. A first approach to solve them is using an exhaustive search. Theoretically, this method always finds the solution, but is not efficient as its execution time grows exponentially. In order to improve this method heuristics were proposed. Heuristics are intelligent techniques, methods or procedures that use expert knowledge to solve tasks; they try to obtain a high performance referring to solution quality and used resources. Metaheuristics, term first used by Fred Glover in 1986 (Glover, 1986), arise to improve heuristics, and can be defined as (Melián, Moreno & Moreno, 2003) ‘intelligent strategies for designing and improving very general heuristic procedures with a high performance’. Since Glover the field has been extensively developed. The current trend is designing new metaheuristics that improve the solution to given problems. However, another line, very interesting, is reuse existing metaheuristics in a coordinated system. In this article we present two different methods following this line.
TopBackground
Several studies have shown that heuristics and metaheuristics are successful tools for providing reasonably good solutions (excellent in some cases) using a moderate number of resources. A brief look at recent literature (Glover & Kochenberger, 2003), (Hart, Krasnogor & Smith, 2004), (Pardalos & Resende, 2002) reveals the wide variety of problems and methods which appear under the overall topic of heuristic optimization. Within this, obtaining strategies which cooperate in a parallel way is an interesting trend. The interest is on account of two reasons: larger problem instances may be solved, and robust tools, that offer high quality solutions despite variations in the characteristics of the instances, may be obtained.
There are different ways of obtaining this cooperation. One way are ant colony systems (Dorigo & Stützle, 2003) and swarm based methods (Eberhart & Kennedy, 2001) appear as one of the first cooperative mechanisms inspired by nature. Nevertheless, the cooperation principle they have presented to date is too rigid for a general purpose model (Crainic & Toulouse, 2003). Another way are parallel metaheuristics, where very interesting perspectives appear. This is the line we will follow.
There have been huge efforts to parallelize different metaheuristics. Thus we may find synchronic implementations of these methods where the information is shared at regular intervals, (Crainic, Toulouse & Gendreau, 1997) using Tabu Search and (Lee & Lee, 1992) using Simulated Annealing. More recently there have been multi-thread asynchronic cooperative implementations (Crainic, Gendreau, Hansen & Mladenovic, 2004) or multilevel cooperative searches (Baños, Gil, Ortega & Montoya, 2004) which, according to the reports in (Crainic & Toulouse, 2003) provide better results than the synchronic implementations.
However, it seems that a cooperative strategy based on a single metaheuristic does not cover all the possibilities and the use of strategies which combine different metaheuristics is recommended. The paper (Le Bouthillier & Crainic, 2005) is a good example. A whole new area of research opens up. Questions such as, ‘what will be the role of each metaheuristic?’ or ‘What cooperation mechanisms should be used?’ arise.
Within parallel metaheuristics, we will focus following the classification of (Crainic & Toulouse, 2003) on Multi-search metaheuristics, where several concurrent strategies search the solution space. Among them, we concentrate on those techniques, known as Cooperative multi-search metaheuristics, where each strategy exchanges information with the others during the execution.
Key Terms in this Chapter
Heuristic: A method or approach that tries to apply expert knowledge in the resolution of a problem with the aim of increasing the probability of solving it.
Metaheuristic: A high-level strategy for solving a very general class of computational problems by combining user given black-box procedures usually heuristics in a hopefully efficient way.
Blackboard: A shared repository of problems, partial solutions, suggestions, and contributed information. The blackboard can be seen as a dynamic “library” of contributions to the current problem that have been recently “published” by other knowledge sources
Parallel Metaheuristics: Metaheuristics in which different threads search concurrently the solution space. They appear naturally in develop of metaheuristics as a way of improving the acceleration factor in the search of solutions.
Knowledge Extraction/Discovery: The non-trivial process of identifying valid, novel, potentially useful and ultimately understandable patterns from large data collections. The overall process and discipline of extracting useful knowledge and includes data warehousing, data cleansing and data manipulation tasks right through to the interpretation and exploitation of results
Data Mining: The most characteristic stage of the Knowledge Extraction process, where the aim is to produce new useful knowledge by constructing a model from the data gathered for this purpose
Fuzzy Rules: Linguistic if-then constructions that have the general form “if A then B” where A and B are collections of propositions containing linguistic variables (A is called the premise and B is the consequence). The use of linguistic variables and fuzzy if-then rules exploits the tolerance for imprecision and uncertainty.
Optimization Problem: A computational problem whose object is to find the best from all feasible solutions.
Cooperative Multi-Search Metaheuristics: A parallelization strategy for metaheuristics in which parallelism is obtained from multiple concurrent explorations of the solution space and where metaheuristics exchange information during their execution in order to cooperate.
Problem Instance: A concrete representation of a problem with characteristics that distinguish it from the rest.