Метаэвристические алгоритмы для задач комбинаторной оптимизации

Авторы: 
Журнал: 
Страница: 
56
УДК: 
519.658
В настоящей работе сделан краткий обзор основных метаэвристических алгоритмов для задач комбинаторной оптимизации. Метаэвристики — это общие эвристики, позволяющие находить близкие к оптимальным решения различных задач оптимизации за приемлемое время. Метаэвристики пытаются объединить основные эвристические методы в рамках алгоритмических схем более высокого уровня, направленных на эффективное изучение пространства поиска. Метаэвристики включают две категории: метаэвристики локального поиска и эволюционные алгоритмы.
info_eng: 
We survey metaheuristic algorithms that perform directed random searches of possible solutions of combinatorial optimization problems, optimal or near optimal, until a particular termination condition is met or after a predefined number of iterations. Metaheuristics combine basic heuristic methods in higher level frameworks aimed at efficiently and effectively exploring a search space. Metaheuristics fall in two categories: local search metaheuristics and evolutionary algorithms. In this paper, we describe the major solution methods: Local Search Metaheuristics (Simulated Annealing, Tabu Search, Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search) and Evolutionary Algorithms (Genetic Algorithms, Ant Colonies Optimization).