Нежно въведение в генетичния алгоритъм

Изображение на ген

Когато започвате да провеждате изследвания за изкуствени интелигентни, може би сте чували за нещо, наречено „Генетичен алгоритъм“. След като видите този термин, може да не желаете да се ровите в него, тъй като съдържа думата „алгоритъм“. Не се страхувайте! В тази статия ще ви покажа простотата на генетичния алгоритъм и се надявам да ви вдъхновите да изградите такъв за свой собствен.

Какво е генетичен алгоритъм?

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

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

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

Работният процес на генетичния алгоритъм

Както бе споменато по-горе, генетичният алгоритъм е силно вдъхновен от естествения подбор, така че за да видите как работи генетичният алгоритъм, всъщност трябва да разгледате как работи естественият подбор.

естествен процес на подбор (опростен)

Диаграмата по-горе илюстрира процеса на естествен подбор. Ясно е, че този процес включва 5 основни стъпки. Първоначалната стъпка е селекция, в тази стъпка природата ще избере индивиди, които имат силен ген от първоначалната популация, след което те започват да преминават в следващия етап, който се чифтосва. След като преминат през етап на чифтосване, те ще родят дете, което наричаме тази стъпка: „възпроизвеждане“. Тогава това конкретно дете мутира, за да добави известна промяна в гена и накрая се премести обратно в популацията.

Процесът на генетичен алгоритъм е доста подобен на процеса по-горе, единственото различно е, че добави някои допълнителни подробности.

процес на генетичен алгоритъм

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

Какво по дяволите е фитнесът

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

Опитайте се да си представите, че ви е създаден проблем, проблемът е да намерите най-добрия маршрут за червена качулка, за да пътувате до баба си. Да предположим, че тя иска да стигне до баба си в най-кратки срокове, следователно годността на маршрута може да се изчисли, като се използва времето, необходимо за пътуване. Ако има маршрут с дължина 400 метра и й отне 10 минути, за да измине, то фитнесът му определено ще е по-малък от фитнес на трасе, дълъг 500 метра, но само 8 минути, за да пътува като фитнес на Маршрутът се изчислява на базата на времето за пътуване, а не на дължината му. Следователно трасето с дължина 500 метра е по-вероятно да бъде избрано за комбиниране с други маршрути.

Избор на добрата!

Изборът на подходящо решение е това, на което се подбира етапът на генетичния алгоритъм. След изчисляване на фитнес резултата, следващата стъпка е да използвате някои мистериозни методи, за да изберете списък с решения, които по-късно могат да бъдат използвани за създаване на по-добро решение.

Въпреки че можете да създадете свой собствен начин за избор на подходящи решения, има някои известни методи, които можете да използвате:

  • Фитнес пропорционален избор
  • Избор на турнири
  • Избор на отрязване
  • Фитнес равномерен избор

Списъкът по-горе не е адекватен списък, можете да разберете повече методи тук.

Нека вземем за пример първия метод. За разлика от името си, действителната концепция, която стои зад този метод, е абсурдно проста. Фитнес пропорционалният избор AKA на колелото на рулетката е методът за избор на „потенциални“ решения за рекомбинация.

Представете си, ако в торба има 10 мрамора, по-точно 5 сини мрамора, 3 червени мрамора и 2 бели мрамора. Можете лесно да изчислите, че ако вземете произволен мрамор от чантата, ще имате 5/10 шанс да изберете син, 3/10 за червен и 2/10 за бял. Така действа пропорционалният избор на фитнес, обаче процесът е малко по-различен.

При пропорционалния избор на фитнес първо се избира случайно число, след което то ще се използва за сравнение с годността на произволно избран разтвор. Фитнес стойността обикновено е ограничена да отиде от 0 до 1. Ако случайната стойност е по-малка от тази фитнес оценка, тогава решението ще бъде избрано. По този начин, колкото по-висока е годността на дадено решение, толкова по-голям е шансът да бъде избран. Например, ако случайно число отива от 0 до 1, има 50%, то ще бъде по-малко от 0,5 и 80%, ще бъде по-малко от 0,8, но няма вероятност да е по-малко от 0,2, това означава, че ако разтворът има 0.8 годност, има 80%, той ще бъде избран за рекомбинация, а разтвора, който има 0,2 фитнес, ще има само 20%. Въпреки че 0,2 фитнес решение се избира рядко, но също така помага да се променят чертите на решението, тъй като това решение може да съдържа някои атрибути, необходими за по-късен успех.

Извършване на кросоувър

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

Подобно на етапа на подбор, в етапа на кросоувър можете да измислите свои собствени техники за кросоувър, но има и някои техники, които можете да използвате:

  • Кросоувър с една точка
  • Кросоувър в две точки
  • Уеднаквен кросоувър
  • Три родителски кросоувър

