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

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

Інститут Математики і Комп’ютерних Наук.

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

Курсової проект.

Тема:

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

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

Несов Роман Геннадьевич.

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

Кленин Олександр Сергеевич.

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

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

.. ... .3.

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

.. .. .4.

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

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

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

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

. .9.

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

.. .. .11.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|Хромосома |Вектор (послідовність) з нулів і одиниць. | | |Кожна позиція (біт) називається геном. | |Індивідуум = |Набір хромосом = варіант вирішення даної завдання. | |генетичний | | |код | | |Кросовер |Операція, коли він дві хромосоми обмінюються своїми | | |частинами. | |Мутація |Cлучайное зміна одній або кількох позицій в | | |хромосомі. |.

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

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

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

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

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

|3 |Докладний опис генетичного aлгоритма |.

1. Створення структури рішення шуканої завдання у вигляді масиву a[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.