Podręcznik

Zanim zaczniemy wybierać konkretne algorytmy optymalizacji, musimy się zastanowić: jak wygląda przestrzeń, w której będziemy szukać rozwiązań? To jedno z najważniejszych pytań, jakie należy sobie zadać w kontekście minimalizacji.

Przestrzeń poszukiwań – nie tylko zbiór liczb

W poprzednim rozdziale wprowadziliśmy pojęcie przestrzeni poszukiwań – zbioru wszystkich możliwych konfiguracji zmiennych decyzyjnych. Teraz dodajmy coś istotnego: ten zbiór może mieć bardzo różną strukturę.

Najczęściej spotykamy dwie sytuacje:

• zmienne decyzyjne mogą przyjmować wartości ciągłe – np. długość pręta w metrach: 1.37 m, 2.03 m, 0.88 m, itd.

• lub wartości dyskretne – np. wybór trasy w problemie komiwojażera, rozmieszczenie urządzeń na siatce, przypisanie pracowników do zadań.

Niektóre problemy można też przedstawić jako mieszane – część zmiennych jest ciągła, a część dyskretna. Takie przypadki są typowe np. w inżynierii procesowej.

Przestrzeń ciągła – gładka, ale nie zawsze łatwa

Przestrzeń ciągła to taka, w której zmienne mogą przyjmować dowolne wartości z pewnego przedziału. Matematycznie mówimy wtedy, że $x \in \mathbb{R}^n$.

Zaletą przestrzeni ciągłej jest to, że możemy używać narzędzi analizy matematycznej – np. obliczać pochodne, badać gradienty, korzystać z metod iteracyjnych typu Newtona czy spadku gradientu. Tyle że jest pewien haczyk: takie metody zakładają gładkość funkcji celu (czyli że nie ma skoków, ostrych minimów ani zerwań ciągłości).

Problemy:

• minimum może być lokalne, a nie globalne,

• funkcja może być „płaska” – przez co gradient nic nie mówi,

• ograniczenia mogą tworzyć bardzo wąskie lub nieregularne obszary.

Przestrzeń dyskretna – przeliczalna, ale ogromna

Z kolei przestrzeń dyskretna to taka, w której zmienne mogą przyjmować jedynie określone, policzalne wartości – np. liczby całkowite, ciągi permutacji, konfiguracje binarne.

Przykład:

• Problem komiwojażera: przestrzeń to zbiór wszystkich permutacji miast (czyli $n!$ możliwości).

• Alokacja pracowników do zmian: przestrzeń to zbiór możliwych macierzy przydziału z warunkami logicznymi.

Zaletą przestrzeni dyskretnej jest to, że nie potrzebujemy pochodnych, a każdy punkt jest „jednostką”, którą da się jednoznacznie opisać. Ale przestrzenie dyskretne rosną wykładniczo – tzn. liczba możliwych rozwiązań może szybko przekroczyć zdolność obliczeniową nawet dużych komputerów.

Problemy:

• przeszukiwanie wyczerpujące staje się niemożliwe,

• często nie ma pojęcia "bliskich" rozwiązań – trudno stosować pojęcie lokalnego minimum,

• konieczne są sprytne strategie eksploracji (np. losowe skoki, heurystyki).

Różnice w optyce algorytmów

Wybór algorytmu powinien być dostosowany do rodzaju przestrzeni, bo algorytmy myślą (a raczej "liczą") w zupełnie inny sposób zależnie od tego, czy mają do czynienia z przestrzenią ciągłą czy dyskretną.

W przestrzeni ciągłej algorytmy często opierają się na lokalnej analizie funkcji celu:

• szukają kierunku największego spadku (gradient),

• opierają się na pochodnych, macierzy Hessego lub metodach quasi-Newtona,

• iteracyjnie poprawiają rozwiązanie w stronę minimum,

• zakładają pewną gładkość i regularność przestrzeni.

Typowe algorytmy:

• metoda największego spadku,

• metoda Newtona i quasi-Newtona (BFGS),

• algorytmy ewolucyjne z kodowaniem rzeczywistoliczbowym.

W przestrzeni dyskretnej wszystko wygląda inaczej:

• nie mamy pojęcia o "nachyleniu", bo między punktami nie istnieje pojęcie pochodnej,

• bliskość rozwiązań nie zawsze przekłada się na podobieństwo funkcji celu,

• konieczne są inne strategie eksploracji: permutacje, losowanie, heurystyki lokalne.

Typowe podejścia:

• algorytmy zachłanne i lokalne przeszukiwanie (hill climbing),

• algorytmy metaheurystyczne: symulowane wyżarzanie, algorytmy genetyczne,

• strategie oparte na populacjach i losowym próbkowaniu.

Przykład porównawczy

Załóżmy, że projektujemy most i chcemy:

• w przestrzeni ciągłej: dobrać grubości, długości i przekroje belek,

• w przestrzeni dyskretnej: wybrać z katalogu gotowe komponenty (typu prefabrykaty).

Pierwszy problem daje więcej swobody, ale może prowadzić do rozwiązań nierealnych. Drugi wymaga kompromisów, ale łatwiej go uwzględnić w kosztorysie i harmonogramie.