Dimitrios Haracaris, opracowane na podstawie książki dr Wojciecha Bożejki „Równoległe algorytmy szeregowania zadań produkcyjnych”

8. METODY PRZYBLIŻONE ZADAŃ OPTYMALIZACJI DYSKRETNEJ

W celu uniknięcia niedogodności związanych z otrzymywaniem rozwiązania dokładnego (optymalnego) problemu optymalizacyjnego, próbuje sie wyznaczyć jego rozwiązanie przybliżone. Metody heurystyczne (przybliżone) charakteryzują sie dużym stopniem przystosowania do problemu,

który rozwiązują oraz do kryterium, które maja minimalizować. Często jednak metoda przybliżona doskonale sprawdzająca sie w rozwiązywaniu jednego problemu, nie sprawdza sie w innym. Wynika to w dużej mierze ze specjalizacji algorytmów heurystycznych – parametry ich działania musza być doskonale dostrojone. Pewnym wyjściem jest tu zastosowanie mechanizmu automatycznego strojenia Innym rozwiązaniem jest zastosowanie równoległych algorytmów przybliżonych.

Heurystyka nie gwarantuje znalezienia rozwiązania optymalnego, chociaż „dobra” metoda heurystyczna generuje w krótkim czasie rozwiązania niewiele różniące sie od optymalnego, a wiec w pełni zadawalające z praktycznego punktu widzenia.

Głównym zadaniem heurystyki jest usprawnienie algorytmu rozwiązywania danego problemu. Najważniejsze znaczenie ma eliminowanie z dalszych rozważań części niesprawdzonych jeszcze dokładnie obiektów, które nie rokują wyznaczenia dobrego rozwiązania. Od jakości stosowanej heurystyki zależy złożoność algorytmu rozwiązania problemu.

Algorytmy poszukiwań lokalnych

W konstrukcji wielu algorytmów przybliżonych stosowana jest metoda iteracyjnego polepszania bieżącego rozwiązania poprzez lokalne przeszukiwanie. Rozpoczyna sie ona od pewnego rozwiązania początkowego (startowego). Następnie generuje sie jego otoczenie (sąsiedztwo) oraz wyznacza najlepsze rozwiązanie z tego otoczenia, które przyjmuje sie za rozwiązanie startowe w kolejnej iteracji. Otoczeniem jest zbiorem wszystkich permutacji możliwych do wygenerowania z permutacji za pomocą pojedynczego ruchu. Sposób określania otoczenia jest jednym z podstawowych elementów algorytmu.

Najczęściej stosowane są trzy rodzaje otoczeń:

• wymiana par przyległych (API), otoczenie zawiera wszystkie permutacje wygenerowane przez zamianę dwóch sąsiadujących elementów,

otoczenie zawiera n-1 permutacji

• wymiana par dowolnych(NPI), otoczenie zawiera wszystkie permutacje wygenerowane przez zamianę dwóch dowolnych elementów,

otoczenie zawiera n(n-1)/2 permutacji

• technika przenoszenia i wstawiania (INS) - permutacje generowane przez wyjęcie pewnego elementu z pozycji a i włożenie go tak aby zajmował pozycję b, część elementów należy wtedy przesunąć, otoczenie zawiera (n-1)² permutacji

Przeszukiwanie tabu

Metoda tabu jest modyfikacją metody lokalnych poszukiwań. Dopuszcza sie możliwość zwiększania wartości funkcji celu (przy wyznaczaniu nowego rozwiązania generującego otoczenie), aby w ten sposób zwiększyć szanse na osiągniecie minimum globalnego. Takie ruchy „w górę” należy jednak kontrolować, ponieważ w przeciwnym razie po osiągnięciu minimum lokalnego nastąpiłby szybki do niego powrót. W celu uniknięcia „zapętlenia”, skierowania poszukiwań w obiecujące regiony

przestrzeni oraz umożliwienie wyjścia z ekstremum lokalnego wprowadza sie tzw. mechanizm zabronień. Wykonując ruchy zapamiętuje sie rozwiązania, atrybuty rozwiązań lub ruchów na tzw. liście tabu. Generując otoczenie nie rozpatrujemy rozwiązań znajdujących sie na tej liście chyba, ze spełniają warunki, przy których ograniczenia tabu można pominąć. Podstawowymi elementami metody tabu search są :

• ruch: funkcja, która transformuje jedno rozwiązanie w drugie,

• otoczenie: zbiór rozwiązań możliwych do otrzymania z jednego ustalonego

rozwiązania za pomocą pewnej klasy ruchów,

• lista tabu: lista zawierająca atrybuty ruchów lub rozwiązań dla pewnej liczby ostatnio rozpatrywanych rozwiązań, skojarzona z operatorami jej modyfikacji (dodawanie i usuwanie atrybutów) oraz operatorami badania zabronień,

