Advanced Search

For these advanced searches, the goal is to find a node n such that f(n) ≥ f(i) for all nodes i in the state space. The goal is to find the state with the highest score.

Hill-Climbing

Looks at all immediate neighbors of current state m to find a successor n such that f(n) > f(m) and f(n) \geq f(t) for all successors t of m, then move from m to n. If no such n is found, halt.

Not complete, terminates at local maxima.

Pseudocode

1. Pick initial state s
2. Pick t in neighbors(s) with largest f(t)
3. if(f(t) ≤ f(s)) then STOP, return s
4. s = t. GOTO 2

Repeated Hill Climbing with Random Restarts

1. When stuck, pick random new start and run basic hill climbing
2. Repeat k times
3. Return the best of the k local optima

Simulated Annealing

Instead of picking the best move, simulated annealing picks a random move and checks successor. If the successor is an improvement over the current state, the move is made; otherwise make the move with some small probability < 1. The probability decreases exponentially with the badness of the move.

Pseudocode

1. Pick initial state s
2. Randomly pick t in the neighbors(s)
3. if(f(t) better) then accept s ← t
4. else accept s ← t with small probability
5. GOTO 2 until bored

Genetic Algorithm

Pseudocode

1. Let s₁,...,s_N be the current population
2. Let p_i = f(s_i)/∑_jf(s_j) be the reproduction probability
3. for(k = 1; k < N; k += 2)
• parent1 = randomly pick according to p
• parent2 = randomly pick another
• randomly select a crossover point, swap strings of parents 1, 2 to generate childern t[k], t[k+1]
4. for(k = 1; k ≤ N; k++)
• randomly mutate each position in t[k] with a small probability (mutation rate)
5. The new generation replaces the old: {s} ← {t}. Repeat.