Booth Id:
ROBO045
Category:
Robotics and Intelligent Machines
Year:
2024
Finalist Names:
Teeples, Sky (School: Provo High School)
Abstract:
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.