In this work, we experimentally verify if a population of genetic algorithms employing weak selection converges to a population composed exclusively of models. We investigate the minimum vertex cover problem, the minimum dominating set problem, and the 3-coloring problem. In doing so, we extend the work of Livnat et al., who established this property for the satisfiability problem, and Šircelj, who examined the satisfiability problem through experimental analysis.
We detail the selection of parameter values used for the experimental evaluation of each problem. The experiments were conducted using varying values of the weak selection parameter and population size. We used two types of reproduction; product reproduction and recombination. We also used both methods in combination with mutation.
For the minimum vertex cover and minimum dominating set problems, we demonstrate that, given a sufficiently large product of population size and the weak selection parameter, the population converges to a population of models. However, these models are qualitatively inferior to the optimal solutions. In the case of the 3-coloring problem, convergence to a model population was observed only in a limited number of instances.
|
