A Novel Approach for Optimization of Genetic Algorithm Parameters Used in Solving NP-Complete Problems via the Generic Sudoku N x N Paradigm

Overview

Genetic Algorithms mimic evolution of a species in nature, where each generation is made up of a population of chromosomes, which, through crossover and mutation, evolve increasingly fit offspring. Two crucial parameters in this process are Crossover Rate (CR), and Mutation Rate (MR). The goal of this project was to find a generic way to identify optimal values for CR and MR. A routine was run to optimize CR and MR for the 3x3 and 4x4 Sudoku problems, and those values were used to determine if there was a corresponding reduction in runtime of genetic algorithms to solve a partition problem, and an Image Segmentation problem as it relates to identifying and categorizing skin cancer. I expected optimization via S-3x3 and S-4x4 problems to produce similar CR and MR parameter values, however they ended up being quite different: S-3x3 (CR:29, MR:20) vs S-4x4 (CR:49, MR:6). Due to the size difference of the search space (81 squares for the 3x3 versus 256 for the 4x4), the 4x4 Sudoku optimized parameters proved to be more fine tuned and robust. The following average runtimes in seconds were achieved given a fixed population of 40 chromosomes, A star (*) indicates solution was not found. 4x4 Sudoku 16-Partition Image Seg Benchmark (C50, M20): *177.58s, 5.64s, 40.16s Optimized (C49, M6): 78.35s 5.13s 39.37s Image segmentation quality did not seem to differ between the two sets of parameters. Generically optimizing Crossover Rate and Mutation Rate parameters using the N x N Sudoku grid paradigm did correlate to improved performance in solving other problems. However, unique differences in problem constraints did affect the extent of those gains.

Competition history

• ISEF 2024 Robotics and Intelligent Machines · Entry ROBO045 · Los Angeles, California, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.