Poprzedni

2. Heurystyki

2.4. Algorytmy ewolucyjne

Algorytmy ewolucyjne (EA) to klasa metaheurystycznych technik optymalizacji inspirowanych zasadami ewolucji biologicznej. Są one wykorzystywane do znajdowania przybliżonych rozwiązań złożonych problemów optymalizacji, szczególnie w przypadku problemów optymalizacji dyskretnej, w których przestrzeń rozwiązań jest nieciągła i często duża. Algorytmy ewolucyjne są szczególnie skuteczne w optymalizacji dyskretnej ze względu na ich zdolność do eksploracji i wykorzystywania różnych regionów przestrzeni rozwiązań. Wykorzystują mechanizmy analogiczne do doboru naturalnego, mutacji i krzyżowania, aby iteracyjnie ulepszać rozwiązania.

Podstawowe elementy algorytmów ewolucyjnych

  • Populacja: Zbiór rozwiązań kandydackich problemu optymalizacji. Każde rozwiązanie w populacji jest oceniane na podstawie funkcji dopasowania, która mierzy jego jakość.
  • Selekcja: Proces wybierania najlepiej działających rozwiązań z bieżącej populacji, które mają pełnić rolę rodziców dla następnego pokolenia. Często opiera się to na wartościach dopasowania, przy czym lepsze rozwiązania mają większą szansę na wybranie.
  • Krzyżowanie (rekombinacja): Operator genetyczny używany do łączenia części dwóch rozwiązań rodzicielskich w celu stworzenia potomstwa. Chodzi o odziedziczenie dobrych cech od obojga rodziców w celu wytworzenia potencjalnie lepszych rozwiązań.
  • Mutacja: Operator genetyczny wprowadzający małe losowe zmiany do rozwiązania. Pomaga to utrzymać różnorodność genetyczną w populacji i umożliwia algorytmowi eksplorację nowych obszarów przestrzeni rozwiązań.
  • Zastępowanie: Proces tworzenia nowej populacji poprzez zastąpienie części lub całości starej populacji nowymi rozwiązaniami. Można to zrobić, stosując różne strategie, takie jak zastąpienie całej populacji lub tylko jej części.
  • Zakończenie: Kryteria zakończenia algorytmu. Może to być maksymalna liczba pokoleń, kryterium zbieżności, w którym rozwiązania nie ulegają już znaczącej poprawie, lub znalezienie zadowalającego rozwiązania.

Przykłady algorytmów ewolucyjnych

  1. Algorytmy genetyczne(GAs):

      Algorytmy genetyczne są najbardziej znanym typem algorytmów ewolucyjnych. Działają na populacji rozwiązań, wykorzystując operatory inspirowane genetyką naturalną. W problemach dyskretnych algorytmy genetyczne obsługują permutacje, kombinacje lub dowolne struktury dyskretne. Na przykład w problemie komiwojażera (TSP) algorytmy genetyczne mogą generować i rozwijać trasy, łącząc różne sekwencje miast w celu znalezienia krótszych ścieżek. Algorytmy genetyczne mogą cierpieć na przedwczesną konwergencję, w której populacja staje się zbyt podobna, co zmniejsza różnorodność i szansę na znalezienie lepszych rozwiązań.
    • .

  2. Strategie ewolucyjne (ES):

    Strategie ewolucyjne koncentrują się na optymalizacji parametrów o wartościach rzeczywistych, ale można je dostosować do problemów optymalizacji dyskretnej. ES można stosować w problemach, w których rozwiązania są kodowane jako liczby rzeczywiste, ale mają charakter dyskretny, takich jak optymalizacja parametrów sieci neuronowych w uczeniu maszynowym. Jednakże obsługa rozwiązań dyskretnych wymaga dodatkowych technik kodowania i ostrożnego postępowania z operacjami mutacji i rekombinacji.

Reprezentacja rozwiązań w algorytmach ewolucyjnych

W algorytmach ewolucyjnych (EA) reprezentacja rozwiązań jest krytycznym aspektem, ponieważ bezpośrednio wpływa na sposób ewolucji rozwiązań za pomocą operatorów genetycznych, takich jak krzyżowanie, mutacja i selekcja. Prawidłowa reprezentacja zapewnia, że ​​algorytm może skutecznie eksplorować przestrzeń rozwiązań i skutecznie stosować operatory genetyczne w celu ulepszania rozwiązań. Reprezentacja rozwiązań w algorytmach ewolucyjnych różni się w zależności od rodzaju rozwiązywanego problemu. Przykłady reprezentacji.

Reprezentacja binarna

