Політехнічний університет Бухарестського університету рік - ppt завантажити
Політехнічний університет Бухареста Навчальний рік 2008-2009 Автоматичне навчання Політехнічний університет Бухареста Навчальний рік 2008-2009 Адіна Магда Флореа http://turing.cs.pub.ro/inva_09 та curs.cs.pub.ro
№ курсу 9 Генетичні алгоритми Вступ Основна схема Моделювання проблем Приклад Вибір Рекомбінація мутації TSP з генетичними алгоритмами Паралельне впровадження AG 2
1. Вступ Г.А. - США, Дж. Х. Голланд (1975) Еволюційні алгоритми - Німеччина, І. Рехенберг, Х.-П. Швефель (1975-1980) Генетичне програмування (1960-1980, 2000) Дж. Коза Оптимізація Економічні моделі Екологічні моделі Моделі навчання соціальних систем 3
Вступ - рахунок діє на популяцію особин = потенційні рішення - застосовує принцип виживання, заснований на адаптації (придатності) Кожне покоління - новий підхід до рішення Еволюція популяції особин, які краще адаптуються до середовища Моделює природні процеси: відбір, рекомбінація, мутація, міграція, місцезнаходження Населення - паралельний пошук 4
2. Основна схема Генерує популяцію вихідних особин (генів) Представлення проблеми Фітнес-функція Генерує популяцію початкових особин (генів) Оцінює цільову функцію Критерій зупинки дотриманий? так ні найкращі особи Початок Вибір результатів Кросовер/рекомбінація Отримати нову популяцію нащадків Мутація 5 поколінь
3. Моделювання проблеми Початкова популяція Встановити представництво - ген - індивід Визначити кількість особин у популяції Встановити функцію оцінки (ціль) Початкова популяція (гени) випадково створена Селекція Виділення - вилучення підмножини генів із існуючої популяції як визначення якості - функція оцінки Визначає особин, відібраних для рекомбінації, і скільки нащадків дає кожна людина 6
Моделювання проблеми Критерій зупинки Рішення багатопопуляційних ГА, що відповідає критерію Кількість поколінь Бюджет плато для найкращої придатності Мультипопуляційні ГА Кращі результати - субпопуляції Кожна популяція еволюціонує окремо Індивідууми змінюються через кілька поколінь 7
Вибір (1) Перший крок: придатність до фітнесу - пропорційне присвоєння - присвоєння рангу (2) Ефективний відбір: батьків відбирають у формі на основі одного з алгоритмів: вибір колеса рулетки стохастична універсальна вибірка stohastica) місцевий відбір (місцевий відбір) відбір турніру (відбір турніру) відсікання відбору (усічений відбір) 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) Перевірте, чи є якість найкращої людини достатньо доброю, якщо ви зупинитеся, перейдіть на
5. Відбір Першим кроком є призначення придатності (F) Пряме присвоєння на основі цільової функції АБО Призначення на основі механізму Кожна особа в популяції отримує значення придатності На основі значення придатності вибір (S) робиться відповідно до схеми відбору 18
Відбір Імовірність розмноження може бути пов’язана з особиною - вона залежить від величини функції придатності особини та значення функції пристосованості решти особин у популяції. Ця ймовірність може бути використана при відборі 19
Термін тиску на відбір: ймовірність відбору найкращої особини порівняно із середньою ймовірністю відбору всіх особин: діапазон значень кількості нащадків особини, втрата різноманітності: частка особин у популяції, яка не відібрана інтенсивність відбору: середнє значення придатності популяції після застосування методу відбору коваріації: коваріація розподілу придатності популяції після застосування методу відбору 20
А1. Пропорційне призначення фітнесу Кожен ген має відповідну фізичну форму Розрахуйте середню фізичну форму популяції Кожна особа буде скопійована в новій популяції у фітнес-фітнесі порівняно із середньою фітнес-формою 5,76, індивідуальною фізичною формою 20,21 - копіювати 3 рази Особи з фізичною формою, рівною або меншою в середньому ігнорувати Нове населення - може бути менше Нове населення заповнене випадково обраними особами зі старого населення 21
А2. Призначення фітнесу на основі ранжування Фітнес, який призначається кожній особі, залежить лише від її положення серед осіб у популяції. Положення індивіда в популяції залежить від цільової функції Pos = 1 - найменш хороший Pos = Nind - найкращий Населення впорядковується відповідно до фітнес 22
Призначення фітнесу на основі рангу Nind - кількість особин в популяції Pos - положення особи в популяції (найгірший Pos = 1, найкращий Pos = Nind) SP - тиск підбору (ймовірність вибору найкращої особини щодо ймовірності середній вибір усіх осіб) Лінійний ранг Фітнес (Позиція) = 2 - SP + 2 * (SP - 1) * (Позиція - 1)/(Nind - 1) Лінійний ранг допускає значення SP в (1,0, 2,0). відбором особи для рекомбінації є придатність (нормалізована) порівняно із загальною придатністю населення 23
Призначення фітнесу на основі рангу Нелінійний ранг: Фітнес (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/Nпокажчик Положення першого покажчика задано випадковим числом в діапазоні [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 (Тур) = 1- 0,096 * журнал (1 + 7,11 * (Тур-1)), SelVarTour (2) = 1-1/ 35
6. Кросовер/рекомбінація Виробляє нових людей шляхом рекомбінації батьківської інформації Бінарні подання двійкові багатоточкові одноманітні Цілі/реальні подання дискретні реальні лінійні проміжні 36
6.1 Бінарна рекомбінація Випадково обрана позиція кросовера 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 маска 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/м, інакше 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