НОУ ІНТУІТ, Лекція, Діагностична задача в інтервальній постановці
При такому виборі цільова функція буде невід'ємною у всій області допустимих значень та приймати значення 0 лише на рішеннях інтервальної діагностичної задачі.
Однак у класичному розумінні цільової функції як функції пристосованості необхідно, щоб пристосовані особини оцінювалися вище, ніж менш пристосовані. Цього легко досягти, якщо здійснити нормалізацію цільової функції та звернути її:
Таким чином, цільова функція прийматиме значення в діапазоні від 0 до 1. При цьому більшому значенню цільової функції відповідає великий ступінь пристосованості хромосоми, тобто дана цільова функція є "істинно" функцією пристосованості. Вочевидь, що з рішеннях інтервальної діагностичної завдання цільова функція прийматиме значення 1.
У ході дослідження поставленої інтервальної діагностичної задачі було написано програму, яка вирішує це завдання. Основу програми є реалізація простого генетичного алгоритму мовою C. Ця реалізація має ім'я SGA-C v. 1.1 (Simple Genetic Algorithm on C), і є інтерпретацією коду з книги Goldberg D.E. "Genetic Algorithms in Search, Optimization, and Machine Learning" (1989) мовою C.
SGA-C реалізує простий генетичний алгоритм, який містить оператори відбору, схрещування та мутації, та механізм завдання ймовірності застосування цих операторів. При цьому SGA-C дозволяє досліднику зробити налаштування для вирішення його специфічних завдань за допомогою набору функцій файлу app.c. Для вирішення поставленої інтервальної діагностичної задачі були написані такі функції:
- Функція початкової ініціалізації даних користувача: зчитуєосновних параметрів (характеристики поля, довжини діагностичної послідовності), характеристичних матриць ЛА, вхідних та вихідних векторів.
- Функція пристосованості objfunc(): здійснює обчислення функції за формулами (20.10)-(20.12).
- Функція звіту app_report () : друкує всіх знайдених у ході роботи програми рішень та їх кількості.
- Функція chrom2matrix (): Декодування хромосоми в матрицю.
- Функції matrix_sum(), matrix_mult(): реалізують операції складання та множення матриць.
Розглянемо ряд прикладів вирішення сформульованої діагностичної задачі із застосуванням даної програми.
Розв'яжемо інтервальну діагностичну задачу для ЛА з прикладу 1.
Згідно з описаною вище рекомендацією, ймовірність оператора кросинговера покладемо рівною 0.1, а ймовірність оператора мутації . Нехай населення складається з 20 хромосом, довжина хромосоми дорівнює 9 і максимальна кількість поколінь дорівнює 100. За таких параметрів генетичного алгоритму програмою було знайдено рішення: . Як відомо (приклад 1), це рішення є шуканим рішенням інтервальної діагностичної задачі .
Як було сказано вище, ймовірності операторів відіграють велику роль під час роботи генетичного алгоритму. Щоб проілюструвати це, це завдання вирішувалося за різних ймовірностей оператора схрещування ( ) та оператора мутації ( ). У наведеній нижче таблиці міститься інформація про знаходження рішення інтервальної діагностичної задачі для різних значень і (у клітині таблиці стоїть 0, якщо рішення не знайдено, 1 - якщо знайдено).
З цієї таблиці можна зробити такі висновки: