Често задавани въпроси

Генетичните алгоритми (ГА) са методи за търсене и оптимизация, вдъхновени от биологичната еволюция. Те поддържат популация от кандидат-решения и я подобряват в продължение на поколения чрез три оператора: селекция (избор на най-добрите индивиди), кръстосване (комбиниране на две решения) и мутация (случайна промяна на решение). ГА са особено ефективни, когато пространството за търсене е голямо, сложно или слабо разбрано.

Генетичните алгоритми са подходящи за задачи по оптимизация и търсене, при които трябва да се намери най-доброто решение от голям брой възможности. Примери включват планиране на маршрути (задача на търговския пътник), планиране на разписания, инженерно проектиране, оптимизация на функции и стратегия на игри. Особено полезни са, когато фитнес функцията не е диференцируема или няма известно аналитично решение.

Не. Урокът обяснява концепциите стъпка по стъпка с диаграми и интерактивни демонстрации в браузъра. Не са необходими познания по програмиране. Ако искате да приложите собствен ГА след това, основните умения за програмиране ще помогнат, но не са задължителни за разбиране на материала.

Методите, базирани на градиент (като градиентното спускане), следват наклона на фитнес функцията и могат да затънат в локален оптимум. Генетичните алгоритми изследват пространството за търсене с цяла популация едновременно и са по-малко склонни да затънат — но обикновено са по-бавни и изискват повече изчислителни ресурси. ГА не изискват фитнес функцията да бъде диференцируема или непрекъсната, което ги прави приложими към по-широк клас задачи.

Няма универсални правила, но емпиричните насоки предполагат: размер на популацията 20–100, вероятност за кръстосване 80–95%, вероятност за мутация 0,5–1%. Подходящите стойности зависят от конкретния проблем и кодирането. Глава Параметри разглежда опциите подробно, а интерактивното демо ви позволява да експериментирате директно.

Не. Генетичните алгоритми са евристики — те търсят добри решения, но не могат да гарантират намирането на глобалния оптимум. Качеството на резултатите зависи силно от избора на кодиране, фитнес функция и параметри. За много реални задачи почти оптимално решение, намерено бързо, е по-практично от точното решение, чието изчисляване би отнело твърде много време.

Задачата на търговския пътник (TSP) търси най-краткия маршрут, който посещава набор от градове точно по веднъж и се връща в началната точка. Това е класически NP-труден комбинаторен оптимизационен проблем. TSP се използва в урока за демонстрация на пермутационното кодиране и показване как ГА се справят с комбинаторни задачи за търсене. Вижте главата за примера с TSP за подробности.

Текстът и изображенията в този урок са публикувани под лиценза Creative Commons Attribution–ShareAlike 4.0 (CC BY-SA 4.0). Можете свободно да ги споделяте и адаптирате при условие, че посочите съответното авторство и разпространявате адаптациите под същия лиценз.

Интерактивните JavaScript демонстрации могат да се използват само като част от този сайт; всяко друго използване изисква предварително писмено съгласие. Контакт: marek@obitko.com.