Podręcznik

Warunki zakończenia są istotnym elementem sterującym działaniem algorytmu genetycznego. To one decydują, kiedy proces ewolucyjny zostaje zatrzymany, a najlepsze znalezione rozwiązanie uznane za wynik końcowy. Ich odpowiedni dobór wpływa zarówno na jakość rozwiązań, jak i na czas działania algorytmu.

W praktyce stosuje się kilka klas warunków zakończenia, często wykorzystywanych równolegle.

Zakończenie po ustalonej liczbie pokoleń

Najczęstszy i najprostszy sposób zatrzymania działania algorytmu. Proces ewolucyjny kończy się po osiągnięciu ustalonej liczby iteracji (pokoleń).

$\text{Stop, jeśli } t \geq T_{max}$

gdzie $t$ to aktualny numer pokolenia, a $T_{max}$ – maksymalna liczba pokoleń.

Zaletą tej metody jest jej przewidywalność i łatwość implementacji. Wadą – brak związku z faktyczną jakością rozwiązań. Może prowadzić do zakończenia przedwcześnie lub kontynuowania obliczeń mimo osiągnięcia optimum.

Zakończenie po czasie działania

Algorytm zatrzymuje się po upływie określonego czasu rzeczywistego. Stosowane w systemach o ograniczonych zasobach obliczeniowych lub tam, gdzie wymagane są wyniki w czasie rzeczywistym.

$\text{Stop, jeśli } \text{czas} \geq T_{czasowy}$

Ten sposób pozwala dostosować pracę algorytmu do ograniczeń środowiska (np. wbudowane systemy, przetwarzanie online). Jednak, podobnie jak poprzedni, nie uwzględnia postępu jakościowego.

Zakończenie przy braku poprawy

Algorytm zatrzymuje się, gdy przez kolejne $N$ pokoleń nie następuje istotna poprawa najlepszego osobnika:

$\text{Stop, jeśli } \max(F_{best}^{(t - N)} \dots F_{best}^{(t)}) - F_{best}^{(t)} \leq \epsilon$

gdzie $F_{best}^{(t)}$ to wartość funkcji celu najlepszego osobnika w pokoleniu $t$, a $\epsilon$ to zadana tolerancja.

Metoda ta jest bardziej adaptacyjna – pozwala zakończyć działanie algorytmu, gdy dalsze przeszukiwanie nie przynosi postępu. Często używana w połączeniu z limitem pokoleń.

Zakończenie po osiągnięciu wartości celu

Jeśli algorytm znajdzie rozwiązanie o jakości przekraczającej z góry określony próg, zatrzymuje się natychmiast:

$\text{Stop, jeśli } F_{best}^{(t)} \geq F_{target}$

To podejście jest szczególnie przydatne w sytuacjach, gdy znamy wartość globalnego optimum lub poziom, który uznajemy za wystarczający.

Zakończenie na podstawie różnorodności populacji

Zanik różnorodności (np. ujednolicenie genotypów) może wskazywać, że algorytm osiągnął stagnację. Wówczas możemy zakończyć jego działanie:

$\text{Stop, jeśli } \text{diversity}(P_t) \leq \delta$

gdzie $\text{diversity}(P_t)$ mierzy zróżnicowanie populacji $P_t$.

Miara różnorodności może opierać się na odległości Hammingowej, wariancji genów, entropii lub innych statystykach. To podejście pozwala wykryć, że populacja „utknęła” w jednym optimum lokalnym.

Złożone i adaptacyjne warunki zakończenia

W praktyce często łączy się kilka kryteriów – np. maksymalna liczba pokoleń ORAZ brak poprawy przez $N$ pokoleń. Stosuje się także warunki adaptacyjne, gdzie próg tolerancji czy oczekiwany postęp zmieniają się w czasie działania algorytmu.

Możliwe jest także zastosowanie monitorowania pochodnych, prędkości zbieżności lub metryk pochodzących z uczenia maszynowego do przewidywania zatrzymania.

Podsumowanie

Warunki zakończenia to jeden z kluczowych parametrów kontrolnych algorytmu genetycznego. Wpływają na jego efektywność, koszt obliczeniowy i jakość wyniku końcowego. Ich dobór powinien uwzględniać:

• charakterystykę problemu,
• wymagania czasowe lub sprzętowe,
• oczekiwany poziom dokładności,
• strategię eksploracji i eksploatacji.

Stosowanie złożonych i wielokryterialnych warunków zakończenia może znacząco poprawić skuteczność i elastyczność algorytmu.