X Код для використання на сайті:
Ширина px

Скопіюйте цей код і вставте його на свій сайт

X Для завантаження презентації, скористайтесь соціальною кнопкою для рекомендації сервісу SvitPPT Завантажити собі цю презентацію

Презентація на тему:
Генетичні алгоритми

Завантажити презентацію

Генетичні алгоритми

Завантажити презентацію

Презентація по слайдам:

Слайд 1

Генетичні алгоритми генетичні успадкування — концептуальна засада генетичних алгоритмів загальна схема генетичних алгоритмів доступне програмне забезпечення генетичних алгоритмів

Слайд 2

У загальному значенні генетичні алгоритми (Genetic Algorithms) — це тип алгоритмів, інспірованих механізмами еволюції живої природи, які застосовуються, головно, до задач глобальної оптимізації (зокрема, задач комбінаторної оптимізації) і деякою мірою для дейтамайнінгу, зокрема, для комбіну вання шаблонів з правил індукції, які були відкриті до цього, навчання нейромереж, пошуку зразків у даних, відкриття шаб лонів у тексті тощо. Генетичні алгоритми належать нині до стан дартного інструментарію методів дейтамайнінгу. Генетичні успадкування — концептуальна засада генетичних алгоритмів

Слайд 3

Ідея генетичних алгоритмів запозичена з живої природи і по лягає в машинній організації еволюційного процесу створення, модифікації' і відбору кращих розв'язків, виходячи з того, що в процесі відтворення і модифікації розв'язків кращі з них (подібно До процесу селекції в рослинництві й тваринництві) можуть дати Ще ліпших «нащадків», тобто нові, прийнятніші варіанти розв'я зання задачі. Щоб краще зрозуміти концептуальні засади генети чних алгоритмів, зупинимося на короткому огляді механізмів природного добору і генетичного успадкування, що розглядаються в еволюційній теорії зародження і розвитку життя на нашій планеті. Ця теорія стверджує, що кожний біологічний вид ціле спрямовано розвивається й змінюється так, щоб у найкращий спосіб пристосуватися до навколишнього середовища.

Слайд 4

Ключову роль в еволюції відіграє природний добір. Його суть полягає в тому, що найпристосованіші особи краще виживають і приносять більше потомства, ніж менш пристосовані. При цьому завдяки передаванню генетичної інформації, що називається ге нетичним успадковуванням, нащадки успадковують від батьків основні властивості. Проте слід зауважити, що сам по собі при родний добір ще не забезпечує розвитку біологічного виду. Дій сно, якщо передбачити, що всі нащадки народжуються приблиз но однаковими, то покоління будуть відрізнятися тільки за чисе льністю, але не за пристосованістю. Тому дуже важливо вивчити, у який спосіб відбувається успадкування, тобто як властивості нащадка залежать від властивостей батьків. Основний закон успадкування полягає в тому, що нащадки схожі на своїх батьків. Зокрема, нащадки пристосованіших бать ків будуть напевно одними з найпристосованіших у своєму поко лінні. Щоб зрозуміти, на чому грунтується ця схожість, нам по трібно буде трохи заглибитися в будову клітини тварин.

Слайд 5

Майже в кожній клітині будь-якої тварини є ряд хромосом, що несуть інформацію про цю тварину. Основна частина хромосоми — нитка ДНК (молекула дезоксирибоза Нуклеїнової Кислоти), яка складається з чотирьох видів спеціальних з'єднань (молекул) — нуклеотидів, що чергуються в певній послідовності. Нуклеотиди позначають буквами А, Т, С і G, і саме порядок їх розміщення є кодом усіх генетичних властивостей даного організму. Кажучи точніше, ДНК визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати ме. Отже, генетичний код окремого індивідуума — це просто дуже довгий рядок комбінацій із чотирьох букв А, Т, С і G, а сам ген — це відрізок ланцюга ДНК, що відповідає за певну власти вість особи, наприклад за колір очей, тип волосся, колір шкіри і т. д. Різні значення генів називають аллелями. Вся сукупність гене тичних ознак людини кодується за допомогою приблизно 60 тис. генів, які разом містять більше ніж 90 млн нуклеотидів.

Слайд 6

Розрізняють два види клітин: статеві (такі, як сперматозоїд і яйцеклітина) і соматичні. У кожній соматичній клітині людини міститься 46 хромосом. Ці 46 хромосом насправді є 23 парами, причому в кожній парі одна з хромосом отримана від батька, а друга — від матері. Парні хромосоми відповідають за такі самі ознаки, наприклад, батьківська хромосома може містити ген чор ного кольору очей, а парна їй материнська — ген блакитних очей. Існують певні закони, що керують участю тих або інших генів у розвитку особи. Зокрема, в нашому прикладі нащадок буде чор нооким, оскільки ген блакитних очей є «слабким» (рецесивним) \ пригнічується домінантним геном будь-якого іншого кольору. У статевих клітинах хромосом тільки 23, і вони непарні. У мо мент запліднення відбувається злиття чоловічої і жіночої статевих клітин і утворюється клітина зародка, що містить якраз 46 хромо сом. Які ж властивості нащадок отримає від батька, а які від мате рі? Це залежить від того, які саме статеві клітини брали участь у заплідненні. Річ у тім, що процес вироблення статевих клітин (так званий мейоз) в організмі схильний до випадковості, із-за чого нащадки все ж багато чим відрізняються від своїх батьків.

Слайд 7

У мейозі, зокрема, відбувається наступне: парні хромосоми со матичної клітини зближуються впритул, потім їх нитки ДНК розри ваються в кількох випадкових місцях і хромосоми обмінюються своїми ідентичними ділянками. Цей процес забезпечує появу нових варіантів хромосом І називається перехрещуванням хромосом або кросинговером (від анг. crossing-over). Кожна з хромосом, що знову з'явилася, виявиться потім усередині однієї зі статевих клітин, і її генетична інформація може реалізуватися в нащадках даної особи. Другим важливим чинником, що впливає на спадковість, £ мутації, тобто раптові спадкові зміни організму або його частин, ознак, властивостей, які виражаються у зміні деяких дільниць ДНК. Мутації також випадкові і можуть бути викликані різними зовнішніми чин никами, такими, наприклад, як радіоактивне опромінення. Якщо му тація сталася в статевій клітині, то змінений ген може передатися на щадку й виявитися у вигляді спадкової хвороби або в інших нових властивостях нащадка. Вважається, що саме мутації є причиною по яви нових біологічних видів, а кросинговер визначає мінливість уже всередині виду (наприклад, генетичні відмінності між людьми).

Слайд 8

Важливе місце в еволюційній теорії відводиться поняттю по пуляції як елементарній еволюційній одиниці. Популяція — це сукупність особин певного виду організмів, які здатні до вільного схрещування, населяють певну територію і деякою мірою ізольо вані від сусідніх популяцій. У рамках кожної популяції відбува ється процес розмноження — репродукції (Reproduction), що являє собою комбінацію послідовностей (strings, хромосом) у опуляци для створення нової послідовності (нащадка). За реродукціі нащадок бере частини позицій генів від обох батьків, матиме частину ознак кожного із них. На рис. 9.13а) показана спрощена схема процесу репродукції, де ознаки батьків виражені хромосомою, котра складається з шести генів, що мають дві аллелі, позначені на схемі нулями і одиницями. Нащадок отримав чотири гени від другого батька (перша, друга, третя і шоста по зиція) і два від першого (четверта і п'ята позиції).

Слайд 9

У генетичних алгоритмах важливе значення мають: форму вання початкового ряду елементів (популяції), операції кросинговера, що в теорії генетичних алгоритмів частіше називають кросовером (Cross-over), і мутації (Mutation). Кросовер -— це комбінування (змішування) хромосом шляхом замін значень генів і утворення нових хромосом на їх місцях. На рис. 9.13 б) наведена спрощена схема кросовера, де показано, як шляхом заміни ідентичних ділянок двох батьків отримані два нащадки з новими ознаками. Мутація — спонтанне перетворення (видозміна) символів (характерних особливостей) у послідовності (хромосомі). На рис. 9 в) показано, як у результаті мутації п'ятого гена (зна чення 0 замінено 1) отримана нова хромосома.

Слайд 10

Слайд 11

а) репродукції осіб популяції; б) кросовера осіб популяції; в) мутації хромосоми ці процеси можуть комбінуватися для формування гібридних операторів, операцій репродукції (відтворення) і схрещування з тим, щоб бути спроможними створювати конкуренцію між попу ляціями.

Слайд 12

Загальна схема генетичних алгоритмів У концептуальному плані загальна схема генетичних алгоритмів досить проста. Спочатку генерується початкова попу ляція особин (індивідуумів, хромосом), тобто деякий ряд розв'язків задачі. Як правило, це робиться випадково. Потім не обхідно змоделювати розмноження всередині цієї популяції. Для цього випадково підбираються кілька пар індивідуумів, прово диться схрещування хромосом у кожній парі, а отримані нові хромосоми поміщають у популяцію нового покоління. У генетич ному алгоритмі зберігається засадний принцип природного до бору: чим пристосованіший індивідуум (чим більше відповідне йому значення цільової функції), тим з більшою ймовірністю він буде брати участь у схрещуванні.

Слайд 13

У концептуальному плані загальна схема генетичних алгоритмів досить проста. Спочатку генерується початкова попу ляція особин (індивідуумів, хромосом), тобто деякий ряд розв'язків задачі. Як правило, це робиться випадково. Потім не обхідно змоделювати розмноження всередині цієї популяції. Для цього випадково підбираються кілька пар індивідуумів, прово диться схрещування хромосом у кожній парі, а отримані нові хромосоми поміщають у популяцію нового покоління. У генетич ному алгоритмі зберігається засадний принцип природного до бору: чим пристосованіший індивідуум (чим більше відповідне йому значення цільової функції), тим з більшою ймовірністю він буде брати участь у схрещуванні.

Слайд 14

Потім моделюються мутації в кількох випадково вибраних особинах нового покоління, тобто змінюються деякі гени. Після цього стара популяція частково або повністю знищується і ми пе реходимо до розгляду наступного покоління. Популяція наступно го покоління в більшості реалізацій генетичних алгоритмів містить стільки ж особин, скільки й початкова, але внаслідок відбору пристосованість (значення цільової функції) у ній в середньому вища. Операція доведення кількості особин поточної популяції до початково визначеної величини називається редукцією. Опи сані процеси відбору, схрещування і мутації повторюються вже Для цієї нової популяції. У кожному наступному поколінні буде спостерігатися виник нення абсолютно нових розв'язків задачі. Серед них будуть як погані, так і кращі, але завдяки процедурі добору кількість кра щих розв'язків буде зростати. Зауважимо, що в природі не буває абсолютних гарантій, і навіть найпристосованіший тигр може за гинути від пострілу мисливця, не залишивши потомства. Імітую чи еволюцію в комп'ютері, можна уникати подібних небажаних подій і завжди зберігати життя кращому з індивідуумів поточно-0 покоління. Така методика називається «стратегією елітизму», коли в наступне покоління відбираються особини з найкращими показниками.

Слайд 15

Описана послідовність дій за реалізації генетичних алгоритмів може перетворюватися в різні програмні реалізації залежно від типу розв'язуваної задачі і вибраних для цього підходів. Зокрема, в низці випадків може вводитися інша, ніж описана вище, єрархія базових понять, наприклад, кожний індивідуум може характери зуватися низкою хромосом, котрі, у свою чергу, містять різні ти пи генів. Пояснимо на прикладі. Нехай розглядається завдання вибору плану вкладення коштів у вибрані наперед N інвестиційних проектів, причому потрібно визначити обсяги вкладень коштів у кожний проект так, щоб за гальний їх обсяг в усі проекти не перевищував величину D, а ви браний критерій ефективності, наприклад рівень рентабельності інвестицій (прибуток на капітал, ROI — Return on Investment), набував максимального значення. Розв'язуючи цю задачу за ге нетичним алгоритмом, вважатимемо, що кожен індивідуум — це інвестиційний план, який містить N хромосом, кожна з яких яв ляє собою вектор із нулів та одиниць — двійковий вираз обсягу вкладень у даний проект. Якщо довжина хромосоми дорівнює ві сьмом двійковим розрядам, то потрібне попереднє нормування всіх чисел на інтервалі від 0 до 255 (усього значень 28). Такі хромосоми називаються безперервними і уможливлюють подан ня значень довільних числових параметрів.

Слайд 16

Мутації безперервних хромосом випадковим способом змі нюють у них один біт (ген), впливаючи у такий спосіб на значен ня параметра. Кросовер також можна здійснювати стандартно, об'єднуючи частини відповідних хромосом (з однаковими номе рами) різних індивідуумів. Особливістю цієї задачі є те, що зага льний обсяг капіталу, що інвестується, фіксований і дорівнює D. Очевидно, що із-за мутацій і схрещувань можна отримувати розв'язки, для реалізації яких потрібний капітал, більший або менший ніж D. У генетичному алгоритмі використовується спе ціальний механізм аналізування таких розв'язків, що дає змогу враховувати обмеження типу «сумарний капітал = D " за підра хунку пристосованості індивідуума. У процесі еволюції особини з суттєвим порушенням зазначених обмежень «вимирають». Унаслідок дії алгоритму отриманий розв'язок за сумарним капі талом може не дорівнювати точно, але бути близьким до заданої величини D. У процесі роботи генетичного алгоритму оцінюється значення цільової функції для кожного плану і здійснюється опе рація редукції для всієї популяції.

Слайд 17

Цю саму задачу можна подати і в іншій генетичній інтерпре тації, якщо ввести умову, що кожний із інвестиційних проектів aбо цілком приймається, або відхиляється. Тоді кожний варіант плану (хромосому) можна подати у вигляді послідовності з N нулів та одиниць, причому, якщо на цьому місці в хромосомі сто їть одиниця, то це означає, що і-й проект (і - 1, 2, ..., ЛО вклю чений у план, а якщо нуль — не включений. Популяція склада ється із кількох варіантів планів. Визначення допустимості пла нів і оцінювання їх за вибраними критеріями проводиться ана логічно.

Слайд 18

У загальному вигляді стратегію отримання рішень за допомо гою генетичних алгоритмів можна реалізувати такими кроками: 1) ініціалізуйте популяцію; 2) виберіть батьків для репродукції і оператори мутації і кросовера; 3) виконайте операції, щоб згенерувати проміжну популяцію індивідуумів і оцінити їхні придатності; 4) виберіть членів популяції для отримання нової генерації (версії); 5) повторюйте кроки 1—З, поки не буде досягнуте деяке пра вило зупинки. На рис. 10 показана узагальнена схема реалізації генетично го алгоритму. До його основних характеристик належать: розмір популяції, оператор кросовера і ймовірність його використання, оператор мутації і її ймовірність, оператор селекції, оператор ре дукції, правило (критерій) зупинки процесу виконання генетич ного алгоритму. Оператори селекції, кросовера, мутації і редукції ще називають генетичними операторами.

Слайд 19

Критерієм зупинки процесу здійснення генетичного алгорит му може бути одна з трьох подій: • сформовано задану користувачем кількість поколінь; • популяція досягла заданої користувачем якості (наприклад, значення якості всіх особин перевищило задану порогову вели чину); • досягнутий деякий рівень збіжності. Тобто особини в попу ляції стали настільки подібними, що дальше їх поліпшення відсувається надзвичайно повільно, і тому продовження здійснення ітерацій генетичного алгоритму стає недоцільним. Після завершення роботи генетичного алгоритму з кінцевої популяції вибирається та особина, яка дає максимальне (або мі німальне) значення цільової функції і, отже, є результатом здій снення генетичного алгоритму. За рахунок того, що кінцева популяція краща, ніж початкова, отриманий результат являє собою поліпшене рішення.

Слайд 20