• kryterium aspiracji: warunki, przy których można pominąć ograniczenia wprowadzone przez listę tabu

• warunek zakończenia: algorytm zazwyczaj kończy działanie, jeżeli: (a)

wykonał z góry określoną liczbę iteracji, (b) w kolejnych iteracjach nie uzyskano poprawy wartości funkcji kryterialnej, (c) aktualne otoczenie jest zbiorem pustym.

Symulowane wyżarzanie

Metoda symulowanego wyżarzania, ze względu na prostotę implementacji

oraz uniwersalność, jest z powodzeniem stosowana do rozwiązywania wielu

problemów optymalizacyjnych, jej podstawowe idee pochodzą z termodynamiki. Posiada

ona pewne analogie z procesem wyżarzania (chłodzenia) ciała stałego, stad w jej opisie używa sie pojęć z tej właśnie dziedziny. Cechą charakterystyczną metody jest stopniowe obniżanie parametru kontrolnego zwanego temperaturą. Konstrukcja algorytmu opartego na metodzie symulowanego wyżarzania wymaga określenia następujących elementów:

• funkcji akceptacji: funkcja prawdopodobieństwa z jakim są przyjmowane

(za rozwiązania startowe w następnej iteracji) elementy otoczenia,

• schemat chłodzenia: funkcja określająca zmianę funkcji akceptacji w zależności

od parametru kontrolnego zwanego temperatura (zwykle zależnego od numeru iteracji algorytmu).

Parametr kontrolny (temperatura) zmienia sie zazwyczaj co ustalona liczbę iteracji algorytmu według jednego ze schematów chłodzenia. Podstawowe schematy :

• geometryczny t_i + 1 = λ_it_i

• logarytmiczny $\ t_{i + 1} = \ \frac{t_{i}}{1 + \lambda_{i}t_{i}}$

• oparty na twierdzeniu Hajeka $\ t_{i + 1} = \ \frac{A}{ln(i + 2)}$ A – liczba kroków potrzebna do opuszczenia ekstremum lokalnego

Przy implementacji algorytmu należy tak ustalić jego parametry, aby po wykonaniu pewnej liczby iteracji prawdopodobieństwo akceptacji rozwiązań znacznie różniących sie od najlepszego do tej pory wyznaczonego malało, przez co szybko dochodzimy do pewnego minimum lokalnego. Po jego osiągnięciu przywraca sie początkowe wartości parametrom (zwiększając prawdopodobieństwo akceptacji „gorszych” rozwiązań) umożliwiając w ten sposób znaczne oddalenie sie od bieżącego minimum.

Algorytmy ewolucyjne

Określenia „algorytmy ewolucyjne” oraz „algorytmy genetyczne” obejmują grupę metod obliczeniowych, których wspólna cecha jest korzystanie, przy rozwiązywaniu danego problemu, z mechanizmu opartego na zjawisku naturalnej ewolucji gatunków. Są one bezpośrednią adaptacja tego zjawiska, stad w ich opisie używa sie pojęć z genetyki W metodach tych, na wyróżnionych podzbiorach zbioru rozwiązań dopuszczalnych (populacji osobników), wykonywane są cyklicznie trzy podstawowe operacje:

• selekcja: polegająca na wyborze, z bieżącej populacji, pewnego podzbioru

osobników najlepiej przystosowanych (najbardziej obiecujących) zwanych rodzicami, na bazie których zostanie utworzone następne pokolenie,

• krzyżowanie: polegająca na wygenerowaniu z odpowiednio dobranych par rodziców nowych osobników (potomstwa),

• mutacja: wykonywana z niewielkim prawdopodobieństwem na zbiorze potomków,

w celu zapobiegnięcia stagnacji w procesie poszukiwań.

Selekcja i krzyżowanie są najmocniejszymi operatorami na zbiorze osobników.

Dzięki nim cały proces ten ma charakter ewolucyjny i prowadzi do wygenerowania podzbioru zawierającego „najbardziej obiecujące” rozwiązania.

Działanie algorytmu zaczyna się od wygenerowania populacji o stałej liczebności. W kolejnej iteracji tworzona jest generacja w następujący sposób: z bieżącej populacji wybierana jest pewna ilość najlepszych osobników, z nich przez mechanizm krzyżowania generuje się nowych osobników (potomstwo). Na części z nich dokonuje się mutacji aby zróżnicować populacje. Tak wygenerowane potomstwo zastępuje najgorszych osobników w bieżącej populacji tworząc nową generację. Algorytm kończy działania po wygenerowaniu liczby osobników z góry ustalonej.

TO DODAJE ABY KAŻDY MÓGŁ SOBIE OBEJRZEĆ SCHEMATY ALGORYTMÓW I WSZYSTKIE METODY,

TEGO SIĘ NIEUCZCIE !!