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



Сторінка3/10
Дата конвертації12.04.2017
Розмір0.65 Mb.
1   2   3   4   5   6   7   8   9   10

1.2 Доцільність використання генетичних алгоритмів в задачах оптимізації

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

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

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

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

а)обробляють не значення параметрів самого завдання, а їх закодовану форму;

б)здійснюють пошук рішення виходячи не з єдиної точки, а з їх деякої популяції;

в)використовують тільки цільову функцію, а не її похідні або іншу додаткову інформацію;

г)застосовують імовірнісні, а не детерміновані правила вибору.

Перераховані чотири властивості, які можна сформулювати також як кодування параметрів, операції на популяціях, використання мінімуму інформації про завдання і рандомізація операцій приводять у результаті до стійкості генетичних алгоритмів і до їх переваги над іншими широко вживаними технологіями [12].




1.3 Основні поняття генетичних алгоритмів

При описі генетичних алгоритмів використовуються визначення, запозичені з генетики. Наприклад, мова йде про популяцію особин, а в якості базових понять застосовуються ген, хромосома, генотип, фенотип, алель. Також використовуються відповідні цим термінам визначення з технічного лексикону, зокрема, ланцюг, двійкова послідовність, структура.

Популяція — це кінцева множина особин.

Особини, що входять в популяцію, у генетичних алгоритмах представляються хромосомами з закодованими в них множинами параметрів задачі, тобто рішень, які інакше називаються точками в просторі пошуку (search points). У деяких роботах особини називаються організмами.

Мутація – зміна генетичного матеріалу. Мутації розглядаються як рушійна сила еволюції, де менш сприятливі мутації видаляються з генофонду, а сприятливі накопичуються.

Хромосоми (інші назви — ланцюжки або кодові послідовності) — це впорядковані послідовності генів.

Кросинговер — явище обміну ділянками хромосом.

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

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

Фенотип — це набір значень, які відповідає даному генотипу, тобто декодована структура або безліч параметрів задачі (розв’язок, точка простору пошуку).

Алель — це значення конкретного гена, також визначається як значення властивості або варіант властивості.

Локус чи позиція вказує місце розміщення даного гена в хромосомі (ланцюжку). Множина позицій генів — це локи.

Дуже важливим поняттям у генетичних алгоритмах вважається функція пристосованості (fitness function), яка інакше називається функцією оцінки. Вона являє міру пристосованості даної особини в популяції. Ця функція відіграє найважливішу роль, оскільки дозволяє оцінити ступінь пристосованості конкретних особин у популяції і вибрати з них найбільш пристосовані (тобто мають найбільші значення функції пристосованості) відповідно з еволюційним принципом виживання «найсильніших» (які найкраще пристосувалися).

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

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

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


2. ЕТАПИ ВИКОРИСТАННЯ ГЕНЕТИЧНОГО АЛГОРИТМУ




2.1 Загальна схема генетичного алгоритму

Схема використання генетичного алгоритму для вирішення деякої задачі складається з таких етапів:



  1. Генерація випадкового початкового стану

Перше покоління створюється з довільно вибраних рішень (хромосом). Це відрізняється від стандартних методів, коли початковий стан завжди одне й те саме.

д)Обчислення коефіцієнта пристосованості (fitness)

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

е)Відтворення

Хромосоми, що мають високий рівень пристосованості (fitness), потрапляють до нащадків (які потім можуть мутувати) з більшою ймовірністю. Нащадок, результат злиття 'батька' і 'матері', є комбінацією їх ген. Цей процес називається 'кросінговер' (crossing over).

ж)Наступне покоління

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




Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8   9   10


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал