Политехнически университет в Букурещ Университетска година

Политехнически университет в Букурещ Академична 2008-2009 г. Автоматично обучение Политехнически университет в Букурещ Академична 2008-2009 г. Adina Magda Florea 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. Schwefel (1975-1980) Генетично програмиране (1960-1980, 2000) J. Koza Оптимизация Икономически модели Екологични модели Модели на обучение на социални системи 3

Въведение - акаунт Работи върху популация от индивиди = потенциални решения - прилага принципа на оцеляване, основан на адаптация (фитнес) Всяко поколение - нов подход към решението Еволюция на популация от индивиди, по-добре адаптирани към околната среда Моделира естествени процеси: селекция, рекомбинация, мутация, миграция, местоположение Население на лица - паралелно търсене 4

2. Основна схема Генерира популацията на първоначалните индивиди (гени) Представяне на проблема Фитнес функция Генерира популацията на първоначалните индивиди (гени) Оценява целевата функция Критерият за спиране е изпълнен? да не най-добрите индивиди Стартиране на избор на резултат Кросоувър/Рекомбинация Вземете нова популация потомци Мутации поколения 5

3. Моделиране на проблеми Първоначална популация Установяване на представителност - ген - индивид Определяне на броя на индивидите в популацията Установяване на функция за оценка (цел) Първоначална популация (гени) произволно създадена селекция Селекция - извличане на подмножество гени от съществуваща популация като дефиниция на качеството - функцията за оценка Определя лицата, избрани за рекомбинация и колко потомци всеки индивид произвежда

Моделиране на проблеми Критерий за спиране Решение за мултипопулация GA, което отговаря на критерия брой поколения Бюджет на плато за най-добра годност Мултипопулация GAs По-добри резултати - субпопулации Всяка популация се развива отделно Индивидите се променят след няколко поколения 7

Избор (1) Първа стъпка: присвояване на фитнес - пропорционално присвояване - възлагане въз основа на ранг (2) Ефективен подбор: родителите се избират във фитнес въз основа на един от алгоритмите: селектиране на колела на рулетка стохастично универсално вземане на проби stohastica) местна селекция (местна селекция) турнирна селекция (турнирна селекция) съкратена селекция (съкратена селекция) 8

Реинтеграция на потомството - ако се появят по-малко индивиди или по-малко деца, тогава допълнителни индивиди трябва да бъдат реинтегрирани в новата популация.Алгоритъмът за подбор определя схемата за реинтеграция (обикновено) глобална реинтеграция - в цялата популация за. избор на колело на рулетка, универсално стохастично вземане на проби, избор на отрязване местно повторно вмъкване за локален избор 9

Кросоувър/рекомбинация Рекомбинацията създава нови индивиди чрез комбиниране на информация от родители (родители - чифтосваща се популация). Различни схеми за рекомбинация Една възможност - случайно чифтосване Същото като генетично кръстосване над PM процент на новонаселените индивиди се избират и произволно сдвояват. Точка на кръстосване се избира за всяка двойка (еднаква или различна вероятност) Информацията се обменя между двете лица, базирани на точка 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) Директно присвояване въз основа на целевата функция ИЛИ Присвояване въз основа на механизъм Всеки индивид от популацията получава стойност на пригодност Въз основа на стойността на пригодността изборът (S) се извършва съгласно схема за подбор 18

Селекция Вероятността за възпроизвеждане може да бъде свързана с индивид - това зависи от стойността на фитнес функцията на индивида и стойността на фитнес функцията на останалите индивиди от популацията. Тази вероятност може да се използва при селекция 19

Условия на натиск за избор: вероятността за избор на най-добрия индивид в сравнение със средната вероятност за селекция на всички индивиди се разпространява: диапазонът от стойности на броя на потомците на индивидуална загуба на разнообразие: делът на индивидите в популацията, който не е избран интензитет на селекция: средна годност на популацията след прилагане на ковариация за избор на метод за подбор: ковариация на разпределението на фитнес на популацията след прилагане на метод на подбор

А1. Пропорционално задание за фитнес Всеки ген има свързана годност Изчислете средната годност на популацията Всеки индивид ще бъде копиран в новата популация във фитнес фитнес в сравнение със средната фитнес средна фитнес 5,76, индивидуална фитнес 20,21 - копиране 3 пъти Лица с фитнес равна или по-ниска средно игнориране Ново население - може да е по-малко Ново население е запълнено с произволно избрани индивиди от старото население 21

А2. Присвояване на фитнес въз основа на ранга Фитнесът, присвоен на всеки индивид, зависи само от неговата позиция сред индивидите в популацията. Позицията на индивид в популацията зависи от целевата функция Pos = 1 - най-малко добрият Pos = Nind - най-добрият Популацията се подрежда според фитнес 22

Фитнес назначение въз основа на Nind rank - брой индивиди в популацията Pos - позиция на индивида в популацията (най-лоша Pos = 1, най-добра Pos = Nind) SP - селективен натиск (вероятност за избор на най-добрия индивид спрямо вероятността среден подбор на всички индивиди) Линеен ранг Фитнес (Поз) = 2 - SP + 2 * (SP - 1) * (Поз - 1)/(Nind - 1) Линейният ранг позволява SP стойности в (1.0, 2.0]. на избора на човек за рекомбинация е пригодността (нормализирана) в сравнение с общата годност на популацията 23

Присвояване на фитнес въз основа на ранг Нелинеен ранг: Fitness (Pos) = Nind * X (Pos - 1)/ i = 1, Nind (X (i - 1)) X се изчислява като корен на полинома: 0 = (SP - Nind ) * X (Nind - 1) + SP * X (Nind - 2) +. + SP * X + SP Нелинеен диапазон позволява SP стойности в [1.0, Nind - 2.0] SP по-висока Вероятността да се избере индивид за рекомбинация е фитнес (нормализиран) спрямо общата годност на популацията 24

Задание за фитнес въз основа на Линеен ранг SP = 2  0.2 SP = 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

S1. Избор на колело на рулетка или стохастично вземане на проби с заместване на 11 индивида, линеен ранг и SP = 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,2 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] - толкова указатели, колкото индивида ще бъдат избрани NPointer - брой индивиди, които трябва да бъдат избрани Разстояние между указатели 1/Npointer Позицията на първия указател се дава от произволно число в диапазона [0.1/NPointer]. За да изберат 6 индивида, разстоянието между указателите е 1/6 = 0,167. 1 произволно число в диапазона [0, 0,167]: 0,1. 1, 2, 3, 4, 6, 8 29

S3. Местен подбор Всеки индивид е в квартал Структуриране на популацията Квартал - група индивиди, които могат да рекомбинират (потенциален) Линеен квартал: пълен и половин пръстен 30

След това се дефинира квартал за всеки избран човек. Местен подбор Първата половина от популацията се избира произволно (или с помощта на алгоритъм за подбор - стохастично вземане на проби или турнир). След това се дефинира квартал за всеки избран човек. Изберете друг човек за рекомбинация в квартала (най-добре, фитнес пропорционално или произволно). 32

Локален подбор Разстояние на изолация между индивидите Колкото по-малък е кварталът, толкова по-голяма е изолацията Припокриващи се квартали - възниква предаване на характеристиките Размерът на квартала определя скоростта на разпространение Бързо разпространение срещу поддържане на голямо разнообразие Високо разнообразие - предотвратява преждевременното сближаване 33

S4. Избор на турнир Броят на индивидите от популацията се избира на случаен принцип и като родител се избира най-добрият индивид. Процесът се повтаря за това колко индивида искаме да изберем. Параметърът за размера на турнира е Тур. Обиколка - стойности между 2. Nind Връзка между обиколка и интензивност на селекцията Размер на турнира 1 2 3 5 10 30 Интензивност на селекцията 0,56 0,85 1,15 1,53 2,04 Средна стойност на фитнес на населението след прилагане на метод за подбор 34

Избор на турнир Интензивност на избора: SelIntTour (Tour) = sqrt (2 * (log (Tour) -log (sqrt (4.14 * log (Tour))))))) Загуба на разнообразие: LossDivTour (Tour) = Tour - (1/(Tour -1)) - Обиколка - (Обиколка/(Обиколка-1)) (Приблизително 50% от населението е загубено за Обиколка = 5). Ковариация на селекцията: SelVarTour (Tour) = 1- 0,096 * дневник (1 + 7,11 * (Tour-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 Рекомбинация на многоточкови m кръстосани позиции ki индивидуални 1: 0 1 1 1 0 0 1 1 0 1 0 индивидуални 2: 1 0 1 0 1 1 0 0 1 0 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 Еднородна рекомбинация Генерализира простата двоична и многоточкова кръстосана маска - със същия размер като индивида; произволно създадени и паритетът на битовете в маската показва кой родител ще даде на потомството кой бит поотделно 1: 0 1 1 1 0 0 1 1 0 1 0 поотделно 2: 1 0 1 0 1 1 0 0 1 0 1 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