Combinatorial optimization problems
Combinatorial optimization problems are usually represented with a discrete representation, and the number of solutions in the search space is exponential in the number of variables. Genetic algorithms and estimation of distribution algorithms (EDAs) are optimization methods extensively applied to these problems.
Research that describe the use of EDAs for finding the minimal energy configuration of the Ising model problem are described in Santana:2005, Santana_and_Mendiburu:2013, where Markov-network based EDAs are applied; and in Echegoyen_et_al:2012, where EDAs based on Bayesian networks are used. EDAs that incorporate inference methods based on message passing are used to solve the Ising model in Santana_et_al:2013f. In all these previous examples, the Ising model is defined on the typical 2d-lattice. An investigation of EDAs and other optimization methods for the Ising model defined on chimera topologies is presented in Santana_et_al:2016.
Other combinatorial problems that we have approached using EDAs are the Max-SAT problem, Santana_et_al:2008b, Echegoyen_et_al:2009a, Echegoyen_et_al:2012; and the NK-model of fitness landscapes Santana_et_al:2012e, Santana_et_al:2012j, Martins_et_al:2018b, Cosson_et_al:2022. Combinatorial problems defined on permutation representation, such as the quadratic assignment problem have been investigated in Ceberio_et_al:2015.
Bayesian optimization is an efficient optimization methods that requires a relatively small number of evaluations and therefore can be applied to very costly functions.
One question to be solved by BO applications is kernel selection, i.e., how to select the kernel function of the Gaussian process according to the characteristics of the optimization problem. In Roman_et_al:2014, Roman_et_al:2019c, we propose different dynamic kernel selection criteria for BO.
Another important challenge for BO is the existence of functions with that many optimal solutions, where some of them are local and some others are global. This type of problems, that has deserved more attention in the field of evolutionary computation is investigated in Roman_et_al:2019a for BO.
For integer problems, the mathematical programming formulation is usually applied together with some branch-and-bound search strategy that allows a more efficient search for solutions. Key questions in this domain are how to increase the scalability of the approach to problems with more variables and how to increase the computational efficiency of the algorithm.
One of the combinatorial problems that can be addressed with a mathematical programming formulation is the Hamiltonian Cycle Problem (HCP). In Murua_et_al:2020a, Murua_et_al:2022, we have proposed an adaptation of a branching algorithm to solve a multi-objective variant of the HCP. The approach incorporates information about the dominance relationships between partial solutions and complete solutions as part of the branch-and-bound search.
Applications in industry, transportation, and services
Real-world optimization problems are usually more difficult to tackle and complex to solve. They exhibit characteristics that require a careful selection of the problem representation and constraints.
The vehicle routing problem is an example of constrained problems that determine a large number of unfeasible solutions. In Santana_et_al:2017, we present a comparison of probabilistic-based optimization approaches for the problem of finding an optimal set of routes for a fleet of vehicles that have to serve a number of customers.
Additive manufacturing is one area where several optimization problems arise. For example, the direct energy deposition technology requires de solution of the tool-path problem. In Murua_et_al:2020, we introduce the sequence strategy generation and an optimization algorithm to solve it. Another area where optimization is essential is in the energy sector. In Garcia_and_Santana:2021, we proposed a unified framework for the analysis of the effect of control policies on automatic voltage regulators. We constrain the analysis to the formalization of the optimization problem.
Recently, attention of the EA community has been given to the design of optimization benchmarks that could capture some of the complexities of real-world optimization problems. The traveling-thief problem (TTP) combines characteristics of the TSP and the knapsack problem. We introduce different approaches for multi-objective variants of this problem in Santana_and_Shakya:2020, Santana_and_Shakya:2022.
Evolutionary Algorithms (EAs)
Evolutionary algorithms are population-based optimization methods inspired in the theory of natural selection. Our main research directions on EAs include the following areas:
Fitness landscapes and benchmarking