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
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.
Mathematical Programming
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:
EDAs
Genetic Programming
Multi-objective optimization
Fitness landscapes and benchmarking