[SOLVED] (CS571) Assignment-2

——————————————————————————————————————————-

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?