Toward an improvement of the genetic algorithm

Abstract

A considerable amount of research has been conducted on the optimization of genetic algorithms, what lead to a wide range of different genetic operators and solution representations; however, parameter tuning, which is a very crucial part of the good performance of the algorithm, is rarely discussed. This step can be considered a search for a set of good parameters that maximize the performance of the algorithm. Taking this into consideration, we can say that this process is a double search search for good parameters, then search for a solution. In this work, we propose a genetic algorithm that combines the two search spaces, where a chromosome does not only represent a solution to the problem at hand but a set of genetic parameters too. This method achieved a 4% increase in performance compared to the classic genetic algorithms. This result was reached after comparing the performance of our methods with all the combinations of genetic operators found in the state of the art, taking into consideration the temporal and hardware limitations. Furthermore, this search space unification led to the elimination of the need to initialize parameters for each problem, which made it problem-independent. Keywords: NP-completeness, MAX-SAT, Evolutionary Algorithms, Genetic Algorithm, Parameter tuning.