Дослідження генетичних алгоритмів для пошуку оптимальних шляхів в системі проведення метромарафонів

Abstract

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