→ Пошук по сайту       Увійти / Зареєструватися
Знання Генетичні алгоритми

Популярно про генетичні алгоритми

"Історія появи еволюційних алгоритмів"

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

Теорія еволюції вплинула на зміну світогляду людей з самої своєї появи. Теорія, яку Чарльз Дарвін представив у роботі, відомої як "Походження видів", в 1859 році, стала початком цієї зміни. Багато області наукового знання в даний час насолоджуються свободою думки в атмосфері, яка багато в чому зобов'язана революції, викликаної теорією еволюції і розвитку. Але Дарвін, подібно багатьом своїм сучасникам, хто припускав, що в основі розвитку лежить природний відбір, не міг не помилятися. Наприклад, він не зміг показати механізм успадкування, при якому підтримується мінливість. Його гіпотеза про Пангенезис виявилася неправильною. Це було на 50 років до того, як теорія спадковості почала поширюватися по світу, і за тридцять років до того, як "еволюційний синтез" зміцнив зв'язок між теорією еволюції і відносно молодий наукою генетикою. Однак Дарвін виявив головний механізм розвитку: відбір у поєднанні з мінливістю або, як він його називав, "спуск з модифікацією". У багатьох випадках, специфічні особливості розвитку через мінливість і відбір все ще не безперечні, однак, основні механізми пояснюють неймовірно широкий спектр явищ, які спостерігаються в Природі.

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

Історія еволюційних обчислень почалася з розробки ряду різних незалежних моделей. Основними з них були генетичні алгоритми і класифікаційні системи Голланда (Holland), опубліковані на початку 60-х років і одержали загальне визнання після виходу в світ книги, що стала класикою в цій області, - "Адаптація в природних і штучних системах" ("Adaptation in Natural and Artifical Systems ", 1975). У 70-х роках у рамках теорії випадкового пошуку Растрігіним Л.А. був запропонований ряд алгоритмів, що використовують ідей біонічної поведінки особин. Розвиток цих ідей знайшов відображення у циклі робіт Букатовой І.Л. по еволюційному моделювання. Розвиваючи ідеї Цетлін М.Л. Про доцільність і оптимальному поведінці стохастичних автоматів, Неймарк Ю.І. запропонував здійснювати пошук глобального екстремуму на основі колективу незалежних автоматів, моделюючих процеси розвитку та елімінації особин. Великий внесок у розвиток еволюційного програмування внесли Фогел (Fogel) і Уолш (Walsh). Незважаючи на різницю у підходах, кожна з цих "шкіл" взяла за основу низку принципів, що існують у природі, і спростила їх до такої міри, щоб їх можна було реалізувати на комп'ютері.

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

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

Звичайно, на практиці ми не можемо розділяти ці речі так строго. Ці категорії - просто два полюси, між якими лежать різні обчислювальні системи. Ближче до першого полюса - еволюційні алгоритми, такі як Еволюційне Програмування (Evolutionary Programming), Генетичні Алгоритми (Genetic Algorithms) і Еволюційні Стратегії (Evolution Strategies). Ближче до другого полюса - системи, які можуть бути класифіковані як Штучна Життя (Artificial Life).

Звичайно, еволюція біологічних систем не єдиний "джерело натхнення" творців нових методів, що моделюють природні процеси. Нейронні мережі (neural networks), наприклад, засновані на моделюванні поведінки нейронів у мозку. Вони можуть використовуватися для ряду задач класифікації, наприклад, задачі розпізнавання образів, машинного навчання, обробки зображень і ін Область їх застосування частково перекривається зі сферою застосування ГА. Модельований відпал (simulated annealing) - інша методика пошуку, яка заснована скоріше на фізичних, а не біологічних процесах.

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

Генетичні Алгоритми - адаптивні методи пошуку, які останнім часом часто використовуються для вирішення задач функціональної оптимізації. Вони засновані на генетичних процесах біологічних організмів: біологічні популяції розвиваються протягом кількох поколінь, згідно законів природного відбору і за принципом "виживає найбільш пристосований" (survival of the fittest), відкритому Чарльзом Дарвіном. Наслідуючи цьому процесу генетичні алгоритми здатні "розвивати" вирішення реальних завдань, якщо ті відповідним чином закодовані. Наприклад, ГА можуть використовуватися, щоб проектувати структури моста, для пошуку максимального відносини міцності / ваги, або визначати найменш марнотратне розміщення для нарізки форм з тканини. Вони можуть також використовуватися для інтерактивного управління процесом, наприклад на хімічному заводі, або балансуванні завантаження багатопроцесорних системи. Цілком реальний приклад: ізраїльська компанія розробила Schema програмний продукт Channeling для оптимізації роботи стільникового зв'язку шляхом вибору оптимальної частоти, на якій буде вестися розмова. В основі цього програмного продукту і використовуються генетичні алгоритми.

