I. Metoda programowania nieliniowego PNL.

Celem ćwiczenia jest zapoznanie się z podstawową metodą rozwiązywania nieliniowego zadania optymalizacji z ograniczeniami na przykładzie algorytmu optymalizacji lokalnej z ograniczeniami lub algorytmu genetycznego z ograniczeniami.

Algorytm optymalizacji lokalnej lub algorytm optymalizacji globalnej (algorytm genetyczny) z ograniczeniami pozwala na wyliczenie takiego wektora zmiennych decyzyjnych x, dla którego funkcja celu osiąga minimum :

Przy ograniczeniach:

--> Wstęp teoretyczny (na postawie informacji zawartych na stronie: http://pl.wikipedia.org)[Author:M]

Algorytm genetyczny to rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Sposób działania algorytmów genetycznych nieprzypadkowo przypomina zjawisko ewolucji biologicznej, ponieważ ich twórca John Henry Holland właśnie z biologii czerpał inspiracje do swoich prac.

Najczęściej działanie algorytmu przebiega następująco:

1. Losowana jest pewna populacja początkowa.

2. Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą udział w procesie reprodukcji.

3. Genotypy wybranych osobników poddawane są operatorom ewolucyjnym:

1. są sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie),

2. przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.

4. Rodzi się drugie (kolejne) pokolenie i algorytm powraca do kroku drugiego, jeżeli nie znaleziono dostatecznie dobrego rozwiązania. W przeciwnym wypadku uzyskujemy wynik.

Działanie algorytmu genetycznego obejmuje kilka zagadnień potrzebnych do ustalenia:

1. ustalenie genomu jako reprezentanta wyniku

2. ustalenie funkcji przystosowania/dopasowania

3. ustalenie operatorów przeszukiwania

II. Zadania do wykonania

1. f(x) = (x₁ - 2)² + (x₂ - 2)²

Punkt optymalny: x* = [2, 2]

Wartość optymalna funkcji: f(x*) = 0

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-5, 5]

x₂ = [-5, 5]

Wizualizacja rozwiązania bez ograniczeń:

1. ograniczenie nieaktywne

Ograniczenie: x₁ + x₂ < 6

Punkt optymalny: x* = [2, 2]

Wartość optymalna funkcji: f(x*) = 0

Wizualizacja rozwiązania z ograniczeniem:

2. ograniczenie aktywne

Ograniczenie: x₁ + x₂ < 2

Punkt optymalny: x* = [0.937, 1.055] x* = [1, 1]

Wartość optymalna funkcji: f(x*) = 2.023 f(x*) = 2

-5 : 5 -2:2

--> Wizualizacja rozwiązania z ograniczeniem:[Author:M]

2. f(x) = 2x₁² - 2x₁x₂ + x₂²

Punkt optymalny: x* = [0, 0]

Wartość optymalna funkcji: f(x*) = 0

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-2, 2]

x₂ = [-2, 2]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie nieaktywne

Ograniczenie: 4x₁ + 3x₂ < 12

Punkt optymalny: x* = [0, 0]

Wartość optymalna funkcji: f(x*) = 0

Wizualizacja rozwiązania z ograniczeniem:

2. ograniczenie aktywne

Ograniczenie: - x₁ - 2x₂ < - 4

Punkt optymalny: x* = [1, 1.5] x* = [0.904, 1.548]

Wartość optymalna funkcji: f(x*) = 1.25 f(x*) = 1.232

-2 : 2 0 : 2

Wizualizacja rozwiązania z ograniczeniem:

3. f(x) = x₁² + x₁x₂ + 0.5x₂² - x₁ - x₂

Punkt optymalny: x* = [0, 1]

Wartość optymalna funkcji: f(x*) = -0.5

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-2, 2]

x₂ = [-2, 2]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie nieaktywne

Ograniczenie: - 2x₁ + 3x₂ < 6

Punkt optymalny: x* = [0, 1]

Wartość optymalna funkcji: f(x*) = - 0.5

Wizualizacja rozwiązania z ograniczeniem:

b) ograniczenie aktywne

