Вопрос 33: Алгоритм гармонии

Алгоритм использует простуюаналогию. Импровизируя вместе, музыканты стараются добиться оптимального состояния (звучания). Целевая функция при этом определяется эстетической оценкой качества музыки. Ее значение зависит от того, каккой набор звуков (компоненты решения) извлекают иполнители из своих инструментов.

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

Входные данные алгоритма:

• целевая функция f(x), x = $(x_1, x_2, ..., x_n)$
• вероятность использования решений из памяти cr
• вероятность выбора соседнего значения ar

Псевдокод алгоритма гармонии:

Память представляет собой набор векторов ($x^1, ..., x^s$), где $x^i = (x^i_{11}, ..., x^i_{n})$ – найденные решения. На каждой итерации создается одно новое решение, каждый из компонентов которого определяется следующим образом:

• с вероятностью, равной cr, он становится равным соответствующему компоненту случайного вектора из памяти;
• с вероятностью, равной 1 - cr, он выбирается случайным образом.

Далее, с вероятностью, равной ar, компонент изменяется на случайное значение из заданного интервала. Елси получившееся решение лучше, чем худшее решение в памяти, оно его заменяет, иначе алгоритм переходит к следующей итерации, либо завершается по достижению КОП.

Выбор и настройка параметров Мехрард Махвади с коллегами предложили изменять параметры алгоритма в процессе его выполнения. В частности, в их модификации вероятность выбора соседнего значения ar линейно возрастает:

При этом размемр диапазона, в пределах которго может измениться решение, экспоненциально уменьшается:

Standard Deviation пришел к выводу, что оптимальным значением для ẟ является среднеквадратичное отклонение текущего решения. При этом вероятность использования решения из cr следуюе устнаваливать близкой к едининце (0.99).