Metaheuristic

These are properties that characterize most metaheuristics: or combinatorial optimization and then generalized later in some cases. • They can draw on domain-specific knowledge in the form of heuristics that are controlled by a higher-level strategy of the metaheuristic. • They can contain mechanisms that prevent them from getting stuck in certain areas of the search space. • Modern metaheuristics often use the search history to control the search. == Classification ==

of the different classifications of metaheuristics There are a wide variety of metaheuristics The following list is therefore to be understood as an example. Local search vs. global search One approach is to characterize the type of search strategy. and bacterial foraging algorithm. Single-solution vs. population-based Another classification dimension is single solution vs population-based searches. particle swarm optimization, The latter is particularly useful if the computational effort for the evaluation is considerably greater than that for the generation of descendants. This is the case in many practical applications, especially in simulation-based calculations of solution quality. Nature-inspired and metaphor-based metaheuristics A very active area of research is the design of nature-inspired metaheuristics. Many recent metaheuristics, especially evolutionary computation-based algorithms, are inspired by natural systems. Nature acts as a source of concepts, mechanisms and principles for designing of artificial computing systems to deal with complex computational problems. Such metaheuristics include simulated annealing, evolutionary algorithms, ant colony optimization and particle swarm optimization. A large number of more recent metaphor-inspired metaheuristics have started to attract criticism in the research community for hiding their lack of novelty behind an elaborate metaphor. As a result, a number of renowned scientists of the field have proposed a research agenda for the standardization of metaheuristics in order to make them more comparable, among other things. Another consequence is that the publication guidelines of a number of scientific journals have been adapted accordingly. == Applications ==

Most metaheuristics are search methods and when using them, the evaluation function should be subject to greater demands than a mathematical optimization. Not only does the desired target state have to be formulated, but the evaluation should also reward improvements to a solution on the way to the target in order to support and accelerate the search process. The fitness functions of evolutionary or memetic algorithms can serve as an example. Metaheuristics are used for all types of optimization problems, ranging from continuous through mixed integer problems to combinatorial optimization or combinations thereof. In combinatorial optimization, an optimal solution is sought over a discrete search-space. An example problem is the travelling salesman problem where the search-space of candidate solutions grows faster than exponentially as the size of the problem increases, which makes an exhaustive search for the optimal solution infeasible. Additionally, multidimensional combinatorial problems, including most design problems in engineering such as form-finding and behavior-finding, suffer from the curse of dimensionality, which also makes them infeasible for exhaustive search or analytical methods. Metaheuristics are also frequently applied to scheduling problems. A typical representative of this combinatorial task class is job shop scheduling, which involves assigning the work steps of jobs to processing stations in such a way that all jobs are completed on time and altogether in the shortest possible time. In practice, restrictions often have to be observed, e.g. by limiting the permissible sequence of work steps of a job through predefined workflows and/or with regard to resource utilisation, e.g. in the form of smoothing the energy demand. Popular metaheuristics for combinatorial problems include genetic algorithms by Holland et al., or various engineering tasks. An example of the mixture of combinatorial and continuous optimization is the planning of favourable motion paths for industrial robots. == Metaheuristic Optimization Frameworks ==

A MOF can be defined as ‘‘a set of software tools that provide a correct and reusable implementation of a set of metaheuristics, and the basic mechanisms to accelerate the implementation of its partner subordinate heuristics (possibly including solution encodings and technique-specific operators), which are necessary to solve a particular problem instance using techniques provided’’. There are many candidate optimization tools which can be considered as a MOF of varying feature. The following list of 33 MOFs is compared and evaluated in detail in: == Contributions ==

Many different metaheuristics are in existence and new variants are continually being proposed. Some of the most significant contributions to the field are: • 1952: Robbins and Monro work on stochastic optimization methods. and Dueck and Scheuer, independently proposed a deterministic update rule for simulated annealing which accelerated the search. This led to the threshold accepting metaheuristic. • 1992: Dorigo introduces ant colony optimization in his PhD thesis. • 1995: Wolpert and Macready prove the no free lunch theorems. == See also ==