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

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

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

Предисловие

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

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

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

Стратегия

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

Сама импровизация заключается в следующем:

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, одного из моих любимых авторов и ученых.

Послесловие

Хочу завести добрую традицию — определять голосованием тему будущего поста. Так что просьба ко всем неравнодушным проголосовать за тему следующего поста.