 |
|
Основні поняття генетичних алгоритмів
ВСТУП
Тема науково-дослідної роботи: «Еволюційне програмування. Генетичні алгоритми».
Актуальність дослідження Дуже актуальною є тема еволюційного програмування та генетичних алгоритмів, тому що еволюція не зупиняється, з кожним днем все більше і більше ми наближаємось до того часу коли все за нас будуть виконувати машини. Генетичні алгоритми значно спрощують вирішення цілком складних задач та прискорюють вирішення задачі за допомогою спеціальних методів оптимізації. Еволюційне програмування використовують для розвитку комп'ютерних програм. Системи розроблені еволюційним програмуванням містять спеціальний транслюючий модуль, що переводить знайдені залежності з внутрішньої мови системи на зрозумілу користувачу мову, математичних формул, таблиці тощо, роблячи їх легкодоступними.
Об’єктом дослідження являються основи еволюційного програмування та ознайомлення з генетичними алгоритмами.
Метою дослідженняєознайомлення з використанням задач моделювання, дослідити генетичні алгоритми.
Генетичні алгоритми
Основні поняття генетичних алгоритмів
Групу алгоритмів, що використовують ідею Дарвіна як основну про еволюцію називають генетичними алгоритмами. Вони можуть ділитися на такі напрями: генетичні алгоритми, стратегії еволюції, генетичне програмування, еволюційне програмування.
Генетичні алгоритми використовуються для вирішення таких задач: пошук глобального екстремуму для багато параметричних і наближених функцій, задач для знаходження найкоротшого шляху, оптимального розміщення, налаштування нейронних систем, розроблення ігрових стратегій.
Фактично генетичні алгоритми оптимізують значення багато параметричних функцій, тому їх галузь використання така широка. Всі представлені задачі формуються як функції, які залежать від деякої кількості параметрів і глобальний максимум яких відповідатиме розв’язку задачі.
Ідея генетичних алгоритмів запозичена в живої природи й полягає у організації еволюційного процесу, кінцевою метою якого є отримання оптимального рішення на складної комбінаторної завданню. Розробник генетичних алгоритмів виступає у разі як творець, який має правильно встановити закони еволюції, щоб домогтися бажаної мети якнайшвидше.
Нижче, у підрозділах, буде описано кожний з пунктів даного довільного алгоритму.
Оскільки якість рішення звичайно оцінюється деякою оцінної функцією, генетичні алгоритми також називають методом оптимізації багато екстремальних функцій. У процесі еволюції популяція виробляє якості, необхідних виживання і пристосування, і який це й є оптимальним розв'язанням.
Сьогодні генетичні алгоритми довели свою конкурентоспроможність під час вирішення багатьох тяжких завдань і найбільше у практичних додатках, де математичні моделі мають складну структуру й застосування їх стандартних методів типу гілок і національних кордонів, динамічного чи лінійного програмування вкрай ускладнено.
Довільний генетичний алгоритм зображено на рисунку1.1.
Рис.1.1 - Схема роботи генетичного алгоритму
Іншими словами генетичний алгоритм — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.
Особливістю генетичного алгоритму є акцент на використання оператора схрещення, який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі.
Батьком-засновником генетичних алгоритмів вважається Джон Голланд, книга якого Адаптація в природних і штучних системах є фундаментальною в цій сфері досліджень.
Генетичні алгоритми застосовуються при розробці програмного забезпечення, в системах штучного інтелекту, оптимізації, штучних нейронних мережах і в інших галузях знань.
Слід зазначити, що з їх допомогою вирішуються завдання, для яких раніше використовувалися тільки нейронні мережі. У цьому випадку генетичні алгоритми виступають просто в ролі незалежного від нейронних мереж альтернативного методу, призначеного для вирішення тієї ж самої задачі.
Прикладом може служити задача комівояжера, що спочатку розв’язувалась за допомогою мережі Хопфілда.
Генетичні алгоритми часто використовуються спільно з нейронними мережами. Вони можуть підтримувати нейронні мережі або навпаки, або обидва методи взаємодіють у рамках гібридної системи, призначеної для вирішення конкретного завдання [1].