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.