Neural Improvement Heuristics for Graph Combinatorial Optimization Problems.

Recent advances in graph neural network (GNN) architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, neural improvement (NI) models have been particularly successful. However, the existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and nodewise positional encodings (PEs). To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the preference ranking problem (PRP) with a performance in the 99 th percentile. We also extend the proposal to two well-known problems: the traveling salesman problem and the graph partitioning problem (GPP), recommending operations in the 98 th and 97 th percentile, respectively.

Redefining Neural Architecture Search of Heterogeneous Multinetwork Models by Characterizing Variation Operators and Model Components.

With neural architecture search (NAS) methods gaining ground on manually designed deep neural networks-even more rapidly as model sophistication escalates-the research trend is shifting toward arranging different and often increasingly complex NAS spaces. In this conjuncture, delineating algorithms which can efficiently explore these search spaces can result in a significant improvement over currently used methods, which, in general, randomly select the structural variation operator, hoping for a performance gain. In this article, we investigate the effect of different variation operators in a complex domain, that of multinetwork heterogeneous neural models. These models have an extensive and complex search space of structures as they require multiple subnetworks within the general model in order to answer different output types. From that investigation, we extract a set of general guidelines whose application is not limited to that particular type of model and are useful to determine the direction in which an architecture optimization method could find the largest improvement. To deduce the set of guidelines, we characterize both the variation operators, according to their effect on the complexity and performance of the model; and the models, relying on diverse metrics which estimate the quality of the different parts composing it.

Analysis of the transferability and robustness of GANs evolved for Pareto set approximations.

The generative adversarial network (GAN) is a good example of a strong-performing, neural network-based generative model, even though it does have some drawbacks of its own. Mode collapsing and the difficulty in finding the optimal network structure are two of the most concerning issues. In this paper, we address these two issues at the same time by proposing a neuro-evolutionary approach with an agile evaluation method for the fast evolution of robust deep architectures that avoid mode collapsing. The computation of Pareto set approximations with GANs is chosen as a suitable benchmark to evaluate the quality of our approach. Furthermore, we demonstrate the consistency, scalability, and generalization capabilities of the proposed method, which shows its potential applications to many areas. We finally readdress the issue of designing this kind of models by analyzing the characteristics of the best performing GAN specifications, and conclude with a set of general guidelines. This results in a reduction of the many-dimensional problem of structural manual design or automated search.

Multi-Objectivising Combinatorial Optimisation Problems by Means of Elementary Landscape Decompositions.

In the last decade, many works in combinatorial optimisation have shown that, due to the advances in multi-objective optimisation, the algorithms from this field could be used for solving single-objective problems as well. In this sense, a number of papers have proposed multi-objectivising single-objective problems in order to use multi-objective algorithms in their optimisation. In this article, we follow up this idea by presenting a methodology for multi-objectivising combinatorial optimisation problems based on elementary landscape decompositions of their objective function. Under this framework, each of the elementary landscapes obtained from the decomposition is considered as an independent objective function to optimise. In order to illustrate this general methodology, we consider four problems from different domains: the quadratic assignment problem and the linear ordering problem (permutation domain), the 0-1 unconstrained quadratic optimisation problem (binary domain), and the frequency assignment problem (integer domain). We implemented two widely known multi-objective algorithms, NSGA-II and SPEA2, and compared their performance with that of a single-objective GA. The experiments conducted on a large benchmark of instances of the four problems show that the multi-objective algorithms clearly outperform the single-objective approaches. Furthermore, a discussion on the results suggests that the multi-objective space generated by this decomposition enhances the exploration ability, thus permitting NSGA-II and SPEA2 to obtain better results in the majority of the tested instances.

Anatomy of the Attraction Basins: Breaking with the Intuition.

Solving combinatorial optimization problems efficiently requires the development of algorithms that consider the specific properties of the problems. In this sense, local search algorithms are designed over a neighborhood structure that partially accounts for these properties. Considering a neighborhood, the space is usually interpreted as a natural landscape, with valleys and mountains. Under this perception, it is commonly believed that, if maximizing, the solutions located in the slopes of the same mountain belong to the same attraction basin, with the peaks of the mountains being the local optima. Unfortunately, this is a widespread erroneous visualization of a combinatorial landscape. Thus, our aim is to clarify this aspect, providing a detailed analysis of, first, the existence of plateaus where the local optima are involved, and second, the properties that define the topology of the attraction basins, picturing a reliable visualization of the landscapes. Some of the features explored in this article have never been examined before. Hence, new findings about the structure of the attraction basins are shown. The study is focused on instances of permutation-based combinatorial optimization problems considering the 2-exchange and the insert neighborhoods. As a consequence of this work, we break away from the extended belief about the anatomy of attraction basins.

