ОБРОБКА І ПЕРЕДАЧА ІНФОРМАЦІЇ. СУЧАСНІ КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ - Золота колекція рефератів - 2018

ГЕНЕТИЧНІ АЛГОРИТМИ — СИНТЕЗ ІНФОРМАТИКИ Й БІОЛОГІЇ

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

Мета цього проекту — огляд вищезгаданої теми, для того щоб надалі розробити систему, що генерує рішення за допомогою генетичних алгоритмів. Нижче буде докладно освітлена ця тема й порушені найважливіші аспекти цього завдання. Спочатку заглянемо в джерело цих алгоритмів.

ПРИРОДНИЙ ДОБІР У ПРИРОДІ

Еволюційна теорія стверджує, що кожний біологічний вид цілеспрямовано розвивається й змінюється для того, щоб якнайкраще пристосуватися до навколишнього середовища. У процесі еволюції багато видів комах і риб набули захисного забарвлення, їжак став невразливим завдяки голкам, людина стала власником складної нервової системи. Можна сказати, що еволюція — це процес оптимізації всіх живих організмів. Розглянемо, якими ж засобами природа вирішує завдання оптимізації.

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

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

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

При розмноженні тварин відбувається злиття двох батьківських статевих клітин, і їх ДНК взаємодіють, утворюючи ДНК нащадка. Основний спосіб взаємодії — кросовер (cross-over, схрещування). При кросовері ДНК предків діляться на дві частини, а потім обмінюються своїми половинками.

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

ЩО ТАКЕ ГЕНЕТИЧНИЙ АЛГОРИТМ

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

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

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

Генетичний алгоритм — це проста модель еволюції в природі, реалізована у вигляді комп’ютерної програми. У ньому використовуються як аналог механізму генетичного спадкування, так і аналог природного добору. При цьому зберігається біологічна термінологія в спрощеному вигляді.

Ось як моделюється генетичне спадкування:

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

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

Добір у генетичному алгоритмі — це процес формування нової популяції зі старої, після чого стара популяція гине. Після добору до нової популяції знову застосовуються операції кросовера й мутації, потім знову відбувається добір, і так далі.

Добір у генетичному алгоритмі тісно пов’язаний із принципами природного добору в природі в такий спосіб:

Таким чином, модель добору визначає, як слід будувати популяцію наступного покоління. Як правило, ймовірність участі індивідуума в схрещуванні береться пропорційною до його пристосованості. Часто використовується так звана стратегія елітизму, при якій кілька найкращих індивідуумів переходять у наступне покоління без змін, не беручи участі в кросовері й доборі. У будь-якому випадку кожне наступне покоління буде в середньому кращим за попереднє. Коли пристосованість індивідуумів перестає помітно збільшуватися, процес зупиняють і як розв’язок завдання оптимізації беруть найкращого зі знайдених індивідуумів.

Повертаючись до завдання оптимального розподілу інвестицій, пояснимо особливості реалізації генетичного алгоритму в цьому випадку.

Індивідуум - варіант розв’язання завдання = набір з 10 хромосом Xj.

Хромосома Xj = обсяг вкладення в проект j = 16-розрядний запис цього числа.

Оскільки обсяги вкладень обмежені, не всі значення хромосом є припустимими. Це враховується при генерації популяцій.

Оскільки сумарний обсяг інвестицій фіксований, то реально варіюються тільки 9 хромосом, а значення 10-ої визначається за ними однозначно.

Докладний опис генетичного алгоритму

1. Створення структури розв’язання цього завдання у вигляді масиву а[і], і = 1,... n, де n — максимальна кількість компонентів структури. Приклад: пошук функції у = f(x) найкращого в класі поліномів наближення експериментальних точок {x_i, y_i}, j = 1,... m.

Структура визначається бітовим масивом, де кожному елементу масиву відповідає найпростіший багаточлен типу x_i, і = 1, ... n, де n — максимальний ступінь полінома.

2. Створення показника ефективності структури, заповненої конкретними значеннями. Приклад: показником ефективності для нашого прикладу буде величина, визначена методом найменших квадратів J_a = І₁ + І₂ + …+ І_m,

де I_j = (y_j-f_a(x_j))², f_a(x) є сумою всіх елементів виду а_iх¹ а_x = 0 або 1.

3. Завдання деякого масиву різних структур S_k, k = 1…N, розмірністю N, більшою, ніж кількість компонентів n у структурі.

Цей масив можна згенtрувати випадково, задавши нулі й одиниці в кожній структурі.

4. Розрахунок показників ефективності J_k для кожної структури S_k за формулою, заданою в пункті 2.

5. Природний добірструктурзадеяким правилом вибору найкращих структур серед заданого масиву структур. Приклад: можна за правилом виду J₀= M(J_k) — середнє значення J_k, якщо.J_к <J₀, то структура залишається, інакше вмирає. Якщо різниця між попереднім J₀ і новим J₀ менша від якогось малого числа, то кінець розрахунку.

6. Заміна вибулих структур новими, породженими від найбільш пристосованих структур за допомогою генетичних операторів:

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

Приклад: з (1,1,0,1,0,0,1,0) вийде (1,1,0,1,1,0,1,0);

б) інверсія — перестановка в структурі певної її частини навпаки.

Приклад:з (1,1,0,1,0,0,1,0) вийде(1,1,0,0,1,0,1,0);

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

Приклад: з (А, В, С, D, Е) і (a, b, с, d, е) вийде (А, В, с, d, Е).

7. Перехід до етапу 4.

Вплив параметрів генетичного алгоритму на ефективність пошуку. Оператори кросовера й мутації

Найтрадиційнішим підходом є відхід від традиційної схеми «розмноження», що використовується в більшості реалізованих ГА-мах і повторює класичні схеми. Класична схема припускає обмеження чисельності нащадків шляхом використання так званої ймовірності кросовера. Така модель надає величині, що відповідає чисельності нащадків, недетермінованого характеру. Є метод, що пропонує відійти від імовірності кросовера й використовувати фіксовану кількість шлюбних пар на кожному поколінні, при цьому кожна шлюбна пара «дає» двох нащадків. Такий підхід ефективний тим, що робить процес пошуку більш керованим і передбачуваним у плані обчислювальних витрат.

Як генетичні оператори одержання нових генотипів «нащадків», використовуючи генетичну інформацію хромосомних наборів батьків, застосовуються два типи кросоверів — одно- і двухточковий. Обчислювальні експерименти показали, що навіть для простих функцій не можна говорити про перевагу того або іншого оператора. Більше того, було показано, що використання механізму випадкового вибору одно- або двухточкового кросовера для кожної конкретної шлюбної пари часом виявляється ефективнішим, ніж детермінований підхід до вибору кросоверів, оскільки досить важко визначити, який з двох операторів більше підходить для кожного конкретного ландшафту пристосованості. Натомість використання випадкового вибору мало па меті насамперед згладити розходження цих двох підходів і поліпшити показники середнього очікуваного результату. Для всіх представлених тестових функцій так і відбулося: випадковий вибір виявився ефективнішим за найгірший.

Підвищення ефективності пошуку при використанні випадкового вибору операторів кросовера викликало застосування аналогічного підходу при реалізації процесу мутагенезу нових особин, однак у цьому випадку перевага перед детермінованим підходом не настільки очевидна в силу традиційно малої ймовірності мутації. В основному ймовірність мутації складає 0,001-0,01.

Вибір батьківської пари

Перший підхід найпростіший — це випадковий вибір батьківської пари («панміксія»), коли обидві особини, які складуть батьківську пару, випадковим чином вибираються з усієї популяції, причому будь-яка особина може стати членом декількох пар. Незважаючи на простоту, такий підхід універсальний для розв’язання різних класів завдань. Однак він досить критичний для чисельності популяції, оскільки ефективність алгоритму, що реалізує такий підхід, знижується зі зростанням чисельності популяції.

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

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

