Перспективні прикладні системи підтримки прийняття рішень. Генетичні алгоритми

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

 

 

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

• Основний (класичний) ГА складається з наступних кроків
• Ініціалізація, або вибір початкової популяції хромосом.
• Оцінювання пристосованості хромосом в популяції
• Перевірка умови закінчення алгоритму.
• Селекція хромосом
• Використання генетичних операторів
• Формування нової популяції
• Вибір найкращої хромосоми

 

Розглянемо ГА більш детально:

Ініціалізація, або вибір початкової популяції хромосом. Полягає у випадковому виборі заданої кількості N хромосом (особин), які представляються двійковими послідовностями довжини L.

Оцінювання пристосованості хромосом в популяції полягає у розрахунку функції пристосованості для кожної хромосоми.

Перевірка умови закінчення алгоритму. Алгоритм може бути закінчений, якщо його виконання не приводить до покращення отриманого результату або через певний проміжок часу..

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

Використання генетичних операторів до відібраних у результаті селекції батьківських хромосом приводить до створення популяції нащадків. В класичному га використовують два основних генетичних оператора: оператор схрещування (crossover) і оператор мутації (mutation). Як і живих організмах, ймовірність мутації звичайно дуже мала (рм<0,1).

В ГА мутація може виконуватися на популяції батьків перед схрещуванням або на популяції нащадків, утворених у результаті схрещування.

Оператор схрещування. На першому етапі схрещування вибиваються пари хромосом з батьківської популяції. Операції схрещування полягають у обміні фрагментами ланцюжків між двома батьківськими хромосомами. Далі для кожної пари вибирається позиція гена (локус) в хромосомі, який визначає точку схрещування. Якщо хромосома містить L війкових чисел, то точка схрещування LK вибирається випадковим чином з інтервалу [1, L]. В результаті схрещування утворюються два нащадки

Оператор мутації з малою ймовірністю змінює значення гену в хромосомі на протилежне.

Формування нової популяції. Хромосоми, отримані у результаті генетичних операторів до популяції предків, утворюють нову популяцію. Така популяція стає поточною для даної ітерації k ГА. На кожній ітерації розраховується значення функції пристосованості для всіх хромосом. В результаті перевірки умови закінчення ітерацій відбувається або зупинка алгоритму, або перехід до нового кроку ГА – селекції. В результаті селекції вся попередня популяція замінюється популяцією нащадків з кількістю N.

Вибір найкращої хромосоми. Найкращою вважається хромосома з максимальним значенням функції пристосованості.

 

 

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

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

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

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

 

 

1. Єремєєв А.В. Розробка та аналіз генетичних і гібридних алгоритмів для вирішення задач дискретної оптимізації,  2012.
2. Коршунов Ю.М. «Математичні основи кібернетики. Для студентів вузів», 2007.
3. Вентцель Є.С. «Дослідження операцій»,1992.
4. Завада О.П. «Алгоритмізація і програмування», 2004.
5. http://ua-referat.com/Генетичний_алгоритм
6. http://bukvar.su/informatika_programmirovanie/page,3,170754-Geneticheski...
7. https://studfiles.net/preview/5465767/
8. http://studopedia.com.ua/1_310240_I-genetichni-algoritmi.html