Metody przybliżone rozwiązywania zadań optymalizacji dyskretnej

Większość deterministycznych problemów planowania i sterowania w dyskretnych systemach wytwarzania jest formułowana jako zagadnienia optymalizacji, w których wszystkie zmienne decyzyjne (bądź ich część ) przyjmują wartości dyskretne, całkowitoliczbowe lub binarne. Zadania takie często nazywa się problemami optymalizacji dyskretnej lub dyskretno-ciągłej, należą do klasy problemów wyjątkowo kłopotliwych z obliczeniowego punktu widzenia. Zagadnienia te sprowadzają się do zadania minimalizacji funkcji celu K(x) na zbiorze rozwiązań dopuszczalnych X, określonym przez zestaw warunków ograniczających. Głównymi powodami tych kłopotów są: częsty brak „klasycznych”, analitycznych własności (różniczkowalność, liniowość, itp.), wielo-ekstremalność ze znaczną liczbą ekstremów lokalnych. NP.-trudność większości problemów pochodzących z praktyki oraz przekleństwo wielowymiarowości.

Wielokrotnie, w celu uniknięcia kłopotów, próbuje się zamiast rozwiązywać problem dokładnie, wyznaczyć pewne jego rozwiązanie przybliżone. Dokładność tego przybliżenia posiada tendencję przeciwstawną do czasu obliczeń, tzn. uzyskanie dokładniejszego rozwiązania wymaga dłuższego czasu trwania algorytmu, przy czym ta ostatnia zależność posiada charakter silnie nieliniowy. Jest to czynnikiem powstania wielu rodzajów zarówno modeli jak i metod rozwiązywania, zwykle dedykowanych dla wąskich klas zagadnień. Często dla tego samego problemu NP.-trudnego występuje w literaturze kilka, kilkanaście różnych algorytmów o istotnie różnych cechach numerycznych.

Metody przybliżone

Metoda przybliżona wyznacza pewne rozwiązanie bliskie rozwiązaniu dokładnemu. Metod przybliżonych jest zdecydowanie więcej niż dokładnych, zwykle są one problemowo-zorientowane. Zasadniczo, jakość metody przybliżonej jest oceniania z dwóch punktów widzenia: złożoność obliczeniowa algorytmu oraz dokładność przybliżenia. Dalsza charakterystyka bierze pod uwagę, między innymi, gwarancje zbieżności do rozwiązania optymalnego, szybkość tej zbieżności. Jakość wszystkich wymienionych ocen zalezy od metody, problemu oraz konkretnych danych liczbowych podanych do algorytmu.

W ostatnich latach nastąpił burzliwy rozwój metod przybliżonych o dobrych i bardzo dobrych własnościach numerycznych potwierdzonych eksperymentalnie. Znaczna część tych metod czerpie swoje inspiracje z Natury i ma związek z dziedziną Sztucznej Inteligencji oraz Uczenia Maszynowym.

Symulowane wyżarzanie

Metoda symulowanego wyżarzania, odprężenia, używa analogi do termodynamicznego procesu studzenia, w celu wyprowadzenia trajektorii poszukiwań z ekstremum lokalnego lub uniknięcia takiego ekstremum. Stany ciała są postrzegane jako analogiczne do rozwiązań, zaś energia ciała - analogiczna do wartości funkcji celu.

Kroki algorytmu w klasycznym podejściu podczas minimalizacji funkcji

1. Losowy wybór punktu startowego
   . Przyjęcie temperatury
   ,

2. Wyznaczenie wartości funkcji
   w punkcie
   ,

3. Wyznaczenie
   , gdzie
   jest realizacją zmiennej losowej o rozkładzie normalnym z medianą w punkcie
   i średnią wariancją równą
   ,

4. Wyznaczenie wartości funkcji
   w nowym punkcie,

5. Podstawienie wartości
   do
   z prawdopodobieństwem danym rozkładem Boltzmanna
   ,

6. Zmniejszenie temperatury
   , gdzie
   jest stałą z przedziału
   ,

7. Zwiększenie kroku iteracyjnego i powrót do kroku 3.

Temperatura jest zmieniana w czasie iteracji według schematu studzenia. Powszechnie stosowane są dwa schematy zmian temperatury: geometryczny i logarytmiczny. Dowiedziono, że przy pewnych założeniach schemat logarytmiczny (w przeciwieństwie do pozostałych) gwarantuje w dostatecznie długim czasie znalezienie optimum globalnego z prawdopodobieństwem 1. Wariant ten nie ma jednak zastosowania praktycznego, gdyż jest zbyt powolny. Badania empiryczne sugerują, że największą przydatność praktyczną ma schemat geometryczny (najszybszy). Schemat studzenia ma silny wpływ na zachowania się metody. Jeżeli studzenie jest zbyt szybkie, algorytm symulowanego wyżarzania szybko kończy swoje działanie w lokalnym ekstremum słabej jakości. Jeżeli studzenie jest zbyt powolne, czas przebiegu algorytmu staje się nieakceptowanie długi. W praktyce, właściwy dobór wszystkich parametrów sterujących metody wymaga wykonania znacznej liczby testów komputerowych.

Poszukiwanie z zakazami (Tabu Search)

TS powiela naturalny proces poszukiwania rozwiązania wykonywany przez człowieka. Podstawowa wersja TS rozpoczyna działanie od pewnego rozwiązania początkowego. Elementarny krok tej metody wykonuje, dla podanego rozwiązania - przeszukuje całe sąsiedztwo danego rozwiązania. Sąsiedztwo jest zdefiniowane poprzez ruchy (przejścia) która można wykonać z danego punktu, w którym się aktualnie znajdujemy. (Ruch transformuje jedno rozwiązanie w drugie rozwiązanie). Celem tego poszukiwania jest znalezienie rozwiązania z najmniejszą wartością funkcji celu. Następnie proces jest powtarzany od najlepszego znalezionego rozwiązania dostarczając trajektorii poszukiwań. Metoda TS zwraca jako wynik najlepsze rozwiązanie z trajektorii.

Aby zapobiec cyklicznemu powtarzaniu się rozwiązań na trajektorii, zatrzymaniu w ekstremum lokalnym, oraz aby prowadzić trajektorię poszukiwań w obiecujące obszary zbioru rozwiązań, wprowadzono pamięć historii poszukiwań. Najczęściej stosowaną klasą pamięci używaną dla TS jest pamięć krótkoterminowa zwana listą zabronień. Lista ta przechowuje przez ograniczony okres czasu najświeższe rozwiązania z trajektorii poszukiwań, wybrane atrybuty tych poszukiwań, ruchy prowadzące do tych rozwiązań lub atrybuty ruchów, traktując je wszystkie jako formę zabronienia dla ruchów wykonywanych w przyszłości. Wykonanie ruchu posiadające zabronione atrybuty jest zabronione. Poszukiwanie zatrzymuje się, jeżeli została wykonana pewna liczba iteracji bez poprawy wartości funkcji celu, wykonano założoną z góry całkowitą liczbę iteracji, przekroczono czas obliczeń, znaleziono rozwiązanie satysfakcjonujące użytkownika.

Do innych metod przybliżonych należą również takie algorytmy jak B&B, czyli podziału i ograniczeń, poszukiwanie mrówkowe i wiele innych.

Opracowane na podstawie książki „Algorytmy szeregowania” C. Smutnicki

---