Description
1. Implement 5-queens problem solvers using the hill-climbing algorithm and the genetic algorithm.
(a) (30 points) Implement a program that performs the hill-Climbing algorithm to
find a solution.
(b) (30 points) Implement a program that performs the genetic algorithm with 8
states including the three operations, i.e., selection, crossover, mutation to find
a solution.
Program specification.
i. You can use numpy library.
ii. Find the board.py, and please do not modify it.
iii. An initial state locates a queen per each row. Please use an appropriate and simple
local search strategy.
iv. The function get fitness in the board.py returns the number of attacking
pairs. It assumes a queen per each row, which means it checks only columns and
diagonals.
v. The hill-climbing algorithms can stuck in local minima. Please implement the
random restart procedure when they stuck.
vi. Please report running time and a solution.
Running time: 200ms
1 – – – –
– – – 1 –
– 1 – – –
– – – – 1
– – 1 – –
vii. Submit hill.py and genetic.py.
