Лекция по основам теории алгоритмов Генетические алгоритмы Составитель: к.т.н. Варламов А.Д. 2010. - презентация

1 Лекция по основам теории алгоритмов Генетические алгоритмы Составитель: к.т.н. Варламов А.Д. 2010

2 Введение Давно известно что самые лучшие идеи человек заимствовал от природы. Генетические алгоритмы – один из подобных примеров. Алгоритмы, построенные по аналогии с естественными процессами, протекающими в природе, называются генетическими. Первые исследования в области GА относятся к 50-м годам (моделирование биологических систем). В годы Холланд в университете Мичигана развил теорию генетических алгоритмов до того уровня, на котором они понимаются сегодня.

3 Истоки идеи генетических алгоритмов (теория эволюции и естественный отбор) В определенных природных условиях выживает либо сильнейший, либо наиболее приспособленный к этим условиям. Развитие отдельных форм жизни происходит благодаря процессу, который называется естественный отбор. Ч. Дарвин – автор теории эволюции Пример: При нападении на оленье стадо хищников выживают наиболее быстрые животные. По прошествии времени оленье стадо образуют лишь только самые быстрые и сильные особи.

4 Ключевые понятия генетических алгоритмов, заимствованные из генетики В природе улучшаются особи, а в алгоритме формируется (улучшается) решение. Поэтому одним из ключевых понятий ГА является особь. Особь – одно из возможных решений задачи; Популяция – множество особей (массив возможных решений); Поколение – этап существования популяции; Мутация – случайное изменение особи; Скрещивание – получение новых особей из двух других; Приспособленность (живучесть) особи – величина, характеризующая степень соответствия искомого решения оптимальному; Ген – один бит информации особи.

5 Примеры особей Для задачи: решить уравнение x-100=0 особями могут быть: x=5, x=-34, x=88 (наилучшая особь), x=-15, x= (наихудшая особь), x=0. Вопрос: Какие из этих особей при естественном отборе вероятнее всего умрут в силу плохой приспосабливаемости?

6 Приспосабливаемость В природе особи приспосабливаются к условиям окружающей среды, а в генетическом алгоритме особи (решения) Приспосабливаются к условию задачи. Приспосабливаемость (живучесть) в генетическом алгоритме – это количественная величина, которая определяет, на сколько текущее решение близко к оптимальному. Для решения уравнения x-100=0 выживаемость будет определяться по формуле: Приспосабливаемость = |x-100|. Для решения задачи оптимизации затрат на перевозку товаров выживаемость будет определяться по формуле: Приспосабливаемость = Затраты на перевозку.

7 Вопросы Задача 1. Требуется определить значения 20 параметров автомобиля, при которых он будет достигать максимальной скорости. Задача 2. Требуется минимизировать функцию с помощью генетического алгоритма. Y = 100(x 2 - x 1 2 )+(1-x 1 ) 2 +90(x 4 - x 3 2 ) 2 +(1-x 3 ) 2 +10,1{(x 2 -1) 2 +(x 4 -1) 2 }+19,8(x 2 -1)( x 4 -1) Задача 3. Задан объем консервной банки. Найти высоту и радиус основания банки, при которых общая площадь ее поверхности будет минимальной. Что в данных задачах будет особью, что приспособленностью, из какого количества генов будет состоять каждая особь?

8 Общий генетический алгоритм 1.Создание популяции (зародился мир), 2.Цикл по поколениям, 3.Определение приспосабливаемости каждой особи, 4.Сортировка особей по их живучести, 5.Скрещивание. (Скрещиваются между собой только наиболее живучие особи. Новые особи, полученные в результате скрещивания, заменяют собой старые более слабые особи), 6.Мутация части особей, 7.Лучшая особь поколения считается текущим (промежуточным) решением.

9 Скрещивание Генетикой доказано, что не физические особенности, а только гены передаются по наследству следующему поколению. (из законов генетики) В генетических алгоритмах механизм наследования генов реализуется через процедуру скрещивания. Чаще всего скрещивание в генетическом алгоритме представляет собой получение из двух особей-родителей двух особей- потомков. Пусть скрещиваются две особи: 201 × 82 Результат скрещивания зависит от выбранного типа кроссовера и случайных параметров выбора генов. Если i-й ген одного предка передался некоторому потомку, то i-й ген другого предка передастся, соответственно, другому потомку.

