Особенности алгоритма поиска гармонии (HS)

Поиск гармонии Harmony Search (HS) — это метаэвристический алгоритм оптимизации [Geem, 2009], основанный на подражании процедуре импровизации музыканта. В ходе процедуры исполнения музыкального произведения каждый музыкант (= переменная возможного решения) берет (= генерирует) ноту (= значение) для нахождения наилучшего звучания с целью достижения определенной гармонии (= глобального оптимума). Основная цель сочинения или исполнения музыкального произведения — достижение гармонии, при которой отдельные звуки воспринимаются как единое целое.

Таким образом, реализация процедуры достижения гармонии в музыке аналогична поиску оптимума в процессе оптимизации. Другими словами, процесс импровизации музыканта соответствует процедуре поиска лучшего решения. С одной стороны, идеальная гармония, как указывается в [Geem, 2009], определяется стандартами звуковой эстетики: музыкант всегда старается выполнить некоторый отрывок музыкального произведения в соответствии со своим пониманием идеальной гармонии. С другой стороны, оптимальное решение некоторой проблемы должно являться наилучшим с учётом заданных целей и ограничений. Оба процесса: и работа музыканта, и решение некоторой оптимизационной проблемы имеют много общего: подразумевают нахождение наилучшего значения или оптимума.

Подобные сходства между двумя процессами были использованы для разработки нового алгоритма. Поиск гармонии можно рассматривать как успешный пример преобразования качественного процесса импровизации (на основе некоторых случайных возмущений) в количественный процесс оптимизации по некоторым идеализированным правилам [Geem, 2009].

Алгоритм поиска гармонии имеет некоторые преимущества по сравнению с известными алгоритмами оптимизации, основанными на использовании, например, градиентного спуска:

HS не требует сложных вычислений;

HS не требует настройки начальных значений параметров, используемых в процедуре оптимизации, что позволяет выходить из локального экстремума;

HS может работать как с дискретными, так и с непрерывными параметрами, в то время как градиентные методы работают только с непрерывными переменными.

Алгоритм поиска гармонии сводится к выполнению следующих шагов [Geem, 2009]:

Инициализация памяти гармоний: взять k случайных векторов .

Создание нового вектора X': для каждой компоненты этого вектора:

с вероятностью взять элемент из памяти гармоний: ;

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

Пошаговая настройка: только для компоненты, которая выбрана из памяти гармоний:

с вероятностью изменить на число, задаваемое следующим образом:

для дискретных переменных, или для непрерывных переменных с вероятностью ничего не делать.

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

Повторить шаги, начиная со 2-го, заданное число раз.

Оптимальное решение — это лучший вектор, полученный в результате работы алгоритма.

Параметры алгоритма:

• · k— размер памяти, обычно берётся в пределах от 1 до 50.
• — частота выбора из памяти. Типичные значения от 0.7 до 0.99;
• ·, частота пошаговой настройки. Типичные значения от 0.1 до 0.5;
• · д — расстояние между двумя соседними значениями для дискретного набора данных;
• · bw — величина шага для изменения непрерывных переменных в процессе оптимизации.

На основе алгоритма HS разработан комбинированный генетический алгоритм, в котором выбор различных генетических операторов при выполнении процедуры оптимизации зависит в различные моменты времени от знака приращения функции фитнесса. Этот алгоритм может быть использован для повышения эффективности обучения нейронных сетей (НС) в смысле уменьшения ошибки обучения или сложности топологии НС [Комарцова и др., 2004].