Genetic Algorithms for Discrete Bayesian Optimization

Optimization methods represent a powerful instrument widely used in science, industry and economic applications, where each process is characterized by a certain potential to be optimized. This function, properly known as “objective function”, could be a measure of expended time, costs, profits, quality, but, in many cases, we may not know its structure or even it may be expensive to evaluate it: we talk about expensive black-box functions. Bayesian Optimization is the main optimization strategy used to solve this class of problems. It is based on two main components, a Gaussian Process, used as surrogate model for the objective function, and an acquisition function that guides the decision about the next to evaluate point. The major weakness of this strategy is the fact that the problem variables are broadly supposed to be continuous, whereas in real-world applications we usually face with categorical or integer-valued variables. Common approaches used to overcome this limit are either to round the continuous value to the closest integer or to manipulate the exploration proposed by the acquisition function or to change the surrogate model adopted. Using the existing methods as a benchmark, we propose an alternative approach characterized by the application of metaheuristics strategies in the manipulation of search space exploration of standard Bayesian Optimization. Metaheuristics are a class of optimization methods commonly used to solve instances of a problem which are believed hard in general, reducing the effective size of the search space and exploring it efficiently. We will focus in particular on two subclasses, the Local Search metaheuristics and the Genetic Algorithms. Firstly we illustrate the two proposed methods from a theoretical point of view. The Local Search Bayesian Optimization (LSBO) introduces the Local Search approach in the generation of the neighbourhood of the current solution and so in the definition of the subset of points on which to evaluate the acquisition function to detect the next candidate solution. The Genetic Bayesian Optimization (GBO) uses instead a Genetic Algorithm approach to guarantee a wide and efficient space exploration. We don’t focus in this case on the current solution only, but on a population of parents selected through a quasi-elitist strategy. The neighbours, offspring of the selected population, are generated by applying mutation and recombination operators on them. The aim of this second method is not to lose the information provided by the correlation among variables and exploit it in the reproduction phase. In support of our optimization methods, a case study application on Mobile Networks is brought up. Here we focus on a configuration of 12 telecommunication antennas, each of which can assume 5 different values. These represent the discrete variables of the problem, which is so characterized by a large solution search space. The goal of our work is to provide an automated optimization solution that, relying on real-time measures and key performance indicators, proposes the optimal network configuration.