UK 
EnglishDefault
Polski🚚 Оптимізатор Маршрутів Постачання — Генетичний Алгоритм у Дії
Спостерігайте, як генетичний алгоритм еволюціонує маршрути доставки між складами та клієнтами — відбір, кросовер і мутація скорочують відстань.
Про Оптимізатор Маршрутів Постачання
Ефективна маршрутизація автопарку доставки — це варіант однієї з найвідоміших задач інформатики: задачі комівояжера (TSP). Маючи склад і набір клієнтів, у якому порядку їх слід відвідати, щоб мінімізувати загальну пройдену відстань? Для будь-якої кількості зупинок, що перевищує жменьку, перевірка кожного можливого порядку є обчислювально безнадійною — лише 16 клієнтів дають понад 650 мільярдів різних маршрутів. Реальне логістичне програмне забезпечення натомість використовує метаевристики, що ведуть пошук інтелектуально, ніколи не гарантуючи ідеальної відповіді, і генетичний алгоритм (ГА) — один з найстаріших і найінтуїтивніших серед них.
Ця симуляція еволюціонує популяцію маршрутів-кандидатів доставки покоління за поколінням. У кожному поколінні маршрути оцінюються за загальною відстанню, пристосованіші (коротші) маршрути мають більшу ймовірність бути обраними як батьки, впорядкований кросовер поєднує два батьківські маршрути в дійсний дочірній маршрут, мутація обміну зсуває маршрути від їхньої поточної форми, а елітизм гарантує, що єдиний найкращий маршрут виживає незмінним. Спостерігайте, як найкращий маршрут малюється наживо на карті, а графік відстані за поколіннями трендує вниз у міру того, як популяція загалом стає пристосованішою — інколи виходячи на плато локального оптимуму, перш ніж вдала мутація проб'ється крізь нього.
Часті питання
Що таке генетичний алгоритм?
Генетичний алгоритм (ГА) — це евристика пошуку, натхненна природним відбором. Замість того, щоб виводити рішення аналітично, ГА підтримує популяцію кандидатів-рішень — тут це повні маршрути доставки — і повторно застосовує відбір, кросовер і мутацію для виведення нових кандидатів. Пристосованіші особини (коротші маршрути) із більшою ймовірністю передають свою структуру наступному поколінню. За багато поколінь середня якість популяції зростає, хоча жоден окремий маршрут ніколи не розв'язувався напряму, бо пошук паралельно досліджує багато ділянок простору рішень і постійно рекомбінує все, що працює.
Що насправді роблять кросовер і мутація тут?
Кожен маршрут — це перестановка зупинок клієнтів, тому звичайний кросовер створював би недійсні маршрути з повторюваними або пропущеними клієнтами. Ця симуляція використовує впорядкований кросовер (OX): суцільний відрізок зупинок копіюється з батька A на тих самих позиціях, а решта зупинок заповнюється з батька B у порядку їх появи, пропускаючи вже розміщені зупинки. Це гарантує дійсну перестановку. Мутація — це мутація обміну: з імовірністю, що дорівнює частоті мутацій, дві випадково обрані зупинки в маршруті міняються місцями, зсуваючи маршрут від його поточної форми, не створюючи при цьому недійсного туру.
Чому важливий елітизм?
Відбір, кросовер і мутація — усі стохастичні, тож покоління може випадково дати популяцію, яка в середньому гірша за попередню — кросовер може зруйнувати хороший маршрут, а мутація — пошкодити майже оптимальний. Елітизм копіює єдиний найкращий маршрут поточного покоління безпосередньо в наступне покоління, повністю незмінним. Це гарантує, що найкраща знайдена відстань ніколи не може погіршитися від покоління до покоління, тому крива «найкращої відстані» на графіку завжди рівна або спадає, але ніколи не зростає.
Як це пов'язано зі справжньою задачею комівояжера?
Це невеликий варіант маршрутизації транспорту задачі комівояжера (TSP): знайти найкоротший замкнений тур, що починається й закінчується на складі та відвідує кожного клієнта рівно один раз. TSP є NP-складною задачею — кількість можливих маршрутів для N клієнтів дорівнює (N−1)!/2, що для лише 16 клієнтів перевищує 650 мільярдів. Точні алгоритми (метод гілок і меж, динамічне програмування) можуть розв'язати скромні за розміром випадки, але погано масштабуються. Генетичні алгоритми поряд з іншими метаевристиками, як-от імітація відпалу та мурашиний алгоритм, обмінюють гарантію оптимальності на маршрут, який зазвичай дуже добрий і знаходиться за частку часу — саме такий компроміс роблять реальні логістичні системи для флотів із десятками чи сотнями зупинок.
Чому маршрут іноді застрягає в локальному оптимумі?
Якщо вся популяція сходиться до маршрутів зі спільною базовою структурою, кросовер між двома схожими батьками здебільшого відтворює ту саму структуру, а невеликі мутації обміну рідко достатні, щоб вирватися з локально хорошого, але глобально неоптимального циклу — наприклад, маршруту з одним ребром перетину, якого можна уникнути. Це називається передчасною збіжністю: різноманітність популяції зникає ще до того, як знайдено найкращий можливий тур. Підвищення частоти мутацій, збільшення розміру популяції або використання нової карти для порівняння прогонів — способи побачити цей компроміс між дослідженням (різноманітністю) і використанням (уточненням того, що вже працює).
Що таке турнірний відбір і навіщо його використовувати?
Турнірний відбір обирає невелику випадкову підмножину популяції (турнір, тут розміром 3) і вибирає найпристосованішого члена цієї підмножини як батька. Він простий, швидкий, а його тиск відбору легко налаштувати через розмір турніру: більший турнір збільшує ймовірність того, що єдина найкраща особина домінуватиме у відтворенні (швидша збіжність, вищий ризик передчасної збіжності), тоді як менший турнір зберігає більше різноманітності. Це дозволяє уникнути деяких пасток пропорційного до пристосованості відбору (рулетки), де один маршрут із незвично короткою відстанню може миттєво домінувати над усією популяцією.
Як розмір популяції та частота мутацій впливають на швидкість збіжності?
Більша популяція досліджує більше простору перестановок маршрутів за покоління і менш схильна втрачати корисну різноманітність через випадковий дрейф, але кожне покоління коштує більше обчислень відстані. Вища частота мутацій вносить більше випадковості, допомагаючи вирватися з локальних оптимумів, але й частіше порушуючи хороші маршрути, що може сповільнити збіжність або навіть тимчасово погіршити середнє значення популяції (елітизм у будь-якому разі захищає єдиний найкращий маршрут). На практиці є оптимальна зона — розміри популяції приблизно від десятків до низьких сотень і частота мутацій у кілька відсотків на ген, як правило, дають найшвидшу збіжність для задач такого розміру.
Популяція перестановок маршрутів еволюціонує під турнірним відбором, впорядкованим кросовером і мутацією обміну; найпристосованіший (найкоротший) маршрут виживає завдяки елітизму, поки карта перемальовує поточний найкращий тур, а графік відстані трендує вниз.
3D · рушій Three.js / WebGL · ціль 60 FPS · працює повністю на клієнті, без встановлення