Сравнительный анализ генетических алгоритмов поиска оптимального решения

Размещено на http://www.allbest.ru/

СРАВНИТЕЛЬНЫЙ АНАЛИЗ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ПОИСКА ОПТИМАЛЬНОГО РЕШЕНИЯ

Д.С. Кадников (dskadnikov@yandex.ru)

МГТУ им. Н.Э. Баумана (Калужский филиал), Калуга

Л.Г. Комарцова (lkomartsova@yandex.ru)

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

Введение

алгоритм гармония комбинированный генетический

Опыт последних лет показал, что применение одного метода для решения сложных задач и проблем далеко не всегда приводит к успеху. В гибридной архитектуре, объединяющей несколько парадигм, эффективность одного подхода может компенсировать слабость другого. Комбинируя различные подходы, можно обойти недостатки, присущие каждому из них в отдельности. Поэтому одной из ведущих тенденций в современной информатике стало развитие интегрированных, гибридных и синергетических систем. Подобные системы состоят из различных элементов (компонентов), объединённых в интересах достижения поставленных целей. Интеграция и гибридизация различных методов и технологий позволяет решать сложные задачи, которые невозможно решить на основе каких-либо отдельных методов или технологий [Chia Feng et al., 2004], [Комарцова, 2009], [Курейчик и др., 2000].

Одним из перспективных направлений создания гибридных систем является совместное использование таких технологий как искусственные нейронные сети, генетические алгоритмы (ГА), нечеткие системы, различные модификации алгоритмов оптимизации роя частиц, муравьиных колоний, поиска гармоний и т.д. Последний из названных алгоритмов является мало исследованным, поэтому в докладе проводится его анализ и создание на его базе гибридного ГА, эффективность которого в сравнении с другими подобными ГА показывается на примере решения известных тестовых задач распознавания ирисов и вин [http://www.ics.uci.edu/~mlearn/databases/].

1. Особенности алгоритма поиска гармонии (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].

2. Сравнение комбинированных генетических алгоритмов

Ранее авторами в работе [Комарцова и др., 2004] были созданы и исследованы комбинированные генетические алгоритмы НGAPSO (Hibrid of Genetic Algorithm and Particle Swarm Optimization - гибридный генетический алгоритм оптимизации роя частиц) и Island GA - (параллельный генетический алгоритм островного типа), которые показали свою эффективность по сравнению с простым ГА (GA) при решении задачи обучения многослойной нейронной сети (НС). Ошибка распознавания НC, обученной с помощью НGAPSO и Island GA при решении широко распространенных тестовых задач распознавания ирисов и вин [http://www.ics.uci.edu/~mlearn/databases/], была значительно ниже, чем для GA.

Сравнение предложенного комбинированного HS c созданными ранее алгоритмами НGAPSO, Island GA и GA проведено на тех же тестовых функциях.

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

Полученные результаты сравнительного анализ четырех исследуемых алгоритмов: классического ГА - GA, гибридного - HGAPSO, параллельного - Island GA и алгоритма HS показывают динамику изменения наилучшего (усредненного по всем запускам) значения функции качества (процента распознавания НС) в течение всех поколений работы алгоритмов. Приведенные ниже значения ошибок и времени обучения (в секундах-с) НС являются усредненными (по 50 запускам):

1) Задача распознавания ирисов:

для GA - время обучения 42с, Еобуч=19.98%, Еобобщ=25.32%;

для HGAPSO - время обучения 287с, Еобуч=6.04%, Еобобщ=8.92%;

для Island GA - время 221с, Еобуч=3.02%, Еобобщ=5.44%;

для HS - время обучения 242с, Еобуч=2.03%, Еобобщ=3.82%.

2) Задача распознавания вин.

для GA - время обучения 67с, Еобуч=27.22%, Еобобщ=33.28%;

для HGAPSO - время обучения 365с, Еобуч=14.9%, Еобобщ=22.8%;

для Island GA - время обучения 469с, Еобуч=5.42%, Еобобщ=12.97%;

для HS - время обучения 304с, Еобуч=4.14%, Еобобщ=6.72%.

Лучшие найденные решения:

1) Задача распознавания ирисов: для GA - Еобуч=2%, Еобобщ = 6%; для HGAPSO - Еобуч = 2%, Еобобщ = 6%; для Island GA - Еобуч = 1%, Еобобщ = 4%; HS - Еобуч = 0.83% Еобобщ = 2.52%.

2) Задача распознавания вин: для GA - Еобуч = 6%, Еобобщ = 15.4%; для HGAPSO - Еобуч = 4%, Еобобщ = 11.5%; для Island GA - Еобуч = 2%, Еобобщ = 3.8%; HS - Еобуч = 1.8%; Еобобщ = 3.1%.

Заключение

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

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

Таким образом, наилучшими в экспериментах оказались гибридные алгоритмы на основе HS и параллельные ГА, хотя они и требуют больших вычислительных затрат.

Список литературы

[Комарцова и др., 2004] Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. - М.: МГТУ им. Н.Э. Баумана. 2004.

[Комарцова, 2009] Комарцова Л.Г. Проблемы интеграции интеллектуальных технологий в гибридных системах. // Сб. статей Третьей Всерос. Н-т конф. «Нечеткие системы и мягкие вычисления» (НСМВ-2009). -Т.1.-Волгоград. 2009.[http://www.ics.uci.edu/~mlearn/databases/], http://www.ics.uci.edu/~mlearn/databases/

[Курейчик и др., 2000] Курейчик В.М. Курейчик В.В. Эволюционные, синергетические и гомеостатические стратегии в искусственном интеллекте: состояние и перспективы // Новости искусственного интеллекта. 2000. №3.

[Chia-Feng and al., 2004] Chia-Feng J., Yuan-Chang L. On the hybrid of genetic algorithm and particle swarm optimization for evolving recurrent neural network, IEEE Proc. of Neural Networks International Joint Conference, Vol.3., July 2004.

[Geem, 2009] Geem Z.W. Music-inspired harmony search algorithm: theory and applications. - Berlin.: Springer. 2009.

Размещено на Allbest.ru