10 Примеры скрещивания 201 × 82 Одноточечный кроссовер: (1й предок) (2й предок) = (1й потомок) (2й потомок) При скрещивании особей 201 и 82 получили особи 210 и 73

11 Примеры скрещивания 201 × 82 Двуточечный кроссовер: (1й предок) (2й предок) = (1й потомок) (2й потомок) При скрещивании особей 201 и 82 получили особи 209 и 74

12 Примеры скрещивания 201 × 82 Случайный кроссовер: (1й предок) (2й предок) = (1й потомок) (2й потомок) При скрещивании особей 201 и 82 получили особи 83 и 200

13 Мутация Мутации разрушают шифр ДНК и деформируют существо, превращая его в урода. Мутация может быть разрушающей, а в ряде случаев даже губительной, но не созидательной. (опыты на фруктовых червях) Однако, в генетических алгоритмах в отдельных (но не частых) случаях мутация приводит к положительным изменениям. Они оказываются особенно полезными когда в популяции все особи стали примерно одинаковыми. Это даст скачек развитию всей популяции. Мутация представляет собой случайное маловероятное изменение произвольного гена цепочки на противоположный. Пусть мутирует особь 201: 1.Число представляется в двоичном коде: , 2.Изменяется на противоположный случайно выбранный ген: Результат переводится в десятичный вид: 193. Таким образом, число 201 мутировало в число 193.

14 Пример мутации числа число 201 мутировало в число 193.

15 Основные параметры ГА Основные параметры ГА: Количество особей в популяции (размер популяции). Количество поколений. Вероятность мутации особи в каждом поколении. Используемый вид кроссовера. Критерий выбора особей для скрещивания. Вопрос: от каких вышеперечисленных параметров зависит вычислительная сложность генетического алгоритма?

16 Процесс схождения популяции Зависимость выживаемости лучшей особи от номера поколения. На графике видно постепенное улучшение популяции из поколения в поколение.

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

18 Примеры работы генетического алгоритма Особью являются параметры алгоритма, который выделяет лицо человека анфас. Найденная наилучшая особь – это алгоритм с такими параметрами, при котором контур лица выделяется наиболее точно.

19 Примеры работы генетического алгоритма Аналогично, особью являются параметры алгоритма, который выделяет губы человека. Найденная наилучшая особь – это алгоритм с такими параметрами, при котором губы выделяются наиболее точно.

20 Примеры работы генетического алгоритма Аналогично, особью являются параметры алгоритма, который выделяет зрачки человека. Найденная наилучшая особь – это алгоритм с такими параметрами, при котором зрачки выделяются наиболее точно.

21 Пример реализации генетического алгоритма //решение уравнения x=1000 void main () { float pm; int c,n,i,j,j1,k; unsigned short x[1000], a[1000], q; clrscr(); /* coutpm; coutc; coutn;} */ pm=0.01; c=15; n=1000; //Создание популяции randomize(); for(j=0; j

22 Некоторые особенности ГА 1. Об истинности теории Дарвина много лет ведутся споры. Большинство ученых современности отрицают влияние естественного отбора на процесс эволюции. Эволюция и естественный отбор – вещи разные. Генетический алгоритм – это информационный аналог естественного отбора, но не эволюции. 2. Малый размер популяции может привести к тому, что особи популяции перестанут улучшаться. Большой размер популяции может значительно увеличить временную сложность алгоритма. Сильное ограничение числа особей в популяции может свести на нет ее схождение. Пример 1: запрещены браки между близкими родственниками. Запрет имеет обоснование на генетическом уровне, Пример 2: если не меняться аквариумными рыбками с другими любителями рыбок, они будут чаще болеть и умирать. 3. Природой не зря предусмотрена вероятность мутаций, не смотря на то, что они губят большинство особей. Для развития популяции в целом мутации необходимы.

23 Вопросы по лекции