Оңтайландыру әдістері: Метаэвристикалар

Optimization technique
In computer science and mathematical optimization, a metaheuristic is a higher level procedure or heuristic designed to find, generate, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. suggested that it was Fred Glover who coined the word metaheuristics. Most literature on metaheuristics is experimental in nature, describing empirical results based on computer experiments with the algorithms. But some formal theoretical results are also available, often on convergence and the possibility of finding the global optimum.

Another classification dimension is single solution vs population based searches. particle swarm optimization,

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.

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’’. 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.