Metaheuristic

A metaheuristic (composed of the preposition and meta heuristics from the verb εὑρίσκειν ( heuriskein ) ) calls the computer science an algorithm for the approximate solution of optimization problems. In contrast to the specific problem heuristics can be applied only to a specific optimization problem metaheuristics define an abstract sequence of steps, which (in theory) can be applied to any problems. However, the individual steps must be implemented to specific problems again.

Metaheuristics can be used for such problems, for which no other efficient solution algorithm is known, eg severe combinatorial optimization problems. In general, there is no guarantee that a metaheuristic finds an optimal solution. In principle, all these methods can compute good solutions, but also arbitrarily bad compared to an optimal solution be. In general, the success and duration depend metaheuristischer method crucially on the definition and implementation of each step. There is no metaheuristic, which is better for any problems as all the other ( no- free - lunch theorems ).

Examples of metaheuristics

Many metaheuristics based on the principle of local search:

The exact definition of each step depends on the problem under investigation from ( for examples see local search ), and the solution thus found is not globally optimal in general. Through Tabu list prevents solutions already found to be inspected more often. To avoid getting stuck in local optima as far as possible, you can, for example,

• Several attempts to start ( climber algorithm)
• Between only larger, later only minor degradations accept ( Simulated cooling ( engl. simulated annealing) and deluge algorithm)
• Combine several solutions already found a new solution or solutions randomly change ( evolutionary algorithms).

A whole class of other nature-inspired method uses swarm intelligence. In so-called Ant Colony Optimization ( engl. Ant Colony Optimization) is this the natural behavior of ants modeled on the route search, whereas particle swarm optimization, the behavior of birds or schools of fish is taken as a model. To what extent is this based on the nature of rapidly finding good solutions of benefit is controversial. Even with artificial neural networks and similar statistical methods such as Self-Organizing Maps, there have been attempts.

• Algorithm