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

 Практична робота №2

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

Мета роботи:

Вивчити основні принципи побудови генетичних алгоритмів та методику застосування основних генетичних операторів для вирішення задач теорії штучного інтелекту.

Завдання:

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

[pic 1],                                        (1)

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

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

Теоретичні відомості:

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

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

[pic 3]                                                (2)

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

[pic 4]                                                (3)

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

[pic 5]                                (4)

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

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

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

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

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

Таблиця 1

Початкова популяція

Обчислення функції пристосування

Функція пристосування обчислюється на основі підстановки значень генів хромосоми до рівняння

[pic 7]                                (5)

Таблиця 2

Значення функції пристосування

Процес відбору

Для проведення відбору обчислюється коефіцієнт пристосування. Для цього визначається різниця між еталонним значенням поліному та значенням функції пристосування: