We investigate the design and analysis of a feature-free deep learning (DL) approach for combinatorial optimization. Motivated by the success of DL in continuous domains, we propose a generic methodology that constructs a two-dimensional image representation of a combinatorial landscape via random-walk sampling. These images are then used as inputs to a Convolutional Neural Network (CNN) to address two high-level optimization tasks through supervised learning: (i) inferring landscape properties and (ii) tackling the challenging problem of automated algorithm selection. Specifically, using NK-landscapes as a benchmark test suite, we consider: (i) the prediction of the degree of landscape non-linearity and (ii) the automated selection of the best perturbation strength in a portfolio of iterated local search algorithms. Our experimental results show that, compared with supervised approaches based on established landscape features from the literature, the proposed feature-free method achieves higher accuracy in landscape property inference and greater solution quality gains in the algorithm selection task, while significantly outperforming the single best solver. Overall, these results provide empirical evidence that feature-free deep learning is a promising paradigm for both characterizing discrete landscapes and guiding the design of automated solving techniques, opening new opportunities for landscape-aware optimization.

ABSTRACT The Increasing Population Covariance Matrix Adaptation Evolution Strategy (IPOP‐CMA‐ES) algorithm is a reference stochastic optimizer dedicated to blackbox optimization, where no prior knowledge about the underlying problem structure is available. This paper aims to accelerate IPOP‐CMA‐ES thanks to high‐performance computing and parallelism when solving large optimization problems. We first show how BLAS and LAPACK routines can be introduced in linear algebra operations, and we then propose two strategies for deploying IPOP‐CMA‐ES efficiently on large‐scale parallel architectures with up to thousands of CPU cores. The first parallel strategy processes the multiple searches in the same ordering as the sequential IPOP‐CMA‐ES, while the second one processes concurrently these multiple searches. These strategies are implemented in MPI+OpenMP and compared on 6144 cores of the supercomputer Fugaku. We manage to obtain substantial speedups (up to several thousand) and even super‐linear ones, and we provide an in‐depth analysis of our results to understand precisely the superior performance of our second strategy. These results are finally confirmed on a local compute cluster with 512 cores.

Specialized graybox local search and crossover have been successfully combined within the framework of the so-called Drils (Deterministic recombination and iterated local search) algorithm. As for any evolutionary algorithm, the initial design framework, and the underlying high-level choices and parameters, are crucially important. The Drils algorithm is no exception, and recent enhanced variants exist in the literature. In this paper, we aim at: (i) improving the performance of the latest variants of Drils, and (ii) providing a better principled understanding of graybox search behavior and dynamics. On the basis of a preliminary analysis using Local Optima Networks of small-size NKQ-landscapes, we first highlight the difference of using local search with and without crossover. We then propose to pipeline these two techniques in a simple two-phase like iterated local search scheme which is shown to provide substantial improvements over the latest Drils+ variant for large-size NKQ-landscapes. We further report a dedicated analysis in an attempt to provide new insights into the impact of local search and crossover on the phenotype and the genotype of the local optima encountered in the search trajectory.

In the context of pseudo-Boolean optimization, surrogate functions based on the Walsh-Hadamard transform have been recently proposed with great success. It has been shown that lower-order components of the Walsh-Hadamard transform have usually a larger influence on the value of the objective function. Thus, creating a surrogate model using the lower-order components of the transform can provide a good approximation to the objective function. The Walsh-Hadamard transform in pseudo-Boolean optimization is a particularization in the binary representation of a Fourier transform over a finite group, precisely defined in the framework of group representation theory. Using this more general definition, it is possible to define a Fourier transform for the functions over permutations. We propose in this paper the use of surrogate functions based on the Fourier transforms over the permutation space. We check how similar the proposed surrogate models are to the original objective function and we also apply regression to learn a surrogate model based on the Fourier transform. The experimental setting includes two permutation problems for which the exact Fourier transform is unknown based on the problem parameters: the Asteroid Routing Problem and the Single Machine Total Weighted Tardiness.

Landscape analysis is a very useful tool in optimization to understand the structure of the search space of a problem when there is some kind of distance or neighborhood defined over the solutions. Local Optima Networks (LON) have been proposed to serve as a summary of the landscape of a problem. LONs are graphs where the nodes are the local optima of the search space according to a particular neighborhood and edges join local optima when one can be reached from the other using some kind of perturbation followed by hill climbing. In this paper we enhance local optima networks to include precise information on the transition probabilities among local optima, yielding a Markov Chain for the visited local optima during the search. The new analysis tool, called Local Optima Markov Chain (LOMA), is built on top of the static landscape information depending on the problem and includes information about algorithm dynamics. We show how LOMAs can be used to compute metrics that are out of the reach of other landscape-aware tools, thus offering more information to understand algorithm dynamics.

The structure of local optima in multi-objective combinatorial optimization and their impact on algorithm performance are not yet properly understood. In this paper, we are interested in the representation of multi-objective landscapes and their multi-modality. More specifically, we revise and extend the network of Pareto local optimal solutions (PLOS-net), inspired by the well-established local optima network from single-objective optimization. We first define a compressed PLOS-net which allows us to enhance its perception while preserving the important notion of connectedness between local optima. We then study an alternative visualization of the (compressed) PLOS-net that focuses on good-quality solutions, improves the distinction between connected components in the network, and generalizes well to landscapes with more than 2 objectives. We finally define a number of network metrics that characterize the PLOS-net, some of them being strongly correlated with search performance. We visualize and experiment with small-size multiobjective nk-landscapes, and we disclose the effect of PLOS-net metrics against well-established multi-objective local search and evolutionary algorithms.

Designed for graybox optimization problems, the state-of-the-art Drils algorithm (Deterministic Recombination and Iterated Local Search) follows the framework of a hybrid iterated local search by combining the efficient identification of improving moves and the fast recombination of local optima. The Drils algorithm uses a perturbation mechanism in order to feed the graybox crossover with promising local optima. The perturbation is a key element to avoid that the search gets trapped. In this paper, we revisit the Drils algorithm by focusing on two main questions: (i) how the perturbation is performed, and (ii) how strong it should be. We propose two alternative designs of the perturbation within the framework of Drils. The so-obtained algorithms are proved to provide substantial improvements. This is demonstrated based on extensive experiments using a diverse set of NKQ-landscapes, with different degrees of ruggedness, as well as, different dimensions ranging from relatively small to very large. Besides, we provide a comprehensive analysis on the impact of the proposed mechanisms allowing us to highlight the guiding principles for an accurate design and configuration of the perturbation as a function of landscape characteristics.

The design of effective features enabling the development of automated landscape-aware techniques requires to address a number of inter-dependent issues. In this paper, we are interested in contrasting the amount of budget devoted to the computation of features with respect to: (i) the effectiveness of the features in grasping the characteristics of the landscape, and (ii) the gain in accuracy when solving an unknown problem instance by means of a feature-informed automated algorithm selection approach. We consider multi-objective combinatorial landscapes where, to the best of our knowledge, no in depth investigations have been conducted so far. We study simple cost-adjustable sampling strategies for extracting different state-of-the-art features. Based on extensive experiments, we report a comprehensive analysis on the impact of sampling on landscape feature values, and the subsequent automated algorithm selection task. In particular, we identify different global trends of feature values leading to non-trivial cost-vs-accuracy trade-off(s). Besides, we provide evidence that the sampling strategy can improve the prediction accuracy of automated algorithm selection. Interestingly, this holds independently of whether the sampling cost is taken into account or not in the overall solving budget.

So far, multi-objective NK landscapes have been investigated under the assumption of a homogeneous nature of the involved objectives in terms of difficulty. However, we argue that problems with heterogeneous objectives, e.g., in terms of multi-modality, can be challenging for multi-objective evolutionary algorithms, and deserve further considerations. In this paper, we propose a model of multi-objective NK landscapes, where each objective has a different degree of variable interactions (K), as a benchmark to investigate heterogeneous multi-objective optimization problems. We show that the use of a rank-annotated neighborhood network with labeled local optimal solutions, together with landscape metrics extracted from the heterogeneous objectives, thoroughly characterize bi-objective NK landscapes with a different level of heterogeneity among the objectives.

Understanding the landscape underlying NK models is of fundamental interest. Different representations have been proposed to better understand how the ruggedness of the landscape is influenced by the model parameters, such as the problem dimension, the degree of non-linearity and the structure of variable interactions. In this paper, we propose to use neural embedding, that is a continuous vectorial representation obtained as a result of applying a neural network to a prediction task, in order to investigate the characteristics of NK landscapes. The main assumption is that neural embeddings are able to capture important features that reflect the difficulty of the landscape. We propose a method for constructing NK embeddings, together with metrics for evaluating to what extent this embedding space encodes valuable information from the original NK landscape. Furthermore, we study how the embedding dimensionality and the parameters of the NK model influence the characteristics of the NK embedding space. Finally, we evaluate the performance of optimizers that solve the continuous representations of NK models by searching for solutions in the embedding space.

Blackbox optimization refers to the situation where no analytical knowledge about the problem is available beforehand, which is the case in a number of application fields, e.g., multi-disciplinary design, simulation optimization. In this context, the so-called Simultaneous Optimistic Optimization (SOO) algorithm is a deterministic tree-based global optimizer exposing theoretically provable performance guarantees under mild conditions. In this paper, we consider the efficient shared-memory parallelization of SOO on a high-end HPC architecture with dozens of CPU cores. We thereby propose different strategies based on eliciting the possible levels of parallelism underlying the SOO algorithm. We show that the naive approach, performing multiple evaluations of the blackbox function in parallel, does not scale with the number of cores. By contrast, we show that a parallel design based on the SOO-tree traversal is able to provide substantial improvements in terms of scalability and performance. We validate our strategies with a detailed performance analysis on a compute server with two 64-core processors, using a number of diverse benchmark functions with both increasing dimensions and number of cores.

In this paper, we investigate the design of escape mechanisms within the state-of-the-art decomposition-based evolutionary multi-objective Moea/d framework. We propose to track the number of improvements made with respect to the single-objective sub-problems defined by decomposition. This allows us to compute an estimated sub-problem improvement probability which serves as an activation signal for some solution perturbation mechanism to occur. We report the benefits of such an approach by conducting a comprehensive experimental analysis on a broad range of combinatorial bi-objective bit-string landscapes with variable dimensions and ruggedness. Our empirical findings provide evidence on the effectiveness of the proposed escape mechanism and its ability in providing substantial improvement over conventional Moea/d. Besides, we provide a detailed analysis of parameters impact and anytime behavior in order to better highlight the strength of the proposed techniques as a function of available budget and problem characteristics.

Efficient hill climbers are at the heart of the latest gray-box optimization techniques, where some structural information about the optimization problem is available. Focusing on NK-landscapes as a challenging class of k-bounded pseudo-boolean functions, we propose a quality-enhanced and a time-accelerated hill climber. Our investigations are based on the idea of performing several simultaneous moves at each iteration of the search process. This is enabled using graph coloring to structure the interacting variables of an NK-landscape, and to identify subsets of possibly improving independent moves in the Hamming distance 1 neighborhood. Besides being extremely competitive with respect to the state-of-the-art first- and best- ascent serial variants, our initial design exposes a natural degree of parallelism allowing us to convert our serial algorithm into a parallel hill climber without further design efforts. As such, we also provide a multi-threaded implementation using up to 10 shared-memory CPU-cores. Using a range of large-scale random NK-landscapes with up to 106 variables, we provide evidence on the efficiency and effectiveness of the proposed hill climber and we highlight the strength of our parallel design in attaining substantial acceleration factors for the largest experimented functions.

In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the ε-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on a multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available.

On the one hand, surrogate-assisted evolutionary algorithms are established as a method of choice for expensive black-box optimization problems. On the other hand, the growth in computing facilities has seen a massive increase in potential computational power, granted the users accommodate their approaches with the offered parallelism. While a number of studies acknowledge the impact of parallelism for single-objective expensive optimization assisted by surrogates, extending such techniques to the multi-objective setting has not yet been properly investigated, especially within the state-of-the-art decomposition framework. We first highlight the different degrees of parallelism in existing surrogate-assisted multi-objective evolutionary algorithms based on decomposition (S-MOEA/D). We then provide a comprehensive analysis of the key steps towards a successful parallel S-MOEA/D approach. Through an extensive benchmarking effort relying on the well-established bbob-biobj test functions, we analyze the performance of the different algorithm designs with respect to the problem dimensionality and difficulty, the amount of parallel cores available, and the supervised learning models considered. In particular, we show the difference in algorithm scalability based on the selected surrogate-assisted approaches, the performance impact of distributing the model training task and the efficacy of the designed parallel-surrogate methods.

Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.

We consider the design and analysis of surrogate-assisted algorithms for expensive multi-objective combinatorial optimization. Focusing on pseudo-boolean functions, we leverage existing techniques based on Walsh basis to operate under the decomposition framework of MOEA/D. We investigate two design components for the cheap generation of a promising pool of offspring and the actual selection of one solution for expensive evaluation. We propose different variants, ranging from a filtering approach that selects the most promising solution at each iteration by using the constructed Walsh surrogates to discriminate between a pool of offspring generated by variation, to a substitution approach that selects a solution to evaluate by optimizing the Walsh surrogates in a multi-objective manner. Considering bi-objective NK landscapes as benchmark problems offering different degree of non-linearity, we conduct a comprehensive empirical analysis including the properties of the achievable approximation sets, the anytime performance, and the impact of the order used to train the Walsh surrogates. Our empirical findings show that, although our surrogate-assisted design is effective, the optimal integration of Walsh models within a multi-objective evolutionary search process gives rise to particular questions for which different trade-off answers can be obtained.

Building a surrogate model of an objective function has shown to be effective to assist evolutionary algorithms (EAs) to solve real-world complex optimisation problems which involve either computationally expensive numerical simulations or costly physical experiments. However, their effectiveness mostly focuses on small-scale problems with less than 10 decision variables. The scalability of surrogate assisted EAs (SAEAs) have not been well studied yet. In this paper, we propose a Gaussian process surrogate model assisted EA for medium-scale expensive multi-objective optimisation problems with up to 50 decision variables. There are three distinctive features of our proposed SAEA. First, instead of using all decision variables in surrogate model building, we only use those correlated ones to build the surrogate model for each objective function. Second, rather than directly optimising the surrogate objective functions, the original multi-objective optimisation problem is transformed to a new one based on the surrogate models. Last but not the least, a subset selection method is developed to choose a couple of promising candidate solutions for actual objective function evaluations thus to update the training dataset. The effectiveness of our proposed algorithm is validated on benchmark problems with 10, 20, 50 variables, comparing with three state-of-the-art SAEAs.

We expose and contrast the impact of landscape characteristics on the performance of search heuristics for black-box multiobjective combinatorial optimization problems. A sound and concise summary of features characterizing the structure of an arbitrary problem instance is identified and related to the expected performance of global and local dominance-based multiobjective optimization algorithms. We provide a critical review of existing features tailored to multiobjective combinatorial optimization problems, and we propose additional ones that do not require any global knowledge from the landscape, making them suitable for large-size problem instances. Their intercorrelation and their association with algorithm performance are also analyzed. This allows us to assess the individual and the joint effect of problem features on algorithm performance, and to highlight the main difficulties encountered by such search heuristics. By providing effective tools for multiobjective landscape analysis, we highlight that multiple features are required to capture problem difficulty, and we provide further insights into the importance of ruggedness and multimodality to characterize multiobjective combinatorial landscapes.

Parallelization is an important paradigm for solving massive optimization problems. Understanding how to fully benefit form the aggregated computing power and what makes a parallel strategy successful is a difficult issue. In this study, we propose a simple parallel iterative tabu search (PITS) and study its effectiveness with respect to different experimental settings. Using the quadratic assignment problem (QAP) as a case study, we first consider different small- and medium-size instances from the literature and then tackle a large-size instance that was rarely considered due the its inherent solving difficulty. In particular, we show that a balance between the number of function evaluations each parallel process is allowed to perform before resuming the search is a critical issue to obtain an improved quality.

Extracting a priori knowledge informing about the landscape underlying an unknown optimization problem has been proved extremely useful for different purposes, such as designing finely-tuned algorithms and automated solving techniques. Focusing on continuous domains, substantial progress has been achieved with the development of the so-called exploratory landscape analysis (ELA) approach, which provides a unified methodology for integrating features into sophisticated machine learning techniques. In particular, much efforts have been devoted to the systematic design of algorithm selection models aiming at improving existing state-of-art solvers. Nonetheless, designing the ELA features themselves is a bottleneck that can prevent further advances. The contribution of this paper is thereby two fold. Firstly, we consider the design of insightful features on the basis of the search tree constructed by the so-called SOO global optimizer, which is shown to imply an informative sampling of the search space using a limited budget. Secondly, we provide empirical evidence on the relevance of the proposed features and their potential in complementing existing ELA features for both predicting high-level problem properties, and selecting algorithms from a portfolio of available solvers. Our empirical findings are based on a comprehensive analysis using the diverse set of BBOB functions and solvers from the COCO platform.

A number of surrogate-assisted evolutionary algorithms are being developed for tackling expensive multiobjective optimization problems. On the one hand, a relatively broad range of techniques from both machine learning and multiobjective optimization can be combined for this purpose. Different taxonomies exist in order to better delimit the design choices, advantages and drawbacks of existing approaches. On the other hand, assessing the relative performance of a given approach is a difficult task, since it depends on the characteristics of the problem at hand. In this paper, we focus on surrogate-assisted approaches using objective space decomposition as a core component. We propose a refined and fine-grained classification, ranging from EGO-like approaches to filtering or pre-screening. More importantly, we provide a comprehensive comparative study of a representative selection of state-of-the-art methods, together with simple baseline algorithms. We rely on selected benchmark functions taken from the bbob-biobj benchmarking test suite, that provides a variable range of objective function difficulties. Our empirical analysis highlights the effect of the available budget on the relative performance of each approach, and the impact of the training set and of the machine learning model construction on both solution quality and runtime efficiency.

The working principles of the well-established multi-objective evolutionary algorithm Moea/d relies on the iterative and cooperative improvement of a number of single-objective sub-problems obtained by decomposition. Besides the definition of sub-problems, selection and replacement are, like in any evolutionary algorithm, the two core elements of Moea/d. We argue that these two components are however loosely coupled with the maintained population. Thereby, we propose to re-design the working principles of Moea/d by adopting a set-oriented perspective, where a many-to-one mapping between sub-problems and solutions is considered. Selection is then performed by defining a neighborhood relation among solutions in the population set, depending on the corresponding sub-problem mapping. Replacement is performed following an elitist mechanism allowing the population to have a variable, but bounded, cardinality during the search process. By conducting a comprehensive empirical analysis on a range of combinatorial multi- and many-objective NK-landscapes, we show that the proposed approach leads to significant improvements, especially when dealing with an increasing number of objectives. Our findings indicate that a set-oriented design can constitute a sound alternative for strengthening the practice of multi- and many-objective evolutionary optimization based on decomposition.

Pareto Local Search (PLS) is a simple, yet effective optimization approach dedicated to multi-objective combinatorial optimization. It can however suffer from a high computational cost, especially when the size of the Pareto optimal set is relatively large. Recently, incorporating decomposition in PLS had revealed a high potential, not only in providing high-quality approximation sets, but also in speeding-up the search process. Using the bi-objective Unconstrained Binary Quadratic Programming (bUBQP) problem as an illustrative benchmark, we demonstrate some shortcomings in the resulting decomposition-guided Parallel Pareto Local Search (PPLS), and we propose to revisit the PPLS design accordingly. For instances with a priori unknown Pareto front shape, we show that a simple pre-processing technique to estimate the scale of the Pareto front can help PPLS to better balance the workload. Furthermore, we propose a simple technique to deal with the critically-important scalability issue raised by PPLS when deployed over a large number of computing nodes. Our investigations show that the revisited version of PPLS provides a consistent performance, suggesting that decomposition-guided PPLS can be further generalized in order to improve both parallel efficiency and approximation quality.

Although several sequential heuristics have been proposed for dealing with the Unconstrained Binary Quadratic Programming (UBQP), very little effort has been made for designing parallel algorithms for the UBQP. This paper propose a novel decentralized parallel search algorithm, called Parallel Elite Biased Tabu Search (PEBTS). It is based on D2TS, a state-of-the-art sequential UBQP metaheuristic. The key strategies in the PEBTS algorithm include: (i) a lazy distributed cooperation procedure to maintain diversity among different search processes and (ii) finely tuned bit-flip operators which can help the search escape local optima efficiently. Our experiments on the Tianhe-2 supercomputer with up to 24 computing cores show the accuracy of the efficiency of PEBTS compared with a straightforward parallel algorithm running multiple independent and non-cooperating D2TS processes.

