Генетические алгоритмы Студент гр. 4057/2 Мима Андрей Доклад на семинаре по специальности

План доклада Описание задачи Решаемые проблемы Немного истории Описание алгоритма Отбор популяции Скрещивание Мутации Завершимость Сходимость Шаблоны и строящие блоки

План доклада (2) Геометрическая интерпретация Геометрическая интерпретация (2) Пример: диофантово уравнение Пример (приспособленность) Пример (пригодность) Пример (кроссовер) Пример (потомство) Преимущества и недостатки Литература

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

Решаемые проблемы Аппроксимация функций Задачи о кратчайшем пути Задачи размещения Настройка искусственной нейронной сети Игровые стратегии Обучение машин Поиск экстремума

Немного истории J. Holland «Adaptation in Natural and Artificial Systems» (1975) Kenneth De Jong, David E. Goldberg «Genetic algorithms in search optimization and machine learning» (1989) Чарльз Дарвин ( )

Генетический алгоритм

Отбор популяции Решение задачи – вектор (битовая строка) Популяция – фиксированное число особей Естественный отбор – функция приспособленности (fitness function) Плохие особи отмирают, хорошие отбираются, некоторые хорошие дублируются

Скрещивание Особи случайным образом разбиваются на пары Оператор кроссовера – точка раздела, вокруг которой происходит обмен хромосом: => => Существуют различные способы скрещивания

Мутации Оператор мутации – каждый бит новой особи популяции с определенной вероятностью инвертируется 01 Вероятность мутации крайне мала, порядка 1% => После этого новое поколение сформировано

Критерии остановки Найдено решение, удовлетворяющее наилучшему критерию Достигнуто максимальное число поколений Превышено время/вычислительные ресурсы Функция приспособленности более не улучшается от поколения к поколению

Сходимость Пропорциональный отбор – для каждой особи: отношение ее приспособленности к средней приспособленности популяции. Целая часть сколько раз записать особь в промежуточную популяцию, дробная вероятность попасть туда снова Одноточечный кроссовер Шаблон – строка, сост. из символов 0, 1, * Теорема шаблонов

Шаблоны и строящие блоки Порядок шаблона – количество фиксированных битов в нем Определяющая длина – расстояние между крайними фиксированными битами шаблона Строящий блок – шаблон, удовлетворяющий: Высокая приспособленность Низкий порядок Короткая длина

Геом. интерпретация f(x) = 10 + x sin(x)

Геом. Интерпретация (2)

Пример: Диофантово уравнение a+2b+3c+4d=30 Хромосома(a,b,c,d) 1 (1,28,15,3) 2 (14,9,2,4) 3 (13,5,7,3) 4 (23,8,16,19) 5 (9,13,5,2)

Пример (приспособленность) ХромосомаПриспособленность 1|114-30|=84 2|54-30|=24 3|56-30|=26 4|163-30|=133 5|58-30|=28

Пример (пригодность) ХромосомаПригодность 1(1/84)/ = 8.80% 2(1/24)/ = 30.8% 3(1/26)/ = 28.4% 4(1/133)/ = 5.56% 5(1/28)/ = 26.4%

Пример (кроссовер) Родитель 1Родитель 2Потомок (13 | 5,7,3)(1 | 28,15,3)(13,28,15,3) (9,13 | 5,2)(14,9 | 2,4)(9,13,2,4) (13,5,7 | 3)(9,13,5 | 2)(13,5,7,2) (14 | 9,2,4)(9 | 13,5,2)(14,13,5,2) (13,5 | 7, 3)(9,13 | 5, 2)(13,5,5,2)

Пример (потомство) Хромосома-потомокВыживаемость (13,28,15,3)|126-30|=96 (9,13,2,4)|57-30|=27 (13,5,7,2)|57-30|=22 (14,13,5,2)|63-30|=33 (13,5,5,2)|46-30|=16

Преимущества и недостатки Универсальный метод оптимизации - широкий спектр задач Большое количество модификаций Применение полезно только когда нет специального алгоритма решения Проблемы общие для всех алгоритмов поиска

Обзор литературы Дискретная математика: алгоритмы (Генетические алгоритмы) ed/genetic-2005 АИ, ГА - Генетические алгоритмы Кафедра «Технологии программирования» Генетические алгоритмы

Спасибо за внимание Вопросы?