![]() ![]() Simulated annealing is a stochastic process and people often adjust the ‘cooling process’ to speed up finding a good solution. As the “temperature slowly cools down” after each iteration, the probability of accepting a random solution went down, so the algorithm is forced to find solutions that are better than the candidate solution. This gives more opportunity to the algorithm to explore in the early stage. In the beginning of the “annealing” process while the “temperature is hot”(temperature is a parameter set by the user), the “shape of the iron” is more flexible (the search space for different solutions is big), therefore, a new solution would have a higher chance to be accepted even if the solution proposed is not better than the candidate solution. Simulated annealing is a simple algorithm: the candidate solution is updated if the new solution generated is better than the candidate solution (measured by the loss function) or by random chance. You can find the comparison of two algorithms in this paper. Simulated annealingĭifferent from the genetic algorithm, where a population of solutions are generated and optimized in each generation in search of a better solution, simulated annealing is an iterative procedure that continuously updates one candidate solution until a termination condition is reached. In summary, it is able to find a solution quickly in simple puzzles, however, for difficult ones, it is likely trapped in the suboptimal search space. I compared the results of solving three Sudoku puzzles with different difficulties using the genetic algorithm, you can find them in this notebook. When the top performer from a generation has no rol-wise and col-wise error, we find the answer to the puzzle. Therefore, the best performer of the next generation Soduku solutions would be better or at least the same as the best performer from the current generation. While elite solutions from a generation are kept to the next generation to ensure good minimum performances, crossing over and mutations are done to generate additional and potential better solutions. The below figure illustrates my implementation of a cross-over and a mutation. The next generation will then have 100 solutions (30 elites from the previous generation, 35 from crossing over, 35 from mutations). Mutation can be done by randomly swapping two numbers from a chosen block using solutions from the current generation pool, we can form some (e.g 35) solutions this way. Cross over is done by taking a percentage of two randomly sampled solutions from the current generation to form a new solution, we can form some (e.g 35) solutions this way. The rest of the solutions of the next generation are made with cross-overs and mutations. The genetic algorithm mimics the natural evolution, where for each generation (iteration), a fixed number of solutions (e.g N = 100, N is also called a population) are generated and evaluated, the ones with the greatest fitnesses (e.g top 30%, 100 x 30% = 30 solutions, also called elites) are going to be kept to the next generation. (black: given puzzle, blue: correctly predicted numbers, red: incorrectly predicted numbers, green: correct number of incorrectly predicted position) The below example has a quality score of 2. The quality of a potential solution = number of overlapping numbers row-wise + number of overlapping numbers column-wise Below is the formula I used to measure the overall accuracy of a potential solution, the correct solution should have a value 0, meaning there are no overlapping numbers for each row or column. In both methods shown here, Sudoku is solved by filling each block with nine unique numbers, this means only the column and row constraints would need to be checked. Metric to measure how good a solution is (loss function)īefore thinking about what approach to use, it is important to come up with a measure for the accuracy of a solution. Note that neither of these two approaches is guaranteed to find the best/correct solution, but they can find a close form solution relative quickly. Both of them are search algorithms aiming to find the optimal solution by iteratively evaluating the current solution and update the search by comparing against the previous round of solution. In this blog post, I will show you two independent machine learning methods in solving Sudoku puzzles, one is Genetic Algorithm, the other is Simulated Annealing. My last blog post was about how to solve Sudoku with Simple Data Science Tricks such as backtracking, it was smart, however, what if in a project like this we don’t have access to the optimal method? Can we use machine learning methods to search for a good solution? Solving Sudoku with machine learning methods - genetic algorithm and simulated annealing ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |