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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Чорноморський національний університет
імені Петра Могили

Факультет комп’ютерних наук

Кафедра інформаційних технологій і програмних систем

КУРСОВА РОБОТА 

з дисципліни «Методи і системи штучного інтелекту»

на тему: «Генетичні алгоритми»

6.050101 – КР.ПЗ.01 – 304.21410702

Виконав: студент 3 курсу, групи 304

напряму підготовки 6.050101 «Комп’ютерні науки»
_________________________В.Ю. Гнатовський__ 

        (підпис, ініціали та прізвище)

___________________________

                (дата)

Керівник: доц. каф. ІТ і ПС,
канд. техн. наук, доц. Калініна І. О.

Національна шкала _________________________

Кількість балів: ________ Оцінка: ECTS ______

м. Миколаїв – 2017 рік

ЗМІСТ

ВСТУП        3

1 ЗАВДАННЯ        4

2 ТЕОРЕТИЧНІ ВІДОМОСТІ        5

РЕЗУЛЬТАТИ РОБОТИ ПРОГРАМИ        13

ВИСНОВКИ        14

ДОДАТОК А ЛІСТИНГ ПРОГРАМНОГО КОДУ        15

ВСТУП

        Генетичний алгоритм - це в першу чергу еволюційний алгоритм, іншими словами, основна фішка алгоритму - схрещування (комбінування). Як нескладно здогадатися ідея алгоритму нахабним чином взята у природи, благо вона не подасть на це до суду. Так от, шляхом перебору і найголовніше відбору виходить правильна «комбінація».                                                        Алгоритм ділиться на три етапи:

• Схрещування

• Селекція (відбір)
• Формування нового покоління

        Якщо результат нас не влаштовує, ці кроки повторюються до тих пір, поки результат нас не почне задовольняти чи відбудеться одне з нижче перерахованих умов:

• Кількість поколінь (циклів) досягне заздалегідь обраного максимуму

Вичерпано час на мутацію

1 ЗАВДАННЯ

Скласти програму для знаходження цілих невід’ємних коренів рівняння.

[pic 1],                                        (1)

де [pic 2]- цілі додатні числа.

Реалізувати генетичний алгоритм, для вирішення задачі для різної кількості змінних рівняння, для різних значень коефіцієнтів с; передбачити можливість зміни кількості хромосом у популяції та кількості мутованих хромосом; навести кількість епох, необхідних для вирішення задачі.                        Варіант:

2 ТЕОРЕТИЧНІ ВІДОМОСТІ

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

Представимо рівняння (1) в загальному вигляді:

[pic 4]                                                (2)

        Так як розв’язками цього рівняння є натуральні числа, то справедливим є обмеження

[pic 5]                                                (3)

Розглянемо приклад:

[pic 6]                                (4)

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

Послідовність кроків алгоритму:

1. Створити початкову популяцію хромосом.
2. Обчислити функцію пристосування для кожного екземпляру популяції.
3. Провести відбір за деяким критерієм на основі значення функції пристосування.
4. З відібраних екземплярів, шляхом рекомбінації (кросовера), створити нову популяцію.
5. Провести операцію мутації з довільно обраним екземпляром популяції.
6. Якщо рішення не знайдене, обчислити функцію пристосування для кожного екземпляру нової популяції та перейти до кроку 3.
7. Кінець

Створення початкової популяції