Delikatne wprowadzenie do algorytmu genetycznego

Obraz genu

Rozpoczynając badania nad sztuczną inteligencją, być może słyszałeś o czymś zwanym „algorytmem genetycznym”. Po zobaczeniu tego terminu możesz nie chcieć się w niego zagłębić, ponieważ zawiera słowo „algorytm”. Nie bój się! W tym artykule pokażę prostotę algorytmu genetycznego i mam nadzieję, że zainspiruję cię do zbudowania jednego dla siebie.

Co to jest algorytm genetyczny?

Algorytm genetyczny jest w zasadzie metodą mocno zainspirowaną procesem doboru naturalnego w celu znalezienia najlepszego rozwiązania problemu.

W naturze przetrwają tylko silni, proces eliminacji słabych nazywa się doborem naturalnym. Algorytm genetyczny wykorzystuje tę samą zasadę, aby wyeliminować „słabe” rozwiązania i wreszcie stworzyć najlepsze rozwiązanie.

Zwykle algorytm genetyczny jest używany, gdy nie możesz wiedzieć, jakie będzie rozwiązanie. Na przykład chcesz stworzyć samochód, który może poruszać się po różnych rodzajach terenu. Nie możesz wiedzieć, jak będzie wyglądał ten samochód, ale znasz cel tego samochodu. W takim przypadku algorytm genetyczny może zostać wykorzystany do wygenerowania samochodu do podróży w różnych terenach, ale algorytm określi projekt samochodu.

Proces pracy algorytmu genetycznego

Jak wspomniano wcześniej, algorytm genetyczny jest silnie zainspirowany doborem naturalnym, więc aby zobaczyć, jak działa algorytm genetyczny, powinieneś naprawdę sprawdzić, jak działa dobór naturalny.

naturalny proces selekcji (uproszczony)

Powyższy schemat ilustruje proces doboru naturalnego. Oczywiste jest, że proces ten obejmuje 5 głównych kroków. Pierwszym krokiem jest selekcja, w tym etapie natura wybierze osobniki, które mają silny gen z początkowej populacji, a następnie zaczną wkraczać w kolejny etap, który jest kojarzeniem. Po przejściu przez etap kojarzenia urodzą dziecko, które nazywamy tym krokiem: „rozmnażanie”. To konkretne dziecko zmutowało następnie, aby dodać pewne zmiany do genu i ostatecznie wróciło do populacji.

Proces algorytmu genetycznego jest dość podobny do powyższego, z tym, że dodaje kilka dodatkowych szczegółów.

proces działania algorytmu genetycznego

Na początek proces działania algorytmu genetycznego zaczyna się od początkowej populacji. Pierwszym głównym etapem jest obliczanie sprawności, obliczanie sprawności można rozważyć jako część procesu selekcji, ponieważ jest ona zasadniczo używana do obliczania „wyniku” każdej osoby w celu wskazania, czy jest to osoba silna, czy słaba. Wszystkie silne byty następnie wybrane i przekazane do etapu zwanego krzyżowaniem, ten etap jest jak etap kojarzenia na poprzednim schemacie. Na tym etapie wybiera się 2 losowych rodziców z listy silnych bytów, aby wykonać coś, co nazywa się crossover, co omówimy później. Po wykonaniu krzyżowania zostaje utworzone i zmutowane dziecko, aby dodać zmienność genu. W końcu to dziecko ponownie dołącza do populacji i proces powtarza się ponownie.

Czym do cholery jest fitness

W algorytmie genetycznym sprawność odgrywa kluczową rolę na etapie selekcji. Sprawność to „wynik” za wybranie bytu, który potrafi przekazać swoje cechy. Na przykład, jeśli dana osoba ma poważną chorobę, jej „wynik sprawności” będzie niski i rzadziej będzie mieć szansę na urodzenie dziecka, ponieważ jego dzieci również odziedziczą chorobę. Dlatego, jeśli sprawność rozwiązania jest niska, możesz nie chcieć tworzyć na nim innego rozwiązania, ponieważ wynik byłby tak zły, jak stare rozwiązanie.

Spróbuj sobie wyobrazić, że masz problem, problem polega na znalezieniu najlepszej drogi dla czerwonego kapturka do podróży do domu babci. Załóżmy, że chce dotrzeć do domu babci w jak najkrótszym czasie, dlatego sprawność trasy można obliczyć na podstawie czasu podróży. Jeśli istnieje trasa o długości 400 metrów, a podróż zajęła jej 10 minut, jej sprawność będzie zdecydowanie mniejsza niż przydatność trasy o długości 500 metrów, ale podróż zajęła jej tylko 8 minut trasa oblicza podstawę na podstawie czasu podróży, a nie jego długości. Dlatego trasa o długości 500 metrów byłaby bardziej skłonna do połączenia z innymi trasami.

