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

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

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

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

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

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

Вопросы Задача 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. Задан объем консервной банки. Найти высоту и радиус основания банки, при которых общая площадь ее поверхности будет минимальной. Что в данных задачах будет особью, что приспособленностью, из какого количества генов будет состоять каждая особь?

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример реализации генетического алгоритма //решение уравнения 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

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

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