Механізм добору

Обговорення питання про вплив методу створення батьківських пар на поводження генетичного алгоритму неможливо вести у відриві від реалізованого механізму добору при формуванні нового покоління. Найефективніші два механізми відбору — елітний і відбір з витисненням.

Ідея елітного добору, загалом, не нова, цей метод грунтується на побудові нової популяції тільки з найкращих особин репродукційної групи, що поєднує в собі батьків, їхніх нащадків і мутантів. В основному це пояснюють потенційною небезпекою передчасної збіжності, віддаючи перевагу пропорційному добору. Швидка збіжність, забезпечувана елітним добором, може бути, коли це необхідно, з успіхом компенсована підходящим методом вибору батьківських пар, наприклад, аутбридингом. Саме гака комбінація «аутбридинг — елітний добір» є однією з найефективніших.

Другий метод, на якому хотілося б зупинитися, це добір витисненням. Чи буде особина з репродукційної групи заноситися в популяцію нового покоління, визначається не тільки величиною її пристосованості, але й тим, чи є в формованій популяції наступного покоління особина з аналогічним хромосомним набором. З усіх особин з однаковими генотипами перевага спочатку, звичайно ж, віддається тим, чия пристосованість вища. У такий спосіб досягаються дві мети: по-перше, не втрачаються кращі знайдені рішення, що характеризуються різними хромосомними наборами, а по-друге, у популяції постійно підтримується достатня генетична розмаїтість. Витиснення в цьому випадку формує нову популяцію скоріше з далеко розташованих особин, замість особин, що групуються біля поточного знайденого рішення. Цей метод особливо добре себе показав при розв’язанні багатоекстремальних завдань, при цьому крім визначення глобальних екстремумів з’являється можливість виділити також ті локальні максимуми, значення яких близькі до глобального.

Особливості генетичних алгоритмів

Генетичний алгоритм — новітній, але не єдино можливий спосіб розв’язання завдань оптимізації. Віддавна відомі два основних шляхи розв’язання таких завдань — перевірний і локально-градієнтний. У цих методів свої переваги й недоліки, і в кожному конкретному випадку слід подумати, який з них вибрати.

Розглянемо переваги й недоліки стандартних і генетичних методів на прикладі класичного завдання комівояжера. Суть завдання полягає в тому, щоб знайти найкоротший замкнутий шлях обходу декількох міст, заданих своїми координатами. Виявляється, що вже для 30 міст пошук оптимального шляху являє собою складне завдання, яке спонукало розвиток різних нових методів (у тому числі нейромереж і генетичних алгоритмів).

Кожний варіант розв'язання (для 30 міст) — це числовий рядок, де на j-ому місці стоїть номер j-oro за порядком обходу міста. Таким чином, у цьому завданні 30 параметрів, причому не всі комбінації значень припустимі. Природно, першою ідеєю є повний перебір всіх варіантів обходу.

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

Другий популярний спосіб грунтується на методі градієнтного спуску. При цьому спочатку вибираються деякі випадкові значення параметрів, а потім ці значення поступово змінюють, домагаючись найбільшої швидкості зростання цільової функції. Досягти локального максимуму, такий алгоритм зупиняється, тому для пошуку глобального оптимуму будуть потрібні додаткові зусилля.

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

Типове практичне завдання, як правило, мультимодальне й багатовимірне, тобто містить багато параметрів. Для таких завдань не існує жодного універсального методу, що дозволяв би досить швидко знайти абсолютно точне рішення.

Однак, комбінуючи перебірний і градієнтний методи, можна сподіватися одержати хоча б наближене рішення, точність якого зростатиме при збільшенні часу розрахунку.

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

Така комбінація дозволяє забезпечити стійко високу ефективність генетичного пошуку для будь-яких типів завдань.

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