Algorytm genetyczny to adaptacyjny algorytm wyszukiwania heurystycznego inspirowany „teorią ewolucji Darwina w przyrodzie”. .' Służy do rozwiązywania problemów optymalizacyjnych w uczeniu maszynowym. Jest to jeden z ważnych algorytmów, ponieważ pomaga rozwiązywać złożone problemy, których rozwiązanie zajęłoby dużo czasu.

Algorytmy genetyczne są szeroko stosowane w różnych zastosowaniach w świecie rzeczywistym, na przykład Projektowanie obwodów elektronicznych, łamanie kodów, przetwarzanie obrazu i sztuczna kreatywność.

W tym temacie szczegółowo wyjaśnimy algorytm genetyczny, w tym podstawową terminologię stosowaną w algorytmie genetycznym, sposób jego działania, zalety i ograniczenia algorytmu genetycznego itp.

Co to jest algorytm genetyczny?

Zanim zrozumiemy algorytm genetyczny, zapoznajmy się najpierw z podstawową terminologią, aby lepiej zrozumieć ten algorytm:

Populacja:Populacja to podzbiór wszystkich możliwych lub prawdopodobnych rozwiązań, które mogą rozwiązać dany problem.Chromosomy:Chromosom jest jednym z rozwiązań w populacji danego problemu, a zbiór genu generuje chromosom.Gen:Chromosom jest podzielony na inny gen lub jest elementem chromosomu.Allele:Allel to wartość nadana genowi w obrębie określonego chromosomu.Sprawność fizyczna:Funkcja przystosowania służy do określenia poziomu sprawności jednostki w populacji. Oznacza zdolność jednostki do konkurowania z innymi jednostkami. W każdej iteracji poszczególne osoby są oceniane na podstawie ich funkcji przystosowania.Operatory genetyczne:W algorytmie genetycznym najlepszy indywidualny partner regeneruje potomstwo lepiej niż rodzice. W tym przypadku operatorzy genetyczni odgrywają rolę w zmianie składu genetycznego następnego pokolenia.Wybór

Po obliczeniu przydatności każdej osoby w populacji przeprowadza się proces selekcji, aby określić, która z jednostek w populacji będzie mogła się rozmnażać i wydać materiał siewny, z którego uformuje się nadchodzące pokolenie.

Dostępne typy stylów selekcji

Wybór koła ruletki Wybór wydarzenia Wybór oparty na rankingu

Zatem teraz możemy zdefiniować algorytm genetyczny jako algorytm wyszukiwania heurystycznego służący do rozwiązywania problemów optymalizacyjnych. Jest to podzbiór algorytmów ewolucyjnych wykorzystywanych w informatyce. Algorytm genetyczny wykorzystuje koncepcje genetyczne i dobór naturalny do rozwiązywania problemów optymalizacyjnych.

Jak działa algorytm genetyczny?

Algorytm genetyczny działa na ewolucyjnym cyklu pokoleniowym, aby wygenerować rozwiązania wysokiej jakości. Algorytmy te wykorzystują różne operacje, które albo ulepszają, albo zastępują populację, aby uzyskać ulepszone rozwiązanie dopasowania.

Zasadniczo obejmuje pięć faz rozwiązywania złożonych problemów optymalizacyjnych, które podano poniżej:

Inicjalizacja Zadanie fitness Wybór Reprodukcja Zakończenie

1. Inicjalizacja

Proces algorytmu genetycznego rozpoczyna się od wygenerowania zbioru osobników, który nazywa się populacją. Tutaj każdy jest rozwiązaniem danego problemu. Osoba zawiera lub charakteryzuje się zestawem parametrów zwanych genami. Geny są łączone w ciąg i generują chromosomy, co jest rozwiązaniem problemu. Jedną z najpopularniejszych technik inicjalizacji jest użycie losowych ciągów binarnych.

2. Przydział sprawności

Funkcja kondycji służy do określenia, jak sprawna jest dana osoba? Oznacza zdolność jednostki do konkurowania z innymi jednostkami. W każdej iteracji poszczególne osoby są oceniane na podstawie ich funkcji przystosowania. Funkcja fitness zapewnia ocenę kondycji każdej osobie. Wynik ten dodatkowo określa prawdopodobieństwo wybrania do reprodukcji. Im wysoki wynik sprawności, tym większe szanse na wyselekcjonowanie do reprodukcji.

3. Wybór

Faza selekcji polega na selekcji osobników do reprodukcji potomstwa. Wszystkie wybrane osobniki łączy się następnie w pary po dwa, aby zwiększyć reprodukcję. Następnie osoby te przekazują swoje geny następnemu pokoleniu.

Dostępne są trzy typy metod selekcji, którymi są:

