Поняття генетичного алгоритму. Його місце серед систем заснованих на еволюційному моделюванні

Історія еволюційного моделювання

Історія еволюційного моделювання почалася з розробки ряду різних незалежних моделей. В 1966 р. Л.Дж.Фогель, А.Дж. Оуэнс, М.Дж.Волш запропонували й дослідили еволю­цію простих автоматів які прогнозували символи в цифрових послідовностях. Пізніше Фогель і Уолш внесли великий вклад у розвиток еволюційного програмування.

На початку 60–х років також були опубліковані роботи Д.Х.Холланда по генетичним алгоритмам (перша назва – «ре­продуктивні плани») і класифікаційним системам, які одержали загальне визнання після виходу у світ книги, що стала класикою в цій області ("Адаптація в природних і штучних системах", 1975).

В 70–х роках у рамках теорії випадкового пошуку Л.А.Растригіним був запропонований ряд алгоритмів, які вико­ристають ідеї біонічного поводження особин. Розвиток цих ідей знайшло відбиття в циклі робіт І.Л.Букатової по еволюційному моделюванню. Розвиваючи ідеї М.Л.Цетлина про доцільне й оп­тимальне поводження стохастичних автоматів, Ю.И.Неймарк запропонував здійснювати пошук глобального екстремума на основі колективу незалежних автоматів, що моделюють процеси розвитку й елімінації особин. Математиком Дж.Х. Конвеєм була розроблена гра "Життя" в основу якої лягла аналогія соціальної взаємодії з метою виживання, ця гра була представлена широ­кому колу громадськості М. Гарднером у журналі "Scientific American" в 1970 і 1971 роках.

В 1986–87р. у роботах Брукса описані прості роботи, що ді­ють як автономні агенти, здатні вирішувати завдання в лабора­торних умовах. В 1986 році Д.Х.Холланд, разом з рядом інших дослідників застосував генетичні алгоритми для рішення бі­льше складних завдань, зокрема, для побудови й уточнення на­борів правил виводу в системах класифікації й для рішення за­вдань генетичного програмування. Завдання створення й на­строювання комп'ютерних програм з використанням генетичних алгоритмів розглянуті Коза (1992). Методологія штучного життя розроблялась Лэнгтоном (1995).

Незважаючи на різницю в підходах, кожна із цих "шкіл" взяла за основу ряд принципів, що існують у природі, і спрос­тила їх настільки, щоб їх можна було реалізувати на комп'ютері.

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

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

"Батьком–засновником" генетичних алгоритмів вважається Джон Холланд (англ. John Holland), книга якого "Адаптація в природних і штучних системах" (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень.

Генетичний алгоритм (репродуктивний план Холланда) – розділ еволюційного моделювання, що запозичив методичні прийоми з теоретичних положень популяційної генетики. Являє собою свого роду модель машинного дослідження пошукового простору, побудовану на еволюційній метафорі. Це стохастичні, евристичні оптимизаційні методи, вперше запропоновані Холла­ндом (1975). Характерні риси: використання рядків (строчок) фіксованої довжини для представлення генетичної інформації, робота з популяцією рядків, використання генетичних операто­рів для формування наступних поколінь. Простий генетичний алгоритм був уперше описаний Гольдбергом на основі робіт Холланда.

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

Досить тривалий час генетичні алгоритми розглядались насампе­ред як методи оптимізації. Однак слід зазначити, що завдання адаптація трохи ширше, ніж завдання оптимізації (про що Хол­ланд говорив у передмові до другого видання (1995)). Тому ге­нетичний алгоритм насамперед необхідно розглядати як універ­сальний метод адаптації, хоча часто він розглядається як метод оптимізації. У цьому випадку можна привести слова Кеннета Ді Янга, одного із класиків ГА. Він пише: «...легко помили­тися, сприймаючи самі ГА як алгоритми оптимізації, а потім дивуватися і/або розчаровуватись, коли вони зазнають невдачі в пошуку «очевидного» оптимуму в певному пошуковому прос­торі. Моя пропозиція із приводу того, як уникнути такого само­обману, полягає в тому, щоб думати про ГА як про (найвищою мірою) ідеалізовану модель природного процесу і як про проце­дуру, що втілює мету й завдання (якщо такі взагалі існують) цього природного процесу. Я не впевнений, чи знайдеться хто–небудь, готовий відповістити на запитання, яка мета й завдання еволюційних систем; однак, по правді говорячи, такі системи взагалі не сприймаються як оптимізатори функцій...».

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

Дата добавления: 2014-01-04