Reprezentacja binarna koduje rozwiązania jako ciągi cyfr binarnych (0 i 1). Jest to jedna z najprostszych i najczęściej używanych reprezentacji w algorytmach ewolucyjnych. W przypadku problemu, w którym rozwiązanie obejmuje wybranie elementów z zestawu (jak problem plecakowy), ciąg binarny może reprezentować, czy każdy element jest uwzględniony (1), czy wykluczony (0). Jeśli są 4 przedmioty, rozwiązanie może być reprezentowane w ten sposób:
[1, 0, 1, 0]
Oznacza to, że pierwszy i trzeci element znajdują się w plecaku, natomiast drugi i czwarty nie.

Krzyżowanie i mutacja w reprezentacji binarnej:

  • Krzyżowanie: Powszechnie stosuje się krzyżowanie jednopunktowe i dwupunktowe. Na przykład krzyżowanie jednopunktowe może zamieniać segmenty ciągów binarnych pomiędzy sobą.
  • Mutacja: Powszechnie stosowana jest mutacja bitowa, w której każdy bit w ciągu ma szansę (z określonym prawdopodobieństwem) na zmianę (0 na 1 lub 1 na 0).

Przykład krzyżowania:

Wyobraźmy sobie dwa rozwiązania binarne:

Rodzic 1: [1, 0, 0, 1]
Rodzic 2: [0, 1, 1, 0]

Krzyżowanie jednopunktowe może wyglądać następująco:

Punkt krzyżowania: 2 

Potomstwo 1: [1, 0, 1, 0] 

Potomstwo 2: [0, 1, 0, 1]

Reprezentacja permutacyjna

Reprezentacja permutacyjna jest używana w problemach, gdzie rozwiązania są permutacjami zbioru elementów. Jest to popularna reprezentacja w problemach kombinatorycznych, takich jak problem komiwojażera (TSP).

Przykład: W TSP rozwiązanie może być reprezentowane jako permutacja miast. Dla 5 miast oznaczonych A, B, C, D i E, możliwa permutacja to:

Rozwiązanie = [B, D, A, E, C]To oznacza, że trasa zaczyna się w mieście B, następnie przechodzi do D, A, E, a kończy w C.

Krzyżowanie i mutacja w reprezentacji permutacyjnej:

  • Krzyżowanie: Krzyżowanie porządkowe (OX) i krzyżowanie częściowo mapowane (PMX) są dostosowane do permutacji bez duplikowania elementów (jak np. w problemie komiwojażera, gdzie nie chcemy, żeby miasta się powtarzały, nawet po wykonaniu krzyżowania).
  • Mutacja: Mutacja wymiany (wymiana dwóch elementów) i mutacja inwersji (odwrócenie kolejności segmentu) są powszechnie stosowane.

Przykład krzyżowania:

Rodzic 1: [A, B, C, D, E]
Rodzic 2: [C, A, B, E, D]

Krzyżowanie porządkowe może wyglądać tak:

Obszar krzyżowania: 2 do 4 

Potomstwo 1: [A, B, C, E, D] 

Potomstwo 2: [C, A, D, B, E]


Reprezentacja Wartości Rzeczywistych

Reprezentacja wartości rzeczywistych używa zmiennych ciągłych do kodowania rozwiązań. Jest to powszechne w problemach optymalizacji, gdzie przestrzeń rozwiązań jest ciągła, jak w optymalizacji parametrów w uczeniu maszynowym.

Dla problemu optymalizacji funkcji rozwiązanie może być reprezentowane jako wektor liczb rzeczywistych

Rozwiązanie = [1.5, -2.3, 0.7]
Ten wektor reprezentuje wartości zmiennych, które są optymalizowane w celu minimalizacji lub maksymalizacji funkcji celu.

Krzyżowanie i Mutacja:

  • Krzyżowanie: Krzyżowanie arytmetyczne, gdzie wartości potomków są interpolowane między wartościami rodziców. Np.jeśli punkt krzyżowania został wybrany jako a=0.6, to potomek 1 (x1') jest wyliczany jako x1'=a*x1 + (1-a)*x2, a potomek 2 (x2') jest wyliczany jako x2' = (1-a)*x1 + a*x2.
  • Mutacja: Często jest stosowana tzw. mutacja gaussowska, która dodaje losową wartość z rozkładu normalnego do wybranej  zmiennej.
Przykład:
Rodzic 1: [1.5, -2.3, 0.7]
Rodzic 2: [2.0, -1.5, 1.2]
Krzyżowanie artymetyczne:
Punkt Krzyżowania: a=0.6,
Potomstwo 1: [1.7, -1.98, 0.9]
Potomstwo 2: [1.8, -1.82, 1.0]



  Poprzedni