Heurystyki
Heurystyki
Heurystyki
Definicja
Przeszukiwanie heurystyczne jest
procesem poszukiwania żądanego
stanu spełniającego zadane warunki
W zadaniach przeszukiwania mianem
“heurystyczne” określa się wszelkie
prawa, kryteria i zasady (również
takie których skuteczność nie jest
całkowicie pewna), które umożliwiają
wybranie najbardziej efektywnych
kierunków działania, jeśli chodzi o
osiągnięcie danego celu.
Heurystyki
Termin: heurystyka
Termin heurystyka jest rozumiany w
zagadnieniach sztucznej inteligencji
następująco.
●
Jest to praktyczna strategia poprawiająca
efektywność złożonych problemów.
●
Powinna prowadzić do rozwiązania wzdłuż
najkrótszej i najbardziej prawdopodobnej
drogi omijając mniej obiecujące ścieżki
●
Podaje proste kryterium wyboru kierunków
postępowania.
●
Powinna umożliwić uniknięcie badania tzw.
Ślepych uliczek i wcześniejsze wykorzystanie
zdobytych w trakcie badania informacji
Heurystyki
Rozwiązywanie problemu: taktyka postępowania
▪
Precyzyjna definicja problemu.
▸
Punkt startu
▸
Punkt docelowy
▪
Analiza problemu.
▪
Określenie i reprezentacja wiedzy
potrzebnej do rozwiązania problemu
▪
Wybór i zastosowanie najlepszej
techniki rozwiązania problemu.
Heurystyki
Analiza problemu: gra w szachy
Punkt wyjścia:
Heurystyki
Analiza problemu: gra w szachy
Punkt decelowy: definicja
wszystkich sytuacji w których
przeciwnik nie może wykonać
ruchu królem.
Heurystyki
Analiza problemu: gra w szachy
Definicja wszystkich możliwych
ruchów określa wszystkie możliwe
kombinacje posunięć tak aby z
punkty wyjściowego dojść do
któregoś z punktów docelowych.
Heurystyki
Gra w szachy definicja ruchów
Heurystyki
Analiza problemu: gra w szachy
Pionek jest w
Pole(e,2)
i
Pole(e,3) jest
puste
i
Pole(e,4) jest
puste
=
>
Przesuń
pionek z
Pole(e,2) do
Pole(e,4)
Heurystyki
Gra w szachy: problemy
●
Trudność w zdefiniowaniu wszystkich
reguł. Może to trwać zbyt długo.
●
Problem uwzględnienia tych reguł
przez program komputerowy (zasoby
efektywność)
Heurystyki
Zbiorniki z wodą: opis problemu
Problem zbiorników z wodą:
Są dwa zbiorniki o pojemności 3 i 4
litrów. Należy tak napełnić zbiorniki
wodą aby w zbiorniku 4 litrowym
znajdowały się dokładnie dwa litry wody.
Można przelewać wodę między
zbiornikami.
Heurystyki
Zbiorniki z wodą: opis problemu
Stany przestrzeni mogą być opisane
jako:
(x,y)
X= 0,1,2,3,4
Y= 0,1,2,3
Punkt wyjścia - (0,0)
Punkt docelowy - (2,0)
Heurystyki
Zbiorniki z wodą: stany przestrzeni
1. Jeśli X<4
2. Jeśli Y<3
3. Jeśli X>0
4. Jeśli Y>0
5. Jeśli X>0
6. Jeśli Y>0
7. Jeśli X+Y>=4 i
Y>0
8. Jeśli X+Y>=3 i
X>0
9. Jeśli X+Y<=4 i
X>0
10. Jeśli X+Y<=3
X>0
11. (0,2)
12. (2,Y)
-> (4,Y)
-> (X,3)
->(X-d,Y)
->(X,Y-d)
->(0,Y)
->(X,0)
->(4,Y-(4-
X))
->(X-(3-
Y),3)
->(X+Y,0)
->(0,X+Y)
->(2,0)
->(0,Y)
Napełnij poj. 4 L
Napełnijpoj 3L
Wylej trochę wody z
poj 4L
Wylej troche wody z
poj 3L
Opróżnij poj. 4L
Opróżnij poj. 3L
Przelej wodę z poj. 3L
do poj 4L dopóki nie
będzie pełen
Przelej wodę z poj 4L
do poj 3L dopóki nie
będzie pełen
Przelej wodę z 3L do
4L
Przelej wodę z 4L do
3L
Przelej 2L z 3L do 4L
Wylej 2L z poj. 4L
Heurystyki
Zbiorniki z wodą: opis problemu
Woda w poj.
4L
0
0
3
3
4
0
2
Woda w poj.
3L
0
3
0
3
2
2
0
Reguła
2
9
2
7
5
9 lub
11
Heurystyki
Strategie przeszukiwania przestrzeni rozwiazań
●
Postęp
●
Systematyczność
Wymagania:
Heurystyki
Strategie przeszukiwania: klasyfikacja
●
Strategie ślepe
▸
Strategia wszerz
▸
Strategia w głąb
▸
Strategia z powracaniem
●
Strategie heurystyczne
▸
Strategia zachłanna (hill-climbing)
▸
Strategia najpierw najlepszy (best-first)
▸
Strategia A
*
Heurystyki
Strategie przeszukiwania: strategia wszerz
Strategia wszerz (breadh-first),
zakłada badanie kolejno poziomów
grafu o jednakowej głębokości,
przyznając wyższy priorytet węzłom o
mniejszej głębokości.
Heurystyki
Strategie przeszukiwania: strategia wszerz
●
W pamięci przechowywane są
wszystkie węzły o danej głebokości
przed wygenerowaniem
jakiegokolwiek węzła o głębokości o
jeden większej
●
W strategii tej występują duże
wymagania dotyczace pamięci
Heurystyki
Strategie przeszukiwania: strategia wszerz
(0,0
)
(4,0
)
(0,3
)
(4,3
)
(0,0
)
(1,3
)
(4,3
)
(0,0
)
(3,0
)
Heurystyki
Strategie przeszukiwania: strategia w głąb
Strategia w głąb (depth-first)- droga w
grafie jest wyznaczana dopóty dopóki
jej ostatni element nie zostanie
określony jako węzeł celu lub końcowy.
Przeszukiwanie jest zawsze
prowadzone od ostatniego
sprawdzanego węzła, którego nie
wszystkie gałęzie były jeszcze
rozwijane.
Heurystyki
Strategie przeszukiwania: strategia w głąb
(0,0
)
(4,0
)
(4,3
)
(0,0
)
(1,3
)
(0,3
)
(4,3
)
(0,0
)
(3,0
)
Heurystyki
Strategie przeszukiwania: strategia w głąb
●
W przypadku grafów o dużej
głębokości może być nieskuteczna
●
Jest często uzupełniana
mechanizmem kontroli głębokości
●
Jest właściwa dla tych problemów
dla których ocena właściwości
węzłów zależy ścisle od oceny
właściwości ich rodziców
●
W pamięci są przechowywane
tylko węzły z aktualnie badanej
ścieżki grafu
●
Oszacowane koszty tej strategii
nie są zazwyczaj osiągane w
rzeczywistości
Heurystyki
Strategie przeszukiwania: strategia z powracaniem
Strategia z powracaniem (backtracking)
jest modyfikacją algorytmu
przeszukiawania w głąb. Różnica polega
na tym że ekspansja danego węzła jest
zastąpiona jego rozszerzaniem
(generowaniem tylko jednego potomka).
Heurystyki
Strategie przeszukiwania: strategia z powracaniem
●
Oszczędność pamięci
●
Gwarancja że po zakończeniu
wszystkie wygenerowane węzły będą
przetestowane
●
Oszczędność pamięci odbywa się
kosztem dodatkowych obliczeń
Heurystyki
Strategie przeszukiwania: strategia zachłanna
(Hill-climbing)
1
Sprawdź punkt wyjściowy. Jeśli punkt
wyjściowy jest punktem docelowym zakończ. W
przeciwnym przypadku potraktuj punkt wyjściowy
jako bieżący
2
Wykonuj “w pętli” następujące operacje dopóki
nie znajdziesz rozwiązania, lub nie będzie więcej
operacji do przetwarzania
a
Wybierz nowy operator wynikajacy z stanu bieżącego
b
Analizuj operator
i
Jeśli jest to punkt docelowy to zakończ działanie
i
Jeśli nie jest to punkt docelowy ale jest lepszy niż stan bieżący
to zamień operator na stan bieżący
i
Jeśli operator nie jest lepszy niż stan bieżący to kontynuuj
“pętlę”
Heurystyki
Strategie przeszukiwania: strategia najpierw najlepszy
Strategia najpierw najlepszy
wykorzystuje peweną funkcję
heurystyczną , która wyraża ocenę
węzła ze względu na następujące
kryteria:
●
Zbieżności czyli osiągnięcia celu
●
Najmniejszej złożoności obliczeniowej
procesu przeszukiwania
Heurystyki
Strategie przeszukiwania: strategia najpierw najlepszy
1
Dodaj stan poczatkowy do zbioru stanów roboczych
R
2
Dopóki nie znaleziono rozwiązania lub zbiór R jest
pusty wykonuj:
a
Wybierz najlepszy stan ze zbioru R
b
Generuj jego węzły potomne
c
Dla każdego z węzłów potomnych wykonuj:
i
Jeżli nie był jeszcze generowany dodaj go do zbioru R i zapamiętaj
jego rodzica
i
Jeśli był już generowany. Sprawdź czy nowa ścieżka jest lepsza od
poprzedniej. Jeśli tak to sprawdzany węzeł zastępuje rodzica.
Heurystyki
Strategie przeszukiwania: algorytm A
*
Algorytm polega na wyznaczeniu
najtańszej drogi w grafie
F(w) = h(w) + g(w)
gdzie
f(w) - koszt drogi
h(w) - koszt drogi łączącej węzęł w
z węzłem celu
g(w) - koszt drogi łączącej węzeł w
węzłem początkowym
Heurystyki
Strategie przeszukiwania: algorytm A
*
Algorytm A
*
zakłada istnienie funkcji
heurystycznej pozwalającej okreslić
odłegłośc węzła w od stanu docelowego
Heurystyki
Pojedynek Kasparow - Big Blue
1997 Gari Kasparow przegrywa
pojedynek szachowy z komputerem IBM
Big Blue.
Heurystyki
Historia komputerowych systemów szachowych
▪
1949 - opracowanie podstaw teoretycznych
automatu szachowego, Alan Turing, David
Champernown
▪
1949 - Claude Shanon - konstrukcja maszyny
“Caissac” do rozwiązywania “końcówek
szachowych”
▪
MADM (Manchaster Automatic Digital Machine)-
program zdolny do rozegrania całej partii. Autor -
Alan Turing
▪
1956 - Maniac I - potrafił grać na podstawowym
poziomie
▪
Lata 60-te - szachowe programy komputerowe
reprezentują poziom początkujących graczy
▪
1967 - pierwszy pojedynek szachowy programów
komputerowych, pomiędzy USA i ZSRR - wynik
2.5:0.5
Heurystyki
Historia komputerowych systemów szachowych
▪
Początek lat 70-tych - problemem szachów
komputerowych zaczęło się interesować
amerykańskie towarzystwo ACM (Association for
Computing Machines)
▪
1974 - mistrzostwa świata w kategorii szachów
komputerowych, wygrał program opracowany w
ZSRR przy udziale Michaiła Botwinnika (mistrza
świata z lat 1948, 1951, 1954, 1958, 1961)
▪
Lata 80-te podejście techniczne
▪
Początek lat 80-tych - komputer przewidujący do
4 ruchów do przodu (firma Bell)
▪
Połowa lat 80-tych program Cray Blitz pracujący
na superkomputerze Cray mógł analizować 100
000 pozycji na sekundę.
Heurystyki
Historia komputerowych systemów szachowych
▪
1985 - Chińczyk Feng-Hsiung Hsu - opracował
specjalizowany układ scalony wielkiej integracji
(VLSI), mogący generować 2 mln ruchów
szachowych w ciągu sekundy
▪
1987 - powstaje komputer ChipTest - potrafi
analizować 50 000 na sekundę (pracował na
stacji roboczej SUN 3/160)
▪
1989 - prace badawcze w laboratorium IBM nad
zbudowaniem komputera , który pokona mistrza
świata. Powstaje Deep Thought II (2 mln pozycji na
sekundę)
▪
Deep Blue - komputer przygotowany do
pokonania mistrza świata
Heurystyki
Charakterystyka Deep Blue
▪
256 specjalizowanych układow VLSI
▪
Komputer IBM RS/6000 SP2, 32 procesory
▪
Każdy z 32 węzłów systemu wykorzystywał kartę
microchannel wyposażoną w 8 dedykowanych
procesorów szachowych
▪
Waga systemu 1.5 tony
Heurystyki
1996 - pojedynek o mistrzostwo świata
Kasparow - Big Blue
▪
Pojedynek składał się z trzech partii
▪
I partia wygrywa Deep Blue
▪
II partia wygrywa Kasparow
▪
III ,IV partia remis
▪
V i VI partia wygrywa Kasparow
Heurystyki
1997 - pojedynek o mistrzostwo świata
Kasparow - Big Blue
▪
6 partii
▪
2 godziny dla kazdego z graczy na pierwsze 40
ruchów
▪
30 minut ostateczny czas na wszystkie kolejne
ruchy
▪
Deep Blue obsługiwany przez operatora
wskazanego przez IBM
▪
Ewentualny czas awarii miał byc odliczany od
czasu ruchu komputera
Heurystyki
1997 - pojedynek o mistrzostwo świata
Kasparow - Big Blue
1
- wygrywa Kasparow
2
- wygrywa Deep Blue
3
Remis
4
Remis
5
Remis
6
Kasparow poddaje się po 19 posunięciu
Heurystyki
Technika gry Deep Blue
●
Początkowo - system ekspercki ktory
korzystając ze zgromadzonych zasobów wiedzy
szachowej miał wyliczać najlepszą odpowiedź na
ruch przeciwnika
●
Wykorzystanie złożonej funkcji oceny pozycji
na szachownicy. Funkcja oceny analizowała cztery
podstawowe wartości
▸
Materialna (pion -1, skoczek i goniec - 3, wieża 5,
królowa 9
▸
Pozycja na szachownicy (zliczanie bezpiecznych pól)
▸
Bezpieczeństwo króla
▸
Tempo gry
Heurystyki
Blue Gene następca Big Blue
●
Masowe przetwarzanie równoległe
●
Wydajność ponad 1 petaflopa (kwadrylion
operacji na sekundę)
●
Przeznaczenie modelowanie występujace w
organizmach żywych (procesy zwijania białek)