Wykład 7 Optymalizacja w sensie Pareto I optymalizacja wielokryterialna



Pobieranie 73.27 Kb.
Data08.05.2016
Rozmiar73.27 Kb.
WYKŁAD 7
1. Optymalizacja w sensie Pareto i optymalizacja wielokryterialna

Dotychczas przedstawione zagadnienia dotyczyły poszukiwania ekstremum jednej funkcji czyli optymalizacji jednego kryterium.

W zagadnieniach praktycznych bardzo często stajemy przed koniecznością uwzględniania większej liczby kryteriów zazwyczaj sprzecznych ze sobą .Dodatkowym utrudnieniem jest fakt, że kryteria te nie są wzajemnie przeliczalne zatem nie można ich sprowadzić do jednego kryterium skalarnego.

W takich warunkach rozsądnym podejściem jest poszukiwanie optymalnego kompromisu .

W odniesieniu do problemów wodno-gospodarczych uwzględnianie większej liczby kryteriów dotyczyć może np. takich zagadnień jak

A. faza projektowania zakładów uzdatniania wody (ZUW) ,

w której zakłada się ,że jakość wody uzyskana w wyniku uzdatniania wiąże się z koniecznością stosowania odpowiedniej ilości odczynników , zaawansowanych technologii wyspecjalizowanych urządzeń itp. tworzących łącznie funkcję jakości wody ,gdzie wektor stanowi zespół parametrów odpowiedzialnych za jakość wody po uzdatnieniu .

Z drugiej strony z uzyskaniem wyższej jakości wiążą się wyższe koszty tworzące przez wektor parametrów funkcję kosztów uzyskania wody o odpowiedniej jakości . Jak łatwo zauważyć obie funkcje stanowiące kryteria zadania optymalizacji wielokryterialnej są przeciwstawne .


B. faza projektowania stacji oczyszczania ścieków (OŚ),

