Reducing the search area of genetic algorithm using neural network autoencoder

Abstract

The article discusses the problem of developing a genetic representation for solving optimization problems by means of genetic algorithms. Traditionally, a genotype representation is a set of N features that defines an N-dimensional genotype space in which algorithm performs a search for the solution. Due to the non-optimal choice of features, the genotype space becomes redundant, the search area for a solution unnecessary increases, which slows down the convergence to the optimum, and leads to the generation of infeasible candidates for the constraints of the problem. The reason for this is the desire to cover all legal candidates for solution of the problem by the search area, since the optimum is feasible by the conditions of the problem. In constrained optimization problems, to find the optimum, it would be sufficient to cover only the area of feasible candidates that fall within the constraints specified by the problem. Since the set of feasible candidates is smaller than the set of all legal candidates, the search area may be narrower. The search area can be reduced by obtaining a more efficient set of features that is representative of the set of feasible solutions. But in the case of a small amount of domain knowledge, developing of an optimal feature set can be a nontrivial task. In this paper, we propose the use of feature learning methods from a sample of feasible solutions that fall under the constraints of the optimization problem. A neural network autoencoder is used as such a method. It is shown that the use of the preparatory stage of learning a set of features for constructing an optimal genotype representation allows to significantly accelerate the convergence of the genetic process to the optimum, making it possible to find candidates of high fitness for a smaller number of iterations of the algorithm.