Основні принципи ГА були сформульовані Голландії (Holland, 1975), і добре описані в багатьох роботах. На відміну від еволюції, яка відбувається у природі, ГА тільки моделюють ті процеси в популяціях, які є істотними для розвитку. Точну відповідь на запитання: які біологічні процеси істотні для розвитку, і які ні? - Все ще відкритий для дослідників.

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

ГА використовують пряму аналогію з таким механізмом. Вони працюють із сукупністю "особин" - популяцією, кожна з яких представляє можливе рішення даної проблеми. Кожна особина оцінюється мірою її "пристосованості" згідно з тим, наскільки "добре" відповідне їй рішення задачі. Наприклад, мірою пристосованості могло б бути ставлення сили / ваги для даного проекту моста. (У природі це еквівалентно оцінці того, наскільки ефективний організм при конкуренції за ресурси.) Найбільш пристосовані особини отримують можливість "відтворює" потомство за допомогою "перехресного схрещування" з іншими особинами популяції. Це призводить до появи нових особин, які поєднують у собі деякі характеристики, які успадковуються ними від батьків. Найменш пристосовані особини з меншою ймовірністю зможуть відтворити нащадків, так що ті властивості, якими вони володіли, будуть поступово зникати з популяції в процесі еволюції.

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

Є багато способів реалізації ідеї біологічної еволюції в рамках ГА. Традиційним вважається ГА, представлений на схемі.

ПОЧАТОК / * генетичний алгоритм * /

Створити початкову популяцію

Оцінити пристосованість кожної особини

зупинення: = FALSE

ПОКИ НЕ зупинення ВИКОНУВАТИ

ПОЧАТОК / * створити популяцію нового покоління * /

ПОВТОРИТИ (розмір_популяціх / 2) РАЗ

ПОЧАТОК / * цикл відтворення * /

Вибрати дві особини з високою пристосованістю з попереднього покоління для схрещування

Схрестити вибрані особини і отримати двох нащадків

Оцінити пристосованості нащадків

Помістити нащадків в нове покоління

КІНЕЦЬ

ЯКЩО популяція зійшлася ТО зупинення: = TRUE

КІНЕЦЬ

КІНЕЦЬ

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

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

Коли слід застосовувати генетичний алгоритм?

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

Тим не менш, можливо найбільш популярний додаток генетичних алгоритмів - оптимізація багатопараметричних функцій. Багато реальні завдання можуть бути сформульовані як пошук оптимального значення, де значення - складна функція, що залежить від деяких вхідних параметрів. У деяких випадках, представляє інтерес знайти ті значення параметрів, при яких досягається найкраще точне значення функції. В інших випадках, точний оптимум не потрібно - рішенням може вважатися будь-яке значення, яке краще деякої заданий величини. У цьому випадку, генетичні алгоритми - часто найбільш прийнятний метод для пошуку "хороших" значень. Сила генетичного алгоритму полягає в його здатності маніпулювати одночасно багатьма параметрами, ця особливість ГА використовувалося в сотнях прикладних програм, включаючи проектування літаків, налаштування параметрів алгоритмів і пошуку стійких станів систем нелінійних диференціальних рівнянь.

Проте нерідкі випадки, коли ГА працює не так ефективно, як очікувалося.

Припустимо є реальне завдання, сполучена з пошуком оптимального рішення, як дізнатися, чи є ГА гарним методом для її вирішення? До теперішнього часу не існує суворого відповіді, однак багато дослідників поділяють припущення, що якщо простір пошуку, яке належить досліджувати, - велике, і передбачається, що воно не зовсім гладке і унімодальне (тобто містить один гладкий екстремум) або не дуже зрозуміло , або якщо функція пристосованості з шумами, або якщо завдання не вимагає строго знаходження глобального оптимуму - тобто якщо досить швидко просто знайти прийнятне "гарне" рішення (що досить часто має місце в реальних завданнях) - ГА буде мати гарні шанси стати ефективною процедурою пошуку, конкуруючи і перевершуючи інші методи, які не використовують знання про простір пошуку.