dotyczy analogicznej sytuacji w procesie oczyszczania ścieków. Otrzymanie na wyjściu oczyszczalni, ścieków oczyszczonych spełniających określone parametry (funkcja określająca stopień oczyszczenie ścieków ) jest pochodną nakładów na zaawansowane procesy oczyszczania , odczynniki chemiczne itp. co z kolei podnosi koszty oczyszczania (funkcja kosztów oczyszczania ścieków.


C. rozważania dotyczące lokalizacji obiektów gospodarki wodnej , powiązane są zazwyczaj z wieloma kryteriami :

  • kryterium kosztów budowy ;

koszt budowy zbiornika retencyjnego rośnie z jego pojemnością użytkową i planowana pojemnością przeciwpowodziową ,

  • kryterium oceniające redukcję strat powodziowych uzyskanych w wyniku budowy zbiornika o odpowiedniej pojemności,

  • kryterium oceniające wpływ (oddziaływanie ) zbiornika na środowisko naturalne ( fauna , flora ) w obszarze budowy zbiornika ,

  • kryterium społeczno – ekonomiczne , mogące wskazywać na zmiany sytuacji ekonomicznej regionu w wyniku budowy zbiornika wynikającej z przychodów z rekreacji , ożywienia koniunktury gospodarczej regionu itp.

Przykłady tego typu można mnożyć , ich wspólna cechą jest fakt ,iż kryteria występujące w zadaniu optymalizacyjnym , są ze sobą sprzeczne tzn. dla wartości wektora parametrów następuje zwiększenie wartości jednej grupy kryteriów , a zmniejszenie wartości kryteriów z drugiej grupy.

Nie rezygnując z uogólnienia problemu w dalszej części mając na uwadze możliwość interpretacji graficznej przedstawiony zostanie problem dwukryterialny (np. problem oczyszczania ścieków) ,którego zrozumieniu pozwoli w dalszej kolejności na swobodne formułowanie i rozwiązywanie problemów wielokryterialnych .



2. Zbiór Pareto
Pojęcie kompromisu optymalnego wprowadzone zostało w 1896 r. przez ekonomistę Vilfreda Pareto który wprowadził współczynniki wagi odpowiadające kolejnym kryteriom . W ten sposób dokonał skalaryzacji problemu wielokryterialnego w której udział poszczególnych kryteriów wyrażony był przez ustalone wagi. Takie podejście nie rozwiązywało problemu wielokryterialnego , pozostawał bowiem problem właściwego doboru współczynników wag od którego uzależnione jest rozwiązanie.

W ogóle zasadniczym pytaniem jest, co to znaczy minimalizacja wielokryterialna ( minimalizacja wektora funkcji , minimalizacja wektorowa ).

Uogólniając zagadnienie optymalizacji jednokryterialnej tj. poszukiwania minimum funkcji kryterialnej względem wektora zmiennych decyzyjnych , w optymalizacji wielokryterialnej należałoby poszukiwać takiego wektora zmiennych decyzyjnych przy którym jednocześnie wszystkie funkcje kryterialne ( wektor funkcji kryterialnych ) osiągały by minimum . Taki wektor zmiennych decyzyjnych nazywany jest punktem utopijnym nadzwyczaj rzadko występującym w praktyce , zwykle bowiem każda z funkcji kryterialnych osiąga minimum przy innym wektorze zmiennych decyzyjnych .

Wybierając do dalszej prezentacji wariant oczyszczania ścieków, bierzemy pod uwagę stopień oczyszczenie ścieków oraz koszt minimalny oczyszczania w wyniku zastosowania odpowiednich urządzeń i odczynników. Przyjmiemy , że elementy te oceniane są w skali 1-10 . Było by idealnym rozwiązaniem gdyby ocena obu kryteriów była maksymalna tj.



  • maksymalne oczyszczenie ścieków 10 punktów

  • minimalny koszt oczyszczenia 10 punktów

Rys 1. Podział zbioru wariantów na zbiór wariantów zdominowanych i zbiór Pareto


Z pewnością nie jest uzasadnione wybieranie tych wariantów ( zbiór D,E,F,G,H,I) w porównaniu z którymi istnieją inne lepiej spełniające oba kryteria . Zbiór D,E,F,G,H,I nazywamy zbiorem zdominowanym . Po odjęciu ze zbioru rozwiązań dopuszczalnych zbioru zdominowanego otrzymamy zbiór wariantów tzw. nieulepszalnych tzn. takich w których nie można poprawić żadnego z kryteriów nie pogarszając pozostałych .Wzrost wartości powoduje spadek .Ten zbiór wariantów ( punkty A,B,C ) zwany jest zbiorem Pareto , a elementy ( warianty ) tego zbioru , są rozwiązaniami optymalnymi w sensie Pareto.

Dla rozpatrywanego przykładu ,zbiór Pareto zawiera zarówno warianty o :



  1. wysokim stopniu oczyszczenia ścieków przy wysokich kosztach oczyszczania (wariant C )

  2. niskim stopniu oczyszczenia ścieków przy niskich kosztach oczyszczania (wariant A)

  3. średnim stopniu oczyszczenia ścieków przy średnich kosztach uzdatniania (wariant B)

Dla przypadku wektora funkcji , do zbioru Pareto należeć będą takie elementy dla których nie ma możliwości poprawienia wartości kryterium bez konieczności pogorszenia wartości nawet jednego z pozostałych kryteriów.

Na tym tle widać , że metody optymalizacji wielokryterialnej powinny umożliwiać wybór wariantu ze zbioru Pareto zgodnie z preferencjami decydenta .

Rys.2 Przestrzeń parametrów i przestrzeń kryteriów
W przypadku bardziej ogólnym należy dokonać wyboru z pewnego zbioru wariantów charakteryzujących się pewnym zestawem cech. Niektóre z tych cech lub ich funkcje stanowią kryteria wyboru ,

-kryterium oczyszczenia ścieków ( funkcja określająca stopień oczyszczenia ścieków ) to np. : zawartość azotanów , fosforanów ,związków biogennych , mętność itp. .Można powiedzieć ,że oczyszczenie ścieków jest funkcją wymienionych parametrów () . Różne zestawy parametrów stanowią punkt w przestrzeni .

-kryterium kosztów oczyszczenia ścieków to : aparatura , technologia , odczynniki . Również w tym przypadku funkcja kosztów oczyszczenia ścieków uzależniona jest od przytoczonych parametrów ( ) .Różne zestawy parametrów stanowią punkt w przestrzeni .

Łącznie wektor parametrów uwzględnianych w funkcjach , jest punktem w przestrzeni parametrów ,której wymiar wynosi odpowiednio


Określając kryteria przenosimy problem z przestrzeni parametrów do przestrzeni kryteriów tzn. do układu w którym współrzędnymi elementów są wartości poszczególnych kryteriów ( rys 2 ). Warto zauważyć ,że elementy przestrzeni kryteriów różniące się parametrami ale o identycznych wartościach funkcji kryterialnych , są w przestrzeni kryteriów nierozróżnialne .
3. Optymalizacja wielokryterialna
Przyjmiemy w dalszej kolejności , że poszczególne kryteria mają zostać zminimalizowane ; wówczas zadanie optymalizacji z rysunku 2 przyjmie postać:
(1)

w której :



zmienna niezależna , wektor elementy którego należą do zbioru parametrów ( rys 2)

, funkcje kryterialne ,

funkcje ograniczeń,

ograniczenia na wartości zmiennych niezależnych

W przypadku bardziej rozbudowanym ( więcej niż dwa kryteria ) zadanie optymalizacji przyjmuje odpowiednio postać :



(2)

w której :



zmienna niezależna , wektor elementy którego należą do zbioru parametrów

( rys 2)


, ,..., funkcje kryterialne ,

funkcje ograniczeń,

ograniczenia na wartości zmiennych niezależnych .

Jeżeli poszczególne funkcje kryterialne konkurują ze sobą (tzn, przyjmują wartości ekstremalne dla różnych należących do rozłącznych zbiorów wartości ) , to zadanie nie ma jednoznacznego rozwiązania


Rys. 3 Przestrzeń kryteriów . Zbiór wariantów optymalnych w sensie Pareto


Zbiór Pareto ma czytelną interpretacje geometryczną , jest to fragment zbioru brzegu parametrów przedstawiony w przestrzeni kryteriów nie zasłonięty od strony minus nieskończoności przez inne elementy zbioru dla poszczególnych kryteriów.

Definicję zbioru Pareto można zapisać następująco :


(3)
Rozwiązaniem zadania optymalizacji wielokryterialnej może być każdy z punktów zbioru Pareto . Metody służące do rozwiązania zadań optymalizacji wielokryterialnej pozwalają najczęściej wybrać jeden z punktów zbioru Pareto na podstawie znajomości dodatkowych parametrów .
Powracając do optymalizacji dwóch funkcji kryterialnych z jakimi mamy do czynienia w przykładzie z oczyszczaniem ścieków , pierwszą czynnością jaka należy wykonać jest określenie zbioru Pareto dla przyjętego wektora parametrów .

Wektor parametrów określimy następująco :

gdzie reagenty wpływające na poziom azotanów w ściekach po

oczyszczeniu



reagenty wpływające na poziom fosforanów,

reagenty wpływające poziom zawiesiny,

sprzęt i technologia konieczna konieczne do właściwego oczyszczania ścieków
Przyjmując przybliżone zależności zmiany poziomu azotanów , fosforanów zawiesiny w funkcji odpowiednich odczynników chemicznych , addytywne kryterium oczyszczania ścieków można zapisać :
(4)
Analogicznie kryterium kosztów oczyszczania ścieków można na potrzeby przykładowego zadania optymalizacji wielokryterialnej przedstawić jako złożenie funkcji kosztów od poszczególnych elementów wektora parametrów ,
(.5)
Przebiegi poszczególnych składowych funkcji kryterialnych przedstawione są na rysunkach 4 i 5 a otrzymany w tych warunkach zbiór Pareto ma postać jak na rysunku 6:

Jak zauważono poprzednio rozwiązaniem zadania optymalizacji wielokryterialnej może być każdy z punktów zbioru Pareto . Wybór punktu będącego rozwiązaniem zadania zależy od decydenta i od metody zezwalającej wybór tego punktu .




  1. Metody wyboru punktu ze zbioru Pareto ( Zmiana funkcji celu)

Najbardziej prostą metodą rozwiązania zadania wielokryterialnego jest jego przekształcenie do standardowego zadania optymalizacji przez utworzenie funkcji celu będącej sumą ważoną wartości wskaźników :


(6)
Interpretacja graficzna tej metody to poszukiwanie stycznej do zbioru Pareto nachylonej pod kątem określonym przez współczynniki .

Wektor utworzony przez współczynniki jest prostopadły do poszukiwanej stycznej . Rozwiązaniem jest punkt wspólny ( punkty wspólne ) dla brzegu zbioru i stycznej .

Metoda sum ważonych oprócz ewidentnej zalety jaką jest jej prostota ma poważną wadę , ponieważ nie pozwala wybrać dowolnego punktu ze zbioru Pareto.

Punkty leżące w „zagłębieniach” nigdy nie zostaną osiągnięte ponieważ styczna nie ma możliwości dotarcia do nich pozostając na punktach dalej wysuniętych . Dla rozpatrywanego przykładu takimi punktami są punkty z przedziału miedzy rozwiązaniami ( rys 7) .


Rys 4 Składowe funkcji kryterialnej

Rys 5 Składowe funkcji kryterialnej

Rys 6 Zbiór Pareto dla funkcji ,


Rys 7 Wybór punktu ze zbioru Pareto metodą sum ważonych

.

5. Metody wyboru punktu ze zbioru Pareto (Metoda epsilon-ograniczeń)

Inną metodą zamiany zadania wielokryterialnego za standardowe zadanie optymalizacji jest metoda epsilon-ograniczeń .

U podstaw tej metody leży wybór jednej z funkcji kryterialnej jako funkcji celu i utworzenie ograniczeń z pozostałych funkcji kryterialnych.

Metodę tą można interpretować jako wybór kryterium najważniejszego przeznaczonego do optymalizacji przy założeniu że pozostałe kryteria spełniają pewne minimalne wymagania . Przekształcenie zadania wielokryterialnego metodą elipson ograniczeń przedstawia się następująco :

(7)

Jeżeli funkcję potraktujemy jako funkcje do optymalizacji , dla rozpatrywanego przykładu z utworzonym zbiorem Pareto (rys 6 ) rozwiązanie zależeć będzie od przyjęcia wartości dla funkcji ( minimalna satysfakcjonująca jakość wody ) . Wówczas minimalne koszty uzyskania takiej jakości wody są na poziomie . Zbiór rozwiązań dopuszczalnych ograniczony został od prawej strony wartością . (rys.8 )



Rys 8 Optymalizacja funkcji przy ograniczeniu .
Jeżeli funkcję potraktujemy jako funkcje do optymalizacji oraz ustalimy wówczas zbiór rozwiązań dopuszczalnych określony jest jak na rysunku 9

Rys 9 Optymalizacja funkcji przy ograniczeniu .


Wadą tej metody jest konieczność dokonania arbitralnego wyboru wartości ograniczeń aby możliwie dobrze spełnić oczekiwania podejmującego decyzję .Przy niewłaściwym doborze ograniczeń możliwe jest otrzymanie pustego zbioru rozwiązań dopuszczalnych . Sytuacje taką obserwujemy na rysunku 10 .

Rys. 10 Niewłaściwy dobór ograniczeń . Zbiór rozwiązań dopuszczalnych pusty



6. Metody wyboru punktu ze zbioru Pareto (Metoda programowania celowego)
Najbardziej zaawansowaną metodą rozwiązywania zadań wielokryterialnych jest metoda programowania celowego, która polega na zastąpieniu zadania wielokryterialnego zadaniem optymalizacji w postaci
(8)

w którym :



współrzędne wektora określającego cel poszukiwań,

współrzędne wektora określającego kierunek poszukiwań.
Przekształcenie o którym mowa prowadzi do poszukiwań punktu ze zbioru rozwiązań dopuszczalnych w którym wartości kryteriów są najbliższe pewnym idealnym ( często nieosiągalnym) wartością określonym przez współrzędne wektora . Przeszukiwana jest przestrzeń kryteriów rozpoczynając od punktu odpowiadającemu idealnym wartością kryteriów w kierunku określonym przez wektor współczynników o współrzędnych .

Wybór współrzędnych punktu stanowi formę określenia przez decydenta „satysfakcjonującego rozwiązania” , a dobór przez decydenta elementów wektora decyduje o stopniu ważności dla decydenta poszczególnych kryteriów .

Przez dowolny wybór punktu metoda programowania celowego pozwala osiągnąć każdy punkt ze zbioru Pareto oraz zapewnia dość naturalny sposób określenia parametrów , dzięki którym możliwe jest wybranie pojedynczego rozwiązania ze zbioru Pareto.

Interpretacja graficzna metody programowania celowego dla problemu dwukryterialnego jest bardzo prosta . Jeżeli współrzędne wektora odpowiadają satysfakcjonującemu rozwiązaniu a współczynnik kierunkowy prostej wynika z przyjętych współczynników wektora , ( ) , wówczas równanie prostej przechodzącej przez punkt o współczynniku kierunkowym ma postać :



(9)
Rozwiązaniem zadania jest punkt wspólny prostej i zbioru Pareto którą to zależność można zapisać następująco :

(10)
Ilustracja wyboru punktu ze zbioru Pareto metoda programowania celowego przedstawiona jest na rysunku 11

Rys. 11 Wybór punktu ze zbioru Pareto metodą programowania celowego .



7. Metody wyboru punktu ze zbioru Pareto (Metoda szkieletu)

Bardzo interesującą a zarazem przystępną metodę postępowania dotyczącą wyboru punktu ze zbioru Pareto przedstawił H. Górecki w książce „Optymalizacja systemów dynamicznych”. Metoda szkieletu opiera się na kilku istotnych definicjach i określeniach , które zacytuję za autorem , dostosowując je jednocześnie do analizowanych wcześniej przykładów liczbowych.

W pierwszej kolejności należy wprowadzić definicję zbioru żądanego

Definicja 1 Zbiór żądany to iloczyn kartezjański przedziałów domkniętych i ograniczonych
(11)
gdzie: są odpowiednio dolnym i górnym poziomem aspiracji, czyli dolną i górną wartością kryteriów jakości zaakceptowanych przez decydenta.

Wykorzystując rysunek 8.11 przyjmiemy np. że



najniższy akceptowalny poziom ścieków oczyszczonych,

najwyższy (wystarczający )poziom ścieków oczyszczonych,

najniższe poniesione koszty związane z oczyszczeniem ścieków,

najwyższe możliwe do poniesienia koszty związane z oczyszczeniem ścieków.

Rys. 12 Zbiór żądany na płaszczyźnie kryteriów



Definicja 2 Brzeg zbioru

(12)
gdzie : , wnętrze zbioru

Dla zbioru żądanego przedstawionego na rys. 12, brzeg zbioru to odcinki AB , BC , CD , DA



Definicja 3 Szkielet jest podzbiorem zbioru i stanowi zbiór punktów o następujących właściwościach :


  1. Punkty szkieletu są lokalnie równo oddalone od brzegu zbioru . Zależność tę można formalnie zapisać w postaci:

(13)
Dla zbioru żądanego z rys.12 zależność ta przedstawia się następująco



(14)
Interpretacja tego groźnie wyglądającego zapisu jest stosunkowo prosta. Odległość punktów szkieletu (względem kolejnych kryteriów i względem przyjętej normy) od brzegu zbioru żądanego ma być jednakowa i najmniejsza z możliwych.


2. Punkty szkieletu określają linię łamaną , której punkty początkowy i końcowy mają odpowiednio współrzędne . Dla przykładu z rysunku 12 .
Definicja 4 Konstrukcja szkieletu.

Aby dokładnie omówić konstrukcje szkieletu należy umiejscowić go w przestrzeni co najmniej trójwymiarowej . Rozważania te będą słuszne dla przestrzeni wyższych rzędów , natomiast zawężenie na wstępie problematyki do przestrzeni dwuwymiarowej , pozbawia wskazówek dotyczących istotnego faktu jakim jest budowa szkieletu przy zmniejszającej się z każdym krokiem postępowania wymiarowości problemu.


Przyjmiemy przestrzeń trójwymiarową . Jak wynika z definicji 1 , zbiór żądany jest iloczynem kartezjańskim dolnych i górnych wymagań w każdym z kierunków przestrzeni.
(15)
o wierzchołkach określonych przez :

(16)
Zgodnie z definicją 4 znajdujemy współrzędne pozostałych punktów szkieletu,

(17)
Określimy następującą formułą :

(18)
Punkty lokalne równo oddalone od brzegów tworzą linie łamaną zaczynającą się w i dochodzą do punktu . Segment jest przekątną sześcianu , której długość równa jest :

w szczególności dla przestrzeni , (19)
Przyjmujemy kierunek w przestrzeni kryteriów i oznaczymy

Punkt znajdujemy podobnie z warunku:

, w szczególności dla przestrzeni (20)

Za każdym krokiem eliminujemy w ten sposób jeden wymiar przestrzeni i przechodzimy kolejno do przestrzeni o jeden wymiar mniejszy.

Szkielet składa się z segmentów tworzących linie łamaną łączącą dwa punkty na antypodach żądanego zbioru w wymiarowej przestrzeni.

Dla przestrzeni antypody to punkty .




Rys. 13. Zbiór szkieletów w przestrzeni 3-wymiarowej
Teraz widać dlaczego rozważania w przestrzeni dwuwymiarowej nie pokazują redukcji wymiaru przestrzeni zbioru żądanego .

Na podstawie definicji i konstrukcji szkieletu możemy sformułować jego następujące właściwości :



  1. współrzędne dowolnego punktu należącego do szkieletu zależą tylko od współrzędnych i przyrostów . Decydent nie potrzebuje żadnej innej informacji która by zmuszała go do określania preferencji w przestrzeni kryteriów dla danego problemu,

  2. szkielet jest zbiorem uporządkowanym w przestrzeni kryteriów składających się z punktów , takich że jeśli

(21)


to co najmniej dla jednego z nich nierówność (21) jest mocna .

c) biorąc pod uwagę założone (lecz zwykle niepewne ) dolną i górną aproksymację kryteriów , wprowadzamy dodatkowe kryterium—preferencję opartą na właściwości szkieletu , mianowicie ze jest równo oddalony od biegów zbioru żądanego.

Te ostatnią własność można nazwać preferencją opartą o „zasadę bezpieczeństwa”, która mówi ze w zbiorze rozwiązań kompromisów optymalnych, najbardziej bezpieczne z punktu widzenia sperturbowanego brzegu zbioru żądanego , jest rozwiązanie leżące na szkielecie .

Szkielet w przestrzeni dwuwymiarowej np. dla przykładu z rys. 12 przedstawia się następująco :


Rys. 14. Konstrukcja szkieletu w przestrzeni


Definicja 5 Obliczanie najlepszego rozwiązania kompromisowego w przestrzeni kryteriów

Idea szukania najlepszego rozwiązania jest oparta o następującą koncepcję optymalności : Punkt jest najbardziej bezpiecznym rozwiązaniem optymalno-kompromisowym w sensie metody szkieletu , jeżeli decyzja jest Pareto-optymalna a punkt należy do szkieletu.

Tak więc punkt przecięcia dwu zbiorów :


  • zbioru optymalnych kompromisów (zbiór Patero, )

  • szkieletu

daje najlepsze bezpieczne rozwiązanie

Na kolejnych rysunkach pokazano możliwe wzajemne usytuowanie zbioru Pareto i szkieletu



Rys 15 Przecięcie zbioru Pareto i szkieletu . Najbezpieczniejsze rozwiązanie dla przyjętego zbioru żądanego .


Rys 16 Przecięcie zbioru Pareto i szkieletu . Najbezpieczniejsze rozwiązanie dla przyjętego zbioru żądanego .



Może się zdarzyć że szkielet nie ma wspólnego punku ze zbiorem żądanym. Wówczas najbezpieczniejszym rozwiązanie w sensie szkieletu jest punkt, należący do brzegu zbioru żądanego i najbliższy brzegowi Pareto . Sytuacje taką obserwujemy na rysunku 17


Rys 17 Brak wspólnego punku Zbioru żądanego i zbioru Pareto. Wyznaczenie najbezpieczniejszego rozwiązania w sensie szkieletu .




©absta.pl 2019
wyślij wiadomość

    Strona główna