валеева. Решение на лучшее в специально определенной окрестности

• Название: Решение на лучшее в специально определенной окрестности
• Дата: 25.02.2020
• Размер: 3.15 Mb.
• Имя файла: валеева.docx
• Тип: Решение; #109780
• страница: 16 из 19

9.2 Метаэвристики и гиперэвристики

Метаэвристика (от греческого «эврика» - «найти» и «мета» - «выше, на более высоком уровне») - это разновидность эвристического алгоритма.
В литературе не дается строгого определения этому новому типу алгоритма, а лишь перечисляются основные свойства, характеризующие метаэвристики:

• 
  являются недетерминированными;
  
• 
  содержат процедуры, позволяющие выбраться из локального оптимума;
  
• 
  допускают абстрактный уровень описания;
  
• 
  не являются проблемно-ориентированными.
  

Известны следующие метаэвристики:

• 
  алгоритм оптимизации муравьиной колонии (AntColonyOptimization, ACO);
  
• 
  эволюционный алгоритм (Evolutionary Computation, EC)
  
• 
  генетический алгоритм (Genetic Algorithms, GA);
  
• 
  итерационный локальный поиск (Iterative Local Search, ILS);
  
• 
  имитация отжига (Simulated Annealing, SA);
  
• 
  поиск с запретами (TabuSearch, TS);
  
• 
  поиск с переменной окрестностью (VariableNeighborhoodSearch, VNS);
  
• 
  вероятностный жадный алгоритм (GRASP);
  
• 
  направленный локальный поиск (GuidedLocalSearch, GLS);
  
• 
  нейронные сети (Neural Networks).
  

Основные характеристики метаэвристик

(1) исследования проводятся в областях пространства поиска с более качественными решениями (интенсификация поиска);

(2) поиск эффективных решений ведется в еще не исследованных областях пространства поиска (диверсификация поиска), когда возникает такая необходимость (не происходит улучшения целевой функции).
Замечание. Известно, что некоторые метаэвристики, в частности GA и SA, используют общую математическую конструкцию конечных цепей Маркова.

Это свойство гарантирует сходимость по вероятности наилучшего найденного решения к оптимальному решению задачи.