This work proposes the use of simple closed state models to capture, analyze and compare the dynamics of multi- and many-objective evolutionary algorithms. Two- and three-state models representing the composition of the instantaneous population are described and learned for representatives of the major approaches to multi-objective optimization, i.e. dominance, extensions of dominance, decomposition, and indicator algorithms. The model parameters are trained from data obtained running the algorithms with various population sizes on enumerable MNK-landscapes with 3, 4, 5 and 6 objectives. We show ways to interpret and use the model parameter values in order to analyze the population dynamics according to selected features. For example, we are interested in knowing how parameter values change for a given population size with the increase of the number of objectives. We also show a graphical representation capturing in one graph how the parameters magnitude and sign relate to the connections between states.

International audience

Subset selection constitutes an important stage of any evolutionary multiobjective optimization algorithm when truncating the current approximation set for the next iteration. This appears to be particularly challenging when the number of solutions to be removed is large, and when the approximation set contains many mutually non-dominating solutions. In particular, indicator-based strategies have been intensively used in recent years for that purpose. However, most solutions for the indicator-based subset selection problem are based on a very simple greedy backward elimination strategy. In this paper, we experiment additional heuristics that include a greedy forward selection and a greedy sequential insertion policies, a first-improvement hill-climbing local search, as well as combinations of those. We evaluate the effectiveness and the efficiency of such heuristics in order to maximize the enclosed hypervolume indicator of candidate subsets during a hypothetical evolutionary process, or as a post-processing phase. Our experimental analysis, conducted on randomly generated as well as structured two-, three- and four-objective mutually non-dominated sets, allows us to appreciate the benefit of these approaches in terms of quality, and to highlight some practical limitations and open challenges in terms of computational resources.

A large spectrum of quality indicators has been proposed so far to assess the performance of discrete Pareto set approximations in multiobjective optimization. Such indicators assign, to any solution set, a real-value reflecting a given aspect of approximation quality. This is an important issue in multiobjective optimization, not only to compare the performance and assets of different approximate algorithms, but also to improve their internal selection mechanisms. In this paper, we adopt a statistical analysis to experimentally investigate by how much a selection of state-of-the-art quality indicators agree with each other for a wide range of Pareto set approximations from well-known two- and three-objective continuous benchmark functions. More particularly, we measure the correlation between the ranking of low-, medium-, and high-quality limited-size approximation sets with respect to inverted generational distance, additive epsilon, multiplicative epsilon, R2, R3, as well as hypervolume indicator values. Since no pair of indicators obtains the same ranking of approximation sets, we confirm that they emphasize different facets of approximation quality. More importantly, our statistical analysis allows the degree of compliance between these indicators to be quantified.

We propose the first large-scale message passing distributed scheme for parallelizing the computational flow of Moea/d, a popular decomposition-based evolutionary multiobjective optimization algorithm. We show how synchronicity and workload granularity can impact both quality and computing time, in an extremely fine-grained configuration where each individual in the Moea/d population is mapped to a single distributed processing unit. More specifically, we deploy our distributed protocol using a large-scale environment of 128 computing cores and conduct a throughout analysis using a broad range of bi-objective combinatorial ρMNK-landscapes. Besides being able to show significant speed-ups while maintaining competitive search quality, our experimental results provide insights into the behavior of the proposed scheme in terms of quality/speedup trade-offs; thus pushing a step towards the achievement of effective and efficient parallel decomposition-based approaches for large-scale multi-objective optimization.

We experiment the SOO (Simultaneous Optimistic Optimization) global optimizer on the BBOB testbed. We report results for both the unconstrained-budget setting and the expensive setting, as well as a comparison with the DiRect algorithm to which SOO is mostly related. Overall, SOO is shown to perform rather poorly in the highest dimensions while agreeably exhibiting interesting performance for the most difficult functions, which is to be attributed to its global nature and to the fact that its design was guided by the goal of obtaining theoretically provable performance. The greedy exploration-exploitation sampling strategy underlying SOO design is also shown to be a viable alternative for the expensive setting which gives rooms for further improvements in this direction.

