44. Меметический алгоритм (Антон)

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

Алгоритм

Он моделирует распространение мемов, вообще похож на генетический, только вместо биологической эволюции – культурная

Этапы:

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

2 – локальный поиск. Каждая особь популяции ищет локальный минимум своей окрестности

3 – взаимодействие особей. Два способа: кооперация и соревнование. Кооперация – обмен накопленной информацией, соревнование – селекция.

4 – если не достигнут критерий окончания поиска, то опять все по новой, на шаг 1. Иначе – выбор лучшего решения из популяции

Для локального поиска можно использовать имитацию отжига(вычислительно сложно), алгоритм подъема

Кооперация – аналог двухточечного скрещивания в га. Выбирается диапазон в пределах длины решения и соответствующие сегменты двух решений меняются местами . в результате две новых особи.

Критерий окончания – число итераций, оценка улучшения результата, оценка разнообразия особей(для случия вырождения популяции)

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

Меметические методы обычно проблемно-специфичны, они широко используют всю имеющуюся информацию о решаемой задаче.

Используются в распознавании образов, в обучении нейронных сетей, в экспертных системах и т.д.

Они типа развиваются, создаются более адаптивные (учитывают предысторию) версии алгоритма.

45. Алгоритм поиска гармонии (Серега)

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

- целевая функция

- вероятность использования решений из памяти cr;

- вероятность выбора соседнего значения ar.

Рассмотрим псевдокод алгоритма гармонии.

1. Генерация начального состояния памяти .

2. Инициализация нового решения

3. Для каждого элемента x_j’ нового решения:

3.1. Если x_j’ rand(0...1)<cr, то x’_j = x_j^rand(0..s) , иначе х_j' = rand(search_area).

3.2. Если rand(0...1)<ar, то

4. Если (из памяти), то заменить на в памяти.

5. Если достигнут критерий окончания поиска, то вернуть (из памяти) иначе перейти на шаг 2.

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

• с вероятностью, равной cr (вероятность использования решения из памяти), он становится равен соответствующему компоненту случайного вектора из памяти;

• с вероятностью, равной 1 - cr, он выбирается случайным образом. Далее, с вероятностью, равной ar (вероятность выбора соседнего значения), компонент изменяется на случайное значение из заданного интервала. Если получившееся решение лучше, чем худшее решение в памяти, оно его заменяет, иначе алгоритм либо переходит к следующей итерации, либо завершается при достижении критерия окончания поиска.

Выбор и настройка параметров. В оригинальном варианте алгоритма эти значения являются

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

Модификации алгоритма.

Improved Harmony Search. В 2007 г. Мехрдад Махдави (Mehrdad Mahdavi) с коллегами опубликовали статью, в которой предложили изменять параметры алгоритма в процессе его выполнения. В частности, в их модификации вероятность выбора соседнего значения ar линейно возрастает:

где к - номер текущей итерации, К - общее число итераций.

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

Такая подстройка параметров позволяет контролировать скорость сходимости алгоритма. Вначале, при малом значении параметра ar и большом , алгоритм экстенсивно исследует область поиска. Это ускоряет локализацию областей, содержащих качественные решения, и не позволяет алгоритму «застрять» в субоптимальном решении. На поздних итерациях наблюдается обратная картина: большое ar и малое заставляют алгоритм интенсивно исследовать ближайшие окрестности уже найденных удачных решений.

Standard Deviation. В своем докладе для международной конференции ICDIM 2008 г. Арпан Мукопадхай (Arpan Mukhopadhyay) с соавторами провели анализ некоторых свойств алгоритма и опубликовали результаты ряда экспериментов с изменением его параметров. Авторы пришли к выводу, что оптимальным значением параметра является среднеквадратическое отклонению текущего решения. При этом вероятность использования решения из памяти cr следует устанавливать близкой к единице (конкретно - 0.99).