тод, заснований на селекції кращих елементів в популяції.
Основою для виникнення генетичних алгоритмів послужила модель біологічної еволюції Ч. Дарвіна і методи випадкового пошуку. Л. Растригин відзначав [17], що випадковий пошук виник як реалізація найпростішої моделі еволюції, коли випадкові мутації моделювалися випадковими кроками оптимального рішення, а відбір - «усуненням» невдалих елементів. Еволюційний пошук з погляду перетворення інформації - це послідовне перетворення одного кінцевого нечіткої множини проміжних рішень в інше. Генетичні алгоритми - це не просто випадковий пошук. Вони ефективно використовують інформацію, накопичену в процесі еволюції.
Мета генетичних алгоритмів полягає в тому, щоб:
· абстрактно і формально пояснювати адаптацію процесів в природній системі та інтелектуальної дослідницької системі;
· моделювати природні еволюційні процеси для ефективного вирішення завдань науки і техніки.
В даний час використовується нова парадигма рішень оптимізаційних задач на основі генетичних алгоритмів і їх різних модифікацій. Генетичні алгоритми здійснюють пошук балансу між ефективністю та якістю рішень за рахунок «виживання найсильніших альтернативних рішень» в невизначених і нечітких умовах.
Генетичні алгоритми відрізняються від інших оптимізаційних і пошукових процедур наступним [7,8,9]:
· працюють в основному не з параметрами завдання, а з закодованим безліччю параметрів;
· здійснюють пошук не шляхом поліпшення одного рішення, а шляхом використання відразу декількох альтернатив на заданій множині рішень;
· використовують цільову функцію, а не її різні приросту для оцінки якості прийняття рішень;
· застосовують не детерміновані, а імовірнісні правила аналізу оптимізаційних задач.
Для роботи генетичних алгоритмів вибирають безліч натуральних параметрів оптимізаційної проблеми і кодують їх у послідовність кінцевої довжини в деякому алфавіті. Вони працюють доти, поки не буде виконано задане число генерацій (ітерацій алгоритму) або на деякій генерації буде отримано рішення певної якості, або коли знайдений локальний оптимум, тобто виникла передчасна збіжність і алгоритм не може знайти вихід з цього стану. На відміну від інших методів оптимізації ці алгоритми, як правило, аналізують різні області простору рішень одночасно і тому вони більш пристосовані до знаходження нових областей з кращими значеннями цільової функції [7].
На малюнку 5 представлена ??блок-схема генетичного алгоритму [4].
Малюнок 5 - Блок-схема генетичного алгоритму
4.1.1 Символьна модель
Мета оптимізації за допомогою ГА полягає в тому, щоб знайти краще можливе рішення або рішення задачі по одному або декільком критеріям. Щоб реалізувати генетичний алгоритм, потрібно спочатку вибрати відповідну структуру для представлення цих рішень. У постановці завдання пошуку примірник цієї структури даних являє собою точку в просторі пошуку всіх можливих рішень.
Структура даних генетичного алгоритму складається з однієї або більше хромосом. Як правило, хромосома - це бітова рядок, так що термін рядок часто замінює поняття «хромосома». В принципі, ГА не обмежені бінарними уявленнями. Відомі інші реалізації, побудовані виключно на векторах дійсних чисел. Незважаючи на те, що для багатьох реальних завдань більше підходять рядки змінної довжини, в даний час структури фіксованої довжини найбільш поширені і вивчені.
Кожна хромосома (рядок) являє собою об'єднання ряду подкомпонентов, званих генами. Гени розташовуються в різних позиціях або локусах хромосоми, і приймають значення, звані алелями. В уявленнях з бінарними рядками, ген-біт, локус - його позиція в рядку, і аллель - його значення (0 або 1). Біологічний термін «генотип» відноситься до повної генетичної моделі особини і відповідає структурі в ГА. Термін «фенотип» відноситься до зовнішніх спостережуваним ознаками і відповідає вектору в просторі параметрів. Надзвичайно простий, але ілюстративний приклад - завдання максимізації наступної функції двох змінних:
Зазвичай, методика кодування реальних змінних і полягає в їх перетворенні в двійкові цілочисельні рядка достатньої довжини - достатньою для того, щоб забезпечити бажану точність. Припустимо, що 10-ти розрядне кодування достатньо для і. Встановити відповідність між генотипом і фенотипом закодованих особин можна, розділивши відповідне двійкове число на. Наприклад, 0000000000 відповідає 0/1023 або 0, тоді як 1111111111 відповідає 1023/1023 або 1. Оптимізована структура даних - 20-ти бітна рядок, що представляє конкатен...
