Sudoku Genetic Algorithms

This assignment will give you a feel for using a generic GA engine as well as implementation of the major components of a GA loop. You are given an annotated [login to view URL] file that you can use as a template to build your own solution. You need to chose a representation. This includes the data structure you use to represent a candidate solution -an individual- and the semantic meaning of each part of your structure. For example, you may chose to represent a solution as a 9  9 multi-dimensional array with digits as items. This may not be the most efficient method in terms of memory requirements and coding complexity since you will need to differentiate the given numbers from the numbers you put yourself. Remember, the solution has to obey the Sudoku rules and it needs to be compatible with the input. The next thing to think of is the metric, the fitness, to assess the quality of your individuals. The evaluator function will assign a value to each individual based on their estimated distance to the solution. You may want to go with a minimization problem or a maximization problem based on how you define the heuristic. If your evaluator assigns smaller values to better individuals, then you have a minimization problem. You will need to define a crossover operator that is compatible with your representation. How will you pair the individuals? How will you merge the genetic material they contain in order to create the offspring? To what extend are you going to allow infeasible solutions? Will you attempt to repair any damage? Amutation operator is also necessary to inject some randomness into your population. Once again, you have to craft a mutation operator for your choice of representation. This generally involves randomly choosing a gene [sequence] and replacing it with some randomly generated genes. Once you have all these operators in-pace, you can run the algorithm on the given inputs. The code can already parse the input for you. You are expected to print out the solved board once you have the solution. A reference implementation can solve all inputs in about a minute per problem, but not on every execution. Submit the completed [login to view URL] file through the METU-Online system.