Якщо ж простір пошуку невелике, то рішення може бути знайдене методом повного перебору, і можна бути впевненим, що найкраще можливе рішення знайдено, тоді як ГА міг з більшою ймовірністю зійтися до локального оптимуму, а не до глобально краще рішення. Якщо простір гладке і унімодальне будь-градієнтний алгоритм, такий як, метод швидкого спуску буде більш ефективний, ніж ГА. Якщо про простір пошуку є деяка додаткова інформація (як, наприклад, простір для добре відомої задачі про комівояжера), методи пошуку, що використовують евристики, що визначаються простором, часто перевершують будь-який універсальний метод, яким є ГА. При досить складному рельєфі функції пристосованості методи пошуку з єдиним рішенням у кожен момент часу, такий як простий метод спуску, могли "затикатися" у локальному вирішенні, проте вважається, що ГА, так як вони працюють з цілою "популяцією" рішень, мають менше шансів зійтися до локального оптимуму і робастної функціонують на багатоекстремального ландшафті.

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

Символьна модель простого ГА

Мета в оптимізації за допомогою ГА полягає в тому, щоб знайти краще можливе рішення або рішення задачі по одному або декільком критеріям. Щоб реалізувати генетичний алгоритм потрібно спочатку вибрати відповідну структуру для подання цих рішень. У постановці задачі пошуку, примірник цієї структури даних представляє точку в просторі пошуку всіх можливих рішень. Структура даних генетичного алгоритму складається з однієї або більшу кількість хромосом (зазвичай з однієї). Як правило, хромосома - це бітова рядок, так що термін рядок часто замінює поняття "хромосома". У принципі, ГА не обмежені бінарним подання. Відомі інші реалізації, побудовані виключно на векторах дійсних чисел (L. Davis, 1991b; Eshelman і Schaffer, 1993; Goldberg, 1991a, 1991b). Незважаючи на те, що для багатьох реальних задач, мабуть, більше підходять рядки змінної довжини, в даний час структури фіксованої довжини найбільш поширені і вивчені. Поки що і ми обмежимося тільки структурам, які є поодинокими рядками по l біт.

Кожна хромосома (рядок) являє собою конкатенацію ряду підкомпоненти званих генами. Гени розташовуються в різних позиціях або локусах хромосоми, і приймають значення звані аллелями. В уявленнях з бінарними рядками, ген - біт, локус - його позиція у рядку, і алель - його значення (0 або 1). Біологічний термін "генотип" відноситься до повної генетичної моделі особини і відповідає структурі в ГА. Термін "фенотип" відноситься до зовнішніх спостережуваним ознаками і відповідає вектору в просторі параметрів. Надзвичайно простий, але ілюстративний приклад - завдання максимізації наступної функції двох змінних:

f (x1, x2) = exp (x1x2), де 0 < x1 < 1 і 0 < x2 < 1.

Зазвичай, методика кодування реальних змінних x1 і x2 полягає в їх перетворення на виконавчі цілочисельні рядка достатньої довжини - достатньою для того, щоб забезпечити бажану точність. Припустимо, що 10-розрядне кодування достатньо і для x1, x2 і. Встановити відповідність між генотипом і фенотипом закодованих особин можна, розділивши відповідне бінарне ціле число - на 210-1. Наприклад, 0000000000 відповідає 0 / 1023 або 0, тоді як 1111111111 відповідає 1023/1023 або 1. Оптимізується структура даних - 20-бітова рядок, що представляє конкатенацію кодувань x1 і x2. Мінлива x1 розміщується в крайніх лівих 10-розрядах, тоді як x2 розміщується у правій частині генотипу особини (20-бітової рядку). Генотип - точка в 20-мірному хеммінінговом просторі, досліджуваному ГА. Фенотип - точка в двовимірному просторі параметрів.

Щоб оптимізувати структуру, використовуючи ГА, потрібно задати деяку міру якості для кожної структури в просторі пошуку. Для цієї мети використовується функція пристосованості. У функціональної максимізації, цільова функція часто сама виступає в якості функції пристосованості (наприклад наш двовимірний приклад); для задач мінімізації, цільову функцію слід інвертувати і змістити потім в область додатніх значень.

Робота простого ГА

Простий ГА випадковим чином генерує початкову популяцію структур. Робота ГА являє собою ітераційний процес, який продовжується до тих пір, поки не виконаються задане число поколінь або будь-якою іншою критерій зупинки. На кожному поколінні ГА реалізується відбір пропорційно пристосованості, одноточковий кроссовер і мутація. Спочатку, пропорційний відбір призначає кожній структурі імовірність Ps (i) рівну відношенню її пристосованості до сумарної пристосованості популяції:

Потім відбувається відбір (із заміщенням) усіх n особин для подальшої генетичної обробки, згідно величиною Ps (i). Найпростіший пропорційний відбір - рулетка (roulette-wheel selection, Goldberg, 1989c) - відбирає особин за допомогою n "запусків" рулетки. Колесо рулетки містить по одному сектору для кожного члена популяції. Розмір i-ого сектора пропорційний відповідає величині Ps (i). При такому відборі члени популяції з більш високою пристосованістю з більшою ймовірністю будуть частіше вибиратися, ніж особини з низькою пристосованістю.

Після відбору, n обраних особин піддаються кросоверу (іноді званого рекомбінацією) із заданою вірогідністю Pc. n рядків випадковим чином розбиваються на n / 2 пари. Для кожної пари з вірогідність Pc може застосовуватися кросовер. Відповідно з імовірністю 1-Pc кросовер не відбувається і незмінені особини переходять на стадію мутації. Якщо кросовер відбувається, отримані нащадки заміняють собою батьків і переходять до мутації.

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

Наприклад, припустимо, один батько складається з 10 нулів, а інший - з 10 одиниць. Нехай з 9 можливих точок розриву обрана точка 3. Батьки і їхні нащадки показані нижче.

Кросовер
Батько1 Нащадок1
0000000000 000~0000000 -> 111~0000000 1110000000
Батько2 Нащадок2
1111111111 111~1111111 -> 000~1111111 0001111111

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

В даний час дослідники ГА пропонують багато інших операторів відбору, кросовера і мутації. Ось лише найпоширеніші з них. Перш за все, турнірний відбір (Brindle, 1981; Goldberg і Deb, 1991). Турнірний відбір реалізує n турнірів, щоб вибрати n особин. Кожен турнір побудований на вибірці k елементів із популяції, і вибору кращої особини серед них. Найбільш поширений турнірний відбір з k = 2.

Елітні методи відбору (De Jong, 1975) гарантують, що при відборі обов'язково будуть виживати кращий або кращі члени популяції сукупності. Найбільш поширена процедура обов'язкового збереження тільки однієї кращої особини, якщо вона не пройшла як інші через процес відбору, кросовера і мутації. Елітизм може бути впроваджений практично в будь-який стандартний метод відбору.

Двухточечной кросовер (Cavicchio, 1970; Goldberg, 1989c) і рівномірне кросовер (Syswerda, 1989) - цілком гідні альтернативи одноточковими оператору. У двухточечной кросовер вибираються дві точки розриву, і батьківські хромосоми обмінюються сегментом, який знаходиться між двома цими точками. У рівномірному кросовер, кожен біт першого батька успадковується першим нащадком із заданою вірогідністю; в іншому випадку цей біт передається другому нащадку. І навпаки.

Шима (schema)

Хоча зовні здається, що ГА обробляє рядки, насправді при цьому неявно відбувається обробка шим, які представляють шаблони подібності між рядками (Goldberg, 1989c; Голланд, 1992). ГА практично не може займатися повним перебором всіх точок у просторі пошуку. Однак він може виробляти вибірку значного числа гіперплоскостей в областях пошуку з високою пристосованістю. Кожна така гіперплоскость відповідає безлічі схожих рядків із високою пристосованістю.

Шuма - це рядок довжини l (що й довжина будь-який рядка популяції), що складається із знаків алфавіту {0; 1; *}, де {*} - невизначений символ. Кожна Шім'а визначає безліч всіх бінарних рядків довжини l, що мають у відповідних позиціях або 0, або 1, залежно від того, який біт знаходиться у відповідній позиції самої Шім'ї .. Наприклад, Шім'а, 10 ** 1, визначає собою безліч з чотирьох пятібітових рядків {10001; 10011; 10101; 10111}. У шим виділяють дві властивості - порядок і певна довжина. Порядок Шім'ї - це число певних бітів ("0" або "1") в Шім'у. Певна довжина - відстань між крайніми певними бітами в Шім'у. Наприклад, вищезгадана Шім'а має порядок o (10 ** 1) = 3, а певна довжина d (10 ** 1) = 4. Кожен рядок у популяції є прикладом 2l шим.

Будуючі блоки

Будуючі блоки (Goldberg, 1989c) - це Шіми, які володіють: 1. високою пристосованістю, 2. нижчим порядком, 3. короткої певною довжиною.

Пристосованість Шими визначається як середнє пристосованість прикладів, які її містять.