За по-добро разбиране ще обясня униформената техника на кросоувър, която е техниката, която смятам за най-лесната техника за изпълнение.

Унифицираният метод на кросоувър включва избор на произволна част от гена на 2 разтвора на случаен принцип, за да се комбинира и създаде ново (надяваме се, по-добро) решение.

Първата стъпка при равномерния кросоувър е да изберете 2 произволни решения от набора от решения, които са избрани в предишния етап на подбор. Тогава всяка част от 2-те разтвора ще бъде избрана за добавяне на базата на дъщерния разтвор на променлива, наречена коефициент на смесване. Коефициентът на смесване е нещото, което решава вероятността да се вземе решение за добавяне към детското решение. Например, има 2 решения: A и B и искате разтворът на детето да има повече части, взети от разтвор A, можете да увеличите съотношението на смесване, след това преминавайте през всички части на разтвора A и B. Във всеки цикъл , създайте ново произволно число и го сравнете със съотношението на смесване, ако е по-малко от съотношението на смесване, тогава изберете разтвора. Част друго изберете В. По същия начин, ако съотношението на смесване е 0,5, тогава А и В ще имат приблизително 50% от бидейки избран.

Равномерен кросоувър със съотношение на смесване 0,5

На горната снимка се демонстрира детският разтвор С, генериран с помощта на разтвор А и В, със съотношение на смесване 0,5 или 50%. Всяка част от двата разтвора беше решена да бъде избрана или да не се основава на съотношението на смесване и съотношението на смесване беше сравнено с произволно число, за да се реши. Това е като хвърляне на монета, за да изберете къде трябва да се използва A вместо B и обратно.

Мутирайте детето!

Не, не не, няма да превърнем децата си в едни момчета с метални нокти и да ги оставим да умрат на произволен ствол на дърво!

Вместо това добавянето на мутация на дете е все едно да им помогнете

Размишлявайки по различен начин, човек може да стане лидер на стадото или пълен глупав задник.

Пример за мутация

Както можете да видите, червеното дете върви по различен път в сравнение с другите деца. Причината за това е, че когато червеното дете следва стадото, добавихме мутация и затова му помогнем да избере различен път. Разбира се, че различният път също може да бъде задънена улица, но ясно, че в този случай пътят води до успех! Това е истинската цел на етапа на мутация.

За да мутирате дете, има и различни техники, които можете да използвате:

  • Мутация на битови низове
  • Flip Bit
  • Non-Uniform
  • униформа

Можете да намерите повече от тях тук.

За да разбера това по-добре, ще демонстрирам техниката „мутация на битови низове“.

Представете си, че правите бот, за да избягвате предмети пред него. Ботът ще трябва да избягва всички обекти, за да стигне до крайната дестинация и естественото му състояние се движи напред. За да избегне обект, неговият ген ще бъде поредица от „леви“ и „десни“ низове, което показва как да се движи бота.

Мутацията на битов низ обикновено се използва за двоичен низ, тъй като този метод прелиства 1 или повече произволни избрани бита в гена. Например:

Пример за мутация на битови низове

Сега се опитайте да трансформирате 1 и 0 в ляво и дясно и помислете как ще се представи ботът. Тъй като ботът може да заседне, когато срещне голям обект, мутацията ще помогне на неговото потомство да избере нова посока за движение и да избегне този обект. Представете си, че в продължение на много поколения ботът се обръща надясно само когато срещне обект и умира, но в следващото поколение ботът изведнъж зави наляво, тъй като десен низ в неговия ген беше обърнат наляво и ботът в крайна сметка достигна своето местоназначение. Ето как функционира мутацията на битови низове.

Краят на процеса

След като мутирате детето, то ще се свърже с друго мутирано дете, за да реформира нова популация и целият процес започва отначало.

И така, когато спира? Отговорът е изключително прост, кога спирате да практикувате да пишете клавиатура с 10 пръста? Когато умението ви за писане е перфектно, разбира се. Същото е и с генетичния алгоритъм, процесът ще спре, ако определеното решение е достигнало желаната годност. Например, искате ботът в предишния пример да достигне дестинацията с възможно най-малко време.

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

заключение

Това е краят на моята статия, надявам се, че след тази статия, вие ще имате по-добра представа за генетичния алгоритъм, вдъхновили да изградите свой собствен.

Ето няколко връзки, за да разгледате повече за генетичния алгоритъм:

  • Даниел Шифман видеоклипове за генетичния алгоритъм:
  • Моят пример за използване на генетичен алгоритъм за отгатване на парола
  • ръководство за генетичен алгоритъм
  • Горан Мурич видео за пример, използващ генетичен алгоритъм за намиране на път