Слайд 21

Доступне програмне забезпечення генетичних алгоритмів Генетичні алгоритми нині можна застосовувати в різ них галузях. їх успішно використовують для розв'язування низки великих і економічно важливих задач у бізнесі і в інженерних розробках. З їх допомогою були розроблені промислові проектні рішення, що уможливили багатомільйонну економію витрат. Фі нансові компанії широко використовують ці засоби у разі про гнозування розвитку фінансових ринків для управління пакетами цінних паперів. Нарівні з іншими методами генетичні алгоритми, зазвичай, використовуються для оцінювання значень безперерв них параметрів моделей великих розмірностей, для розв'язування комбінаторних задач, для задач з оптимізації, що містять одночас но безперервні і дискретні параметри. Іншою галуззю їх застосування є використання в системах добування нових знань із вели ких баз даних, створення і навчання стохастичних мереж, на вчання нейронних мереж, оцінювання параметрів у задачах бага товимірного статистичного аналізу, отримання початкових даних для виконання інших алгоритмів пошуку і оптимізації. Все це зумовило зростання заінтересованості фірм-розробників комер ційного програмного забезпечення стосовно генетичних алгорит мів, що в кінцевому результаті привело до появи на ринку бага тьох програмних продуктів такого виду.

Слайд 22

Незважаючи на те, що розв'язання конкретної оптимізаційної за дачі часто потребує побудови генетичного алгоритму з унікальними значеннями параметрів, низка базових властивостей цих алгоритмів залишається постійною за розв'язання абсолютно різних задач. То му здебільшого для реалізації конкретного генетичного алгоритму не потрібно створювати окремий програмний продукт. Опишемо кілька прикладів програмного забезпечення, що дає змогу реалізовувати широкий набір генетичних алгоритмів, які можна застосовувати для розв'язування найрізноманітніших за дач. Змінними параметрами генетичних алгоритмів у таких додат ках, зазвичай, є різні значення ймовірностей, розмір популяції і низка специфічних властивостей алгоритму. Проте реалізація ге нетичних операторів, як правило, єдина для всіх алгоритмів і прихована від користувача.

Слайд 23

Пакет Evolver 4.0 компанії Palisade Corp. Пакет Evolver яв ляє собою доповнення до програми MS Excel версій 5.0 і 7.0. При цьому Excel використовується як засіб опису початкових даних алгоритму і розрахунків у процесі його виконання. У процесі установки Evolver додає в Excel додаткову панель інструментів, яка забезпечує доступ до пакета. Якщо Evolver не запущений для виконання, то панель інструментів не відображається. У разі за пуску Evolver додаток Excel запускається автоматично.

Слайд 24

Пакет GeneHunter 1.0 компанії Ward System Group. Пакет GeneHunter багато чим схожий з пакетом Evolver. Він також є над будовою над MS Excel версій 5.0 і 7.0 і запускається з меню «Сер віс». Цей пакет русифікований і має низку додаткових настройок для генетичних алгоритмів: включення стратегій елітизму й різно манітності. Поля вікна GeneHunter практично такі самі як і в Evolver. Однак його вікно має низку відмінностей. Для установки параметрів алгоритму служить кнопка «Параметри...». Параметри генетичного алгоритму не зберігаються автоматично з файлом Eхсel. Для збереження параметрів служить кнопка «Модель», після натиснення на яку з'являється відповідне діалогове вікно.

Слайд 25

Пакет Genetic Training Option (GTO) компанії California Scientific Software. Пакет GTO є додатковою утилітою, що поста вляється для нейропакета BrainMaker виробництва компанії «California Scientific Software». Він застосовується як для побу дови нейронних мереж, так і для поліпшення створеної за допо могою BrainMaker мережі. Але в обох випадках окремо від BrainMaker використовуватися не може. Генетичні алгоритми складні для створення, але прості в засто суванні — потребують від користувача тільки формалізації задачі й формування початкових даних. Така ситуація багато в чому сприяє розширенню галузей застосування генетичних алгоритмів.

Завантажити презентацію

Презентації по предмету Біологія