8 METODY PRZYBLIŻONE ZADAŃ OPTYMALIZACJI DYSKRETNEJ

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ń:

otoczenie zawiera n-1 permutacji

otoczenie zawiera n(n-1)/2 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ą :

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

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:

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

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 :

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:

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

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 !!


Wyszukiwarka

Podobne podstrony:
18. Metody przybliżone rozwiązywania zadań optymalizacji dyskretnej I, pytania egzamin inżynierski A
18. Metody przybliżone rozwiązywania zadań optymalizacji dyskretnej II, pytania egzamin inżynierski
Metody przybliżone rozwiązywania zadań optymalizacji dyskretnej
11 Metody rozwiązywania zadań optymalizacji
Metodyka rozwiązywania zadań, Transport Politechnika, Semestr 1, Fizyka
Komputerowy system do?dań?ektywności metaheurystyki ''System Mrówek'' w zakresie optymalizacji dyskr
METODY REALIZACJI ZADAŃ RUCHOWYCH
METODY WYZNACZANIA WILGOTNOŚCI OPTYMALNEJ GRUNTU, METODY WYZNACZANIA WILGOTNOŚCI OPTYMALNEJ GRUNTU
Metody rozwiazywania zadań tekstowych
Metody rozwiązywania zadań tekstowych, matematyka w kształceniu zintegrowanym
Metody rozwiązywania zadań tekstowych, edukacja matematyczna z metodyką
Metody przybliz onego doboru nastaw regulatoro w PID
Metodyka rozw zadań z mechaniki J Nizioł
Typy zadan optymalizacyjnych
Niziol Metodyka rozwiazywania zadan z mechaniki
11 METODY ROZWIˇZYWANIA ZADAŃ TEKSTOWYCH W KSZTAŁCENIU ZINTEGROWANYM
B8 Algorytmy optymalizacji w dyskretnych systemach produkcyjnych
l1 formulowanie zadan optymalizacji

więcej podobnych podstron