ITCS 3153: Introduction to Artificial IntelligenceIn-class assignmentLocal SearchImplement a Simulated Annealing algorithm to solve the N-queens problem. You mayuse the nqueens.py script in Canvas files that provides a Board class, number ofattacking queens heuristic cost function, and getSuccessorStates function.Guidelines:1. Use an linear scheduling function: f(T) = T*decay_rate where decay_rate
...[Show More]
ITCS 3153: Introduction to Artificial Intelligence
In-class assignment
Local Search
Implement a Simulated Annealing algorithm to solve the N-queens problem. You may
use the nqueens.py script in Canvas files that provides a Board class, number of
attacking queens heuristic cost function, and getSuccessorStates function.
Guidelines:
1. Use an linear scheduling function: f(T) = T*decay_rate where decay_rate is a
constant in range (0,1). Note that this function is taking the current
temperature as the input, not the time value “t”. At each iteration, pass in T to
your scheduling function and return a new T value. Do not use the “t” value
shown in the textbook.
2. Set initial T=100.
3. Terminate the algorithm if T is smaller than a threshold value, e.g., 0.00001.
a. Note that this is not the only termination condition.
4. Try different pairs of decay_rate and the threshold for T to terminate the loop:
a. decay_rate=0.9, T=0.000001
b. decay_rate=0.75, T=0.0000001
c. decay_rate=0.5, T=0.00000001
Create a loop to run 10 simulated annealing executions with each of the above decay
rate and T threshold pairs (5a-5c). Each run should have a random starting board of the
same size. For each run, print the following information to console:
a) Initial state and its h-value
b) Final state and its h-value
For each pair of decay rate and T threshold values, print out:
c) Decay rate
d) Threshold for T
e) Average h-value of the final solutions over all 10 runs
Then, create another loop to increase the board size. Use the following board sizes: 4,
8, and 16.
Example final output: (your output should be readable and organized, but doesn’t need
to be exactly like this)
**********************************
Board size: 4
**********************************
######################################
Decay rate 0.9 T Threshold: 1e-06
######################################
Run 0
Initial board:
[1, 0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
[0, 0, 0, 1]
h-value: 6
Final board h value: 2
[0, 0, 1, 0]
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
Run 1
Initial board:
[0, 0, 1, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 1, 0, 0]
h-value: 6
Final board h value: 2
[Show Less]
-preview.jpeg)
-preview.jpeg)
-preview.jpeg)