Після процедури відбору залишаються лише рядки з більш високою пристосованістю. Отже рядки, які є прикладами шим з високою пристосованістю, вибираються частіше. Кросовер рідше руйнує Шім'ї з коротшою певною довжиною, а мутація рідше руйнує Шім'ї з низьким порядком. Тому, такі Шім'ї мають більше шансів переходити з покоління в покоління. Голланд (1992) показав, що, у той час як ГА явним чином обробляє n рядків на кожному поколінні, в той же час неявно обробляються порядку n3 таких коротких шим низького порядку і з високою пристосованістю (корисних великим, "useful schemata"). Він називав це явище неявним паралелізмом. Для вирішення реальних завдань, присутність неявного паралелізму означає, що велика популяція має більше можливостей локалізувати рішення експоненціально швидше популяції з меншим числом особин.

Теорема шим

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

Нехай m (H, t) - число прикладів Шим H в t-му поколінні. Обчислимо очікуване число прикладів H в наступному поколінні або m (H, t +1) у термінах m (H, t). Простий ГА кожному рядку ставить у відповідність імовірність її "виживання" при відборі пропорційно її пристосованості. Очікується, що Шім'а H може бути обрана m (H, t) Ч (f (H) / fср.) Раз, де fср. - Середня пристосованість популяції, а f (H) - середня пристосованість тих рядків у популяції, які є прикладами H.

Імовірність того, що одноточковий кросовер зруйнує шіму дорівнює ймовірності того, що точка розриву потрапить між певними бітами. Імовірність же того, що H "переживає" кросовер не менше 1-Pc_ (d (H) / l-1). Ця ймовірність - нерівність, оскільки Шім'а зможе вижити якщо в кросовер брав участь також приклад схожою Шім'ї. Імовірність того, що H переживе мутацію - (1-Pm) o(H), цей вираз можна апроксимувати як (1-o (H)) для малого Pm і o (H). Твір очікуваного число відборів і ймовірностей виживання відомо як теорема шим:

m (H, t +1) >=

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

Goldberg (1983, 1989c), у своїх дослідженнях теореми великим, висуває гіпотезу будують блоків, що полягає в тому, що "будують блоки об'єднуються, щоб сформувати найкращі рядки". Тобто рекомбінація і експонентний зростання будують блоків веде до формування кращих будують блоків.

У той час як теорема шим пророкує зростання прикладів хороших великим, сама теорема вельми спрощено описує поведінку ГА. Перш за все, f (H) і fср. не залишаються постійними від покоління до покоління. Пристосованості членів популяції знаменно змінюються вже після кількох перших поколінь. По-друге, теорема шим пояснює втрати великим, але не поява нових. Нові Шім'ї часто створюються кросовером і мутацією. Крім того, у міру еволюції, члени популяції стають все більш і більш схожими один на одного так, що зруйновані Шім'ї будуть відразу ж відновлені. Нарешті, доказ теореми шим побудовано на елементах теорії ймовірності та отже не враховує розкид значень, в багатьох цікавих завданнях, розкид значень пристосованості Шім'ї може бути досить великий, роблячи процес формування шим дуже складним (Goldberg і Rudnick, 1991; Rudnick і Goldberg, 1991) . Істотна різниця пристосованості Шім'ї може призвести до збіжності до неоптимальному рішенням.

Незважаючи на простоту, теорема шим описує кілька важливих аспектів поведінки ГА. Мутації з більшою ймовірністю руйнують Шім'ї високого порядку, в той час як кросовера з більшою ймовірність руйнують Шім'ї з більшою певною довжиною. Коли відбувається відбір, популяція сходиться пропорційно відношенню пристосованості кращої особини, до середньої пристосованості в популяції; це відношення - міра тиску відбору ("selection pressure", Back, 1994). Збільшення або Pc, або Pм., Або зменшенні тиску відбору, веде до збільшення здійсненню вибірки або дослідженню простору пошуку, але не дозволяє використовувати всі хороші Шім'ї, якими має в своєму розпорядженні ГА. Зменшення або Pc, або Pм., Або збільшення тиску вибору, веде до поліпшення використання знайдених великим, але гальмує дослідження простору в пошуках нових хороших шим. ГА має підтримати тонке рівновагу між тим і іншим, що зазвичай відоме як проблема "балансу дослідження та використання".

Деякі дослідники критикували зазвичай швидку збіжність ГА, заявляючи, що випробування величезних кількостей перекриваються шим вимагає більшої вибірки і більш повільної, більш керованою збіжності. У той час як збільшити вибірку шим можна збільшивши розмір популяції (Goldberg, Deb, і Clark, 1992; Mahfoud і Goldberg, 1995), методологія управління збіжність простого ГА до цих пір не вироблена.

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

загрузка...
Сторінки, близькі за змістом