Jurusan Teknik Informatika – Universitas Widyatama
Overview • Deskripsi • Heuristic Search
Heuristic Search
– – – – –
Pertemuan : 4 Dosen Pembina : Sriyani Violina Danang Junaedi IF-UTAMA
1
Deskripsi
2
• A alternative to a random-restart hill-climbing when stuck on a local maximum is to do a ‘reverse walk’ to escape the local maximum. • This is the idea of simulated annealing. • The term simulated annealing derives from the roughly analogous physical process of heating and then slowly cooling a substance to obtain a strong crystalline structure. • The simulated annealing process lowers the temperature by slow stages until the system ``freezes" and no further changes occur.
Simulated Annealing Simplified Memory Bounded A* Bi-Directional A* Modified Bi-Directional A* Dynamic Weighthing A*
IF-UTAMA
IF-UTAMA
IF-UTAMA
Simulated Annealing
• Pertemuan ini mempelajari bagaimana memecahkan suatu masalah dengan teknik searching. • Metode searching yang dibahas pada pertemuan ini adalah heuristic search atau informed search yang terdiri dari: – – – – –
Simulated Annealing Simplified Memory Bounded A* Bi-Directional A* Modified Bi-Directional A* Dynamic Weighthing A*
3
IF-UTAMA
4
1
Physical Interpretation of Simulated Annealing
Search using Simulated Annealing • Simulated Annealing = hill-climbing with non-deterministic search • Basic ideas: – – – – –
• A Physical Analogy: • imagine letting a ball roll downhill on the function surface – this is like hill-climbing (for minimization)
like hill-climbing identify the quality of the local improvements instead of picking the best move, pick one randomly say the change in objective function is δ if δ is positive, then move to that state otherwise:
• now imagine shaking the surface, while the ball rolls, gradually reducing the amount of shaking – this is like simulated annealing
• Annealing = physical process of cooling a liquid or metal until particles achieve a certain frozen crystal state
• move to this state with probability proportional to δ • thus: worse moves (very large negative δ) are executed less often
• simulated annealing:
– however, there is always a chance of escaping from local maxima – over time, make it less likely to accept locally bad moves – (Can also make the size of the move random as well, i.e., allow “large” steps in state space) IF-UTAMA
– free variables are like particles – seek “low energy” (high quality) configuration – get this by slowly reducing temperature T, which particles move around randomly 5
Simulated Annealing
Differences
• Probability of transition to higher energy state is given by function:
• The algorithm for simulated annealing is slightly different from the simple-hill climbing procedure. The three differences are:
– P = e –∆E/kt Where ∆E is the positive change in the energy level T is the temperature K is Boltzmann constant.
IF-UTAMA
IF-UTAMA
IF-UTAMA
6
– The annealing schedule must be maintained – Moves to worse states may be accepted – It is good idea to maintain, in addition to the current state, the best state found so far.
7
IF-UTAMA
8
2
Algorithm: Simulate Annealing
Simulate Annealing: Implementation
1.
• It is necessary to select an annealing schedule which has three components:
2. 3. 4.
Evaluate the initial state. If it is also a goal state, then return it and quit. Otherwise, continue with the initial state as the current state. Initialize BEST-SO-FAR to the current state. Initialize T according to the annealing schedule Loop until a solution is found or until there are no new operators left to be applied in the current state. a.
Select an operator that has not yet been applied to the current state and apply it to produce a new state. Evaluate the new state. Compute:
b. • • • •
c.
5.
– Initial value to be used for temperature – Criteria that will be used to decide when the temperature will be reduced – Amount by which the temperature will be reduced.
∆E = ( value of current ) – ( value of new state) If the new state is a goal state, then return it and quit. If it is a goal state but is better than the current state, then make it the current state. Also set BEST-SO-FAR to this new state. If it is not better than the current state, then make it the current state with probability p’ as defined above. This step is usually implemented by invoking a random number generator to produce a number in the range [0, 1]. If the number is less than p’, then the move is accepted. Otherwise, do nothing.
Revise T as necessary according to the annealing schedule
Return BEST-SO-FAR as the answer IF-UTAMA
9
IF-UTAMA
10
SIMPLIFIED MEMORY-BOUNDED A* (SMA*)
Memory Bounded Search • To address complex search problems, we often put constraints on memory requirements. • We will examine two algorithms: (a) IDA* search and (b) SMA* search. • Iterative Deepening A* Search (IDA*) uses a DFS for every iteration where an f-cost limit is used instead of a depth limit. • Each iteration expands all the nodes that lie inside a contour for the current f-cost. • The time complexity depends on the different values that the heuristic can take on. • IDA* is complete, optimal, and memory-bounded. • To improve IDA*, we often increase the f-cost limit by a fixed amount ε on each iteration. Such an approach is called ε-admissible.
• IDA* cannot remember its previous steps since it uses too little memory (between iterations only the f-cost limit is kept). • If the state space is graph, IDA* often repeats itself. • Uses all available memory for the search – drops nodes from the queue when it runs out of space • those with the highest f-costs
– If there is a tie (equal f-values) we first delete the oldest nodes first. – complete if there is enough memory for the shortest solution path – often better than A* and IDA* • but some problems are still too tough • trade-off between time and space requirements
• It is complete and optimal if the available memory allows SMA* to store the shallowest solution path. • When enough memory is available for the whole search tree, the search is optimally efficient. 12
IF-UTAMA
IF-UTAMA
11
IF-UTAMA
12
3
SMA* Code
Simple Memory-bounded A* (SMA*) (Example with 3-node memory)
Progress of SMA*. Each node is labeled with its current fcost. Values in parentheses show the value of the best forgotten descendant.
Search space
f = g+h
A 13(15)
= goal
A
A
12
A
A
12
13
G
0+12=12
13
10
8
B
G
10+5=15 10
10
C
H
G
15
13
A 15(15)
A 15(24) A
8 J
8 K
30+0=30
24+0=24
15
B
G
15
I
13
Ex: Rute Perjalanan
n
B
G
20(∞)
15
24
C
25
∞
Optimal & complete if enough memory Can be made to signal when the best solution found might not be optimal - E.g. if J=19 IF-UTAMA
D 20
14
Solusi SMA*
S
A
B
C
D
E
F
G
H
J
K
L
M
h(n) 80
80
60
70
85
74
70
0
40
100
30
20
70
b(n)
10
15
25
30
5
20
90 45
25
50
70
60
0
B
24+5=29
24
IF-UTAMA
A 20(24) 8
24(∞) 30+5=35
18 H
∞
I 24+0=24
10 F
B
16
16+2=18 20+0=20
E
15
8
D
20+5=25 10
B
8+5=13
h(n):heuristic jarak antar suatu kota dan b(n):perkiraan biaya menuju kota asal IF-UTAMA
IF-UTAMA
15
IF-UTAMA
16
4
Algoritma Bi-Directional A* (BDA*) contd.
Algoritma Bi-Directional A* (BDA*) Function BDA*(masalah) return solusi inputs: masalahruang masalah,jenis solusi, start(S) dan goal(G) variable lokal : BNs,Bng{Best node dr start & goal} OPENs,OPENg{open dr start & goal} CLOSEDs, CLOSEDg{Closed dar start & goal} loop sampai goal ditemukan BNs,OPENs,CLOSEDs A*(OPENs,CLOSEDs,S,G) if BNs in CLOSEDs then {goal ditemukan} vsimpul di CLOSEDg yang sama dengan BNs g_terbaik g(G,v) {biaya sebenarnya dari G ke v melalui parent lama} loop untuk semua suk=simpul di CLOSEDg yang merupakan suksesor v if g(G,v) melalui suk < g_terbaik then g_terbaik g(G,v) melalui suk parent_baru suk endif endloop g(v) g_terbaik parent dari v parent_baru returns solusi endif IF-UTAMA
BNg, OPENg, CLOSEDg A*(OPENg, CLOSEDg, G,S) if BNg in CLOSEDg then {goal ditemukan} usimpul di CLOSEDs yang sama dengan BNg g_terbaik g(S,u) {biaya sebenarnya dari S ke u melalui parent lama} loop untuk semua suk=simpul di CLOSEDg yang merupakan suksesor u if g(S,u) melalui suk < g_terbaik then g_terbaik g(S,u) melalui suk parent_baru suk endif endloop g(S,u) g_terbaik parent dari u parent_baru returns solusi endloop end
17
Solusi Bi-Directional A*
IF-UTAMA
18
Modified Bi-Directional A* • Yang dimodifikasi adalah fungsi heuristiknya menjadi – Untuk pencarian maju f(n)=g(S,n) + 0.5 * (h(n) - b(n)) – Untuk pencarian mundur f(n)=g(G,n) + 0.5 * (b(n) - h(n)) Dimana S G g(S,n) g(G,n) h(n) b(n)
IF-UTAMA
IF-UTAMA
19
= node asal atau initial state = node tujuan atau goal state = jarak/biaya sebenarnya dari S ke n = jarak/biaya sebenarnya dari G ke n = heuristik jarak node n = heuristik biaya node n
IF-UTAMA
20
5
Solusi Modified Bi-Directional A*
Dynamic Weighting A* • Fungsi heuristik yang digunakan f(n)=g(S,n)+(w(n) * h(n)) Dimana S G g(S,n) h(n) w(n)
IF-UTAMA
21
Solusi Dynamic Weighting A*
IF-UTAMA
3. 4.
5.
IF-UTAMA
22
Referensi 1. 2.
IF-UTAMA
= node asal atau initial state = node tujuan atau goal state = jarak/biaya sebenarnya dari S ke n = heuristik jarak node n = bobot dari fungsi heuristik
23
Suyanto.2007.”Artificial Intelligence” .Informatika. Bandung -.2010. “Search[online]”. http://wwwusers.cselabs.umn.edu/classes/Fall2010/csci5511/lectures/AIlecture3.ppt.Tanggal Akses : 18 Februari 2011 -.-.“Informed Search [online]”, http://staff.najah.edu/sites/default/files/5_Informed_Search.ppt, Tanggal Akses : 18 Februari 2011 Ramin Halavati.-.” Informed Search and Exploration]”. http://ce.sharif.ir/courses/84-85/2/ce417/resources/root/Slides/AI04a-Informed%20Search%20and%20Exploration.ppt.Tanggal Akses: 18 Februari 2011 Dan sumber-sumber lain yang terkait
IF-UTAMA
24
6
