Technika optymalizacji
1
Nieliniowe zadanie optymalizacji
statycznej z ograniczeniami -
nieliniowe algorytmy optymalizacji
Wykład 11
dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek: Elektronika i Telekomunikacja III r.
Potok: Elektronika
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Sformułowanie zadania optymalizacji nieliniowej
z ograniczeniami PN :
.
:
)
(
oraz
:
)
(
},
,...,
1
,
0
)
(
:
{
:
gdzie
),
(
min
)
ˆ
(
1
1
R
R
X
x
g
R
R
X
x
f
m
i
g
X
f
f
n
i
n
i
X
→
=
→
=
=
≤
=
=
∈
x
x
x
x
x
Znaleźć
takie, Ŝe:
∧
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Przykład nieliniowego zadania optymalizacji bez ograniczeń
Funkcja wypukła
2
1
2
2
2
1
2
1
*
5
.
0
)
(
min
x
x
x
x
x
x
x
f
X
x
−
−
−
+
=
∈
-5
-4
-3
-2
-1
0
1
2
3
4
5
-5
-4
-3
-2
-1
0
1
2
3
4
5
Minimum globalne
−
+
−
+
=
∇
1
1
2
)
(
2
1
2
1
x
x
x
x
x
f
=
1
1
1
2
H
Hesjan jest ścisle dodatnio określony, a zatem funkcja f(x) ma jedno i tylko jedno minimum globalne
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Przykład nieliniowego zadania optymalizacji bez ograniczeń
-5
-4
-3
-2
-1
0
1
2
3
4
5
-5
-4
-3
-2
-1
0
1
2
3
4
5
200
)
7
(
)
11
(
)
(
min
2
2
2
1
2
2
2
1
−
−
+
+
−
+
=
∈
x
x
x
x
x
f
X
x
Funkcja Himmelblau’a
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
2
2
1
2
3
2
1
2
1
)
(
10
)
(
4
)
(
2
)
(
min
x
x
x
x
x
x
x
f
X
x
+
−
+
=
∈
)}.
2
,
1
,
3
3
(
0
2
/
3
3
)
4
.
2
(
)
(
|
)
,
{(
2
1
2
2
2
1
2
1
=
≤
≤
−
∧
≥
+
∧
≤
+
=
i
x
x
x
x
x
x
x
x
X
i
Przykład nieliniowego zadania optymalizacji z ograniczeniami
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Ilustracja graficzna zadania optymalizacji z ograniczeniami
Technika optymalizacji
2
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Funkcja Lagrange’a
DEFINICJA.
Funkcją Lagrange’a zadania PN nazywamy skalarną
funkcję
gdzie
jest wektorem mnoŜników Lagrange’a.
,
)
(
,
)
(
)
(
x
λ
x
λ
x,
g
f
L
+
=
m
R
∈
λ
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Algorytmy optymalizacji z ograniczeniami
Przykłady transformacji zmiennych dla
typowych ograniczeń:
1.
2.
3.
0
≥
i
x
( )
i
i
i
i
i
i
u
x
u
x
u
x
=
=
=
exp
2
1
0
≤
≤
i
x
W celu uwzględnienia ograniczeń moŜna postąpić w poniŜszy sposób:
• dokonać transformacji zmiennych decyzyjnych
• dokonać transformacji funkcji celu wprowadzając funkcje kary.
)
exp(
)
exp(
)
exp(
sin
2
i
i
i
i
i
i
u
u
u
x
u
x
−
+
=
=
i
i
i
b
x
a
≤
≤
(
)
)
(
sin
2
i
i
i
i
i
u
a
b
a
x
−
+
=
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Algorytmy optymalizacji z ograniczeniami cd.
)
)
(
(
)
)
(
(
)
(
)
,
,
(
1
i
i
i
i
m
i
i
x
g
H
x
g
x
f
x
P
θ
θ
ϕ
σ
θ
σ
+
+
+
=
∑
=
]
,...,
,
[
,
0
2
1
m
i
σ
σ
σ
σ
σ
=
>
]
,...,
,
[
,
0
2
1
m
i
θ
θ
θ
θ
θ
=
>
Transformacja funkcji kryterialnej – funkcja Lagrange’a:
Funkcja kary charakteryzuje się tym, Ŝe w zbiorze rozwiązań dopuszczalnych
X przyjmuje wartość równą zeru lub bliską zeru, a poza tym obszarem
przyjmuje bardzo duŜe wartości.
Gdzie: jest wektorem współczynników kary
jest wektorem przesunięć kary
φ( ) funkcja kary
)
)
(
(
lub
)
)
(
(
.
:
)
)
(
(
1
2
i
i
i
i
i
i
x
g
x
g
np
x
g
θ
θ
θ
ϕ
+
−
+
+
−
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Algorytmy optymalizacji z ograniczeniami cd.
Funkcja H ma poniŜszą własność:
≤
+
>
+
=
+
0
)
(
0
0
)
(
1
)
)
(
(
i
i
i
i
i
i
x
g
dla
x
g
dla
x
g
H
θ
θ
θ
1.
Metody zewnętrznej funkcji kary (metoda Couranta, metoda
Schmita i Foxa)
2.
Metody wewnętrznej funkcji kary (metoda Rosenbrocka,
metoda Carolla)
3.
Metody przesuwanej funkcji kary (metoda Powella).
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Metody przesuwanej funkcji kary (metoda Powella).
)
)
(
(
)
)
(
(
)
(
)
,
,
(
1
i
i
i
i
m
i
i
x
g
H
x
g
x
f
x
P
θ
θ
ϕ
σ
θ
σ
+
+
+
=
∑
=
2
)
)
(
(
)
)
(
(
i
i
i
i
x
g
x
g
θ
θ
ϕ
+
=
+
≤
+
>
+
=
+
0
)
(
0
0
)
(
1
)
)
(
(
i
i
i
i
i
i
x
g
dla
x
g
dla
x
g
H
θ
θ
θ
Transformacja funkcji kryterialnej:
dla
Przykład
{
}
5
.
0
:
2
1
≤
+
=
x
x
x
X
2
2
2
1
)
1
(
)
2
(
)
(
min
−
+
−
=
∈
x
x
x
f
X
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Sformułowanie zadania optymalizacji nieliniowej PN
z ograniczeniami dodatkowo na zmienne decyzyjne x :
m
i
R
R
x
g
R
R
x
f
m
i
g
X
f
f
n
i
n
i
X
,...,
1
,
:
)
(
oraz
:
)
(
},
,...,
1
,
0
,
0
)
(
:
{
:
gdzie
),
(
min
)
ˆ
(
1
1
=
→
→
=
≥
≤
=
=
∈
x
x
x
x
x
x
.
)
(
)
(
)
(
1
∑
=
+
=
m
i
i
i
g
f
L
x
x
λ
x,
λ
Technika optymalizacji
3
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Ciekawe wizualizacje ciągłych funkcji uni i wielomodalnych
Funkcja De Jong’a
Na podstawie www.geatbx.com/download/GEATbx_ObjFunExpl_v37.pdf
Global minimum:
f(x)=0; x
i
=0, i=1,…,n.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Funkcja Rosenbrock’a
Na podstawie www.geatbx.com/download/GEATbx_ObjFunExpl_v37.pdf
n
i
dla
x
x
x
x
f
i
i
n
i
i
,...,
1
)
1
(
)
(
100
)
(
2
2
2
1
1
1
=
−
+
−
=
∑
−
=
+
Ciekawe wizualizacje ciągłych funkcji uni i wielomodalnych
Global minimum:
f(x)=0; x
i
=1, i=1,…,n.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Ciekawe wizualizacje ciągłych funkcji uni i wielomodalnych
Funkcja Rastrigin’a
Na podstawie www.geatbx.com/download/GEATbx_ObjFunExpl_v37.pdf
n
i
dla
x
x
n
x
f
i
n
i
i
,...,
1
))
*
2
cos(
*
10
(
*
10
)
(
1
2
=
−
+
=
∑
=
π
Global minimum:
f(x)=0; x
i
=0, i=1,…,n.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Ciekawe wizualizacje ciągłych funkcji uni i wielomodalnych
Funkcja Ackley’a
Na podstawie www.geatbx.com/download/GEATbx_ObjFunExpl_v37.pdf
π
⋅
=
=
=
=
+
+
∑
−
∑
⋅
−
=
=
=
⋅
−
2
;
2
.
0
;
20
,...,
1
)
(
1
)
cos(
1
1
2
c
b
a
n
i
dla
e
a
e
e
a
x
f
n
x
c
n
x
b
n
i
i
n
i
i
Global minimum:
f(x)=0; x
i
=0, i=1,…,n.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Funkcja Michalewicza
Na podstawie www.geatbx.com/download/GEATbx_ObjFunExpl_v37.pdf
Ciekawe wizualizacje ciągłych funkcji uni i wielomodalnych
π
π
≤
≤
=
=
⋅
⋅
−
=
⋅
i
m
i
i
x
m
n
i
dla
x
i
x
x
f
0
10
;
,...,
1
))
(sin(
)
sin(
)
(
2
2
Global minimum:
f(x)=0; x
i
=0, i=1,…,n.