Podręcznik

Zanim rzucimy się w wir algorytmów ewolucyjnych, warto poznać kilka klasycznych podejść do przeszukiwania przestrzeni rozwiązań. Choć czasem uznawane za przestarzałe, wciąż stanowią punkt odniesienia dla każdej bardziej zaawansowanej metody. W tym podrozdziale skupimy się na przestrzeni dyskretnej – czyli takiej, gdzie liczba możliwych rozwiązań jest skończona (choć może być bardzo duża).

Przeszukiwanie pełne (brute force)

Najbardziej oczywista metoda: sprawdź wszystkie możliwe rozwiązania i wybierz najlepsze. Działa idealnie... pod warunkiem, że masz do przeszukania małą przestrzeń. Niestety, w praktyce:

• liczba możliwych rozwiązań rośnie wykładniczo z liczbą zmiennych,
• przy nawet kilku zmiennych dyskretnych zakres możliwości może sięgać miliardów,
• szybko przekraczamy możliwości obliczeniowe dostępnego sprzętu.

Przykład: jeśli mamy 10 zmiennych całkowitych przyjmujących po 10 wartości, to mamy $10^{10} = 10,000,000,000$ rozwiązań.

Zalety:

• gwarantuje znalezienie najlepszego rozwiązania (jeśli istnieje),
• działa niezależnie od natury funkcji celu,
• bardzo prosta implementacja.

Wady:

• totalnie niepraktyczne dla większych problemów,
• nie wykorzystuje żadnej wiedzy o strukturze przestrzeni.

Przeszukiwanie losowe

Zamiast sprawdzać wszystko – losujemy. Algorytm losowy wybiera kolejne rozwiązania zupełnie przypadkowo z przestrzeni dyskretnej i ocenia ich jakość. Jeśli uda się znaleźć dobre – super. Jeśli nie – próbujemy dalej.

Jak to wygląda w praktyce:

• losujemy rozwiązanie $x$,
• obliczamy wartość funkcji celu $f(x)$,
• zapamiętujemy najlepszy wynik dotąd,
• powtarzamy przez ustaloną liczbę iteracji.

Zalety:

• prostota implementacji – dosłownie kilka linijek kodu,
• możliwość działania równoległego (każdy proces może losować osobno),
• działa w każdej przestrzeni dyskretnej (nie wymaga żadnych założeń).

Wady:

• zupełna przypadkowość – możemy długo błądzić zanim trafimy coś sensownego,
• nie wykorzystuje wiedzy z poprzednich prób – "ślepe strzelanie",
• nie gwarantuje znalezienia rozwiązania lepszego od startowego.

Mimo wad, algorytmy losowe bywają zaskakująco skuteczne w przestrzeniach, gdzie lokalne strategie często wpadają w minima lokalne – np. przy wielu zaporowych ograniczeniach.

Przeszukiwanie losowe z pamięcią

Wariant bardziej zaawansowany: próbujemy wykorzystać doświadczenia z poprzednich losowań. Czyli: pamiętamy coś o przeszłości i nie działamy całkiem na oślep. Oto dwie popularne techniki:

Symulowane wyżarzanie (simulated annealing)

Metoda inspirowana procesami fizycznymi – konkretnie wyżarzaniem metali. Algorytm:

• zaczyna od losowego rozwiązania,
• losowo modyfikuje je (tworzy sąsiada),
• jeśli sąsiad jest lepszy – przyjmuje go,
• jeśli jest gorszy – może go przyjąć z pewnym prawdopodobieństwem $p = e^{-\Delta f / T}$,
• temperatura $T$ maleje w czasie – co zmniejsza prawdopodobieństwo akceptowania gorszych rozwiązań.

To podejście pozwala wyjść z minimum lokalnego, ale z czasem staje się coraz bardziej zachowawcze – koncentruje się na najlepszych rozwiązaniach.

Algorytm tabu (tabu search)

Tutaj z kolei prowadzimy rodzaj "czarnej listy" – pamiętamy, gdzie już byliśmy i unikamy powtórek. Algorytm:

• przechodzi od rozwiązania do jego najlepszego sąsiada,
• jeśli sąsiad był niedawno odwiedzony – jest oznaczany jako tabu (czyli zakazany),
• lista tabu działa jak bufor cykliczny (np. ostatnie 100 odwiedzin),
• pozwala to uniknąć cyklicznego krążenia wokół tego samego minimum.

Algorytmy z pamięcią są inteligentniejszą odmianą przeszukiwania losowego – uczą się w czasie, nie pozwalają wracać do kiepskich punktów, próbują eksplorować nowe rejony przestrzeni.

Dyskretyzowane problemy ciągłe

W tym rozdziale skupiliśmy się na problemach dyskretnych, ale czy nie da się tego zastosować dla czasu ciągłego? Pewnie się da ... przecież komputery w naturalny sposób nie są w stanie pamiętać liczb rzeczywistych, ale rozwiązują problemy z nimi związane. Można więc działać tak jak typowy system cyfrowy - zastosować  podejście zwane dyskretyzacją przestrzeni ciągłej.

Jak to działa:

• dzielimy przestrzeń ciągłą na siatkę (np. co 0.1 jednostki),
• traktujemy punkty siatki jako osobne, dyskretne rozwiązania,
• stosujemy klasyczne metody dyskretne (np. losowe przeszukiwanie, tabu search).

Zalety:

• umożliwia stosowanie metod dyskretnych tam, gdzie oryginalnie są zmienne ciągłe,
• pozwala testować algorytmy bez potrzeby obliczania pochodnych.

Wady:

• precyzja zależy od gęstości siatki – im dokładniej, tym więcej punktów do przeszukania,
• może prowadzić do pomijania istotnych cech funkcji celu (np. minimów między węzłami siatki).