Comparative electiveness of metaheuristic methods

Abstract

The essence of metaheuristic methods and conditions of their application are considered, in particular, limited amount of knowledge and availability of some candidate for optimality. The formal statement of the traveling salesman problem and its solution are presented with 4 algorithms: genetic, annealing, Lin-Kernigan and the method of jumping frogs. The advantages and disadvantages of the annealing algorithm are analyzed. A parallel is drawn between the annealing algorithm and the gradient methods. The set tasks of the salesman in the parameters of the genetic algorithm. The principles of operation of the jumping frog method and the Lin-Kernigan algorithm are given. To perform the experiment, a database of random data was generated that formed a 1000 × 1000 dimension problem with a known exact solution. For the conclusions on the effectiveness of the methods, the rate of convergence of the task was estimated with the maximum approximation to the global extremum and the standard deviation from the exact solution. The genetic algorithm was found to perform best under the given conditions. The further application of the jumping frog algorithm for optimization problems, implemented with a large number of iterations, is promising. One of the ways of using the jumping frog algorithm is the task of placing production.

Keywords

• дискретна оптимiзацiя
• метаевристика
• генетичний алгоритм
• алгоритм стрибаючих жаб
• метод вiдпалу
• алгоритм лiн-кернiгана