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

В.М. Курейчик

Генетичні алгоритми (ГА) є пошукові алгоритми, засновані на механізмах натуральної селекції і натуральної генетики. Вони реалізують «виживання найсильніших» серед розглянутих структур, формуючи і змінюючи пошуковий алгоритм на основі моделювання еволюції [1-7].

Основою для виникнення генетичних алгоритмів вважається модель біологічної еволюції і методи випадкового пошуку [6, 7]. Один з відомих фахівців у світі в області випадкового пошуку та стохастичної оптимізації Растригина пише [6]. Випадковий пошук (СП) виникла як реалізація найпростішої моделі еволюції, коли випадкові мутації моделювалися случайнимішагамі оптимального рішення, а відбір "Відходом" невдалих варіантів. Наприклад, для прикладних оптимізаційних завдань

K (X) extr,

тут K-функціона, X - шукане рішення, extr - екстремум (приймає

залежно від умов завдання мінімальне або максимальне значення).

Тоді, наприклад, для максимізації

K (X) min X *,

де X * - найкраще рішення.

Це вираз реалізовується з урахуванням обмежень та граничних умов. Еволюційний пошук згідно [6] - це послідовне перетворення одного кінцевого безлічі проміжних рішень в інше. Саме перетворення можна назвати алгоритмом пошуку або алгоритмом еволюції.

Растригина виділяє три особливості алгоритму еволюції:

- кожна нова популяція складається тільки з "життєздатних" хромосом;

- кожна нова популяція "Краще" (у сенсі цільової функції) попередньої;

- в процесі еволюції подальша популяція залежить тільки від попередньої [7].

Згідно [7] природа, реалізуючи еволюцію, як би вирішує оптимізаційних задач на основі випадкового пошуку. Виділяється три основних біонічної евристики випадкового пошуку:

- клітинний СП,

- моделювання доцільного поведінки особин,

- моделювання передачі успадковане біологічної інформації.

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

Простий генетичний алгоритм був вперше описаний Гольдберг на основі робіт Холланда [1,2]. Механізм простого ГА (ПГА) нескладний. Він копіює послідовності і переставляє їх частини. Попередньо ГА випадково генерує популяцію послідовностей - стрінгів (хромосом). Потім ГА застосовує безліч простих операцій до початкової популяції і генерує нові популяції. ПГА складається з 3 операторів: репродукція, Кросинговер, мутація. Р е п р о д у к ц і я -- процес, в якому хромосоми копіюються згідно з їх цільової функції (ЦФ). Копіювання хромосом з «кращим» значенням ЦФ має велику ймовірність для їх потрапляння у наступну генерацію. Оператор репродукції (ОР), є штучною версією натуральної селекції, "виживання найсильніших" за Дарвіном. Після виконання ОР оператор Кросинговер (ОК) може виконатися в 3 кроки. На першій кроці члени нового репродукованого безлічі хромосом вибираються спочатку. Далі кожна пара хромосом (стрінгів) перетинається за наступним правилом: ціла позиція k уздовж стринга вибирається випадково між l та довжиною хромосоми менше одиниці тобто в інтервалі (1, L-1). Довжина L хромосоми це число значущих цифр у його довічним коді. Число k, вибрана випадково, між першим і останнім членами, називається точкою ОК або розділяє знаком.

Механізм ОР і ОК. Він включає випадкову генерацію чисел, копіювання хромосом і частковий обмін інформацією між хромосомами.

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

(1)

тут fi (x) -- значення ЦФ i-тої хромосоми в популяції, sum f (x) - сумарне значення ЦФ всіх хромосом в популяції. Величину (1) також називають нормалізованому велічіной.Ожідаемое число копій i-ої хромосоми після ОР визначають

(2)

де n-число аналізованих хромосом.

Кількість копій хромосоми, що переходить в таке положення, іноді визначають на основі вираження

. (3)

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

Поняття "схема" (схемата), згідно з Холланд, є шаблон, що описує підмножина стрінгів, що мають подібні значення в деяких позиціях стринга [8]. Для цього вводиться новий алфавіт (0,1, *), де * - означає: не має значення 1 або 0. Для обчислення числа схем або їх кордону в популяції потрібні точні значення про кожного стринг в популяції.

Для кількісної оцінки схем введені 2 характеристики [1,2]: порядок схеми - О (H); певна довжина схеми - L (H). Порядок схеми - число закріплених позицій (у двійковому алфавіті - число одиниць і нулів), представлених в шаблоні.

Припустимо, що задані крок (тимчасової) t, m прикладів часткових схем H, що містяться в популяції A (t). Все це записують як m = m (H, t) - можливе різне число різних схем H в різний час t.

Протягом репродукції стринги копіюються згідно з їх ЦФ або більш точно: стринг A (i) отримує вибір з ймовірністю, яка визначається виразом (1).

Після збору непересічних популяцій розміру n з переміщенням з популяції A (t) ми очікуємо мати m (H, t +1) представників схеми H в популяції за час t 1. Це обчислюється рівнянням

m (H, t +1) = m (H, t) * N * f (H)/sum [f (j)], (4)

де f (H) - є середня ЦФ стрінгів, представлених схемою H за час t.

Якщо позначити середню ЦФ всієї популяції як f *= sum [f (j)]/n, тоді

m (H, t +1) = m (H, t) * f (H)/f *. (5)

Правило репродукції Холланда: схема з ЦФ вище середньої "живе", копіюється і з нижче середньої ЦФ "Вмирає" [1].

Припустимо, що схема H залишається з вище середньої ЦФ з величиною c? f *, де c-константа. Тоді вираз (5) можна модифікувати так

m (H, t +1) = m (H, t) * (f * + c * f *)/f *= (1 + c) * m (H, t) (6)

Деякі дослідники вважають, що репродукція може призвести до експоненціальним зменшення або збільшення схем, особливо якщо виконувати генерації паралельно [3-5].

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

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

P (s) = 1-O (H)/(L-1). (7)

Якщо ОК виконується за допомогою випадкового вибору, наприклад, з імовірністю P (ОК), то ймовірність виживання схеми визначиться

P (s)? 1-P (ОК) * L (H)/(L-1). (8)

Припускаючи незалежність репродукції (ОР) і ОК, отримаємо [1]:

m (H, t +1)? m (H, t) * f (H)/f * * [1-P (ОК) *

L (H)/(lL)]. (9)

З виразу (9) випливає, що схеми з вище середньої ЦФ і короткою L (H) мають можливість експоненціального зростання в нової популяції.

Розглянемо вплив мутації на можливості виживання. ОМ є випадкова альтернативна перестановка елементів у стринг з імовірністю Р (ОМ). Для того, щоб схема H вижила, все специфічні позиції повинні вижити. Отже, єдина хромосома виживає з ймовірністю (1-P (ОМ)) та приватна схема виживає, коли кожна з l (H) закріплених позицій схеми виживає.

1-L (H) * Р (ОМ). (10)

Тоді ми очікуємо, що приватна схема H отримує очікуване число копій в наступній генерації після ОР, ОК ОМ

m (H, t +1)> m (H, t) * f (H)/f ** [1-Р (ОК) * l (H)/(l-1) -

l (H) * P (ОМ)]. (11)

Це вираз називається "схема теорем" або фундаментальна теорема ГА [1].

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

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

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

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

Список літератури

Holland John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

Goldberd David E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Inc. 1989, 412p.

Handbook of Genetic Algorithms, Edited by Lawrence Davis, Van Nostrand Reinhold, New York, 1991, 385p.

Курейчик В.М., Лях А.В. Завдання моделювання еволюції в САПР. Праці міжнародної конференції (CAD-93), РФ - США, Москва, 1993.

Chambers L.D., Practical Handbook of Genetic Algorithms. CRS Press, Boca Ration FL, 1995, v. 1, 560 p., v. 2, 448 p.

Растригина Л.А. статистичні методи пошуку. М: Наука, 1968.

Еволюційні обчислення і генетичні алгоритми. Укладачі Гудман Е.Д., Коваленко А.П. Огляд прикладної та промислової математики, том 3, вип. 5, Москва, ТВП, 1996, 760с.