Wybór dobrego!

Wybór odpowiedniego rozwiązania jest tym, na czym polega etap selekcji algorytmu genetycznego. Po obliczeniu wyniku fitnessu następnym krokiem jest użycie tajemniczych metod, aby wybrać listę rozwiązań, które można później wykorzystać do stworzenia lepszego rozwiązania.

Chociaż możesz stworzyć swój własny sposób wyboru rozwiązań dopasowywania, istnieje kilka znanych metod, których możesz użyć:

  • Wybór proporcjonalny do kondycji
  • Wybór turnieju
  • Wybór obcięcia
  • Wybór mundurów fitness

Powyższa lista nie jest odpowiednią listą, więcej metod znajdziesz tutaj.

Weźmy pierwszą metodę jako przykład. W przeciwieństwie do nazwy, rzeczywista koncepcja tej metody jest absurdalnie prosta. Wybór proporcjonalny do sprawności AKA Wybór koła ruletki jest metodą wyboru „potencjalnych” rozwiązań rekombinacji.

Wyobraź sobie, że w torbie znajduje się 10 kul, a konkretnie 5 niebieskich, 3 czerwone i 2 białe. Możesz łatwo obliczyć, że jeśli wybierzesz losowy marmur z torby, będziesz miał 5/10 szansy na wybranie niebieskiego, 3/10 na czerwony i 2/10 na biały. Tak działa wybór proporcjonalny do kondycji, jednak proces ten jest nieco inny.

Przy wyborze proporcjonalnym do kondycji najpierw wybierana jest liczba losowa, a następnie używana do porównania ze sprawnością losowo wybranego rozwiązania. Wartość sprawności jest zwykle ograniczona do zera od 0 do 1. Jeśli wartość losowa jest mniejsza niż ta ocena sprawności, wówczas zostanie wybrane rozwiązanie. Zatem im wyższa jest przydatność rozwiązania, tym większa szansa, że ​​zostanie on wybrany. Na przykład, jeśli liczba losowa zmienia się od 0 do 1, jest 50%, to będzie mniejsza niż 0,5, a 80%, będzie mniejsza niż 0,8, jednak prawdopodobnie nie będzie mniejsza niż 0,2, co oznacza, że ​​jeśli rozwiązanie ma sprawność 0,8, istnieje 80%, które zostanie wybrane do rekombinacji, a rozwiązanie o sprawności 0,2 będzie miało tylko 20% do wyboru. Chociaż rozwiązanie fitness 0.2 jest rzadko wybierane, ale pomaga także różnicować cechy rozwiązania, ponieważ może ono zawierać pewne atrybuty, które są potrzebne do późniejszego sukcesu.

Wykonywanie zwrotnicy

Crossover to etap, w którym wybrane rozwiązania są łączone w celu tworzenia nowych rozwiązań. Podobnie jak etap selekcji, istnieje również wiele technik crossovera, które można również znaleźć tutaj.

Podobnie jak na etapie selekcji, na etapie crossovera możesz również wymyślić własne techniki crossovera, jednak istnieją również pewne techniki, których możesz użyć:

  • Zwrotnica jednopunktowa
  • Crossover dwupunktowy
  • Jednolity crossover
  • Crossover z trzema rodzicami

Dla lepszego zrozumienia wyjaśnię jednolitą technikę krzyżowania, którą uważam za najłatwiejszą do zastosowania.

Jednolita metoda krzyżowania polegała na losowym wybraniu losowej części genu 2 roztworu w celu połączenia i stworzenia nowego (miejmy nadzieję lepszego) rozwiązania.

Pierwszym krokiem w jednolitej zwrotnicy jest wybranie 2 losowych rozwiązań z zestawu rozwiązań, które zostały wybrane w poprzednim etapie selekcji. Następnie każda część 2 roztworów zostanie wybrana, aby dodać bazę roztworu potomnego na zmiennej o nazwie stosunek mieszania. Proporcje mieszania decydują o tym, jakie rozwiązanie zostanie prawdopodobnie wybrane do dodania do roztworu potomnego. Na przykład istnieją 2 rozwiązania: A i B, a chcesz, aby roztwór potomny zawierał więcej części pobranych z roztworu A, możesz zwiększyć proporcje mieszania, po tej pętli przez wszystkie części roztworu A i B. W każdej pętli , utwórz nową liczbę losową i porównaj ją ze współczynnikiem zmieszania, jeśli jest on mniejszy niż współczynnik zmieszania, a następnie wybierz rozwiązanie A część jeszcze wybierz B. Podobnie. Jeśli współczynnik zmieszania wynosi 0,5, wówczas A i B będą miały około 50% zostałem zabrany.