• Wybór koła ruletki
• Wybór turnieju
• Wybór na podstawie rang

4. Powielanie

Po procesie selekcji stworzenie dziecka następuje na etapie reprodukcji. Na tym etapie algorytm genetyczny wykorzystuje dwa operatory wariacji stosowane do populacji rodzicielskiej. Poniżej podano dwóch podmiotów zaangażowanych w fazę reprodukcji:

Krzyżowanie:Krzyżowanie odgrywa najważniejszą rolę w fazie reprodukcji algorytmu genetycznego. W tym procesie punkt przecięcia jest wybierany losowo w obrębie genów. Następnie operator krzyżowania zamienia informację genetyczną obojga rodziców z bieżącego pokolenia, tworząc nowego osobnika reprezentującego potomstwo.

Geny rodziców wymieniają się między sobą, aż do osiągnięcia punktu skrzyżowania. To nowo powstałe potomstwo jest dodawane do populacji. Proces ten nazywany jest również krzyżowaniem. Dostępne typy crossoverów:
• Jednopunktowe skrzyżowanie
• Dwupunktowe skrzyżowanie
• Crossover w barwach
• Krzyżowanie algorytmów dziedzicznych
Mutacja
Operator mutacji wstawia losowe geny do potomstwa (nowego dziecka), aby zachować różnorodność w populacji. Można to zrobić poprzez odwrócenie niektórych bitów w chromosomach.
Mutacja pomaga rozwiązać problem przedwczesnej konwergencji i zwiększa dywersyfikację. Poniższy obrazek przedstawia proces mutacji:
Dostępne rodzaje stylów mutacji,
Odwróć mutację bitową Mutacja Gaussa Mutacja wymiany/zamiany

5. Zakończenie

Po fazie reprodukcji stosuje się kryterium zatrzymania jako podstawę zakończenia. Algorytm kończy się po osiągnięciu rozwiązania dotyczącego dopasowania progowego. Wskaże rozwiązanie ostateczne jako najlepsze w populacji.

Ogólny przebieg pracy z prostym algorytmem genetycznym

Zalety algorytmu genetycznego

• Najlepsze są równoległe możliwości algorytmów genetycznych.
• Pomaga w optymalizacji różnych problemów, takich jak funkcje dyskretne, problemy wielocelowe i funkcje ciągłe.
• Zapewnia rozwiązanie problemu, które z czasem ulega poprawie.
• Algorytm genetyczny nie potrzebuje informacji pochodnych.

Ograniczenia algorytmów genetycznych

• Algorytmy genetyczne nie są skutecznymi algorytmami rozwiązywania prostych problemów.
• Nie gwarantuje jakości ostatecznego rozwiązania problemu.
• Powtarzające się obliczanie wartości sprawności może generować pewne wyzwania obliczeniowe.

Różnica między algorytmami genetycznymi a algorytmami tradycyjnymi

• Przestrzeń poszukiwań to zbiór wszystkich możliwych rozwiązań problemu. W algorytmie tradycyjnym utrzymywany jest tylko jeden zbiór rozwiązań, natomiast w algorytmie genetycznym można zastosować kilka zbiorów rozwiązań w przestrzeni poszukiwań.
• Tradycyjne algorytmy potrzebują więcej informacji, aby przeprowadzić wyszukiwanie, podczas gdy algorytmy genetyczne potrzebują tylko jednej funkcji celu, aby obliczyć przystosowanie jednostki.
• Tradycyjne algorytmy nie mogą działać równolegle, podczas gdy algorytmy genetyczne mogą działać równolegle (obliczanie przystosowania indywidualności jest niezależne).
• Jedna duża różnica w algorytmach genetycznych polega na tym, że zamiast działać bezpośrednio na wynikach poszukiwacza, algorytmy dziedziczne działają na ich reprezentacjach (lub renderowaniu), często określanych jako chromosomy.
• Jedną z dużych różnic między algorytmem tradycyjnym a algorytmem genetycznym jest to, że nie działa on bezpośrednio na potencjalnych rozwiązaniach.
• Tradycyjne algorytmy mogą ostatecznie wygenerować tylko jeden wynik, podczas gdy algorytmy genetyczne mogą generować wiele optymalnych wyników z różnych pokoleń.
• Tradycyjny algorytm nie jest bardziej prawdopodobne, aby wygenerować optymalne wyniki, podczas gdy algorytmy genetyczne nie gwarantują wygenerowania optymalnych wyników globalnych, ale istnieje również duża możliwość uzyskania optymalnego wyniku dla problemu, ponieważ wykorzystuje operatory genetyczne, takie jak Crossover i Mutacja.
• Tradycyjne algorytmy mają charakter deterministyczny, natomiast algorytmy genetyczne mają charakter probabilistyczny i stochastyczny.