Omówienie algorytmu genetycznego
Techniki optymalizacji to techniki stosowane w celu znalezienia najlepszego rozwiązania spośród wszystkich możliwych rozwiązań dostępnych przy obecnych ograniczeniach. Algorytm genetyczny jest jednym z takich algorytmów optymalizacyjnych zbudowanych na podstawie naturalnego procesu ewolucyjnego naszej natury. Wykorzystano tu ideę doboru naturalnego i dziedziczenia genetycznego. Wykorzystuje losowe wyszukiwanie z kierunkiem, w przeciwieństwie do innych algorytmów, tj. Znajdowanie optymalnego rozwiązania, zaczynając od funkcji losowego kosztu początkowego, a następnie szukając tylko w przestrzeni o najniższym koszcie (w kierunku prowadzonym). Odpowiednie, gdy pracujesz z ogromnymi i złożonymi zestawami danych.
Co to jest algorytm genetyczny?
Algorytm genetyczny opiera się na strukturze genetycznej i zachowaniu chromosomu populacji. Następujące rzeczy są podstawą algorytmów genetycznych.
- Każdy chromosom wskazuje możliwe rozwiązanie. Tak więc populacja jest zbiorem chromosomów.
- Każda osoba w populacji charakteryzuje się funkcją sprawności. Lepsza sprawność to lepsze rozwiązanie.
- Spośród dostępnych osobników w populacji najlepsze osobniki są wykorzystywane do reprodukcji potomstwa następnego pokolenia.
- Wytworzone potomstwo będzie miało cechy obojga rodziców i jest wynikiem mutacji. Mutacja to niewielka zmiana w strukturze genu.
Fazy algorytmu genetycznego
Poniżej znajdują się różne fazy algorytmu genetycznego:
1. Inicjalizacja populacji (kodowanie)
- Każdy gen reprezentuje parametr (zmienne) w roztworze. Ten zbiór parametrów tworzących rozwiązanie to chromosom. Populacja to zbiór chromosomów.
- Kolejność genów w chromosomie ma znaczenie.
- W większości przypadków chromosomy są przedstawione w postaci binarnej jako 0 i 1, ale możliwe są również inne kodowania.
2. Funkcja fitness
- Spośród dostępnych chromosomów musimy wybrać najlepsze do reprodukcji potomstwa, więc każdy chromosom otrzymuje wartość sprawności.
- Wynik fitness pomaga wybrać osoby, które zostaną wykorzystane do reprodukcji.
3. Wybór
- Głównym celem tej fazy jest znalezienie regionu, w którym szanse na znalezienie najlepszego rozwiązania są większe.
- Inspiracją do tego jest przetrwanie najlepiej przystosowanych.
- Powinno to stanowić równowagę między eksploracją a eksploatacją przestrzeni poszukiwań.
- GA próbuje przenieść genotyp do wyższej sprawności w przestrzeni wyszukiwania.
- Zbyt silna stronniczość wyboru sprawności może prowadzić do nieoptymalnych rozwiązań.
- Zbyt mały wybór odchyleń w zakresie sprawności powoduje nieokreślone wyszukiwanie.
- Zatem stosuje się dobór proporcjonalny do sprawności, który jest również znany jako wybór koła do ruletki, jest operatorem genetycznym stosowanym w algorytmach genetycznych do wybierania potencjalnie użytecznych rozwiązań dla rekombinacji.
4. Powielanie
Generowanie potomstwa odbywa się na 2 sposoby:
- Krzyżowanie
- Mutacja
a) Crossover
Crossover jest najważniejszym etapem w algorytmie genetycznym. Podczas krzyżowania losowy punkt jest wybierany podczas kojarzenia pary rodziców w celu wygenerowania potomstwa.
Istnieją 3 główne typy crossoverów.
- Przejście jednopunktowe : punkt na chromosomach obojga rodziców jest wybierany losowo i oznaczany jako „punkt podziału”. Bity po prawej stronie tego punktu są wymieniane między dwoma chromosomami macierzystymi.
- Crossover dwupunktowy: Dwa punkty crossover są wybierane losowo z chromosomów rodzicielskich. Bity pomiędzy dwoma punktami są zamieniane między organizmami rodzicielskimi.
- Uniform Crossover: W jednolitym crossoverie zazwyczaj każdy bit jest wybierany z jednego elementu nadrzędnego z jednakowym prawdopodobieństwem.
Nowe potomstwo zostanie dodane do populacji.
b) Mutacja
U kilku nowo powstałych potomków niektóre z ich genów można poddać mutacji z niskim prawdopodobieństwem losowym. Oznacza to, że niektóre bity w chromosomie bitowym można przerzucić. Mutacja zajmuje się różnorodnością populacji i zatrzymuje przedwczesną konwergencję.
5. Konwergencja (kiedy przestać)
Oto kilka zasad, które mówią, kiedy zatrzymać:
- Gdy nie ma poprawy jakości rozwiązania po ukończeniu określonej liczby pokoleń ustawionych wcześniej.
- Po osiągnięciu twardego i szybkiego zakresu pokoleń i czasu.
- Do momentu uzyskania akceptowalnego rozwiązania.
Zastosowanie algorytmu genetycznego
W tej sekcji omówimy niektóre obszary, w których często stosuje się algorytm genetyczny.
1. Podróżowanie i trasowanie przesyłek
Problem wędrownego sprzedawcy jest jednym z głównych zastosowań algorytmu genetycznego. Na przykład, gdy planista podróży jest proszony o zaplanowanie podróży, skorzystałby z algorytmu genetycznego, który nie tylko pomaga obniżyć całkowity koszt podróży, ale także skrócić czas. SG jest również wykorzystywany do planowania dostawy produktów z miejsca na miejsce w najbardziej efektywny sposób.
2. Robotyka
Algorytm genetyczny jest szeroko stosowany w dziedzinie robotyki. Roboty różnią się między sobą celem, dla którego zostały zbudowane. Na przykład niewiele jest zbudowanych do zadania gotowania, niewiele do zadań dydaktycznych itp.
- Wybór ważnych funkcji w danym zestawie danych.
- W metodzie tradycyjnej ważne funkcje zestawu danych wybiera się przy użyciu następującej metody. tzn. spojrzysz na ważność tego modelu, a następnie ustawi wartość progową dla funkcji, a jeśli cecha ma wartość ważności większą niż próg, jest to brane pod uwagę.
- Ale tutaj używamy metody zwanej problemem plecakowym.
- Zaczniemy ponownie od populacji chromosomu, gdzie każdy chromosom będzie ciągiem binarnym. 1 oznacza „włączenie” cechy w modelu, a 0 oznacza „wykluczenie” cechy w modelu.
- Funkcja fitness będzie tutaj naszą miarą dokładności zawodów. Im dokładniejszy jest nasz zestaw chromosomów w przewidywaniu wartości, tym bardziej będzie dopasowany.
- Istnieje wiele innych zastosowań algorytmów genetycznych, takich jak analiza DNA, tworzenie harmonogramów, projektowanie inżynierskie.
Wniosek
W obecnym scenariuszu GE stosuje się w dużych firmach produkcyjnych, takich jak samoloty itp., W celu optymalizacji czasu i zużycia zasobów. Kolejni naukowcy pracują nad znalezieniem nowych sposobów łączenia algorytmów genetycznych z innymi technikami optymalizacji.
Polecane artykuły
To jest przewodnik po Czym jest algorytm genetyczny? Tutaj omawiamy wprowadzenie, fazy i zastosowania algorytmu genetycznego. Możesz także przejrzeć nasze inne sugerowane artykuły -
- Algorytmy routingu
- Rodzaje algorytmów
- Algorytmy sieci neuronowej
- Algorytmy eksploracji danych
- przewodnik po przykładach algorytmu C ++