Research Objectives

Frontiers in Massive Optimization and Computational Intelligence

Optimization is ubiquitous to countless modern engineering and scientific applications, and implies problems and algorithms increasingly large-scale and heterogeneous to deal with a huge number of variables and conflicting objectives of different nature, and to face multiple sources of uncertainty. For instance, many optimization problems within the context of sustainable systems, multidisciplinary engineering design and innovation are increasingly complex, and involve large-size instances, cross-domain formulations and heterogeneous objectives, as well as multiple sources of uncertainty. Such characteristics lead to massive optimization problems, and raise new important and difficult scientific challenges for researchers and practitioners, that traditional approaches will hardly succeed when facing them. Those techniques shall be taken to the next level for solving heterogeneous problem classes, with a large number of variables and objectives. What is needed is to push the boundaries of existing optimization approaches, to go beyond the small-scale problems investigated so far in the literature, and to design innovative flexible general-purpose computational intelligence algorithms able to efficiently and effectively tackle such massive optimization problems.

Although some research dealing with the aforementioned characteristics can be found, we aim at proposing a unified approach tackling the issues from today’s complex application domains. In particular, our research group is interested in setting up the foundations and developing cutting-edge autonomous solvers able to globally and jointly address the challenges encountered in problems from massive optimization:

1. Large-scale optimization problems, which commonly involve hundreds of variables that induce a large increase in the solution space where the optimization algorithm operates.
2. Any-objective optimization problems, where one, multiple, or many criteria are to be simultaneously optimized, typically leading to a significant increase in the number of optimal trade-offs to be identified.
3. Cross-domain optimization problems, dealing with continuous, integer, categorical variables, or even more complex structures such as permutations, strings, trees, or graphs, that may be mixed among themselves.
4. Expensive optimization problems, where the propagation of environmental parameters or the requirement of heavy simulations makes it already computationally demanding to obtain the quality of one single candidate solution at the evaluation stage.

The general goal is to foster the next generation of optimization algorithms for solving such problems from the incoming "big" era by precisely investigating the modeling, the algorithmic resolution as well as the fundamental and experimental analysis of massive optimization problems, with a clear emphasis on their multi-objective nature. Arguing that such massive optimization problems raise new challenges, in particular because of (a) their dimensionality in terms of variables, (b) of objectives, (c) their heterogeneity, and (d) their expensive nature, our research program aims at jointly addressing them, and is organized following four interconnected scientific objectives.

Research Objective #1 — Landscape-aware optimization algorithms

The class of optimization problems encountered in real-life complex application domains is wide and heterogeneous. This explains the plethora of ad-hoc optimization techniques specialized in solving a particular problem formulation. On the contrary, general-purpose optimization methods such as branch-&-bound (complete, but quickly impractical for large-size problems) and general-purpose search heuristics from computational intelligence (e.g. stochastic local search, meta-heuristics, evolutionary algorithms) constitute upper-level methodologies that can be used as guiding strategies in designing underlying optimization algorithms. One of the goal of MODŌ precisely lies in the foundation, analysis and intelligent design of enhanced general-purpose optimization algorithms, search paradigms and their design principles, as well as innovative ways of combining them. However, being effective and efficient in solving the target problem always requires a proper configuration and adaptation of the general-purpose optimization approach. As such, most algorithms continue to be designed on the basis of intuition, and require an intensive phase of trials and errors for parameter setting. One way of addressing this in practice is to rely on parameter tuning in order to automatically configure an optimization algorithm by finding the most appropriate parameter setting, specialized for a given set of problem instances. Complementarily, we aim at avoiding hyper-specialized approaches, and at improving the way we develop optimization algorithms by incorporating a more fundamental approach in their design process. Our goal is to understand the difficulties a given optimization approach has to face, and what makes it efficient, independently of the target application, by deriving high-level and relevant features able to catch problem difficulty by means of tools from fitness landscape analysis, graph theory, statistics and machine learning data analysis. Such an analytics-driven methodology, based on fitness landscape analysis and extensive benchmarking efforts, would allow us, not only to understand what makes a problem difficult or an optimization approach efficient, but also to predict the algorithm performance, to select the most appropriate configuration from an algorithm portfolio, and to adapt and improve the algorithm design for unknown optimization domain and problem instances. Such a cross-domain autonomous solver would adaptively adjust its internal mechanisms in order to fully take advantage of the opportunities offered by the target massive optimization problem.

Research Objective #2 — Model-assisted optimization algorithms