MOEA/D is a generic decomposition-based multiobjective optimization framework which has been proved to be extremely effective in solving a broad range of optimization problems especially for continuous domains. In this paper, we consider applying MOEA/D to solve a bi-objective scheduling combinatorial problem in which task durations and due-dates are uncertain. Surprisingly, we find that the conventional MOEA/D implementation provides poor performance in our application setting. We show that this is because the replacement strategy underlying MOEA/D is suffering some shortcomes that lead to low population diversity, and thus to premature convergence. Consequently, we investigate existing variants of MOEA/D and we propose a novel and simple alternative replacement component at the aim of maintaining population diversity. Through extensive experiments, we then provide a comprehensive analysis on the relative performance and the behavior of the considered algorithms. Besides being able to outperform existing MOEA/D variants, as well as the standard NSGA-II algorithm, our investigations provide new insights into the search ability of MOEA/D and highlight new research opportunities for improving its design components.

MOEA/D is an aggregation-based evolutionary algorithm which has been proved extremely efficient and effective for solving multi-objective optimization problems. It is based on the idea of decomposing the original multi-objective problem into several single-objective subproblems by means of well-defined scalarizing functions. Those single-objective subproblems are solved in a cooperative manner by defining a neighborhood relation between them. This makes MOEA/D particularly interesting when attempting to plug and to leverage single-objective optimizers in a multi-objective setting. In this context, we investigate the benefits that MOEA/D can achieve when coupled with CMA-ES, which is believed to be a powerful single-objective optimizer. We rely on the ability of CMA-ES to deal with injected solutions in order to update different covariance matrices with respect to each subproblem defined in MOEA/D. We show that by cooperatively evolving neighboring CMA-ES components, we are able to obtain competitive results for different multi-objective benchmark functions.

In this paper an iterated local search (ILS) is embedded with a variable neighborhood Descent (VND) hyper-heuristic. The proposed hyper-heuristic combines low-level heuristics. Several variants from the literature within the proposed ILS were implemented and tested. This article conducts an empirical study involving hard combinatorial optimization problems, permutation flowshop scheduling problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. The proposed ILS based hyper-heuristic proved its general and applicable across the studied problems.

Random work-stealing has been proved to be extremely beneficial in dynamically load-balancing irregular applications. However, it is known to perform loosely in non-homogenous distributed systems where communications costs are a major obstacle for high performance. In this paper, we investigate the design of an effective work-stealing protocol dealing with the heterogeneity of network link latencies. We propose a generic distributed algorithm which can be easily implemented to fit different types of heterogeneity. The proposed algorithm extends on reference approaches, namely Probabilistic Work Stealing (PWS), and Adaptive Cluster-aware Random Stealing (ACRS), by introducing new adaptive control operations that are shown to be highly accurate in increasing work locality and decreasing steals cost. We provide a comprehensive analysis including: (i) a comparative study on a broad range of harsh network scenarios, and (ii) an in-depth analysis of protocols' behavior at the aim of gaining new insights into dynamic load-balancing in heterogeneous distributed environments. Over all experimented configurations, our results show that although the proposed protocol is not tailored for a specific networked platform, it can save 30% execution time in average compared to its competitors, while demonstrating high quality self-adjusting capabilities.

Wireless sensor networks (WSN) have received significant attention over the last few years as they afford a growing number of applications in various fields. At the same time, these networks provide numerous challenges due to their constraints, primarily related to energy scarcity. To overcome energy waste caused by collisions and contention based algorithm, the channel assignment mechanisms, like TDMA1, seem to be an effective way for scheduling node transmissions. To solve channel assignment problems, graph coloring theory has been exploited in many research works, primarily in order to assure collision-free communications. In this paper, we present a novel distributed coloring algorithm for WSNs taking into account the constraints of a real WSN environment. Our collision aware coloring algorithm assures a 2 hop nodes coloring, in a deterministic time execution, without requiring a neighborhood discovering phase. Performance evaluation results have shown the effectivness of our algorithm in terms of exchanged control packets per node as well as the chromatic number.

To deal with dynamic load balancing in large scale distributed systems, we propose to organize computing resources following a logical peer-to-peer overlay and to distribute the load according to the so-defined overlay. We use a tree as a logical structure connecting distributed nodes and we balance the load according to the size of induced sub trees. We conduct extensive experiments involving up to 1000 computing cores and provide a throughout analysis of different properties of our generic approach for two different applications, namely, the standard Unbalanced Tree Search and the more challenging parallel Branch-and-Bound algorithm. Substantial improvements are reported in comparison with the classical random work stealing and two finely tuned application specific strategies taken from the literature.

