Контрольна робота
Рішення задачі оптимізації методом генетичного алгоритму
Введення
алгоритм змінна кроссинговер
У процесі виконання даної контрольної роботи була написана програма Matlab, основним завданням якої є проведення умовної мінімізації заданої функції декількох змінних на основі застосування генетичного алгоритму (ГА). Генетичний алгоритм був реалізований по рівняннях і даними, заданих відповідно до варіанту. Також була реалізована настройка ГА вбудованою функцією gaoptimset. Результат був порівняний з результатом написаної програми. Також були проведені дослідження роботи ГА з необхідними графічними ілюстраціями відповідно до варіанта.
1. Постановка завдання
Мета роботи.
Навчитися реалізовувати умовну мінімізацію заданої функції декількох змінних на основі застосування генетичного алгоритму (ГА) в середовищі Matlab, навчитися реалізовувати алгоритм, не використовуючи вікно тулбокса, налаштовувати ГА вбудованою функцією MATLAB gaoptimset і досліджувати роботу ГА, реалізуючи різні графіки, діаграми, таблиці.
Завдання на контрольну роботу.
) Провести умовну мінімізацію заданої функції декількох змінних на основі застосування генетичного алгоритму (ГА), програмно реалізованого в Matlab (використовувати тільки стандартну функцію).
) Скласти програму рішення задачі в Matlab у вигляді m-файлу, не використовуючи вікно тулбокса.
) Для налаштування ГА використовувати функцію gaoptimset. Всі задаються опції прописати в розробленій програмі явним чином.
) Провести дослідження роботи ГА з необхідними графічними ілюстраціями відповідно до варіанта.
Індивідуальне завдання.
Варіант №24.
5) Дана наступна функція:
1) Побудувати графік заданої функції при n =2. Визначити візуально, чи має дана функція глобальний мінімум.
) Провести оптимізацію заданої функції в Matlab (за допомогою генетичного алгоритму): знайти глобальний мінімум.
3) Для вирішення завдання скласти програму в середовищі Matlab (m-файл).
4) Результат визначити як середнє по 20 рішенням.
5) У звіті відобразити хід рішення задачі:
- представити графік середніх і найкращих за поколінням значень цільової функції;
провести дослідження залежності рішення від виду функції відбору батьків для кросинговеру і мутації нащадків.
2. Теоретичні відомості
2.1 Поняття генетичного алгоритму
Генетичні алгоритми - це адаптивні методи пошуку, які останнім часом використовуються для вирішення завдань оптимізації. У них використовуються як аналог механізму генетичного наслідування, і аналог природного відбору. При цьому зберігається біологічна термінологія в спрощеному вигляді і основні поняття лінійної алгебри. Основною ідеєю генетичних алгоритмів є організація «боротьби за існування» і «природного відбору» серед цих пробних рішень.
Розглянемо принципи роботи генетичних алгоритмів на максимально простому прикладі. Нехай потрібно знайти глобальний мінімум функції на відрізку [0; 7]. На цьому відрізку функція приймає мінімальне значення в точці x=1. Очевидно, що в точці x=6 функція потрапляє в локальний мінімум. Якщо для знаходження глобального мінімуму використовувати градієнтні методи, то в залежності від початкового наближення можна потрапити в даний локальний мінімум.
Розглянемо на прикладі даної задачі принцип роботи генетичних алгоритмів. Для простоти покладемо, що x приймає лише цілі значення, тобто x? {0, 1, 2, 3, 4, 5, 6, 7}. Це припущення істотно спростить виклад, зберігши всі основні особливості роботи генетичного алгоритму. Виберемо випадковим чином кілька чисел на відрізку [0; 7]: {2, 3, 5, 4}. Запишемо пробні рішення в двійковій формі: {010, 011, 101, 100}. Оскільки генетичні алгоритми використовують біологічні аналогії, то і применяющаяся термінологія нагадує біологічну. Так, одне пробне рішення, записане в двійковій формі, ми будемо називати особиною або хромосомою, а набір всіх пробних рішень - популяцією. Як відомо, принцип природного відбору полягає в тому, що в конкурентній боротьбі виживає найбільш пристосований. У нашому випадку пристосованість особини...