Ograniczenie: x₁ < - 1

Punkt optymalny: x* = [-1, 2] x* = [-1, 2]

Wartość optymalna funkcji: f(x*) = 0 f(x*) = 0

-2 : 2 -2:0, 1:3

Wizualizacja rozwiązania z ograniczeniem:

4. Funkcja Engwall'a f(x) = x₁⁴ + x₂⁴ - 2x₁²x₂ - 4x₁ + 3

Punkt optymalny: x* = [1,309, 0,949]

Wartość optymalna funkcji: f(x*) = -1,74109

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-2, 2]

x₂ = [-2, 2]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie nieaktywne

Ograniczenie: 3x₁ + 4x₂ < 12

Punkt optymalny: x* = [1.31, 0.94]

Wartość optymalna funkcji: f(x*) = - 1.74

Wizualizacja rozwiązania z ograniczeniem:

b) ograniczenie aktywne

Ograniczenie: x₁ + x₂ < 1

Punkt optymalny: x* = [1, 0] x* = [1, 0 ]

Wartość optymalna funkcji: f(x*) = 0 f(x*) = 0

-2:2 0:2, -1:1

Wizualizacja rozwiązania z ograniczeniem:

5. Zmodyfikowana funkcja Himmelblau'a f(x) = (x₁² + x₂ - 11)² + (x₁ + x₂² - 7)² - 200

Punkty optymalne: Cztery identycznej wartości minima lokalne

Wartość optymalna funkcji: f(x*) = -200

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-5, 5]

x₂ = [-5, 5]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie nieaktywne

Ograniczenie: x₁² + x₂² < 25

Punkty optymalne: x₁* = [3, 2] x₂* = [-3.78, -3.28] x₃* = [-2.81, 3.13] x₄* = [3.58, -1.85]

Wartość optymalna funkcji: f(x*) = - 200

Wizualizacja rozwiązania z ograniczeniem:

b) ograniczenie aktywne

Ograniczenie: x₁² + x₂² < 1

Punkt optymalny: x* = [0.82, 0.57] x* = [0.78, 0.62]

Wartość optymalna funkcji: f(x*) = - 70.57 f(x*) = -70.65

-5:5 -1:1

Wizualizacja rozwiązania z ograniczeniem:

--> 6. f(x) = (x₁ - 2)² + (x₂ - 1)²[Author:M]

Punkt optymalny: x* = [2, 1]

Wartość optymalna funkcji: f(x*) = 0

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-2, 4]

x₂ = [-2, 4]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie aktywne

Ograniczenia: x₁² - x₂ < 0

x₁ + x₂ < 2

Punkt optymalny: x₁* = [1, 1] x* = [1, 1]

Wartość optymalna funkcji: f(x*) = 1 f(x*) = 1

Wizualizacja rozwiązania z ograniczeniem:

-2:4 -2:2, 0:2

7. f(x) = (x₁ - 1)² + (x₂ - 5)²

Punkt optymalny: x* = [1, 5]

Wartość optymalna funkcji: f(x*) = 0

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-2, 4]

x₂ = [2, 8]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie aktywne

Ograniczenia: x₁² - x₂ < 0

x₁ + x₂ < 2

Punkt optymalny: x₁* = [-1.127, 3.079] x* = [-1, 3]

Wartość optymalna funkcji: f(x*) = 8.216 f(x*) = 8

Wizualizacja rozwiązania z ograniczeniem:

-2:4 -2:2, 0:4

7. f(x) = (x₁ + 3)² + (x₂ - 1)²

Punkt optymalny: x* = [-3, 1]

Wartość optymalna funkcji: f(x*) = 0

Część programowa:

Ogólne założenia

Populacja początkowa: 40 osobników

Wybór początkowej populacji: losowy

Krzyżowanie: 60%

Mutacja: 12%

Kryterium stopu: brak postępu

Zakres zmiennych: x₁ = [-5, -1]

x₂ = [-1, 3]

Wizualizacja rozwiązania bez ograniczeń:

a) ograniczenie aktywne

Ograniczenia: x₁² - x₂ < 0

x₁ + x₂ < 2

Punkt optymalny: x₁* = [-1.27, 1.62] x* = [-1.25, 1.56]

Wartość optymalna funkcji: f(x*) = 3.378 f(x*) = 3.379

Wizualizacja rozwiązania z ograniczeniem:

-5:-1, -1:3 -2:0, 1:3

III. Wnioski

Efektywność i dokładność obliczeniowa algorytmu genetycznego zależy głównie od prawidłowego doboru zakresu wartości zmiennych oraz w przypadku programowania nieliniowego z ograniczeniami właściwego doboru ograniczeń. Nieprawidłowy dobór obszaru z ograniczeniami nieaktywnymi (λ < 0) i bez ograniczeń (λ = 0) powoduje błędne wskazania wartości optymalnej. W przypadku zbyt dużego obszaru algorytm może idealnie nie trafić w punkt optymalny, zbyt mały obszar powoduje nie znalezienie optymalnego rozwiązania (punkt optymalny będzie znajdował się na brzegach badanego obszaru). W przypadku zadania z ograniczeniami dobór obszaru jest równie ważny, nie musimy jednak obejmować całego obszaru funkcji, wystarczy tylko aby ograniczony obszar poszukiwań w wybranych przedziałach się znajdował. Najlepiej dobrać jak najmniejszy możliwy obszar, mamy wtedy większe prawdopodobieństwo na znalezienie optimum warunkowego.

Kolejnym istotnym problemem jest dobór algorytmu selekcji, ponieważ od nich zależy dokładność odszukanego optimum. Jednak w wybranym programie nie mieliśmy możliwości wyboru algorytmu selekcji.

Ważnym parametrem jest rozmiar populacji. W zadaniach opracowywanych w tym ćwiczeniu optymalna liczba osobników w populacji powinna mieścić się w granicach 30 - 50. Na szybkość i efektywność algorytmu genetycznego poza algorytmem selekcji ma wpływ jakość osobników w początkowej populacji. A więc dobre losowanie (w przypadku zastosowania takiej metody wyboru początkowej populacji) ma bardzo duży wpływ na osiągnięcie optymalnego rozwiązania.

Decydujący wpływ na końcowe rozwiązanie ma kryterium stopu, czyli warunek decydujący o zatrzymaniu pracy algorytmu. Zdecydowanie najlepszym wyborem (naszym zdaniem) jest kryterium na brak postępu, ponieważ w miarę szybko znajduje optymalne rozwiązanie. W przypadku wyboru kryterium na liczbę generacji musimy orientować się jak dobrać tą liczbę. Zbyt mała liczba spowoduje, że algorytm nie dojdzie do rozwiązania optymalnego, natomiast zbyt duża liczba znacznie wydłuży czas wyszukiwania optimum.

Głównym zadaniem tego ćwiczenia był odpowiedni dobór ograniczeń, aby uzyskać ograniczenia aktywne (przesuwające punkt optymalny funkcji celu) i nieaktywne (nie mające wpływy na wartość optymalną funkcji celu). Po przeanalizowaniu wybranych funkcji i ograniczeń stwierdziliśmy, że ćwiczenie zostało wykonane poprawie, potwierdziła to również analiza analityczna (załącznik: przykładowe obliczenia).

Laboratorium	Technika optymalizacji
Autorzy: Dawid Tomasz (140517) Garbicz Marcin (140547) Kier.: EiT Spec.: ESA	Wrocław, dnia 13.11.2006 Prowadzący: Dr inż. Ewa Szlachcic
Ćwiczenie V Zadanie programowania nieliniowego z ograniczeniami	Algorytmy optymalizacji lokalnej i algorytmy optymalizacji globalnej

12

Napisać zdecydowanie ambitniejszy wstęp + opisać ogólnie wpływ ograniczeń.

Komentarz do wszystkich wizualizacji!!!

Podpisać obrazki (dla jakich zakresów zmiennych widoczna wizualizacja) - u nas ręcznie to było zrobione.

Poniżej dodatkowe OBOWIĄZKOWE zadania z zajęć wymyślone przez prowadzącą .

---