We consider the neighborhood tree induced by alternating the use of different neighborhood structures within a local search descent. We investigate the issue of designing a search strategy operating at the neighborhood tree level by exploring different paths of the tree in a heuristic way. We show that allowing the search to 'backtrack' to a previously visited solution and resuming the iterative variable neighborhood descent by 'pruning' the already explored neighborhood branches leads to the design of effective and efficient search heuristics. We describe this idea by discussing its basic design components within a generic algorithmic scheme and we propose some simple and intuitive strategies to guide the search when traversing the neighborhood tree. We conduct a throughout experimental analysis of this approach by considering two different problem domains, namely, the Total Weighted Tardiness Problem (SMTWTP), and the more sophisticated Location Routing Problem (LRP). We show that independently of the considered domain, the approach is highly competitive. In particular, we show that using different branching and backtracking strategies when exploring the neighborhood tree allows us to achieve different trade-offs in terms of solution quality and computing cost.

We present a distributed algorithm, Select Best and Mutate (SBM), in the Distributed Adaptive Metaheuristic Selection (DAMS) framework. DAMS is dedicated to adaptive optimization in distributed environments. Given a set of metaheuristics, the goal of DAMS is to coordinate their local execution on distributed nodes in order to optimize the global performance of the distributed system. DAMS is based on three-layer architecture allowing nodes to decide distributively what local information to communicate, and what metaheuristic to apply while the optimization process is in progress. SBM is a simple, yet efficient, adaptive distributed algorithm using an exploitation component allowing nodes to select the metaheuristic with the best locally observed performance, and an exploration component allowing nodes to detect the metaheuristic with the actual best performance. SBM features are analyzed from both a parallel and an adaptive point of view, and its efficiency is demonstrated through experimentations and comparisons with other adaptive strategies (sequential and distributed).

Given a palette P of at most V colors, and a parameter d, a (d, V)-coloring of a graph is an assignment of a color from the palette P to every node in the graph such that any two nodes at distance at most d have different colors. We prove that for every n-node unit disk graph with maximum degree Δ, there exists a distributed algorithm computing a (1,O(Δ))-coloring under the SINR (Signal-to-Interferenceplus-Noise Ratio) physical model in at most O(Δ log n) time slots, which is optimal up to a logarithmic factor. Our result is based on revisiting a previous coloring algorithm, due to T. Moscibroda and R. Wattenhofer, described in the so called graph-based model. We also prove that, for a well defined constant d, a (d, O(Δ))-coloring allows us to schedule an interference free TDMA-like MAC protocol under the physical SINR constraints. As a corollary, any uniform interferencefree message passing algorithm with running time r can be simulated in the SINR model in O(Δ(log n+τ)) time slots. The latter generic result provides new insights into the distributed scheduling of radio network tasks under the harsh SINR constraints.

The paper presents a deterministic distributed algorithm that, given k ≥ 1, constructs in k rounds a (2k-1,0)-spanner of O(k n1+1/k) edges for every n-node unweighted graph. (If n is not available to the nodes, then our algorithm executes in 3k-2 rounds, and still returns a (2k-1,0)-spanner with O(k n1+1/k) edges.) Previous distributed solutions achieving such optimal stretch-size trade-off either make use of randomization providing performance guarantees in expectation only, or perform in logΩ(1)n rounds, and all require a priori knowledge of n. Based on this algorithm, we propose a second deterministic distributed algorithm that, for every ε > 0, constructs a (1+ε,2)-spanner of O(ε-1 n3/2) edges in O(ε-1) rounds, without any prior knowledge on the graph.

This paper presents efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with small radius and few intercluster edges. Our algorithms can be easily implemented in the distributed CONGEST model of computation i.e., limited message size, improving the time complexity of previous algorithms (Moran and Snir, 2000; Awerbuch, 1985; Peleg, 2000) from linear to sublinear. One important application of our algorithms is efficient construction of sparse graph spanners. In fact, given a parameter k, we show that there exists a sublinear deterministic distributed algorithm that constructs a graph spanner of stretch 2k - 1 with at most O(n1+1k/) edges in the CONGEST model

Visidia is a tool for the simulation and the visualization of distributed algorithms. The simulation has been done using one machine [M. Bauderon et al., (2002)]. We present an approach of such a simulation by using a network of machines. Indeed, we suppose that several machines connected by a network can take part in the simulation. We give both a specification of the set up model and a description of the implementation carried out.