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

Сентябрь 7, 2022

Главная
Алгебра
Генетические алгоритмы

Содержание

2. Введение Давно известно что самые лучшие идеи человек заимствовал от природы. Генетические алгоритмы – один из
3. Истоки идеи генетических алгоритмов (теория эволюции и естественный отбор) В определенных природных условиях выживает либо сильнейший,
4. Ключевые понятия генетических алгоритмов, заимствованные из генетики В природе улучшаются особи, а в алгоритме формируется (улучшается)
5. Примеры особей Для задачи: решить уравнение x-100=0 особями могут быть: x=5, x=-34, x=88 (наилучшая особь), x=-15,
6. Приспосабливаемость В природе особи приспосабливаются к условиям окружающей среды, а в генетическом алгоритме особи (решения) “Приспосабливаются”
7. Общий генетический алгоритм Создание популяции (зародился мир), Цикл по поколениям, Определение приспосабливаемости каждой особи, Сортировка особей
8. Скрещивание Генетикой доказано, что не физические особенности, а только гены передаются по наследству следующему поколению. (из
9. Примеры скрещивания 201 × 82 Одноточечный кроссовер: 11001001 (1й предок) 01010010 (2й предок) = 11010010 (1й
10. Примеры скрещивания 201 × 82 Двуточечный кроссовер: 11001001 (1й предок) 01010010 (2й предок) = 11010001 (1й
11. Примеры скрещивания 201 × 82 Случайный кроссовер: 11001001 (1й предок) 01010010 (2й предок) = 01010011 (1й
12. Мутация Мутации разрушают шифр ДНК и деформируют существо, превращая его в урода. Мутация может быть разрушающей,
13. Пример мутации числа 201 0 11001001 число 201 мутировало в число 193.
14. Основные параметры ГА Основные параметры ГА: Количество особей в популяции (размер популяции). Количество поколений. Вероятность мутации
15. Процесс схождения популяции Зависимость выживаемости лучшей особи от номера поколения. На графике видно постепенное улучшение популяции
16. Практическое применение ГА Области применения генетических алгоритмов: задачи планирования; задачи адаптивного управления; задачи теории игр; транспортные
17. Примеры работы генетического алгоритма Особью являются параметры алгоритма, который выделяет лицо человека анфас. Найденная наилучшая особь
18. Примеры работы генетического алгоритма Аналогично, особью являются параметры алгоритма, который выделяет губы человека. Найденная наилучшая особь
19. Примеры работы генетического алгоритма Аналогично, особью являются параметры алгоритма, который выделяет зрачки человека. Найденная наилучшая особь
20. Пример реализации генетического алгоритма //решение уравнения x=1000 void main () { float pm; int c,n,i,j,j1,k; unsigned
21. Некоторые особенности ГА 1. Об истинности теории Дарвина много лет ведутся споры. Большинство ученых современности отрицают
23. Скачать презентацию

Слайд 2

Введение
Давно известно что самые лучшие идеи человек заимствовал от природы. Генетические

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

Слайд 3

Истоки идеи генетических алгоритмов (теория эволюции и естественный отбор)
В определенных природных условиях

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

Слайд 4

Ключевые понятия генетических алгоритмов, заимствованные из генетики
В природе улучшаются особи, а

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

Слайд 5

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

(наихудшая особь),
x=0.
Вопрос: Какие из этих особей при естественном отборе вероятнее всего умрут в силу плохой приспосабливаемости?

Слайд 6

Приспосабливаемость
В природе особи приспосабливаются к условиям окружающей среды, а в генетическом

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

Слайд 7

Общий генетический алгоритм
Создание популяции (зародился мир),
Цикл по поколениям,
Определение приспосабливаемости каждой особи,
Сортировка

особей по их живучести,
Скрещивание. (Скрещиваются между собой только наиболее живучие особи. Новые особи, полученные в результате скрещивания, заменяют собой старые более слабые особи),
Мутация части особей,
Лучшая особь поколения считается текущим (промежуточным) решением.

Слайд 8

Скрещивание
Генетикой доказано, что не физические особенности, а только гены передаются по

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

Слайд 9

Примеры скрещивания 201 × 82
Одноточечный кроссовер:
11001001 (1й предок)
01010010 (2й предок)
=
11010010 (1й

потомок)
01001001 (2й потомок)
При скрещивании особей 201 и 82 получили особи 210 и 73

Слайд 10

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

потомок)
01001010 (2й потомок)
При скрещивании особей 201 и 82 получили особи 209 и 74

Слайд 11

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

потомок)
11001000 (2й потомок)
При скрещивании особей 201 и 82 получили особи 83 и 200

Слайд 12

Мутация
Мутации разрушают шифр ДНК и деформируют существо, превращая его в урода.

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

Слайд 13

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

Слайд 14

Основные параметры ГА
Основные параметры ГА:
Количество особей в популяции (размер популяции).
Количество поколений.
Вероятность

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

Слайд 15

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

видно постепенное улучшение популяции из поколения в поколение.

Слайд 16

Практическое применение ГА
Области применения генетических алгоритмов:
задачи планирования;
задачи адаптивного управления;
задачи теории игр;
транспортные

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

Слайд 17

Примеры работы генетического алгоритма
Особью являются параметры алгоритма, который выделяет лицо человека

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

Слайд 18

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

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

Слайд 19

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

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

Слайд 20

Пример реализации генетического алгоритма
//решение уравнения x=1000
void main ()
{
float pm;

int c,n,i,j,j1,k;
unsigned short x[1000], a[1000], q;
clrscr();
/*
cout<<"введите вероятность мутации гена\n";
cin>>pm;
cout<<"введите количество поколений\n";
cin>>c;
cout<<"введите количество особей\n";
cin>>n;}
*/
pm=0.01; c=15; n=1000;
//Создание популяции
randomize();
for(j=0; j<=n-1; j++)
{
x[j]=random(32000);
}
for (i=1; i<=c; i++)
{
//Определение приспосабливаемости каждой особи
for (j=0; j<=n-1; j++) a[j]=abs((x[j])-1000);
//Выбор наилучших особей
for (j=0; j<=n-2; j++)
for (j1=j+1; j1<=n-1; j1++) if (a[j1] {
q=a[j]; a[j]=a[j1]; a[j1]=q;
q=x[j]; x[j]=x[j1]; x[j1]=q;
}
cout<<"лучшая особь в "< //Скрещивание
for (j=0; j {
// q=0xAAAA;
q=random(0xAAAA);
x[n-1-j] =(x[j] &q)|(x[j+1]&(~q));
x[n-1-(j+1)]=(x[j+1]&q)|(x[j] &(~q));
}
//Мутация
for (j=0; j {
if (random(1000)<=1000*pm)
{ j1=random(16);
q=pow(2,j1);
x[j]=x[j]^q;
}
}
}
// cout<<"Полученное решение x="< while (bioskey(0)==1);
}

Слайд 21

Некоторые особенности ГА
1. Об истинности теории Дарвина много лет ведутся споры.

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

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

Содержание

ВведениеДавно известно что самые лучшие идеи человек заимствовал от природы. Генетические

Истоки идеи генетических алгоритмов (теория эволюции и естественный отбор)В определенных природных условиях

Ключевые понятия генетических алгоритмов, заимствованные из генетикиВ природе улучшаются особи, а

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

ПриспосабливаемостьВ природе особи приспосабливаются к условиям окружающей среды, а в генетическом

Общий генетический алгоритмСоздание популяции (зародился мир),Цикл по поколениям,Определение приспосабливаемости каждой особи,Сортировка

СкрещиваниеГенетикой доказано, что не физические особенности, а только гены передаются по

Примеры скрещивания 201 × 82Одноточечный кроссовер:11001001 (1й предок)01010010 (2й предок)=11010010 (1й

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

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

МутацияМутации разрушают шифр ДНК и деформируют существо, превращая его в урода.

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

Основные параметры ГАОсновные параметры ГА:Количество особей в популяции (размер популяции).Количество поколений.Вероятность

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

Практическое применение ГАОбласти применения генетических алгоритмов:задачи планирования;задачи адаптивного управления;задачи теории игр;транспортные

Примеры работы генетического алгоритмаОсобью являются параметры алгоритма, который выделяет лицо человека

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

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

Пример реализации генетического алгоритма //решение уравнения x=1000void main (){ float pm;

Некоторые особенности ГА1. Об истинности теории Дарвина много лет ведутся споры.

Похожие презентации