Hill Descent with Random Restarts

Rook Jumping Maze Instructions: Starting at the circled cell in the upper-left corner, find a path to the goal cell marked “G”.  From each numbered cell, one may move that exact number of cells horizontally or vertically in a straight line.  How many moves does the shortest path have?

Solution (select to reveal): [19 moves: RDLRUDRLRLUDLDRRUDD]

Problem:  Using a form of stochastic local search called Hill Descent with Random Restarts, search the space of 5-by-5 Rook Jumping Mazes (RJMs) for a given number of iterations and print the best maze evaluated according to the objective function specified by Rook Jumping Maze Evaluation. 

One problem with pure hill descent is that stochastic local search may become trapped in local minima, where every local step is uphill, making things worse.  One escape strategy is to restart search periodically.  Another way of viewing this is that we iteratively perform pure hill descent, starting each descent at a random state.  The end result is the best result from all descents.   

Using the definitions of hill descent, we may describe our modified algorithm as follows:

• Let j be chosen at random, and j_best ← j.
• For a given number of searches:
• For a given number of iterations:
•  j' ← step(j)
• if  e(j') £ e(j)
• j ← j'
• if  e(j) £ e(j_best)
• j_best ← j
• Let j be chosen at random.
• return j_best

Possible background readings include:

• Russell and Norvig. Artificial Intelligence: A Modern Approach, 3rd edition, Chapter 4 through section 4.1.1 (hill-climbing search).  Here we implement hill descent with random restarts (the iterative reverse of hill climbing) allowing sideways moves. 
• Hoos & Stützle. Stochastic Local Search: Foundations and Applications, section 1.5 (Stochastic Local Search).  The escape strategy used here varies from Hoos & Stützle's "restart strategy" in that we do not know whether or not we are in a local minimum.  In general, it is difficult to tell a local minimum from a search plateau.
• Wikipedia article on "Hill climbing". 

Input Format: 

• a positive integer number of iterations for hill descent optimization
• a positive integer number of hill descents

Output Format:

• Initially prompt the user with "Iterations? " and "Hill descents? ".
• After all hill descents, print the RJM with the best (minimum) objective function evaluation according to the Rook Jumping Maze Evaluation output specification.

Sample Transcripts (input underlined):

Iterations? 10000
Hill descents? 1
2 1 1 4 3 
2 2 3 1 4 
3 2 2 3 3 
3 3 1 1 3 
4 1 3 4 0 

Moves from start:
 0  2  1  2  6 
 6  3  2  4  5 
 1 12 10  2 11 
 7  4  9  8  5 
14 13  3  3 15 

-15

Iterations? 1000
Hill descents? 10
3 4 3 4 3 
2 2 3 3 2 
4 1 1 2 1 
3 2 1 2 3 
3 3 4 4 0 

Moves from start:
 0 15  7  1 14 
 4  4  5  3 13 
11 10  9 10 12 
 1  3  8  2 13 
-- 16  6  2 17 

-17

Iterations? 100
Hill descents? 100
1 2 2 2 1 
1 3 1 2 2 
1 2 2 3 4 
2 1 3 3 2 
1 2 2 4 0 

Moves from start:
 0  1  5  2  6 
 1  2  4  5  3 
 2  2  5  3  6 
 3 --  4  6  4 
 7  3  6  4  7 

-7

Questions:

1. Empirically, keeping the total number of iterations (i.e. descents times iterations per descent) constant (e.g. 10,000), approximately how many restarts yields the best average generated maze?
2. For which kind of optimization tasks is it better not to restart search? That is, for which kinds of functions or iteration constraints is it better to do a single descent for all iterations?

Todd Neller