Jednolita zwrotnica ze stosunkiem mieszania 0,5

Na powyższym zdjęciu pokazano roztwór potomny C wytworzony przy użyciu roztworu A i B o stosunku mieszania 0,5 lub 50%. Każda część obu roztworów została wybrana do wybrania lub nie na podstawie stosunku mieszania, a stosunek mieszania został porównany z liczbą losową w celu podjęcia decyzji. To tak, jak rzucać monetą, aby wybrać miejsce, w którym A powinno być użyte zamiast B i odwrotnie.

Zmutuj dziecko!

Nie, nie, nie zamierzamy przekształcać naszych dzieci w facetów z metalowymi pazurami i pozwolić im umrzeć na przypadkowym pniu drzewa!

Zamiast tego dodanie mutacji dziecku jest jak pomoc

Myśląc inaczej, jednostka może zostać liderem stada lub kompletnym głupkiem.

Przykład mutacji

Jak widać, czerwone dziecko idzie inną drogą niż inne dzieci. Powodem tego jest to, że gdy czerwone dziecko podąża za stadem, dodaliśmy mu mutację i dlatego pomogliśmy mu wybrać inną ścieżkę. Oczywiście ta inna ścieżka może być ślepym zaułkiem, ale oczywiście w tym przypadku ścieżka prowadzi do sukcesu! To jest prawdziwy cel etapu mutacji.

Aby zmutować dziecko, istnieje również wiele różnych technik, których można użyć:

  • Mutacja ciągu bitów
  • Flip Bit
  • Niejednolity
  • Mundur

Możesz znaleźć ich więcej tutaj.

Aby lepiej to zrozumieć, pokażę technikę „mutacji ciągów bitów”.

Wyobraź sobie, że robisz bota, aby unikać przedmiotów przed nim. Bot będzie musiał ominąć wszystkie obiekty, aby dotrzeć do ostatecznego miejsca docelowego, a jego naturalny stan przesuwa się do przodu. Aby uniknąć obiektu, jego genem będzie seria „lewej” i „prawej” struny, która wskazuje, jak bot się poruszy.

„Mutacja ciągu bitów” jest zwykle stosowana do ciągu binarnego, ponieważ ta metoda odwraca 1 lub więcej losowo wybranych bitów w genie. Na przykład:

Przykład mutacji ciągu bitowego

Teraz spróbuj przekształcić 1 i 0 w lewą i prawą i pomyśl o tym, jak bot będzie działał. Ponieważ bot może utknąć, gdy napotka duży obiekt, mutacja pomoże jego potomstwu wybrać nowy kierunek ruchu i uniknąć tego obiektu. Wyobraź sobie, że przez wiele pokoleń bot skręca w prawo tylko wtedy, gdy spotyka obiekt i umiera, ale w następnej generacji bot nagle skręcił w lewo, gdy prawy łańcuch w genie został obrócony w lewo i bot ostatecznie dotarł do celu. Właśnie w ten sposób działa „mutacja ciągów bitów”.

Koniec procesu

Po zmutowaniu dziecka połączy się ono z innym zmutowanym dzieckiem, aby zreformować nową populację, a cały proces rozpocznie się od nowa.

Kiedy to się skończy? Odpowiedź jest niezwykle prosta, kiedy przestajesz ćwiczyć klawiaturę z 10 palcami? Kiedy twoje umiejętności pisania są oczywiście idealne. To samo dotyczy algorytmu genetycznego, proces zostanie zatrzymany, jeśli sprawność danego rozwiązania osiągnie pożądaną sprawność. Na przykład chcesz, aby bot z poprzedniego przykładu dotarł do celu w jak najkrótszym czasie.

Ustawiasz próg sprawności na 4 minuty, jeśli czas bota do ukończenia jest dłuższy niż 4 minuty, oznacza to, że proces będzie powtarzany, dopóki czas bota nie będzie krótszy lub równy 4 minutom.

Wniosek

To koniec mojego artykułu, mam nadzieję, że po tym artykule będziesz miał lepszy wgląd w algorytm genetyczny, który zainspirował Cię do zbudowania własnego.

Oto kilka linków, dzięki którym możesz dowiedzieć się więcej o algorytmie genetycznym:

  • Filmy Daniela Shiffmana o algorytmie genetycznym:
  • Mój przykład użycia algorytmu genetycznego do odgadnięcia hasła
  • tutorialspoint tutorial o algorytmie genetycznym
  • Film Gorana Murica o przykładzie wykorzystującym algorytm genetyczny do znalezienia ścieżki