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

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

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

Генетический алгоритм является эффективным методом решения задач оптимизации при хорошей настройке параметров, от которых зависит эффективность поиска. При решении практических задачах мы не знаем эти оптимальные параметры, поэтому проблема отыскания оптимальных параметров является актуальной задачей. Обычно они определяются через многократные запуски генетического алгоритма с целью нахождения лучших параметров, что занимает много машинного времени. Была поставлена цель: создать модель генетического алгоритма, который сам определял свои эффективные настройки в процессе своей работы, причем данный алгоритм должен работать лучше, чем стандартный генетический алгоритм со случайными параметрами. В качестве настраиваемых параметров были взяты вероятность скрещивания и вероятность мутации. Данная задача сводится к оптимизации в функции двух вещественных переменных. В качестве целевой функции можно взять значение лучшего индивида в поколении или скорость изменения лучшего индивида по сравнению с предыдущими поколениями. Были реализованы алгоритмы локальной оптимизации, использующей данную информацию. Но как оказалось поведение целевой функции не позволяет создать подобные алгоритмы. Во-первых, скорость возрастания функции постепенно уменьшается. Во-вторых, функция очень зашумлена, причем уровень помех непостоянен и зависит напрямую от вероятности мутации. Но было замечено, что если запустить генетический алгоритм со случайными параметрами в каждом поколении, то плотность лучших значений целевой функции будет выше в области оптимальных параметров.

В виду этого был предложен простой, но эффективный метод. Отрезок [0,1], в котором изменяется вероятность скрещивания, разбивается на n частей. Каждому участку ставится в соответствие среднее значение целевой функции (значение лучшего индивида в поколении) при условии, что вероятность скрещивания на данном поколении принадлежит данному участку отрезка [0,1]. В начале работы алгоритма все средние значения равны нулю. В каждом поколении вероятность скрещивания определяется с помощью турнирной селекции по массиву средних значений. После подсчета значения лучшего индивида среднее значение целевой функции, соответствующее вероятности скрещивания, обновляется за счет поступления новой информации. Аналогичные действия проводим с вероятностью мутации.

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

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

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

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

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск