–

Questions

–

1. Genetic Algorithm:
   1. Implement the 8 puzzle problem using a genetic algorithm.

Start state (Can take any random order of numbers with B denoting a blank) An Example:

Goal state (fixed):

1. At each step show the following
   1. Initial population (assume to be 10)
   2. Selection (use Roulette Wheel Selection )

• Crossover (high probability value to be chosen, usually above 0.6)

1. Mutation (low probability value to be chosen, usually below 0.2)
2. Fitness function: No. of misplaced tiles; Manhattan distance

1. Execute for a sufficient number of generations (or, iterations)

2. Simulated Annealing

Simulated annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of applied mathematics, namely locating a good approximation to the global minimum of a given function in a large search space.

1. Implement Simulated Annealing Search Algorithm for solving the 8-puzzle problem. Your start and Goal state should follow similar guidelines as given in Q.1.a .

b. Input : Input should be taken from an input file and processed as a matrix. Other inputs are Temperature variable T, heuristic function, neighbourhood generating function, a probability function to decide state change, and a cooling function.

1. Output : All the following results should be stored in an output file:
   1. The success or failure message
   2. Heuristics chosen, Temperature chosen, cooling function chosen, Start state, and Goal state.

• (Sub) Optimal Path (on success), Total number of states explored. v. Total amount of time taken.

• Objective functions to be checked:
  1. h1 (n)= Number of displaced titles. h2 (n)= Total Manhattan distance.

1. Constraints to be checked:
   1. Check whether the heuristics are admissible. What happens if we make a new heuristics h3 (n)= h1 (n) * h2 (n). iii. What happens if you consider the blank tile as another tile. iv. What if the search algorithm got stuck into Local optimum? Isthere any way to get out of this?