16 September 2013

Гармонический поиск. Harmony Search

AlgorithmsMathematics

Предпредисловие


По обратной связи было решено довести до ума данный пост, так что надеюсь, что теперь его чтение станет более приятным и информативным занятием. Постарался по максимуму учесть все пожелания.

Предисловие


Как я уже писал ранее: есть желание освещать эвристические методы (как достаточно распространенные, так и неизвестные). Данный пост предназначался для того, чтобы понять, будет ли данная тема вам интересна. Что ж, будем надеяться, что я не ошибся. Первый метод, с которым хотелось бы познакомить читателей — метод гармонического поиска (HS).
image

Историческая справка


Итак, с чего же все началось? А началось все не так давно. В 2001 году Geem разработал и предложил свой алгоритм гармонического поиска (Harmony Search, или HS). Некоторые авторы заявляют, что навеян данный алгоритм был игрой джаз-музыкантов, другие говорят, что в основе лежит просто процесс создания приятной мелодии. Сути это не меняет. Важно лишь то, что опытный музыкант может достаточно быстро как сыграться с другими музыкантами, так и сымпровизировать что-нибудь прекрасное. Это и легло в основу алгоритма.

Стратегия


Классический HS оперирует понятием гармонической памяти (по аналогии с родительским пулом генетических алгоритмов). Здесь хранятся вектора, представляющие приближенные решения задачи оптимизации. Изначально они генерируются случайным образом в области, которая исследуется на наличие максимума или минимума (в зависимости от того, что вам нужно). Размер этой памяти, естественно, ограничен. Далее начинается магия импровизация (итеративная часть алгоритма).

Сама импровизация заключается в следующем:
  1. генерируется пробный вектор (либо абсолютно случайно, либо с использованием векторов из памяти),
  2. пробный вектор модифицируется (происходит небольшой сдвиг в компонентах, если пробный вектор был создан с помощью памяти),
  3. модифицированный пробный вектор заменяет худший из имеющихся в памяти.

Для тех, кого интересует более подробное описание алгоритма

Алгоритм


План самого алгоритма был вероломно взят из [3]. Добавим немного формул, чтобы все это приняло более осмысленный вид. Итак, имеем некоторую функцию image, которую необходимо минимизировать, и область поиска (для простоты предполагаем ее многомерным прямоугольным параллелепипедом), в которой точка минимума, а точнее ее приближение, и будет искаться. Следующим шагом генерируем в нашей области поиска начальные гармоники (случайным образом). Величина задается пользователем, и, как несложно догадаться, указывает на количество гармоник, которые могут храниться в памяти. Кроме этого, пользователь еще должен задать — вероятность выбора из гармоник в памяти, — вероятность модификации и — величину той самой модификации. Теперь, когда все приготовления сделаны, с чистой совестью можем приступать творить музыку минимизировать функцию. Итеративная часть продолжается до выполнения критерия остановки алгоритма. Им может быть либо ограничение по количеству итераций, либо количество прогонов без обновления памяти гармоник, либо близость добавляемой гармоники в смысле той или иной метрики. Все зависит от вашего желания. В ходе итеративной части происходит следующее:
  1. Создаем нулевую новую гармонику .
  2. Далее для каждой компоненты гармоники выполняем следующее: генерируем случайное число , равномерно распределенное от нуля до единицы. Если меньше, чем , то в текущую компоненту записываем соответствующую компоненту из наугад выбранной гармоники из памяти. В противном случае компонента генерируется случайно, с учетом принадлежности соответствующей компоненте области поиска . Если компонента была сгенерирована с использованием памяти, то, возможно, она подлежит модификации. Для этого опять генерируется случайное число , равномерно распределенное от нуля до единицы. Если меньше, чем , то компонента меняется на величину , где — случайная величина, равномерно распределенная от до .
  3. Если , то заменяет (происходит обновление памяти).


Pros and Cons


Плюсы:
  • простота (как реализации, так и понимания). Действительно, алгоритм не нагроможден операциями (по сути лишь генерация случайных чисел и модификация вектора);
  • достаточно малое количество настраиваемых параметров и наличие рекомендаций по выбору параметров;
  • является методом нулевого порядка (отпадает необходимость численного дифференцирования, а, следовательно, все сопутствующие этому процессу сложности);
  • метод легко и удобно встраивается в другие методы (например, в меметические алгоритмы, или в качестве дополнительного контура генетического алгоритма).

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

Использованные источники


  1. Zong Woo Geem, Music-Inspired Harmony Search Algorithm (издательство Springer),
  2. Википедия,
  3. Статья под авторством Chukiat Worasucheep (есть ссылки на вариации HS),
  4. Статья Xin-She Yang, одного из моих любимых авторов и ученых.

Послесловие


Хочу завести добрую традицию — определять голосованием тему будущего поста. Так что просьба ко всем неравнодушным проголосовать за тему следующего поста.
Only registered users can participate in poll. Log in, please.
Какой алгоритм описать в следующем посте?
32% Grenade Explosion Method 8
8% Fireworks Algorithm 2
60% Gravitational Search 15
25 users voted. 11 users abstained.
Tags:эвристические алгоритмыоптимизациягармонический поискharmony search
Hubs: Algorithms Mathematics
+3
5.7k 8
Comments 6
Popular right now
Основы HTML и CSS
November 30, 2020FreeНетология
Профессия iOS-разработчик
November 30, 202075,000 ₽SkillFactory
SMM-менеджер
November 30, 202059,998 ₽GeekBrains
Frontend-разработчик с нуля
November 30, 202077,940 ₽Нетология