4. OSIĄGANIE CELU POPRZEZ

4. OSIĄGANIE CELU POPRZEZ

POSZUKIWANIA INFORMOWANE

POSZUKIWANIA INFORMOWANE

© F.A. Dul 2007

Poszukiwania informowane

Poka

ż

emy, w jaki sposób agent mo

ż

e

Poka

ż

emy, w jaki sposób agent mo

ż

e

osi

ą

gn

ąć

zamierzony cel du

ż

o bardziej

osi

ą

gn

ąć

zamierzony cel du

ż

o bardziej

efektywnie poprzez poszukiwania
wykorzystuj

ą

ce dodatkow

ą

wiedz

ę

wykorzystuj

ą

ce dodatkow

ą

wiedz

ę

na temat zadania.

© F.A. Dul 2007

Niniejszy rozdział po

ś

wi

ę

cony jest agentom celowym,

Wprowadzenie

Niniejszy rozdział po

ś

wi

ę

cony jest agentom celowym,

których działanie oparte jest na poszukiwaniu rozwi

ą

zania

w zbiorze rozwi

ą

za

ń

dopuszczalnych.

w zbiorze rozwi

ą

za

ń

dopuszczalnych.

Poszukiwanie informowane (informed search) polega na
znajdywaniu rozwi

ą

zania zadania przy wykorzystaniu innej

znajdywaniu rozwi

ą

zania zadania przy wykorzystaniu innej

dost

ę

pnej wiedzy, specyficznej dla tego zadania.

© F.A. Dul 2007

Wprowadzenie

Plan rozdziału

• Algorytm „best-first”.
• Algorytm agresywny „greedy best-first”.
• Algorytm A*

• Algorytm A*
• Heurystyki
• Algorytmy poszukiwa

ń

lokalnych

• Algorytmy poszukiwa

ń

lokalnych

• Algorytm „hill-climbing”
• Algorytm symulowanego wy

ż

arzania

• Algorytm symulowanego wy

ż

arzania

• Algorytm „local beam”
• Algorytmy genetyczne

© F.A. Dul 2007

4.1. Poszukiwania informowane

Poszukiwania nieinformowane stanowi

ą

form

ę

rozwi

ą

zywania

zadania “na o

ś

lep”.

Podstawowym algorytmem strategii nieinformowanych był
algorytm przeszukiwania drzewa - niezbyt efektywny.

Istotn

ą

popraw

ę

efektywno

ś

ci mo

ż

na uzyska

ć

wykorzystuj

ą

c

dodatkow

ą

informacj

ę

o zadaniu.

dodatkow

ą

informacj

ę

o zadaniu.

Strategie poszukiwania wykorzystuj

ą

ce dodatkowe

informacje o zadaniu nazywa si

ę

(po)informowanymi.

Idea: dodatkowa iInformacja mo

ż

e posłu

ż

y

ć

do

najkorzystniej-

informacje o zadaniu nazywa si

ę

(po)informowanymi.

Idea: dodatkowa iInformacja mo

ż

e posłu

ż

y

ć

do

najkorzystniej-

szego uporz

ą

dkowania w

ę

złów przed ich rozwini

ę

ciem

.

© F.A. Dul 2007

4.1. Poszukiwania informowane

Poszukiwanie informowane

Zasada poszukiwania informowanego:

– wybór w

ę

zła do rozwini

ę

cia uzale

ż

nia si

ę

od funkcji szacuj

ą

cej f(n)

Idea: funkcja szacuj

ą

ca ocenia koszt osi

ą

gni

ę

cia celu

– wybiera si

ę

w

ę

zeł który jest najlepszy ( wg. funkcji szacuj

ą

cj)

Implementacja: brzeg drzewa jest list

ą

uporz

ą

dkowan

ą

malej

ą

co według warto

ś

ci funkcji szacuj

ą

cej odległo

ść

od

Zasad

ę

powy

ż

sz

ą

realizuj

ą

algorytmy:

malej

ą

co według warto

ś

ci funkcji szacuj

ą

cej odległo

ść

od

celu.

• najpierw najlepszy „best-first”.
• najpierw najlepszy agresywny „greedy best-first”.

Zasad

ę

powy

ż

sz

ą

realizuj

ą

algorytmy:

• najpierw najlepszy agresywny „greedy best-first”.
•

algorytm A*

© F.A. Dul 2007

4.1. Poszukiwania informowane

Poszukiwanie informowane

Zasada poszukiwania informowanego:

– wybór w

ę

zła do rozwini

ę

cia uzale

ż

nia si

ę

od funkcji szacuj

ą

cej f(n)

Idea: funkcja szacuj

ą

ca ocenia koszt osi

ą

gni

ę

cia celu

Idea: funkcja szacuj

ą

ca ocenia koszt osi

ą

gni

ę

cia celu

– wybiera si

ę

w

ę

zeł który jest najlepszy ( wg. funkcji szacuj

ą

cj)

Implementacja: brzeg drzewa jest list

ą

uporz

ą

dkowan

ą

Zasad

ę

powy

ż

sz

ą

realizuj

ą

algorytmy:

Implementacja: brzeg drzewa jest list

ą

uporz

ą

dkowan

ą

malej

ą

co według warto

ś

ci funkcji szacuj

ą

cej f(n).

• najpierw najlepszy „best-first”.
• agresywny najpierw najlepszy „greedy best-first”.

Zasad

ę

powy

ż

sz

ą

realizuj

ą

algorytmy:

• algorytm A*

Funkcje szacuj

ą

ce definiuje si

ę

zwykle w oparciu

o odpowiedni

ą

heurez

ę

.

o odpowiedni

ą

heurez

ę

.

© F.A. Dul 2007

Algorytm „greedy best-first”

4.1. Poszukiwania informowane

Algorytm agresywny “najpierw najlepszy” (greedy best-first)

Algorytm agresywny “najpierw najlepszy” (greedy best-first)

- rozwija si

ę

w

ę

zeł który le

ż

y najbli

ż

ej celu.

Funkcja szacuj

ą

ca

f(n) = h(n)

(

h

eurystyczna)

h(n) - oszacowanie kosztu z n do celu.

Funkcja h(n) nie jest cz

ęś

ci

ą

oryginalnego sformułowania

Funkcja h(n) nie jest cz

ęś

ci

ą

oryginalnego sformułowania

zadania!

Funkcja h(n) musi by

ć

okre

ś

lona na podstawie informacji

Funkcja h(n) musi by

ć

okre

ś

lona na podstawie informacji

dodatkowych; najcz

ęś

ciej heurystycznych.

© F.A. Dul 2007

Przykład - poszukiwanie najkrótszej drogi

4.1. Poszukiwania informowane

Odległo

ść

do

Bukaresztu w linii

prostej

h(n) = oszacowanie kosztu z n do celu - Bukaresztu,

np. oszacowanie odległo

ś

ci w linii prostej z n do Bukaresztu

© F.A. Dul 2007

np. oszacowanie odległo

ś

ci w linii prostej z n do Bukaresztu

4.1. Poszukiwania informowane

Przykład - poszukiwanie najkrótszej drogi

Cel został osi

ą

gni

ę

ty!

Rozwi

ą

zanie nie jest jednak optymalne -

© F.A. Dul 2007

Rozwi

ą

zanie nie jest jednak optymalne -

por. {Arad, Sibiu, Rimnicu Vilcea, Pitesti}

4.1. Poszukiwania informowane

Własno

ś

ci algorytmu „greedy best-first”

• Zupełno

ść

Nie, mog

ą

powsta

ć

zap

ę

tlenia,

np. Iasi

Neamt

Iasi

Neamt ...

• Czas

O(b

m

), ale dobra heurystyka mo

ż

e

• Czas

O(b

m

), ale dobra heurystyka mo

ż

e

go znacznie zmniejszy

ć

• Pami

ęć

O(b

m

) (przechowywanie wszystkich

• Pami

ęć

O(b

m

) (przechowywanie wszystkich

w

ę

złów w pami

ę

ci)

• Optymalno

ść

Nie

• Optymalno

ść

Nie

© F.A. Dul 2007

4.1. Poszukiwania informowane

Algorytm A* (A-star)

Najlepsza wersja algorytmu najpierw najlepszy (best-first)

Idea: nie rozwija

ć

ś

cie

ż

ki, która ju

ż

jest najkosztowniejsza.

Funkcja szacuj

ą

ca

Funkcja szacuj

ą

ca

f(n) = g(n) + h(n)

g(n) - koszt

ś

cie

ż

ki od startu do osi

ą

gni

ę

cia n,

h(n) - oszacowanie kosztu od n do osi

ą

gni

ę

cia celu,

h(n) - oszacowanie kosztu od n do osi

ą

gni

ę

cia celu,

f(n) - oszacowanie koszt

ś

cie

ż

ki od startu przez n do

osi

ą

gni

ę

cia celu.

A* u

ż

ywa dopuszczalnej heurystyki do oszacowania h(n)

A* u

ż

ywa dopuszczalnej heurystyki do oszacowania h(n)

Heurystyka jest dopuszczalna, je

ż

eli nigdy nie przeszacowuje

kosztu osi

ą

gni

ę

cia celu, tzn. gdy jest optymistyczna.

kosztu osi

ą

gni

ę

cia celu, tzn. gdy jest optymistyczna.

Przykład: h(n) nigdy nie jest wi

ę

ksza od odległo

ś

ci drogowej

z n do celu.

© F.A. Dul 2007

z n do celu.

Przykład - poszukiwanie najkrótszej drogi

4.1. Poszukiwania informowane

© F.A. Dul 2007

4.2. Heurystyki

Funkcje szacuj

ą

ce definiuje si

ę

zwykle w oparciu o heurez

ę

[heureza] “reguła kciuka”, uproszczenie, odgadni

ę

cie

[heureza] “reguła kciuka”, uproszczenie, odgadni

ę

cie

prawidłowo

ś

ci redukuj

ą

ce koszt rozwi

ą

zania problemu

w przypadkach, gdy jest on trudny lub niezrozumiały...

Algorytm A* u

ż

ywa dopuszczalnej heurystyki do utworzenia

funkcji h(n).

UWAGA! W dalszej cz

ęś

ci b

ę

dziemy uto

ż

samia

ć

poj

ę

cia

heurystyki oraz funkcji h(n) mówi

ą

c: “...heurystyka h(n)”

Heurystyka jest dopuszczalna, je

ż

eli nigdy nie przeszacowuje

kosztu osi

ą

gni

ę

cia celu,tj.:

heurystyki oraz funkcji h(n) mówi

ą

c: “...heurystyka h(n)”

kosztu osi

ą

gni

ę

cia celu,tj.:

1. h(n)

≤

h*(n), h*(n) - rzeczywisty koszt osi

ą

gni

ę

cia celu z n,

2. h(n)

≥

0, zatem h(G) = 0 dla ka

ż

dego celu G.

© F.A. Dul 2007

2. h(n)

≥

0, zatem h(G) = 0 dla ka

ż

dego celu G.

Heurystyka dopuszczalna jest zatem optymistyczna.

4.2. Heurystyki

Heurystyka dopuszczalna

Twierdzenie Je

ż

eli h(n) jest okre

ś

lona w oparciu o heurystyk

ę

dopuszczaln

ą

, to algorytm A* u

ż

ywaj

ą

cy algorytmu

TREE-SEARCH

jest optymalny.

Załó

ż

my,

ż

e na brzegu istnieje cel suboptymalny G

2

.

TREE-SEARCH

jest optymalny.

Dowód

Załó

ż

my,

ż

e na brzegu istnieje cel suboptymalny G

2

.

Niech n b

ę

dzie nierozwini

ę

tym w

ę

złem

brzegu le

żą

cym na najkrótszej drodze

do celu optymalnego G.

f(G

2

) = g(G

2

) gdy

ż

h(G

2

) = 0;

g(G ) > g(G) bo G jest

do celu optymalnego G.

g(G

2

) > g(G) bo G

2

jest

suboptymalny;

f(G) = g(G)

bo h(G) = 0

⇒

⇒

⇒

⇒

f(G

2

) > f(G);

f(G) = g(G)

bo h(G) = 0

⇒

⇒

⇒

⇒

f(G

2

) > f(G);

h(n)

≤

h*(n)

gdy

ż

h jest dopuszczalna;

g(n) + h(n)

≤

g(n) + h

*

(n)

⇒

⇒

⇒

⇒

f(n)

≤

f(G);

© F.A. Dul 2007

Zatem f(G

2

) > f(n) i algorytm A

*

nigdy nie rozwinie w

ę

zła G

2.

c.b.d.o.

Heurystyka zgodna

4.2. Heurystyki

Heurystyka h(n) jest zgodna je

ż

eli dla

ka

ż

dego w

ę

zła n ka

ż

dy nast

ę

pnik n’

generowany przez działanie a spełnia

generowany przez działanie a spełnia

h(n)

≤

c(n,a,n’) + h(n’)

gdzie c(n,a,n’) jest kosztem działania a

Je

ż

eli heurystyka h(n) jest zgodna, to:

gdzie c(n,a,n’) jest kosztem działania a
dla w

ę

złów n i n’.

f(n') = g(n') + h(n')

= g(n) + c(n,a,n') + h(n')

Je

ż

eli heurystyka h(n) jest zgodna, to:

= g(n) + c(n,a,n') + h(n')

≥

g(n) + h(n)

= f(n),

tj. f(n) jest funkcj

ą

niemalej

ą

c

ą

wzdłu

ż

ka

ż

dej

ś

cie

ż

ki.

Twierdzenie Je

ż

eli h(n) jest zgodna, to algorytm A*

u

ż

ywaj

ą

cy algorytmu

GRAPH-SEARCH

jest optymalny.

tj. f(n) jest funkcj

ą

niemalej

ą

c

ą

wzdłu

ż

ka

ż

dej

ś

cie

ż

ki.

© F.A. Dul 2007

Twierdzenie Je

ż

eli h(n) jest zgodna, to algorytm A*

u

ż

ywaj

ą

cy algorytmu

GRAPH-SEARCH

jest optymalny.

Optymalno

ść

algorytmu A*

4.2. Heurystyki

Algorytm A* rozwija w

ę

zły wzgl

ę

dem rosn

ą

cych warto

ś

ci f(n)

dodaj

ą

c kolejno “f-kontury” w

ę

złów.

Kontur i zawiera wszystkie w

ę

zły dla których f = f

i

,

© F.A. Dul 2007

Kontur i zawiera wszystkie w

ę

zły dla których f = f

i

,

przy czym f

i

< f

i+1

Własno

ś

ci algorytmu A*

4.2. Heurystyki

• Zupełno

ść

Tak, chyba

ż

e istnieje niesko

ń

czenie wiele

celów o tym samym koszcie.

• Czas

Wykładniczy

• Czas

Wykładniczy

• Pami

ęć

Wykładniczy (przechowywanie
wszystkich w

ę

złów w pami

ę

ci)

wszystkich w

ę

złów w pami

ę

ci)

• Optymalno

ść

Tak

Najwi

ę

kszym problemem algorytmu A* jest pami

ęć

.

Najwi

ę

kszym problemem algorytmu A* jest pami

ęć

.

Modyfikacje A* pod k

ą

tem ograniczenia pami

ę

ci (zachowuj

ą

ce

zupełno

ść

i optymalno

ść

):

zupełno

ść

i optymalno

ść

):

• iteracyjnie pogł

ę

biany A* (IDA*),

– rozwijanie zatrzymywane jest po przekroczeniu kosztu f = g + h

– rozwijanie zatrzymywane jest po przekroczeniu kosztu f = g + h

• rekursyjny najpierw najlepszy „recursive best-first”

– rekursywne utrzymywanie pami

ę

ci na poziomie liniowym

• algorytm A* z ograniczon

ą

pami

ę

ci

ą

© F.A. Dul 2007

• algorytm A* z ograniczon

ą

pami

ę

ci

ą

– najdro

ż

sze rozwini

ę

cia s

ą

odrzucane gdy brakuje pami

ę

ci

Heurystyki zgodne

Przykład - gra w osiem puzzli

4.2. Heurystyki

Przykład - gra w osiem puzzli

Przykładowe heurystyki:

Przykładowe heurystyki:

• h

1

(n) = liczba

ź

le ustawionych kostek,

• h (n) = całkowita odległo

ść

manhatta

ń

ska (tj. liczba

• h

2

(n) = całkowita odległo

ść

manhatta

ń

ska (tj. liczba

przesuni

ęć

z pozycji docelowej dla ka

ż

dej kostki)

Dla pocz

ą

tkowej konfiguracji kostek (S) mamy:

• h

1

(S) = 8 (wszystkie kostki s

ą

ź

le ustawione),

• h

2

(S) = 3+1+2+2+2+3+3+2 = 18

(przesuni

ę

cia liczone bez uwzgl

ę

dnienia

Dla pocz

ą

tkowej konfiguracji kostek (S) mamy:

© F.A. Dul 2007

2

(przesuni

ę

cia liczone bez uwzgl

ę

dnienia

blokowania przez inne kostki)

Heurystyki dominuj

ą

ce

4.2. Heurystyki

Je

ż

eli dwie heurystyki dopuszczalne, h

1

(n) i h

2

(n) spełniaj

ą

zale

ż

no

ść

h (n)

≥

h (n)

dla ka

ż

dego w

ę

zła n,

h

2

(n)

≥

h

1

(n)

dla ka

ż

dego w

ę

zła n,

to heurystyka h

2

dominuje nad h

1

.

Heurystyka dominuj

ą

ca jest lepsza przy poszukiwaniach.

Heurystyka dominuj

ą

ca jest lepsza przy poszukiwaniach.

© F.A. Dul 2007

Jak wymy

ś

li

ć

dobr

ą

heurystyk

ę

dopuszczaln

ą

?

4.2. Heurystyki

Nie ma ogólnych i zarazem skutecznych reguł wymy

ś

lania

dobrych heurystyk dla szerokiej klasy zagadnie

ń

.

Mo

ż

na jednak poda

ć

kilka wskazówek ułatwiaj

ą

cych

Czasami heurystyka dopuszczalna mo

ż

e by

ć

uzyskana

Mo

ż

na jednak poda

ć

kilka wskazówek ułatwiaj

ą

cych

tworzenie heurystyk.

Czasami heurystyka dopuszczalna mo

ż

e by

ć

uzyskana

poprzez rozlu

ź

nienie organicze

ń

zadania wyj

ś

ciowego.

Koszt rozwi

ą

zania zadania rozlu

ź

nionego jest nie wi

ę

kszy

Koszt rozwi

ą

zania zadania rozlu

ź

nionego jest nie wi

ę

kszy

ni

ż

koszt rozwi

ą

zania zadania wyj

ś

ciowego.

Przykłady dla gry w osiem puzzli:

Przykłady dla gry w osiem puzzli:

• je

ż

eli kostki mogły by porusza

ć

si

ę

w dowolny sposób,

to h

1

(n) okre

ś

la najta

ń

sze rozwi

ą

zanie;

to h

1

(n) okre

ś

la najta

ń

sze rozwi

ą

zanie;

• je

ż

eli kostki mogły by przemieszcza

ć

si

ę

do pól

s

ą

siednich nawet gdy s

ą

one zaj

ę

te, to h

2

(n) okre

ś

la

najta

ń

sze rozwi

ą

zanie.

© F.A. Dul 2007

najta

ń

sze rozwi

ą

zanie.

Jak wymy

ś

li

ć

dobr

ą

heurystyk

ę

dopuszczaln

ą

?

4.2. Heurystyki

Czasami dobr

ą

heurystyk

ę

dopuszczaln

ą

mo

ż

na uzyska

ć

analizuj

ą

c podproblemy zadania wyj

ś

ciowego.

Dla gry w osiem puzzli mo

ż

e to polega

ć

na utworzeniu bazy

Dla gry w osiem puzzli mo

ż

e to polega

ć

na utworzeniu bazy

wzorców wszystkich rozwi

ą

za

ń

dla podzbiorów puzzli, np.:

Heurystyka dla konkretnego zadania jest tworzona z tych
wzorców.

wzorców.

Jeszcze innym sposobem jest tworzenie heurystyki na
podstawie zebranych do

ś

wiadcze

ń

i zastosowanie

© F.A. Dul 2007

podstawie zebranych do

ś

wiadcze

ń

i zastosowanie

algorytmu ucz

ą

cego.

4.3. Algorytmy poszukiwa

ń

lokalnych

Istnieje klasa zada

ń

, w których droga doj

ś

cia do celu nie jest

istotna - cel jest jednocze

ś

nie rozwi

ą

zaniem.

Przykład: rozmieszczenie na szachownicy o

ś

miu królowych

Przykład: rozmieszczenie na szachownicy o

ś

miu królowych

w taki sposób, aby wzajemnie si

ę

nie atakowały.

Zadania takie mo

ż

na rozwi

ą

zywa

ć

Zadania takie mo

ż

na rozwi

ą

zywa

ć

przy pomocy algorytmów poszukiwa

ń

lokalnych.
Stan - rozmieszczenie na szachownicy
o

ś

miu królowych w dowolny sposób.

Poszukiwania lokalne polegaj

ą

na

Poszukiwania lokalne polegaj

ą

na

kolejnych zmianach stanu na takie,
które s

ą

“lepsze”.

Po wykonaniu sekwencji zmian stanu
powinni

ś

my uzyska

ć

stan docelowy

które s

ą

“lepsze”.

© F.A. Dul 2007

powinni

ś

my uzyska

ć

stan docelowy

(tu: jeden ze zbioru stanów docelowych).

Cechy algorytmów poszukiwa

ń

lokalnych:

4.3. Algorytmy poszukiwa

ń

lokalnych

Cechy algorytmów poszukiwa

ń

lokalnych:

• nie potrzebuj

ą

wielkiej pami

ę

ci;

• pozwalaj

ą

rozwi

ą

zywa

ć

zadania o bardzo du

ż

ym

wymiarze stanu.

wymiarze stanu.

Algorytmy poszukiwa

ń

lokalnych s

ą

blisko zwi

ą

zane z

algorytmami optymalizacji.

algorytmami optymalizacji.

Do algorytmów poszukiwa

ń

lokalnych zalicza si

ę

:

• algorytm „hill-climbing”
• algorytm symulowanego wy

ż

arzania

• algorytm „local beam”
• algorytmy genetyczne

© F.A. Dul 2007

4.3. Algorytmy poszukiwa

ń

lokalnych

Algorytm najszybszego wzrostu „hill-climbing”

Idea: zmiana stanu musi najlepiej poprawi

ć

jako

ść

stanu.

Algorytm zachowuje si

ę

“...jak cierpi

ą

cy na amnezj

ę

alpinista

Algorytm zachowuje si

ę

“...jak cierpi

ą

cy na amnezj

ę

alpinista

wspinaj

ą

cy si

ę

w g

ę

stej mgle na Mount Everest”.

function HILL-CLIMBING( problem) return a state that is a local maximum

input: problem, a problem
local variables: current, a node.

neighbor, a node.

neighbor, a node.

current

←

MAKE-NODE(INITIAL-STATE[problem])

loop do

←

neighbor

←

a highest valued successor of current

if VALUE [neighbor]

≤

VALUE[current] then return STATE[current]

current

←

neighbor

current

←

neighbor

Zmiany stanu s

ą

dobierane tak,

ż

e warto

ść

funkcji celu

ro

ś

nie a

ż

do osi

ą

gni

ę

cia najwi

ę

kszej warto

ś

ci w pobli

ż

u

© F.A. Dul 2007

ro

ś

nie a

ż

do osi

ą

gni

ę

cia najwi

ę

kszej warto

ś

ci w pobli

ż

u

stanu startowego.

Algorytm najszybszego wzrostu „hill-climbing”

Problem: w zale

ż

no

ś

ci od stanu pocz

ą

tkowego algorytm

4.3. Algorytmy poszukiwa

ń

lokalnych

Problem: w zale

ż

no

ś

ci od stanu pocz

ą

tkowego algorytm

mo

ż

e znajdywa

ć

maksima lokalne funkcji celu.

• wersja stochastyczna - losowy wybór pomi

ę

dzy kierunkami

wspinaczki,

© F.A. Dul 2007

wspinaczki,

• restart losowy w celu unikni

ę

cia maksimum lokalnego.

Przykład - zadanie o

ś

miu królowych na szachownicy

Nast

ę

pnik - przestawienie pojedynczej królowej na inne pole

4.3. Algorytmy poszukiwa

ń

lokalnych

Nast

ę

pnik - przestawienie pojedynczej królowej na inne pole

w tej samej kolumnie szachownicy.

Heurystyka h(n): liczba par królowych które atakuj

ą

si

ę

Heurystyka h(n): liczba par królowych które atakuj

ą

si

ę

wzajemnie (bezpo

ś

rednio lub po

ś

rednio).

Stan dla którego h(n) = 17
oraz stany nast

ę

pne dla

których h(n) przyjmuj

ą

Minimum lokalne h(n) = 1

© F.A. Dul 2007

których h(n) przyjmuj

ą

warto

ś

ci mniejsze.

Algorytm symulowanego wy

ż

arzania

Idea: dopuszczenie “złych” zmian stanu w celu omini

ę

cia

4.3. Algorytmy poszukiwa

ń

lokalnych

Idea: dopuszczenie “złych” zmian stanu w celu omini

ę

cia

maksimów lokalnych.
Złe zmiany stanu musz

ą

by

ć

coraz mniejsze i zachodzi

ć

Złe zmiany stanu musz

ą

by

ć

coraz mniejsze i zachodzi

ć

coraz rzadziej.
Pomysł zaczerpni

ę

ty z …metalurgii. Opiera si

ę

na technice

wy

ż

arzania metalu.

wy

ż

arzania metalu.

Co jaki

ś

czas dopuszcza si

ę

zmian

ę

stanu na taki, któremu

odpowiada mniejsza warto

ść

funkcji celu.

odpowiada mniejsza warto

ść

funkcji celu.

Pozwala to “przeskoczy

ć

na nast

ę

pny pagórek” i w ten

sposób unikn

ąć

minimum lokalnego.

Je

ż

eli symulowana temperatura maleje dostatecznie wolno,

to algorytm symulowanego wy

ż

arzania znajduje maksimum

globalne z prawdopodobie

ń

stwem d

ążą

cym do jedno

ś

ci.

sposób unikn

ąć

minimum lokalnego.

globalne z prawdopodobie

ń

stwem d

ążą

cym do jedno

ś

ci.

Metoda ta stosowana jest szerorko przy opracowywaniu
topologii układów VLSI, planowaniu rozkłdu lotów, itp.

© F.A. Dul 2007

topologii układów VLSI, planowaniu rozkłdu lotów, itp.

Algorytm symulowanego wy

ż

arzania

4.3. Algorytmy poszukiwa

ń

lokalnych

function SIMULATED-ANNEALING( problem, schedule) return a solution state

input: problem, a problem

schedule, a mapping from time to temperature

schedule, a mapping from time to temperature

local variables: current, a node.

next, a node.
T, a “temperature” controlling the probability of

downward steps

downward steps

current

←

MAKE-NODE(INITIAL-STATE[problem])

for t

←

←

←

←

1 to

∞

∞

∞

∞

do

for t

←

←

←

←

1 to

∞

∞

∞

∞

do

T

←

schedule[t]

if T = 0 then return current
next

←

a randomly selected successor of current

next

←

a randomly selected successor of current

∆

E

←

VALUE[next] - VALUE[current]

if

∆

E > 0 then current

←

next

else current

←

next only with probability e

∆

E /T

else current

←

next only with probability e

∆

E /T

© F.A. Dul 2007

Algorytm poszukiwania wi

ą

zk

ą

„local beam”

Idea: operowanie na zbiorze k stanów zamiast na

4.3. Algorytmy poszukiwa

ń

lokalnych

Idea: operowanie na zbiorze k stanów zamiast na
pojedynczym stanie.

• Przy starcie generuje si

ę

losowo k stanów;

• Przy starcie generuje si

ę

losowo k stanów;

• w ka

ż

dym kroku wyznacza si

ę

rozwini

ę

cia wszystkich

stanów;

stanów;

• je

ż

eli jaki

ś

nast

ę

pnik osi

ą

gn

ą

ł cel, to KONIEC;

• w przeciwnym razie wybiera si

ę

k najlepszych stanów

• w przeciwnym razie wybiera si

ę

k najlepszych stanów

i kontynuuje poszukiwania;

Zaleta: informacja propaguje si

ę

na k w

ą

tków obliczeniowych,

Zaleta: informacja propaguje si

ę

na k w

ą

tków obliczeniowych,

co poprawia zbie

ż

no

ść

algorytmu.

© F.A. Dul 2007

Algorytmy genetyczne

4.3. Algorytmy poszukiwa

ń

lokalnych

Idea: na

ś

ladowanie natury poprzez dobór naturalny najlepiej

przystosowanych “osobników”.

• Algorytm operuje na zbiorze k stanów (

populacji

).

• Stan jest reprezentowany przez ła

ń

cuch (

gen

) utworzony

z liter alfabetu sko

ń

czonego (cz

ę

sto alfabet jest binarny:

z liter alfabetu sko

ń

czonego (cz

ę

sto alfabet jest binarny:

0 i 1)

• Funkcja szacuj

ą

ca (

funkcja dopasowania

). Wi

ę

ksze

warto

ś

ci odpowiadaj

ą

lepszym stanom - “lepiej

warto

ś

ci odpowiadaj

ą

lepszym stanom - “lepiej

dostosowanym”.

• Start ze zbiorem k stanów wygenerowanych losowo.

• Start ze zbiorem k stanów wygenerowanych losowo.
• Stan potomny jest generowany przez kombinacj

ę

dwóch

stanów rodzicielskich.

• Nowa generacja stanów uzyskiwana jest za pomoc

ą

Algorytm genetyczny to algorytm wi

ą

zkowy z rekombinacj

ą

• Nowa generacja stanów uzyskiwana jest za pomoc

ą

selekcji, krzy

ż

owania i mutacji.

© F.A. Dul 2007

Algorytm genetyczny to algorytm wi

ą

zkowy z rekombinacj

ą

genetyczn

ą

.

Algorytmy genetyczne

4.3. Algorytmy poszukiwa

ń

lokalnych

Przykład dla zadania o

ś

miu królowych na szachownicy

•

Funkcja dopasowania: liczba nieatakuj

ą

cych si

ę

par królowych

(min. = 0, max = 8

×

7/2 = 28)

(min. = 0, max = 8

×

7/2 = 28)

•

24/(24+23+20+11) = 31%

•

23/(24+23+20+11) = 29% etc.

Populacja Funkcja Selekcja Krzy

ż

owanie Mutacje

Populacja Funkcja Selekcja Krzy

ż

owanie Mutacje

pocz

ą

tkowa dopasowania

© F.A. Dul 2007

Algorytmy genetyczne

4.3. Algorytmy poszukiwa

ń

lokalnych

function GENETIC_ALGORITHM( population, FITNESS-FN) return an individual

input: population, a set of individuals

FITNESS-FN, a function which determines the quality of the individual

FITNESS-FN, a function which determines the quality of the individual

repeat

new_population

←

empty set

loop for i from 1 to SIZE(population) do

loop for i from 1 to SIZE(population) do

x

←

RANDOM_SELECTION(population, FITNESS_FN)

y

←

RANDOM_SELECTION(population, FITNESS_FN)

child

←

REPRODUCE(x,y)

child

←

REPRODUCE(x,y)

if (small random probability) then child

←

MUTATE(child )

add child to new_population

population

←

new_population

population

←

new_population

until some individual is fit enough or enough time has elapsed
return the best individual

© F.A. Dul 2007

4.5 Zadania eksploracji

Zadania rozpatrywane dotychczas mogły by

ć

rozwi

ą

zywane

offline, czyli przed podj

ę

ciem działa

ń

agenta.

Czasami zadania mysz

ą

by

ć

rozw

ą

zywane online, czyli

• Poszukiwanie online jest niezb

ę

dne w przypadku, gdy

Czasami zadania mysz

ą

by

ć

rozw

ą

zywane online, czyli

naprzemian z obserwacjami i działaniami agenta.

• Poszukiwanie online jest niezb

ę

dne w przypadku, gdy

ś

rodowisko jest dynamiczne lub semi-dynamiczne,

gdy

ż

nie ma mo

ż

liwo

ś

ci uwzgl

ę

dnienia wszystkich

gdy

ż

nie ma mo

ż

liwo

ś

ci uwzgl

ę

dnienia wszystkich

sytuacji nieprzewidywalnych;

• Poszukiwanie online jest niezb

ę

dne równie

ż

w

przypadku zada

ń

eksploracji, gdy

ś

rodowisko jest

przypadku zada

ń

eksploracji, gdy

ś

rodowisko jest

nieznane a priori, np.:

– próbnik (łazik) planetarny,

– próbnik (łazik) planetarny,
– automatyczny zwiadowca,
– nowo narodzone dziecko...

© F.A. Dul 2007

Podsumowanie

• Algorytm „najlepszy-najpierw” jest algorytmem typu G

RAPH-

• Algorytm „najlepszy-najpierw” jest algorytmem typu G

RAPH-

S

EARCH

który rozwija w

ę

zeł o najmniejszej warto

ś

ci kosztu

wykorzystuj

ą

c heurystyk

ę

h(n), która szacuje koszt

poszukiwa

ń

od w

ę

zła n do celu.

poszukiwa

ń

od w

ę

zła n do celu.

• Algorytm agresywny „najlepszy-najpierw” rozwija w

ę

zły

z najmniejsz

ą

warto

ś

ci

ą

h(n). Nie jest optymalny, ale czasem

z najmniejsz

ą

warto

ś

ci

ą

h(n). Nie jest optymalny, ale czasem

efektywny.

• Algorytm A* rozwija w

ę

zły z najmniejsz

ą

warto

ś

ci

ą

f(n) = g(n) + h(n). Algorytm A* jest zupełny i optymalny

f(n) = g(n) + h(n). Algorytm A* jest zupełny i optymalny
je

ż

eli h(n) jest dopuszczalna (dla T

REE-

S

EARCH

)

lub zgodna (dla G

RAPH-

S

EARCH

).

• Efektywno

ść

algorytmów informowanych zale

ż

y od jako

ś

ci

heurystyk.

• Dobra heurystyka mo

ż

e by

ć

cz

ę

sto uzyskana poprzez

• Dobra heurystyka mo

ż

e by

ć

cz

ę

sto uzyskana poprzez

rozlu

ź

nienie ogranicze

ń

zadania.

© F.A. Dul 2007

Podsumowanie

• Metody poszukiwa

ń

lokalnych (np. hill climbing) wykorzystuj

ą

• Metody poszukiwa

ń

lokalnych (np. hill climbing) wykorzystuj

ą

tylko pojedyncze stany, nie wymagaj

ą

wi

ę

c du

ż

ej pami

ę

ci.

• Algorytm stochastyczny symulowanego wy

ż

arzania polega

• Algorytm stochastyczny symulowanego wy

ż

arzania polega

na losowym generowaniu kierunków poszukiwa

ń

o malej

ą

cych amplitudach.

Pozwala wyznacza

ć

efektywnie rozwi

ą

zanie globalne

Pozwala wyznacza

ć

efektywnie rozwi

ą

zanie globalne

„uciekaj

ą

c” z minimów lokalnych.

• Algorytmy genetyczne s

ą

stochastyczn

ą

wersj

ą

algorytmów

hill-climbing które do wyznaczania kierunków poszukiwa

ń

hill-climbing które do wyznaczania kierunków poszukiwa

ń

u

ż

ywaj

ą

mechanizmów genetycznych: krzy

ż

owania, mutacji

i selekcji.

• Zadania eksploracji, w których agent nie ma wiedzy

o

ś

rodowisku, mog

ą

by

ć

rozwi

ą

zywane metodami

poszukiwa

ń

bie

żą

cych (online search).

poszukiwa

ń

bie

żą

cych (online search).

• W metodach online search agent tworzy map

ę

ś

rodowiska

na podstawie której znajduje cel, o ile on istnieje.

© F.A. Dul 2007

• Pomocne jest ulepszanie heurystyk na podstawie obserwacji

ś

rodowiska.