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

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

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

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

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

Особенности настройки генетических алгоритмов при решении задач оптимизации на перестановках

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

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

Задачи комбинаторной оптимизации очень часто встречаются в различных областях науки. Обычно задачи подобного рода не имеют в качестве точного метода нахождения решения более эффективного способа решения, чем полный перебор, что неприемлемо для реальных задач. Сейчас разработано большое количество приближенных алгоритмов решения подобных задач. Одним из перспективных походов в настоящий момент является генетический алгоритм. В ходе выполнения исследования были рассмотрены 4 задачи комбинаторной оптимизации - задача о восстановлении примера, задача о восьми ферзях, задача о сортировке, задача коммивояжера. Каждая из задач реализована в отдельных программных системах. Задачи отличаются друг от друга следующими свойствами: решением является одна (несколько) перестановок, циклический сдвиг влево (например, 12345 - 51234) значительно (незначительно) влияет на значение функции пригодности. Для каждой задачи были проведены исследования по влиянию различных параметров генетического алгоритма. Сравнивалась эффективность генетического алгоритма при различных вероятностях скрещивания и мутации. Получены следующие результаты. Для задач, где циклический сдвиг сильно влияет на значение функции пригодности (например, задача о восстановлении примера) вероятность скрещивания должна быть низкой, а вероятность мутации наоборот высокой. Это объясняется тем, что скрещивание носит более деструктивный характер, чем мутация. Для задач, где циклический сдвиг мало влияет на значение функции пригодности, картина обратная: вероятность мутации низкая, вероятность скрещивания высокая. Кроме того, при анализе эффективности генетического алгоритма для задачи коммивояжера была выявлена непропорциональная связь между размером турнира в турнирной селекции и эффективностью генетического алгоритма. Если рассматривать зависимость распределения области наиболее эффективных параметров вероятности скрещивания и мутации генетического алгоритма, то при небольшом размере турнира распределение имеет почти линейный вид, то есть при низкой мутации вероятность скрещивания должна быть высокой, а при высокой мутации вероятность скрещивания должна быть низкой. При увеличении размера турнира наблюдается сдвиг в область высоких вероятностей мутации и скрещивания.

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

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

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