г. Новосибирск, 15-17 октября 2012 г.

Лукьянов Н.Д.  

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

Стремительное развитие вычислительной техники в 20 веке спровоцировало появление большого количества разнообразных имитационных алгоритмов. К таким алгоритмам относится большинство методов искусственного интеллекта, которые основаны на имитации процессов природы при помощи средств компьютерного моделирования.
Для решения задач оптимизации довольно часто используется такой инструмент искусственного интеллекта как генетический алгоритм (ГА). Основными достоинствами этого алгоритма являются:
1. Он не налагает никаких дополнительных ограничений на вид целевой функции;
2. Простая реализация и возможность распараллеливания.
Однако в специализированной литературе по ГА, на взгляд автора, уделяется недостаточное внимание условию останова. Данный доклад посвящен выбору критерия останова для генетического алгоритма, используемого для задач оптимизации автоматических систем. В [1, 2, 3] приводятся несколько критериев останова, для решения задач оптимизации приемлемыми являются следующие:
• Достижение определенного числа поколений;
• Истечение времени отпущенного на эволюцию;
• Схождение популяции.
В данном докладе подробно рассматривается только третье условие, так как два первых подразумевают введение дополнительных параметров, а также проведение предварительных исследований. 
В качестве авторского условия останова используется комбинированный критерий, состоящий из оценки средней популяции, а также из определения расстояния между особями в поколении.
Так же приведен пример, иллюстрирующий работоспособность предложенного критерия останова.
Список литературы
1. Вороновский, Г.К.  Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. / Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. – Харьков: ОСНОВА, 1997. – 112с.
2. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы: пер. с польск. И. Д. Рудинского. / Д. Рутковская, М. Пилиньский, Л. Рутковский – М. : Горячая линия – Телеком, 2006. – 452 с.: ил. 
3. Тим Джонс, М. Программирование искусственного интеллекта в приложениях: пер. с англ. А.И. Осипова / М. Тим Джонс – М. : ДМК Пресс, 2004. – 312 с.: ил.

Тезисы доклада:abstracts_137477_ru.pdf
Файл с полным текстом: Критерий остановки_Лукьянов.pdf


К списку докладов

Комментарии

Имя:
Код подтверждения: