Предисловие
Как я уже писал ранее: есть желание освещать эвристические методы (как достаточно распространенные, так и неизвестные). Данный пост предназначался для того, чтобы понять, будет ли данная тема вам интересна. Что ж, будем надеяться, что я не ошибся. Первый метод, с которым хотелось бы познакомить читателей — метод гармонического поиска (HS).
Историческая справка
Итак, с чего же все началось? А началось все не так давно. В 2001 году Geem разработал и предложил свой алгоритм гармонического поиска (Harmony Search, или HS). Некоторые авторы заявляют, что навеян данный алгоритм был игрой джаз-музыкантов, другие говорят, что в основе лежит просто процесс создания приятной мелодии. Сути это не меняет. Важно лишь то, что опытный музыкант может достаточно быстро как сыграться с другими музыкантами, так и сымпровизировать что-нибудь прекрасное. Это и легло в основу алгоритма.
Стратегия
Классический HS оперирует понятием гармонической памяти (по аналогии с родительским пулом генетических алгоритмов). Здесь хранятся вектора, представляющие приближенные решения задачи оптимизации. Изначально они генерируются случайным образом в области, которая исследуется на наличие максимума или минимума (в зависимости от того, что вам нужно). Размер этой памяти, естественно, ограничен. Далее начинается магия импровизация (итеративная часть алгоритма).
Сама импровизация заключается в следующем:
- генерируется пробный вектор (либо абсолютно случайно, либо с использованием векторов из памяти),
- пробный вектор модифицируется (происходит небольшой сдвиг в компонентах, если пробный вектор был создан с помощью памяти),
- модифицированный пробный вектор заменяет худший из имеющихся в памяти.
Использованные источники
- Zong Woo Geem, Music-Inspired Harmony Search Algorithm (издательство Springer),
- Википедия,
- Статья под авторством Chukiat Worasucheep (есть ссылки на вариации HS),
- Статья Xin-She Yang, одного из моих любимых авторов и ученых.
Послесловие
Хочу завести добрую традицию — определять голосованием тему будущего поста. Так что просьба ко всем неравнодушным проголосовать, а так же указать, чего не хватило.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends:
- Massacres That Matter - Part 1 - 'Responsibility To Protect' In Egypt, Libya And Syria
- Massacres That Matter - Part 2 - The Media Response On Egypt, Libya And Syria
- National demonstration: No attack on Syria - Saturday 31 August, 12 noon, Temple Place, London, UK
Комментариев нет:
Отправить комментарий