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

Предисловие

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

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

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

Стратегия

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

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

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

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

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

Послесловие

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