——————————————————————————————————————————-
Questions
——————————————————————————————————————————-
- Genetic Algorithm:
- 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:
| 5 | B | 8 |
| 4 | 2 | 1 |
| 7 | 3 | 6 |
Goal state (fixed):
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | B |
- At each step show the following
- Initial population (assume to be 10)
- Selection (use Roulette Wheel Selection )
- Crossover (high probability value to be chosen, usually above 0.6)
- Mutation (low probability value to be chosen, usually below 0.2)
- Fitness function: No. of misplaced tiles; Manhattan distance
- Execute for a sufficient number of generations (or, iterations)
- 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.
- 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.
- Output : All the following results should be stored in an output file:
- The success or failure message
- 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:
- h1 (n)= Number of displaced titles. h2 (n)= Total Manhattan distance.
- Constraints to be checked:
- 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?