Early Classification of Time Series by Simultaneously Optimizing the Accuracy and Earliness.

The problem of early classification of time series appears naturally in contexts where the data, of temporal nature, are collected over time, and early class predictions are interesting or even required. The objective is to classify the incoming sequence as soon as possible, while maintaining suitable levels of accuracy in the predictions. Thus, we can say that the problem of early classification consists of optimizing two objectives simultaneously: accuracy and earliness. In this context, we present a method for early classification based on combining a set of probabilistic classifiers together with a stopping rule (SR). This SR will act as a trigger and will tell us when to output a prediction or when to wait for more data, and its main novelty lies in the fact that it is built by explicitly optimizing a cost function based on accuracy and earliness. We have selected a large set of benchmark data sets and four other state-of-the-art early classification methods, and we have evaluated and compared our framework obtaining superior results in terms of both earliness and accuracy.

An evaluation of methods for estimating the number of local optima in combinatorial optimization problems.

The solution of many combinatorial optimization problems is carried out by metaheuristics, which generally make use of local search algorithms. These algorithms use some kind of neighborhood structure over the search space. The performance of the algorithms strongly depends on the properties that the neighborhood imposes on the search space. One of these properties is the number of local optima. Given an instance of a combinatorial optimization problem and a neighborhood, the estimation of the number of local optima can help not only to measure the complexity of the instance, but also to choose the most convenient neighborhood to solve it. In this paper we review and evaluate several methods to estimate the number of local optima in combinatorial optimization problems. The methods reviewed not only come from the combinatorial optimization literature, but also from the statistical literature. A thorough evaluation in synthetic as well as real problems is given. We conclude by providing recommendations of methods for several scenarios.

On the taxonomy of optimization problems under estimation of distribution algorithms.

Understanding the relationship between a search algorithm and the space of problems is a fundamental issue in the optimization field. In this paper, we lay the foundations to elaborate taxonomies of problems under estimation of distribution algorithms (EDAs). By using an infinite population model and assuming that the selection operator is based on the rank of the solutions, we group optimization problems according to the behavior of the EDA. Throughout the definition of an equivalence relation between functions it is possible to partition the space of problems in equivalence classes in which the algorithm has the same behavior. We show that only the probabilistic model is able to generate different partitions of the set of possible problems and hence, it predetermines the number of different behaviors that the algorithm can exhibit. As a natural consequence of our definitions, all the objective functions are in the same equivalence class when the algorithm does not impose restrictions to the probabilistic model. The taxonomy of problems, which is also valid for finite populations, is studied in depth for a simple EDA that considers independence among the variables of the problem. We provide the sufficient and necessary condition to decide the equivalence between functions and then we develop the operators to describe and count the members of a class. In addition, we show the intrinsic relation between univariate EDAs and the neighborhood system induced by the Hamming distance by proving that all the functions in the same class have the same number of local optima and that they are in the same ranking positions. Finally, we carry out numerical simulations in order to analyze the different behaviors that the algorithm can exhibit for the functions defined over the search space [Formula: see text].

Multi-marker tagging single nucleotide polymorphism selection using estimation of distribution algorithms.

OBJECTIVES: This paper presents an optimization algorithm for the automatic selection of a minimal subset of tagging single nucleotide polymorphisms (SNPs). METHODS AND MATERIALS: The determination of the set of minimal tagging SNPs is approached as an optimization problem in which each tagged SNP can be covered by a single tagging SNP or by a pair of tagging SNPs. The problem is solved using an estimation of distribution algorithm (EDA) which takes advantage of the underlying topological structure defined by the SNP correlations to model the problem interactions. The EDA stochastically searches the constrained space of feasible solutions. It is evaluated across HapMap reference panel data sets. RESULTS: The EDA was compared with a SAT solver, able to find the single-marker minimal tagging sets, and with the Tagger program. The percentage of reduction ranged from 10% to 43% in the number of tagging SNPs of the minimal multi-marker tagging set found by the EDA with respect to the other algorithms. CONCLUSIONS: The introduced algorithm is effective for the identification of minimal multi-marker SNP sets, which considerably reduce the dimension of the tagging SNP set in comparison with single-marker sets. Other variants of the SNP problem can be treated following the same approach.