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

Інформатика, програмування

Далекосхідний Державний Університет

Інститут Математики та Комп'ютерних наук

Кафедра Інформатики

Курсовий проект

Тема: < p> "Генетичні Алгоритми"

Виконав - Студент 3-го курсу

Несов Роман Геннадійович

Керівник - Асистент кафедри інформатики

Кленина Олександр Сергійович

Владивосток 1999

Зміст:

1. Природний відбір в природі. . . . . . . . . . . . . . . . . . . . . .

. . . . . .3

2. Що таке генетичний алгоритм. . . . . . . . . . . . . . . . . . . . .

. . . . .4

3. Детальний опис генетичного aлгорітма. . . . . . . . . . . . . . .6

4. Вплив параметрів генетичного алгоритму на ефективність

пошуку. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .7

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

. .9

6. Список літератури та посилання. . . . . . . . . . . . . . . . . . . . . . .

. . . . .11

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

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

| 1 | Природний відбір в природі |

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

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

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

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

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

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

| 2 | Що таке генетичний алгоритм |

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

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

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

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

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

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

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

Повертаючись до задачі оптимального розподілу інвестицій, пояснимоособливості реалізації генетичного алгоритму в цьому випадку.
Індивідуум = варіант рішення задачі = набір з 10 хромосом ХJ
Хромосома ХJ = обсяг вкладення в проект j = 16-розрядна запис цього числа
Так як обсяги вкладень обмежені, не всі значення хромосом єдопустимими. Це враховується при генерації популяцій.
Так як сумарний обсяг інвестицій фіксованим, то реально варіюютьсятільки 9 хромосом, а значення 10-ій визначається за ним однозначно.

| 3 | Детальний опис генетичного aлгорітма |

1. Створення структури рішення шуканої завдання у вигляді масиву a [i], i = 1,.
. . n, де n - максимальне число компонент структури. Приклад: пошук функціїy = f (x) найкращого у класі поліномів наближення експериментальних точок
(xi, yi), j = 1 ,..., m.

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

2. Створення показника ефективності структури, заповненої конкретнимизначеннями. Приклад: Показником ефективності для нашого прикладу буденев'язки певна методом найменших квадратів Ja = I1 + I2 + .. + Im, де
Ij = (yj-fa (xj)) 2,

де fa (x) є сума всіх елементів виду aixi, де ai = 0 або 1

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

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

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

5. Природний відбір структур за певним правилом вибору найкращихструктур серед заданого масиву структур. Приклад: можна за правилом виду
J0 = M (Jk) - середнє значення Jk, якщо Jk