📐 Multi-objective Optimization
Research on evolutionary and metaheuristic approaches to multi-objective optimization, Pareto front approximation, heterogeneous objectives, and multi-objective reinforcement learning.
Multi-objective optimization (MOO) concerns the simultaneous optimization of two or more conflicting objectives. Unlike single-objective optimization, MOO typically produces a set of trade-off solutions — the Pareto front — rather than a single optimal solution. My research on MOO has developed both novel algorithms and benchmark problems, with a particular focus on combinatorial problems, heterogeneous objectives, and the connection between MOO and reinforcement learning.
Foundations of Multi-objective Optimization
Pareto Optimality and Trade-off Analysis
The Pareto optimality concept lies at the heart of multi-objective optimization: a solution is Pareto-optimal if no objective can be improved without deteriorating at least one other objective. The set of all Pareto-optimal solutions is the Pareto front. Research has examined the properties of Pareto fronts for different problem classes and the computational challenges of approximating them efficiently.
Performance Indicators
Development and evaluation of performance indicators for multi-objective optimization algorithms, including the hypervolume indicator, the inverted generational distance (IGD), and the epsilon indicator. Research on the properties of these indicators, their sensitivity to different aspects of Pareto front quality, and their use as objectives in indicator-based evolutionary algorithms.
Multi-objective Evolutionary Algorithms (MOEAs)
MOEA/D and Decomposition-Based MOEAs
Research on decomposition-based multi-objective evolutionary algorithms, particularly MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). MOEA/D decomposes the multi-objective problem into a set of scalar subproblems and solves them simultaneously using a population of agents. Research includes the analysis of weight vector design, neighborhood size, and update strategies.
NSGA-II and Dominance-Based MOEAs
Evaluation and development of Pareto dominance-based multi-objective evolutionary algorithms, including NSGA-II and its variants. Analysis of how crowding distance, diversity maintenance, and selection pressure affect algorithm performance on benchmark and real-world multi-objective problems.
Estimation of Distribution for MOO
Development of multi-objective EDAs that use probabilistic graphical models to capture dependencies among decision variables and guide the search towards promising regions of the Pareto front. Application to the multi-objective NK landscape problem and analysis of Bayesian network learning techniques for hybrid multi-objective Bayesian EDAs.
Bi-objective Problems with Heterogeneous Objectives
Combinatorial Optimization with Mixed Objectives
Research on bi-objective combinatorial optimization problems where the objectives are of different types — for example, one continuous and one discrete objective. These "heterogeneous" bi-objective problems arise naturally in real-world applications such as logistics (minimizing cost and maximizing quality), scheduling (minimizing makespan and minimizing energy consumption), and engineering design.
NK Landscapes with Heterogeneous Objectives
Development of the multi-objective NK landscape benchmark with heterogeneous objectives — where different objectives have different numbers of epistatic interactions. Analysis of how heterogeneity in objective landscape structures affects the properties of the Pareto front and the performance of multi-objective evolutionary algorithms.
Multi-objective Hamiltonian Cycle
Application of branch-and-fix exact algorithms to the multi-objective Hamiltonian cycle problem. Development of exact methods that can find all Pareto-optimal solutions for this NP-hard combinatorial problem, with analysis of the trade-offs between solution quality and computational cost.
MOO for Reinforcement Learning
Benchmarking MOEAs for Continuous Multi-objective RL
Systematic benchmarking of multi-objective evolutionary algorithms (MOEAs) for solving continuous multi-objective reinforcement learning (RL) problems. The study compares NSGA-II, MOEA/D, and other state-of-the-art MOEAs on a suite of continuous multi-objective RL benchmark environments, analyzing their strengths and weaknesses.
Combinatorial Multi-objective Problems
Bi-objective Traveling Thief Problem (TTP)
Research on evolutionary approaches to the bi-objective traveling thief problem — a complex combinatorial problem combining the traveling salesman problem with a knapsack problem. Development of algorithms with adaptive operators that adjust their search behavior based on the current state of the population and the Pareto front approximation.
Back-Drive in Multi-objective Evolutionary Algorithms
Research on "back-drive" — a mechanism that re-introduces information from previously discarded solutions into the evolutionary search — and its benefits for multi-objective evolutionary algorithms. Analysis of how back-drive can improve diversity maintenance and Pareto front coverage in difficult multi-objective optimization problems.
Selected Publications
- Karshenas H, Santana R, Bielza C and Larrañaga P (2014). Multiobjective Estimation of Distribution Algorithm Based on Joint Modeling of Objectives and Variables. IEEE TEVC.
- Karshenas H, Santana R, Bielza C and Larrañaga P (2012). Multi-objective optimization based on joint probabilistic modeling of objectives and variables. PPSN 2012.
- Karshenas H, Santana R, Bielza C and Larrañaga P (2011). Multi-objective optimization with joint probabilistic modeling of objectives and variables. EMO 2011.
- Martins MS, Delgado MR, Santana R, Lüders R, Gonçalves RA and Almeida CPd (2016). HMOBEDA: Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm. GECCO 2016.
- Martins MSR, Delgado M, Lüders R, Santana R, Gonçalves RA and de Almeida CP (2017). Probabilistic analysis of Pareto Front approximation for a hybrid multi-objective Bayesian estimation of distribution algorithm. LION 11.
- Martins MS, Delgado MR, Lüders R, Santana R, Gonçalves RA and Almeida CPd (2018). Hybrid multi-objective Bayesian estimation of distribution algorithm: a comparative analysis for the multi-objective knapsack problem. JORS.
- Martins MS, Delgado MR, Lüders R, Santana R, Gonçalves RA and Almeida CPd (2018). Exploring the probabilistic graphic model of a hybrid multi-objective Bayesian estimation of distribution algorithm. GECCO 2018.
- Martins MSR, El-Yafrani M, Santana R, Delgado M, Lueders R and Ahiod B (2018). On the performance of multi-objective estimation of distribution algorithms for combinatorial problems. CEC 2018.
- Martins MS et al. (2021). Analysis of Bayesian Network Learning Techniques for a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm. CODA 2021.
- Murua M, Galar D and Santana R (2022). Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm. Journal of Computational Science.
- Murua M, Galar D and Santana R (2020). Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem. CEC 2020.
- Santana R and Shakya S (2020). Dynamic programming operators for bi-objective TTP problem. GECCO 2020.
- Cosson R, Santana R, Derbel B and Liefooghe A (2022). Multi-objective NK landscapes with heterogeneous objectives. GECCO 2022.
- Strickler A, Castro Jr O, Pozo A and Santana R (2016). Investigating selection strategies in multi-objective probabilistic model based algorithms. GECCO 2016.
- Zangari-de-Souza M, Santana R, Mendiburu A, Bengoetxea E and Pozo A (2015). MOEA/D-GM: Using probabilistic graphical models in MOEA/D for solving combinatorial optimization problems. CEC 2015.
- Zangari-de-Souza M, Mendiburu A, Santana R and Pozo A (2017). Multiobjective Decomposition-based Mallows Models Estimation of Distribution Algorithm. GECCO 2017.
- Zangari-de-Souza M, Mendiburu A, Santana R and Pozo A (2017). A decomposition-based binary ACO algorithm for the multiobjective UBQP. CEC 2017.
- Rodrigues EM, Santana R and Pozo A (2016). Transfer weight functions for injecting problem information in the multi-objective CMA-ES. GECCO 2016.
- Rodrigues EM, Santana R and Pozo A (2017). Combining CMA-ES and MOEA/DD for many-objective optimization. CEC 2017.
- Santana R, Bielza C, Lozano JA and Larrañaga P (2009). Mining probabilistic models learned by EDAs in the optimization of multi-objective problems. GECCO 2009.
- Lima RM et al. (2018). Evolutionary Multi-Objective System Design: Theory and Applications. CRC Press.
- Fritsche G, Strickler A, Pozo A and Santana R (2015). Capturing Relationships in Multi-Objective Optimization. Brazilian Conference on Intelligent Systems.