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

Основа за генетични алгоритми

Генетичните алгоритми се основават на аналогия със структурата и поведението на хромозомите на популацията от гледна точка на генетиката. Основата на GA въз основа на това сравнение е следната:

1. Членовете на населението се състезават помежду си за ресурси и брачен партньор
2. Успешните хора (най-силните) се чифтосват, за да имат повече деца от по-малко успешните хора.
3. Гените на „най-силния“ родител се разпространяват в поколението , което означава, че понякога родителите могат да създадат деца, които превъзхождат и двамата.
4. В резултат на това всяко следващо поколение става по-адаптирано към заобикалящата го среда.

Пространството за търсене

В рамките на пространството за търсене популацията от индивиди се поддържа постоянна. Всеки човек в пространството за търсене на определен проблем предоставя потенциално решение. Всеки човек е представен от вектор с крайна дължина от компоненти (подобно на хромозома). Тези променливи елементи приличат на гените по много начини. Следователно една хромозома (индивид) се състои от няколко гена (променливи компоненти).

Фитнес резултат

Всеки човек получава фитнес резултат, мярка за способността му да се „състезава“. Търси се човекът с най-добър фитнес резултат (или такъв, който е много близо до него).

Популацията от n души (хромозома/разтвори) и техните оценки за годност се поддържат от GA. Повече възможности за възпроизвеждане се предлагат на тези с по-високи оценки за годност, отколкото на други. Чрез сливане на хромозомите на родителите, индивидите с по-високи фитнес резултати се избират да се чифтосват и да раждат по-добри деца. Тъй като населението е статично, трябва да се направи място за новодошлите. В резултат на това някои хора умират и биват заменени от новодошли, което в крайна сметка води до ново поколение, след като предишната популация е имала всичките си шансове да се чифтосват. Надяваме се, че с преминаването на поколенията ще се развият по-добри решения и най-малко годните ще умрат.

Средният брой на „по-добрите гени“ в едно ново поколение е по-висок, отколкото в поколението преди него. В резултат на това по-младите поколения винаги имат по-ефективни „частични решения“ от по-ранните. Твърди се, че популацията се е сближила, след като произведеното потомство не показва забележима разлика от потомството, създадено от по-ранни популации. Твърди се, че алгоритъмът е „конвергирал“ върху набор от възможни решения на проблема.

Оператори на генетични алгоритми

След създаването на първоначалното поколение, алгоритъмът се развива/подобрява с помощта на следните оператори:

  1. Селекция: Целта е да се даде приоритет на тези с високи фитнес резултати и да им се позволи да предадат гените си на следващите поколения.
  2. Кръстосано:Това представлява чифтосване между индивиди. Двама индивида се избират с помощта на оператор за избор и кръстосаните сайтове се избират на случаен принцип. След това гените в тези кръстосани места се обменят, като по този начин се създава напълно нов индивид (потомство)

3. Оператор на мутация: Основната идея е да се вмъкнат произволни гени в потомството, за да се поддържа разнообразието в популацията, за да се избегне преждевременно сближаване

Предимства

Генетичният алгоритъм е мощна техника за оптимизация, която има няколко предимства, някои от които включват:

  1. Глобален оптимум: Генетичният алгоритъм е в състояние да претърси цялото пространство на решенията и да намери глобалния оптимум, който е възможно най-доброто решение. Това е в контраст с други техники за оптимизация, като градиентно спускане, които могат да заседнат в локалните оптимуми.
  2. Обработване на сложни и нелинейни проблеми: Генетичният алгоритъм е много подходящ за решаване на проблеми, които са сложни и нелинейни, като например такива, които имат множество решения или имат неизвестни или променящи се връзки между променливи.
  3. Устойчивост: Генетичните алгоритми са устойчиви на шумни или непълни данни и могат да се справят с проблеми с голям брой променливи и ограничения. Те могат също така да се справят с ограничения, които е трудно да се изразят математически, което ги прави универсална техника за оптимизация за широк кръг от проблеми.

Недостатъци

  1. Изчислителни разходи: Генетичният алгоритъм може да бъде скъп от изчислителна гледна точка, особено за големи и сложни проблеми. Изисква голям брой оценки на функциите за сближаване, което може да отнеме много време.
  2. Липса на интерпретируемост:Генетичният алгоритъм генерира решения, които са комбинация от различни градивни елементи, което затруднява интерпретирането на крайното решение и разбирането на връзките между променливите. Това може да е недостатък, когато целта е да се разберат основните връзки в данните.
  3. Липса на контрол: Генетичните алгоритми са метод за стохастична оптимизация и като такъв резултатът може да варира в зависимост от първоначалната популация и началната стойност на генератора на произволни числа. Това затруднява възпроизвеждането на резултатите и може да бъде предизвикателство да се разбере ефектът на различните параметри върху крайното решение.

Резюме

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