Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Застосування генетичних алгоритмів для вирішення задач оптимізації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2019
Тип роботи:
Лабораторна робота
Предмет:
СП
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЕОМ
/
Лабораторна робота №1
з дисципліни: «Технології штучного інтелекту в комп’ютерних та кіберфізичних системах»
на тему: «Застосування генетичних алгоритмів для вирішення задач оптимізації»
Мета роботи: навчитися розв’язувати задачі оптимізації за допомогою генетичного алгоритму, навчитися програмно реалізовувати генетичний алгоритм. Генетичний алгоритм – потужний інструмент для вирішення складних задач. Він знайшов своє застосування серед задач оптимізації, інженерії, штучного інтелекту. В основу алгоритму покладено принципи біології та генетики – створення популяції індивідів, кожен з яких представляється у вигляді хромосоми. Своїм існуванням генетичні алгоритми завдячують спробам наслідування природних процесів, які відбуваються серед живих організмів – селекції та еволюції популяції живих істот. Ідею генетичного алгоритму у 1975 році запропонував Джон Холланд (J.H.Holland). Він припустив, що складений відповідним чином алгоритм біологічної еволюції може бути покладений в основу розв’язання складних проблем.
Представлення об’єктів.Біологічно кожен організм може бути представлений своїм фенотипом ( котрий визначає чим є об’єкт у реальному світі) та генотипом ( котрий містить інформацію про цей об’єкт на рівні хромосомного набору). Кожен ген, тобто елемент інформації генотипу, містить своє відображення у фенотипі. Генетичні алгоритми моделюють природну еволюцію та використовуються здебільшого для розв’язання задач оптимізації. Генетичний алгоритм перейняв термінологію з генетики: хромосома (елемент популяції), популяція ( випадковий набір допустимих розв’язків), алель (значення гена), ген (елемент хромосоми, двійковий розряд), локус (позиція гена у хромосомі), алель (значення гена), покоління ( результат наступної ітерації роботи алгоритму), фенотип ( числове значення хромосоми). Генетичний алгоритм.Класичний генетичний алгоритм зображений на рис.1
/ Рис.1 Блок-схема роботи генетичного алгоритму.
1. Створення початкової популяції. На першому етапі роботи створюємо певну початкову популяцію. Навіть якщо вона буде неконкурентоспроможною алгоритм сам перетворить її у «живу» популяцію. З популяції випадково вибираємо N хромосом у вигляді бітових ланцюжків довжиною L. Вводимо поняття номеру популяції К ( для початкової К=0).
2. На даному етапі необхідно обчислити значення функції відповідності кожної хромосоми. Чим вище значення функції, тим вища якість хромосоми.
3. Умови зупинки алгоритму . Алгоритм припиняє свою роботу у наступних випадках: коли досягнуто шуканого значення( із заданою точністю); коли подальша робота алгоритму не може покращити отриманий результат; коли був вичерпаний заданий ліміт часу чи кількості ітерацій. У випадку зупинки алгоритму виводимо найкращу хромосому.
4. Відбір хромосоми. Обчисливши значення функції відповідності відбираємо нащадків хромосом із найбільшим значенням. Зазвичай відбір проводиться методом рулетки. Результатом роботи операції є батьківський пул з N хромосом. Відповідно його розмір збігається із розміром початкової популяції.
5. Створення нової популяції. Створення нової популяції досягається застосуванням генетичних операторів. За їх допомогою ми утворюємо нову популяцію нащадків. В класичному алгоритмі використовують два генетичних оператори – схрещування та мутація. При цьому схрещування відбувається завжди, а мутація доволі рідко. При реалізації генетичного алгоритму задається ймовірність схрещування Pc (0,5≤ Pc ≥ 1) та ймовірність мутації Pm (0 ≤ Pm ≥ 0,5) . Сутність методу рулетки для селекції хромосом (roulette wheel selection) Метод моделює випадковий вибір, за аналогією рулетки в казино. Рулетка ділиться на частини, кожна з яких відповідає кожній хромосомі. Розмір секції рулетки є пропорційним до значення функції відповідності цієї хромосоми. Чим більше значення функції відповідності, тим більша частина кола відповідає йому на рулетці і навпаки. Математично це можна зобразити так: u(chi ) = ps (chi ) *100% ,
де chi - хромосома, u(chi ) - відрізок кола, який становить частину цілого кола,
i = 1,2KN ,
N-кількість елементів популяції,
/ де F(chi ) -- значення функції відповідності для хромосоми chi ,
ps (chi ) -- ймовірність селекції хромосоми chi .
Для вибору хромосом проводиться обертання рулетки. Ймовірність вибору певної хромосоми є тим більшою, чим більше значення її функції відповідності. Вибір способу кодування Для використання генетичного алгоритму хромосому необхідно представити у відповідному числовому значенні. Найпростіший варіант – бітове представлення. Бітове представлення хромосоми є досить зручне та просте. Проте, проблема такого кодування полягає у тому, що сусідні числа послідовності відрізняються у значеннях кількох бітів. Наприклад, числа 7 та 8 у бітовому
Завдання:
Максимізувати та мінімізувати функцію однієї змінної (x+3)3 – 7, x є [0; 60]. Обчислення провести з точністю до 10-n , де n=0,1,2 …
Розв’язок:
Для кодування виберемо п’ятибітовий двійковий код. Виберемо початкову популяцію (к=0), яка складатиметься із 4 бітових ланцюжків (N=4). Таку комбінацію можна отримати двома шляхами. Перший полягає у випадковому виборі 4 цифр із діапазону від 0 до 31. Інший полягає у підкиданні 20 разів монети( 4 комбінації * 5 бітів). Нехай першим шляхом ми отримали наступну популяцію: 15(01111b), 27(11011b), 10(01010b), 6(00110b). В даному випадку бітове представлення чисел називається популяцією, а числа в десятковому форматі – фенотипом. Кожну із утворених хромосом підставляємо у задану функцію f (x) = x 2 . В результаті отримаємо 152 = 255, 272 = 729, 102 = 100, 62 = 36 - це будуть значення цільової функції. Тепер цю популяцію необхідно розложити на рулетці для проведення вибору хромосом. Для цього знайдемо суму значень цільової функції 225+729+100+36=1090 . Обраховуємо частину кола, яку займе хромосома( наприклад, перший бітовий ланцюжок має значення 225 при сумі 1090, що становить 21% чи 0,21) 225/1090=0,21 ; 729/1090 =0,67 ; 100/1090=0,09 ; 36/1090=0,03. Як видно, сума отриманих значень повинна становити одиницю, перевіримо 0,21+0,67+0,09+0,03=1. Порахуємо очікувану кількість копій кожної хромосоми. Для цього потрібно кожну із частин кола помножити на кількість хромосом, а саме 0,21*4=0,84 ; 0,67*4=2,68 ; ,09*4=0,36 ; 0,03*4=0,12. Оскільки у нас є 4 хромосоми, то рулетку будемо обертати 4 рази (щоб кожній хромосомі дати шанс на виживання). Нехай ми отримали наступний батьківський пул – одна копія першого та третього ланцюжків , дві других і жодного четвертого. Отримані результати і виправдали сподівання – найкращі ( відповідно до значення цільової функції) хромосоми збільшили свою популяцію, середні залишились на тому ж рівні, а найгірші відмерли. Отримавши батьківський пул необхідно застосувати генетичні оператори – схрещування та генеруємо числа від 1 до 4 ( відповідно до кількості хромосом). Нехай ми отримали наступні результати:
Таблиця 2. Вибір партнера для схрещування
/
Вибравши партнера, необхідно вибрати пункт поділу хромосоми. Лінія схрещування будується підкиданням монети 2 рази. Як результат, отримаємо двійковий код 00, 01, 10, 11 , що в свою чергу і буде вказувати на 2, 3,4 – ту позиції. Це відбудеться при ймовірності схрещування Рс=1. Нехай у результаті підкидання монети ми отримали такі дані
Таблиця 3. Проведення лінії схрещування
/
Отже, проводимо схрещування. 1-ша хромосома схрещується з 2-ю і лінія схрещування проходить через 3 позицію, 3 з 4 і лінія проходить через 4 позицію:
/
Рис.3. Застосування операції схрещування
Далі виконуємо операцію мутації. Операція виконується для кожної алелі окремо. Нехай ймовірність мутації становить Рм=0,003, то маючи 20 бітів, зміниться 20*0,003= 0,06 біти. Це означає, що жоден з бітів не зазнає мутації. Але якщо ймовірність становить Рм=0,3 то зміниться 20*0,3=6 бітів. Тому випадковим чином генеруємо 4 номери позиції зміни позиції хромосоми і їх значення міняємо на протилежні. Наприклад, якщо випали позиції 3, 6, 18, 9, то хромосоми приймуть такі значення
1. 01011 2. 01001 3. 11010 4. 01111 Після закінчення операцій нове покоління піддається оцінюванню. Для цього обчислюємо значення функції.
Таблиця 4. Результат застосування генетичних операторів
/
Отже, лише після першої генерації середнє значення функції відповідності збільшилось із 272 до 437. Найкраща хромосома з першого покоління отримала дві копії завдяки високій оцінці відповідності. Алгоритм можна використовувати і для мінімізації функції. Зазначимо, що без втрати загальності , можна розв’язувати тільки задачі максимізації. Якщо потрібно функцію мінімізувати, то відповідно переходимо до максимізації функції g, де g= -f . При розв’язку задач максимізації функції багатьох змінних суть алгоритму не змінюється. Кожна хромосома зображається бітовим кодом довжиною /, де перші m1 бітів відповідають змінній x1, другі m2 бітів – змінній x2 і так до останніх mi бітів, що відповідають змінній xk Для вибору початкової популяції можна згенерувати випадково біт за бітом N хромосом. При наявності інформації про розміщення оптимумів можна використати її для визначення початкових розв’язків. Решта алгоритму є очевидною. При розв’язку задачі із заданою точністю, наприклад із 4 значущими десятковими цифрами для кожної змінної, кожний відрізок D, ділиться на (bi - ai ) ×104 рівних відрізків. Нехай mi таке найменше ціле число, що (bi - ai )×104 £ 2mi -1. Тоді зображення, в якому кожна змінна xi закодована у вигляді бітового ланцюжка довжини mi буде задовольняти вимоги точності. Значення цього ланцюжка можна представити у десятковій системі числення за допомогою наступного представлення xi = ai + dec(ch)× (bi - ai ) /(2mi -1) , де dec(ch) – десяткове представлення бітового ланцюжка ch.
Висновок: навчився розв’язувати задачі оптимізації за допомогою генетичного алгоритму, програмно реалізовувати генетичний алгоритм.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора