Година на Политехничкиот универзитет во Букурешт - преземање ppt
Политехнички универзитет во Букурешт Академска година 2008-2009 година Автоматско учење Политехнички универзитет во Букурешт Академска година 2008-2009 година Адина Магда Флореа http://turing.cs.pub.ro/inva_09 и curs.cs.pub.ro
Курс бр. 9 генетски алгоритми Вовед Основна шема Моделирање на проблеми Пример Избор Рекомбинација Мутација на TSP со генетски алгоритми Паралелна имплементација AG 2
1. Вовед GA - САД, J. H. Holland (1975) Еволуциони алгоритми - Германија, I. Rechenberg, H.-P. Швефел (1975-1980) генетско програмирање (1960-1980, 2000) Ј. Коза за оптимизација Економски модели Еколошки модели модели на учење на социјалните системи 3
Вовед - сметка Работи на популација на поединци = потенцијални решенија - го применува принципот на преживување заснован на прилагодување (кондиција) Секоја генерација - нов пристап кон решението Еволуција на популација на поединци подобро прилагодена на околината Модели на природни процеси: избор, рекомбинација, мутација, миграција, локација Население на поединци - паралелно пребарување 4
2. Основна шема Генерира популација на почетни лица (гени) Претставување на проблемот Функција за фитнес Генерира популација на почетни лица (гени) Ја проценува целта на функцијата Критериумот за запирање исполнет? да не најдобрите поединци Започнете Избор на резултати Кросовер/рекомбинација Добијте ново потомство на популација Мутација 5 генерации
3. Моделирање на проблеми Почетна популација Воспоставете репрезентација - ген - индивидуален Одредете број на лица во популацијата Воспоставете функција за проценка (цел) Почетна популација (гени) случајно создадена Избор на избор - извлекување подмножество на гени од постојната популација како дефиниција на квалитет - функција за проценка Определува индивидуи избрани за рекомбинација и колку потомци произведува секое поединечно 6
Моделирање на проблеми Критериум за стопирање Решение за повеќенаселени GA што го исполнува критериумот број на генерации плато буџет за најдобра кондиција ГП за повеќенаселение Подобри резултати - подпапулации Секоја популација се развива одделно Поединците се менуваат по голем број генерации 7
Избор (1) Прв чекор: задача за фитнес - пропорционална задача - задача заснована на ранг (2) Ефективен избор: родителите се избираат во фитнес засновани на еден од алгоритмите: избор на тркалачко тркало, стохастичко универзално земање примероци стохастика) локална селекција (локална селекција) избор на турнир (избор на турнир) избор на кратење (скратена селекција) 8
Повторно вметнување на потомство - ако се појават помалку поединци или помалку деца, тогаш дополнителни лица мора да бидат вметнати во новата популација. Алгоритмот за избор ја одредува шемата за повторно вметнување (општо) на глобалната реинтеграција - во целата популација за. избор на рулет-тркала, стохастичко универзално земање примероци, избор на отсекување локално вметнување за локален избор 9
Вкрстување/рекомбинација Рекомбинацијата произведува нови лица со комбинирање на информации од родители (родители - популација на парење). Различни шеми за рекомбинација Една можност - случајно парење Исто како и генетско вкрстување Се избираат проценти на премиери на новонаселени лица и случајно се парат Се избира точка на вкрстување за секој пар (иста или различна веројатност) Информацијата се разменува помеѓу двајцата лица врз основа на кросовер точка 10
Мутација со мали случајни нарушувања Потомство - мутација Мутација со мали случајни нарушувања Различни форми на мутација, во зависност од репрезентацијата Мутација - истражување наспроти експлоатација Едноставна шема Секој бит има веројатност за мутација 12
Ефектот на мутација и селекција 14
4 Пример Пресметај го максимумот на функцијата f (x1, x2,. Xn) Пронајди x1, x2,. xn за кој f е максимум Користете GA 15
Претставување Скалирање на променливите со множење со 10n, каде n е саканата точност Променлива = цел број (Var × 10 n) Променливите се претставени во бинарни Променливи се споени - индивидуално Ако сакаме знак: Додадете вредност и свртете се на позитивно или на Бит за знак Бинарна претстава или Сив-код 16
Пресметка Почетна популација случајна мутација на избор на вкрстена трансформација на секоја индивидуа во променливи: x1, x2,. xn Тестирајте го квалитетот на секоја индивидуа: f (x1, x2,. xn) Тест дали квалитетот на најдобрата индивидуа е доволно добар ако застанете инаку одете на 2 17
5. Избор Првиот чекор е доделување на фитнес (F) Директно доделување засновано врз целната функција ИЛИ Доделување засновано врз механизам Секој поединец во популацијата добива вредност на фитнес Врз основа на вредноста на фитнесот изборот (С) е направен според шемата за избор 18
Избор Веројатноста за репродукција може да се поврзе со индивидуа - зависи од вредноста на функцијата за фитнес на индивидуа и од вредноста на функцијата за подготвување на останатите лица во популацијата. Оваа веројатност може да се користи при избор 19
Поим за избор на термини: веројатност за избор на најдобра индивидуа во споредба со просечната веројатност за избор на сите поединци: опсег на вредности на бројот на потомци на индивидуална загуба на разновидност: процентот на поединци во популацијата што не е избран интензитет на избор: просечна подготвеност на популацијата по примена на метод на избор коваријанса на избор: коваријанса на дистрибуција на физичка подготвеност по примена на метод на избор 20
А1 Пропорционална задача за фитнес Секој ген има поврзана фитнес Пресметајте ја просечната подготвеност на населението Секоја индивидуа ќе биде копирана во новата популација во форма на кондиција во споредба со просечната кондиција на фитнес 5,76, индивидуалната кондиција 20,21 - копирајте 3 пати Поединци со фитнес еднаква или под просечно игнорирај Нова популација - може да биде помала Новата популација е исполнета со случајно избрани лица од старата популација 21
А2 Задача за фитнес заснована на ранг Фитнесот што му е доделен на секоја индивидуа зависи само од неговата позиција меѓу поединците во популацијата Позицијата на поединецот во популацијата зависи од целната функција Поз = 1 - најмалку добро Поз = Ниту - најдобро Популацијата е подредена фитнес 22
Доделување на фитнес заснован на Нинд ранг - број на поединци во популацијата Поз - позиција на поединецот во популацијата (најлошо Поз = 1, најдобро Пос = Незначително) СП - притисок на избор (веројатност за избор на најдобра индивидуа во однос на веројатноста просечен избор на сите поединци) Линеарен ранг Фитнес (Поз) = 2 - СП + 2 * (СП - 1) * (Поз - 1)/(Ништо - 1) Линеарниот ранг дозволува SP вредности во (1,0, 2,0). да изберете поединец за рекомбинација е кондиција (нормализирана) во споредба со вкупната подготвеност на населението 23
Задача за фитнес заснована на ранг Нелинеарно рангирање: Фитнес (Поз) = Нинд * X (Поз - 1)/ i = 1, Нинд (Х (и - 1)) X се пресметува како корен на полиномот: 0 = (СП - Нинд ) * X (Nind - 1) + SP * X (Nind - 2) +. + SP * X + SP Нелинеарниот опсег дозволува SP вредности во [1.0, Nind - 2.0] SP повисока Веројатноста за избор на поединец за рекомбинација е кондиција (нормализирана) во однос на вкупната подготвеност на населението 24
Задача за фитнес заснована на линеарен ранг СП = 2 0.2 СП = 1,5 0,5.1,5 Фитнес задача линеарен ранг и нелинеарен ранг 25
Задача за фитнес заснована на ранг во споредба со пропорционална задача: Го избегнува проблемот со стагнација ако притисокот во изборот е пренизок или предвремената конвергенција генерира премногу тесна област за пребарување Овозможува лесен начин за контрола на притисокот при избор Општо поцврсто 26
Доделување на фитнес засновано врз интензитетот на избор на својства на ранг: SelIntRank (SP) = (SP-1) * (1/sqrt ()). Губење на разновидност: LossDivRank (SP) = (SP-1)/4. Коваријанта на избор: SelVarRank (SP) = 1 - ((SP-1) 2/) = 1-SelIntRank (SP) 2. 27
С1. Избор на рулет или стохастичко земање примероци со замена на 11 лица, линеарен ранг и СП = 2 6 случајни броеви (рамномерно распоредени помеѓу 0,0 и 1,0): 0,81, 0,32, 0,96, 0,01, 0,65, 0,42. Индивидуален број 1 2 3 4 5 6 7 8 9 10 11 Фитнес-вредност 2.0 1,8 1,6 1,4 1,0 1,0 0,8 0,6 0,4 0,2 0,0 Веројатно. избор 0,18 0,16 0,15 0,13 0,11 0,09 0,07 0,06 0,03 0,02 6, 2, 9, 1, 5, 3 28
S2. Стохастички универзални примероци Покажувачите се поставуваат на еднакво растојание на интервал [0.1] - ќе бидат избрани толку многу индикатори колку поединци во опсегот [0.1/NPointer]. За да изберат 6 лица, растојанието помеѓу покажувачите е 1/6 = 0,167. 1 случаен број во опсегот [0, 0,167]: 0,1. 1, 2, 3, 4, 6, 8 29
S3. Локален избор Секоја индивидуа е во соседството Структуирање на населението Соседство - група на поединци кои можат да рекомбинираат (потенцијално) Линеарно соседство: целосна и половина прстен
Потоа се дефинира соседство за секоја избрана индивидуа. Локален избор Првата половина од популацијата е избрана случајно (или со користење на алгоритам за избор - стохастичко земање примероци или турнир). Потоа се дефинира соседство за секоја избрана индивидуа. Изберете друга индивидуа за рекомбинација во соседството (најдобро, фитнес пропорционално или случајно). 32
Локален избор Изолационо растојание помеѓу поединците Колку е помало соседството, толку е поголема изолацијата Населени места што се преклопуваат - се појавува пренос на карактеристиките Големината на соседството ја одредува брзината на размножување Брзо размножување наспроти одржување на висока разновидност Голема разновидност - спречува предвремена конвергенција
S4. Избор на турнир Избор на број на поединци во популацијата е избран по случаен избор и најдобрата индивидуа е избрана за родител. Процесот се повторува за колку лица сакаме да избереме. Параметарот за големината на турнирот е Тур. Тура - вредности помеѓу 2. Неповрзани врски помеѓу турнејата и интензитетот на изборот Големина на турнирот 1 2 3 5 10 30 Интензитет на избор 0,56 0,85 1,15 1,53 2,04 Просечна вредност на подготвеноста на населението по примена на метод за избор 34
Избор на турнир Интензитет на избор: SelIntTour (турнеја) = sqrt (2 * (log (Tour) -log) (sqrt (4,14 * log (Tour))))))) Губење на разновидност: LossDivTour (Tour) = Tour - (1/(Tour) -1)) - Тура - (Тура/(Тур-1))) (Околу 50% од популацијата е изгубена за Тур = 5). Коваријација на избор: SelVarTour (Тура) = 1- 0,096 * дневник (1 + 7,11 * (Тур-1)), SelVarTour (2) = 1-1/ 35
6. Вкрстување/рекомбинација Произведува нови лица со рекомбинирање на родителски информации Бинарни претстави бинарна повеќе точка униформа Цел број/реални претстави дискретни реални линеарни средно 36
6.1 Бинарна рекомбинација Случајно избрана позиција на вкрстување occur 2 потомци се појавуваат 37
Бинарна рекомбинација Индивидуален пример 1: 0 1 1 1 0 0 1 1 0 1 0 позиција на вкрстување = 5 2 нови индивидуи се создаваат: потомци 1: 0 1 1 1 0 | 1 0 0 1 0 1 потомство 2: 1 0 1 0 1 | 0 1 1 0 1 0 38
6.2 Рекомбинирани позиции во кросовер со повеќе точки м индивидуално 1: 0 1 1 1 0 0 1 1 0 1 0 индивидуално 2: 1 0 1 0 1 1 0 0 1 1 1 1 поз. крст (m = 3) 2 6 10 потомци 1: 0 1 | 1 0 1 1 | 0 1 1 1 | 1 потомство 2: 1 0 | 1 1 0 0 | 0 0 1 0 | 0 39
6.3 Единствена рекомбинација Генерализира едноставната бинарна и повеќе точка Crossover маска - со иста големина како и индивидуата; случајно креирана и паритетот на битовите во маската означува кој родител ќе им даде на потомството што битно индивидуално 1: 0 1 1 1 0 0 1 1 0 1 0 индивидуално 2: 1 0 1 0 1 1 0 0 1 0 1 маска 1: 0 1 1 0 0 0 1 1 0 1 0 маска 2: 1 0 0 1 1 1 0 0 1 0 1 (обратна маска 1) потомство 1: 1 1 1 0 1 1 1 1 1 1 1 потомство 2: 0 0 1 1 0 0 0 0 0 0 0 Спирс и Де Јонг (1991) - парамеризација со асоцирање на веројатност 40
6.4 Вистинска дискретна рекомбинација Дискретна рекомбинација Размена на реални вредности помеѓу поединци. индивидуална 1: 12 25 5 индивидуална 2: 123 4 34 За секоја вредност, родителот што придонесува е избран по случаен избор со еднаква веројатност примерок 1: 2 2 1 примерок 2: 1 2 1 По рекомбинацијата: потомство 1: 123 4 5 потомство 2: 12 4 5 41
Дискретна реална рекомбинација Дискретна рекомбинација Можни позиции на потомство Може да се користи со какви било вредности (бинарни, реални или симболи). 42
Средна реална рекомбинација Само за реални вредности Вредностите од потомците избрани околу вредностите од родителите Правило: потомство = родител 1 + Алфа (родител 2 - родител 1) каде Алфа е случајно избран фактор за скалирање во опсегот [-d, 1 + d] . d = 0 или d> 0. Добра вредност d = 0,25. Секоја вредност кај потомството е резултат на комбинирање на родителите со нова Алфа за секоја променлива 43
Средно реално комбинирање индивидуа 1: 12 25 5 индивидуално 2: 123 4 34 Алфа вредности се: примерок 1: 0,5 1,1 -0,1 примерок 2: 0,1 0,8 0,5 Нови лица (потомство = родител 1 + Алфа (родител 2 - родител 1) потомство 1: 67,5 1,9 2,1 потомство 2: 23,1 8,2 19,5 44
Вистинска средна рекомбинација Опсег на вредности на потомците во споредба со оној на родителите Распределба на потомците по средно рекомбинација 45
Линеарна реална рекомбинација Линеарна рекомбинација Слично на средното, но се користи само една алфа. индивидуално 1: 12 25 5 индивидуално 2: 123 4 34 Алфа вредности се: примерок 1: 0,5 примерок 2: 0,1 Нови индивидуи: потомство 1: 67,5 14,5 19,5 потомство 2: 23,1 22,9 7,9 46
Линеарна реална рекомбинација Линеарна рекомбинација 47
7. Мутација По рекомбинацијата - мутација на потомците Вредностите од потомците се поместуваат со инверзија (бинарна) или со додавање на мали случајни вредности (чекор на мутација), со ниска веројатност Веројатноста за мутација е обратно пропорционална со големината на поединците Колку подолго имаме индивидуи веројатноста за мутација е помала 48
7.1 Бинарна мутација Разменувајте бинарни вредности За секоја индивидуа, битот што треба да се премести е случајно избран 11 вредности, бит 4 пред мутација 1 по мутација 49
7.2 Мутација со реални вредности Ефект на мутација Големина на чекор - тешко; може да варира за време на еволуцијата Мал - добар, бавен; голем - побрз Оператор за мутација: мутирана променлива = променлива ± опсег · делта (+ или - со еднакви веројатности) опсег = 0,5 * променлив домен делта = збир (a (i) 2-i), a (i) = 1 со веројатност 1/m, инаку a (i) = 0. 50
8. Користење на GA за: - Проблем 0/1 ранец - TSP 51
8.1 0/1 проблем со ранец Дадени се многу предмети, секој со тежина/тежина w (i) и вредност/профит p (i). Определете го бројот на предмети од секој тип што треба да бидат вклучени во колекцијата a.i. тежината треба да биде помала од дадената вредност W и вкупната вредност да биде максимална. Проблем ранец 0/1 - 0 или 1 предмет од секој тип. Мултиобјективен проблем за оптимизација: максимизирајте ја добивката и минимизирајте ја тежината Не постои (единствено) оптимално решение, но сет на решенија со оптимално „размена“ = збир на решенија за кои еден критериум не може да се подобри без да се влоши друг 52
0/1 проблем со ранец Врши максимална сума (x (i) * p (i)) Ограничи ја сумата (x (i) * w (i)) (2, 0) - избери 0: 4 1 2 0 xx (0, 1) Повратни информации: Политика за приватност Повратни информации
За проектот: SlidePlayer Услови на услугата