Конференции ИВТ СО РАН

VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых)

1-3 ноября 2006 года, Красноярск, Россия

Тезисы докладов

Математическое моделирование

Исследование эффективности коэволюционного алгоритма на тестовых функциях одной переменной

Сергиенко Р.Б.

Сибирский государственный аэрокосмический университет (Красноярск)

Коэволюционный генетический алгоритм – это несколько параллельно действующих стандартных генетических алгоритмов (конкурирующих подпопуляций). Для каждой подпопуляции возможен выбор типа селекции, скрещивания, мутации. После заданного интервала адаптации оценивается пригодность каждой подпопуляции, происходит перераспределение ресурсов в соответствии с вычисленными пригодностями подпопуляций. Возможна миграция лучшего индивида из одной подпопуляции в другую. Как и стандартный генетический алгоритм, коэволюционный алгоритм используется в качестве оптимизирующей процедуры, то есть для отыскания оптимума заданной функции. Однако коэволюционный алгоритм позволяет автоматически подбирать наилучшие настройки для конкретной функции, что повышает эффективность оптимизации. Кроме того, коэволюция позволяет исследовать особенности тех или иных настроек генетического алгоритма, а также в режиме реального времени сравнивать их. Для подпопуляций возможно следующее варьирование основных настроек. Тип селекции: пропорциональная или турнирная (с размером турнира 2). Тип скрещивания: одноточечное, двухточечное, равномерное. Мутация: средняя (мутирует в среднем один бит из бинарной строки-индивида), высокая, слабая. Коэволюция включает три генетических алгоритма. Исходный размер популяции для всех алгоритмов — 100, число поколений — 100, интервал адаптации — 10, размер штрафа для «проигравших» алгоритмов — 5% популяции, размер «социальной карты» (минимальное число индивидов в популяции) — 20 индивидов, число запусков программы для усреднения значений — 50, требуемая точность решения — 4-й знак после запятой. Основными показателями эффективности, используемыми при сравнении алгоритмов, стали усредненное по запускам значение размера популяции алгоритма по завершении работы коэволюции, а также надёжность алгоритма, то есть отношение числа запусков алгоритма, в которых с заданной точностью найден оптимум функции, к общему числу запусков. В части тестовых задач целевые функции являются одноэкстремальными, остальные функции – многоэкстремальные. Проведенные исследования позволяют определить, какие настройки стандартного генетического алгоритма более эффективны для нахождения локального оптимума, а какие — для нахождения глобального оптимума. Проведенные исследования позволили установить особенности работы коэволюционного алгоритма на функциях одной переменной, а также сравнить эффективность стандартных генетических алгоритмов с различными настройками.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]