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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16 Пример: Диофантово уравнение 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)

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

18 Пример (пригодность) ХромосомаПригодность 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%

19 Пример (кроссовер) Родитель 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)

20 Пример (потомство) Хромосома-потомокВыживаемость (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

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

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

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