In expensive optimization, evaluating the quality of a candidate solution is particularly demanding computationally speaking. This is typically the case when this evaluation step corresponds to the result of a (black-box) complex system simulation, or because of the large number of environmental parameters encountered in multidisciplinary engineering design and innovation, as well as sustainable systems. In this context, existing algorithms from optimization and computational intelligence suffer from slow convergence, and their scalability then raises new scientific challenges. To overcome this, we will rely on surrogate models and machine learning algorithms in order to predict the solutions quality without systematically computing their (expensive) objective value(s). The goal here is to accelerate the convergence of the optimization process and to improve the quality of final solutions. More particularly, we will focus on the suitability of advanced statistical and machine learning meta-models for large-scale optimization, the choice of the output to be predicted by these meta-models, their prediction accuracy and their parameter sensibility, the uncertainties and inaccuracies occurring in their responses, the choice of the data set from which the meta-model learns from, and the integration of the learning phase within the optimization process. Because of the target application context, the computational cost of designed approaches is prohibitive. As a consequence, we will attach a particular attention to distributed approaches for addressing these different issues, with an effective parallelization on high performance computing platforms. Complementarily, we will investigate estimation-of-distribution and other model-assisted computational intelligence algorithms, that consist in explicitly modeling the key features (such as variable interactions) that impact solutions quality, and to use this model as an algorithm component in order to produce new candidate solutions with an expected improved quality.

Research Objective #3 — Decomposition-based optimization algorithms

Given the large-scale nature of the target applications and the underlying optimization problems, in terms of the number of variables and objectives, a natural answer is to decompose the original global massive optimization problem to be solved into several sub-problems for which solutions are computed and aggregated taking inspiration from the “divide and conquer” paradigm. However, setting up an effective decomposition-based optimization approach relies on the design and integration of several components that are to be configured accurately. First, we will address the definition of the set of sub-problems to be solved cooperatively, by decomposing the original problem into a set of sub-problems within a smaller region of the variable space and/or the objective space, so as to increase the efficiency of the optimization process. Second, we will design cooperative computational intelligence algorithms and mechanisms in order to solve each sub-problem, and to specify the local rules of interaction and cooperation governing the global optimization process. The idea is to view the solving of an optimization problem as a complex system operating at different local parts (the sub-problems), so that the overall global computational power is eventually larger than the sum of its parts. At last, we will take advantage from the decentralized nature of decomposition-based approaches in order to deploy them efficiently on large-scale distributed and parallel platforms. In addition, decomposition-based optimization approaches will open important challenges in the design of new ways of combining general-purpose search heuristics (e.g. stochastic local search, meta-heuristics, evolutionary algorithms) with exact algorithms (e.g. mathematical programming, dynamic programming) and/or machine learning algorithms in order to solve massive optimization problems.

Research Objective #4 — Decentralized parallel optimization algorithms

The purpose of this research topic is to push forward the design, study, and validation of generic approaches addressing the big nature of nowadays optimization problems, through the investigation of appropriate optimization techniques that can fit in the large-scale and distributed nature of modern compute facilities. On the one hand, the power of modern and massively parallel compute platforms is becoming both huge and increasingly available for the community. Distributed large-scale high-speed interconnected CPUs, together with multi-core processors, many-core accelerators and co-processors, are without a doubt increasingly popular and widely deployed, not only in high-performance dedicated clusters and grids, but also in non-expert oriented environments such as distributed workstations and cloud compute facilities. On the other hand, and following the evolution of modern computational science, the characteristics of massive optimization give rise to difficult challenges, beyond the ability of commonly-used optimization algorithms. In this respect, there is evidence that decentralized evolutionary computing will play a crucially important role in order to foster the next generation of optimization techniques, and to accelerate their widespread uptake. We aim at fostering the cross-fertilization of optimization algorithms and parallel distributed computing. Knowledge about parallel computing helps in creating parallel algorithms for clouds, multi-core or GPU architectures. However, this also implies the need for a careful definition of proper benchmarks, software tools, and metrics to measure the behavior of algorithms in a meaningful way. More concretely, a conceptual separation between physical parallelism and decentralized algorithms (whether implemented in parallel or not) is needed in order to better analyze the resulting algorithms. In particular, all the previously-mentioned issues, such as sub-problem solving, expensive evaluation, or model-assisted approaches, will be though while taking their effective parallelization into account, and the potential gain of having a large distributed computing power available. Second, from a purely technological point-of-view, the deployment of the designed approaches over a real parallel computing testbed poses several technicalities that need to be addressed. One main issue we will tackle is to consider the cooperation rules within the different search procedures operating at every sub-problem. This can in fact constitute a bottleneck towards the design of highly scalable parallel decomposition for massive optimization.