Лабораторна робота №5

Вступ

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

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

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

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

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

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

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

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

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

Оцінити пристосованість кожного індивіду

останов := FALSE

ПОКИ не останов ВИКОНУВАТИ

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

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

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

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

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

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

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

КІНЕЦЬ

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

КІНЕЦЬ

КІНЕЦЬ

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

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