Malware authors have seen obfuscation as the mean to bypass malware detectors based on static analysis features. For Android, several studies have confirmed that many anti-malware products are easily evaded with simple program transformations. As opposed to these works, ML detection proposals for Android leveraging static analysis features have also been proposed as obfuscation-resilient. Therefore, it needs to be determined to what extent the use of a specific obfuscation strategy or tool poses a risk for the validity of ML Android malware detectors based on static analysis features. To shed some light in this regard, in this article we assess the impact of specific obfuscation techniques on common features extracted using static analysis and determine whether the changes are significant enough to undermine the effectiveness of ML malware detectors that rely on these features. The experimental results suggest that obfuscation techniques affect all static analysis features to varying degrees across different tools. However, certain features retain their validity for ML malware detection even in the presence of obfuscation. Based on these findings, we propose a ML malware detector for Android that is robust against obfuscation and outperforms current state-of-the-art detectors.

Learning-based methods have gained significant popularity in the field of combinatorial optimization in recent times. Researchers in the deep learning community aim to design models that, given an instance of a problem, directly generate optimal solutions in the first shot. However, due to the inherent complexity of certain combinatorial problems, achieving this in a single attempt is not trivial, and additional strategies are required to search for the optimal solution in several tries. For this purpose, researchers have proposed sampling techniques or active search which, in our opinion, are computationally wasteful with a limited performance. In this paper we develop strategies that efficiently exploit the fast inference capability of learning methods. Particularly, the objective is to solve the entire problem by solving it in fragments. It can be applied to any problem where the improvement of the overall solution is guaranteed by improving any part of the problem. To illustrate this, we focus on the Linear Ordering Problem (LOP) as a case of study. We employ a Neural Combinatorial Optimization model within a sliding-window optimization strategy, where specific parts of a candidate solution are optimized without compromising the overall solution quality. We explore various implementation aspects, including window size, step size and overlapping configurations. Experimental results show that the presented method achieves superior performance and better efficiency compared to baseline strategies and competitors, and significantly surpasses the previous learning methods for LOP instances of size 200, achieving an average gap to the best known value of only 0.04% within a 1-minute run-time.

The current quest for environmentally sustainable AI models has led to NAS algorithms that not only pursue model accuracy, but also energy efficiency in a simultaneous manner, which increases the architecture optimization problem complexity. In this paper, we aim at simplifying this problem by using factorization. More specifically, we analyze the fitness landscapes of NAS from the point of view of search distributions related to the accuracy and computational complexity of the neural network architectures. For these search distributions, we extract probability factorizations and compute a number of descriptors of the search difficulty for methods based on probability distributions. Our results reveal that each objective can induce search distributions with different strengths of interactions between variables. Therefore, methods that intend to optimize the computational cost of NAS can require different types of factorizations than those focused on the accuracy.

Neural Combinatorial Optimization has emerged as a new paradigm in the optimization area. It attempts to solve optimization problems by means of neural networks and reinforcement learning. In the past few years, due to their novelty and presumably good performance, many research papers have been published introducing new neural architectures for a variety of combinatorial problems. However, the incorporation of such models in the conventional optimization portfolio raises many questions related to their performance compared to other existing methods, such as exact algorithms, heuristics, or metaheuristics. This article aims to present a critical view of these new proposals, discussing their benefits and drawbacks with respect to the tools and algorithms already present in the optimization field. For this purpose, a comprehensive study is carried out to analyze the fundamental aspects of such methods, including performance, computational cost, transferability, and reusability of the trained model. Moreover, this discussion is accompanied by the design and validation of a new neural combinatorial optimization algorithm on two well-known combinatorial problems: the Linear Ordering Problem and the Permutation Flowshop Scheduling Problem. Finally, new directions for future work in the area of Neural Combinatorial Optimization algorithms are suggested.

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.

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 99th 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 98th and 97th percentile, respectively.

Choosing the best kernel is crucial in many Machine Learning applications. Gaussian Processes are a state-of-the-art technique for regression and classification that heavily relies on a kernel function. However, in the Gaussian Processes literature, kernels have usually been either ad hoc designed, selected from a predefined set, or searched for in a space of compositions of kernels which have been defined a priori. In this paper, we propose a Genetic Programming algorithm that represents a kernel function as a tree of elementary mathematical expressions. By means of this representation, a wider set of kernels can be modeled, where potentially better solutions can be found, although new challenges also arise. The proposed algorithm is able to overcome these difficulties and find kernels that accurately model the characteristics of the data. This method has been tested in several real-world time series extrapolation problems, improving the state-of-the-art results while reducing the complexity of the kernels.

The performance of support vector machines in nonlinearly separable classification problems strongly relies on the kernel function. Toward an automatic machine learning approach for this technique, many research outputs have been produced dealing with the challenge of automatic learning of good-performing kernels for support vector machines. However, these works have been carried out without a thorough analysis of the set of components that influence the behavior of support vector machines and their interaction with the kernel. These components are related in an intricate way and it is difficult to provide a comprehensible analysis of their joint effect. In this paper, we try to fill this gap introducing the necessary steps in order to understand these interactions and provide clues for the research community to know where to place the emphasis. First of all, we identify all the factors that affect the final performance of support vector machines in relation to the elicitation of kernels. Next, we analyze the factors independently or in pairs and study the influence each component has on the final classification performance, providing recommendations and insights into the kernel setting for support vector machines.

Multi-task learning, as it is understood nowadays, consists of using one single model to carry out several similar tasks. From classifying hand-written characters of different alphabets to figuring out how to play several Atari games using reinforcement learning, multi-task models have been able to widen their performance range across different tasks, although these tasks are usually of a similar nature. In this work, we attempt to expand this range even further, by including heterogeneous tasks in a single learning procedure. To do so, we firstly formally define a multi-network model, identifying the necessary components and characteristics to allow different adaptations of said model depending on the tasks it is required to fulfill. Secondly, employing the formal definition as a starting point, we develop an illustrative model example consisting of three different tasks (classification, regression, and data sampling). The performance of this illustrative model is then analyzed, showing its capabilities. Motivated by the results of the analysis, we enumerate a set of open challenges and future research lines over which the full potential of the proposed model definition can be exploited.

Among the characteristics of traditional evolutionary algorithms governed by models, memory volatility is one of the most frequent. This is commonly due to the limitations of the models used to guide this kind of algorithms, which are generally very efficient when sampling, but tend to struggle when facing large amounts of data to represent. Neural networks are one type of model which conveniently thrives when facing vast amounts of data, and does not see its performance particularly worsened by large dimensionality. Several successful neural generative models, which could perfectly fit as a model for driving an evolutionary process are available in the literature. Whereas the behavior of these generative models in evolutionary algorithms has already been widely tested, other neural models -those intended for supervised learning-have not enjoyed that much attention from the research community. In this paper, we take one step forward in this direction, exploring the capacities and particularities of back-drive, a method that enables a neural model intended for regression to be used as a solution sampling model. In this context, by performing extensive research into the most influential aspects of the algorithm, we study the conditions which favor the performance of the back-drive algorithm as the sole guiding factor in an evolutionary approach.

Image segmentation is a relevant problem in computer vision present in multiple application domains. One of the most used methods for image segmentation is U-net, a type of convolutional network with additional constraints in its architecture. Studies regarding the U-net usually rely on well-known architectures, which leads to a narrow exploration of the possibilities, and possibly impacting the performance. Genetic Programming approaches have become increasingly popular for designing neural networks due to studies where the generated models were able to achieve results comparable to humans. These approaches can evolve the structure at different levels of abstraction, reducing the need for a specialist. In this paper, we propose the use of Grammatical Evolution for evolving U-net architectures. We propose a mirror grammar, which is capable of generating a variety of flexible U-nets that better explores the search space. We show that the proposed grammar can capture the complex constraints that define the U-nets and achieve comparable results in terms of accuracy, on a benchmark of segmentation problems of varying difficulty.

A number of local search based algorithms have been designed to escape from the local optima, such as, iterated local search or variable neighborhood search. The neighborhood chosen for the local search as well as the escape technique play a key role in the performance of these algorithms. Of course, a specific strategy has a different effect on distinct problems or instances. In this paper, we focus on a permutation-based combinatorial optimization problem: the linear ordering problem. We provide a theoretical landscape analysis for the adjacent swap, the swap and the insert neighborhoods. By making connections to other different problems found in the Combinatorics field, we prove that there are some moves in the local optima that will necessarily return a worse or equal solution. The number of these non-better solutions that could be avoided by the escape techniques is considerably large with respect to the number of neighbors. This is a valuable information that can be included in any of those algorithms designed to escape from the local optima, increasing their efficiency.

The identification of network attacks which target information and communication systems has been a focus of the research community for years. Network intrusion detection is a complex problem which presents a diverse number of challenges. Many attacks currently remain undetected, while newer ones emerge due to the proliferation of connected devices and the evolution of communication technology. In this survey, we review the methods that have been applied to network data with the purpose of developing an intrusion detector, but contrary to previous reviews in the area, we analyze them from the perspective of the Knowledge Discovery in Databases (KDD) process. As such, we discuss the techniques used for the collecion, preprocessing and transformation of the data, as well as the data mining and evaluation methods. We also present the characteristics and motivations behind the use of each of these techniques and propose more adequate and up-to-date taxonomies and definitions for intrusion detectors based on the terminology used in the area of data mining and KDD. Special importance is given to the evaluation procedures followed to assess the detectors, discussing their applicability in current, real networks. Finally, as a result of this literature review, we investigate some open issues which will need to be considered for further research in the area of network security.

The aim of this paper is to introduce the concept of intersection between combinatorial optimisation problems. We take into account that most algorithms, in their machinery, do not consider the exact objective function values of the solutions, but only a comparison between them. In this sense, if the solutions of an instance of a combinatorial optimisation problem are sorted into their objective function values, we can see the instances as (partial) rankings of the solutions of the search space. Working with specific problems, particularly, the linear ordering problem and the symmetric and asymmetric traveling salesman problem, we show that they can not generate the whole set of (partial) rankings of the solutions of the search space, but just a subset. First, we characterise the set of (partial) rankings each problem can generate. Secondly, we study the intersections between these problems: those rankings which can be generated by both the linear ordering problem and the symmetric/asymmetric traveling salesman problem, respectively. The fact of finding large intersections between problems can be useful in order to transfer heuristics from one problem to another, or to define heuristics that can be useful for more than one problem.

Sentiment analysis consists of evaluating opinions or statements based on text analysis. Among the methods used to estimate the degree to which a text expresses a certain sentiment are those based on Gaussian Processes. However, traditional Gaussian Processes methods use a predefined kernels with hyperparameters that can be tuned but whose structure can not be adapted. In this paper, we propose the application of Genetic Programming for the evolution of Gaussian Process kernels that are more precise for sentiment analysis. We use use a very flexible representation of kernels combined with a multi-objective approach that considers simultaneously two quality metrics and the computational time required to evaluate those kernels. Our results show that the algorithm can outperform Gaussian Processes with traditional kernels for some of the sentiment analysis tasks considered.

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.

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.

Strategies to automatize the selection of Machine Learning algorithms and their parameters have gained popularity in recent years, to the point of coining the term Automated Machine Learning. The most general version of this problem is pipeline optimization, which seeks an optimal combination of preprocessors and classifiers, along with their respective parameters. In this paper we address the pipeline generation problem from a broader perspective, that of problem complexity understanding as a previous step before proposing a solution, a comprehension we consider critical. The main contribution of this work is the analysis of the characteristics of the fitness landscape. Furthermore, a recently introduced tool for pipeline generation is used to investigate how an automatic method behaves in the previously studied landscape. Results show the high complexity of the pipeline optimization problem, as it can contain several disperse optima, and suffers from a severe lack of generality. Results also suggest that, depending on the dimensions of the search, the model quality target, and the data being modeled, basic search methods can produce results that match the user's expectations.

Local search algorithms are one of the most developed metaheuristics to solve combinatorial optimisation problems. Particularly, hill-climbing algorithms are simple but effective techniques that have been extensively used to deal with this kind of problems. These algorithms draw paths through the search space, choosing at each step a better solution than the current solution. As already known, they stop when a local optimum is reached. It is commonly believed that the closer the solution to the local optimum, the better its fitness. This premiss has a main implication: under this intuition, it is assumed that at each step of a hill-climbing algorithm, the new solution reduces the distance to the local optima. In this paper, we prove that this statement is not necessarily true. In fact, for some permutation-based combinatorial optimisation problems, such as the Permutation Flowshop Scheduling Problem, the Linear Ordering Problem and the Quadratic Assignment Problem, when considering the 2-exchange and the insert neighbourhoods, we find that, in most of the cases, the paths defined by a hill-climbing algorithm do not monotonically reduce the distance to the local optimum. Moreover, this distance remains constant for several steps, or it even increases for some steps. We provide an analysis of the solutions found in the attraction basins according to the distance to the local optimum and to the number of steps of the algorithm. We also give some visual examples of the paths followed by the algorithm.

In machine learning, generative models are used to create data samples that mimic the characteristics of the training data. Generative adversarial networks (GANs) are neural-network based generator models that have shown their capacity to produce realistic samples in different domains. In this paper we propose a neuro-evolutionary approach for evolving deep GAN architectures together with the loss function and generator-discriminator synchronization parameters. We also propose the problem of Pareto set (PS) approximation as a suitable benchmark to evaluate the quality of neural-network based generators in terms of the accuracy of the solutions they generate. The covering of the Pareto front (PF) by the generated solutions is used as an indicator of the mode-collapsing behavior of GANs. We show that it is possible to evolve GANs that generate good PS approximations. Our method scales to up to 784 variables and that it is capable to create architecture transferable across dimensions and functions.

In the past, evolutionary algorithms (EAs) that use probabilistic modeling of the best solutions incorporated latent or hidden variables to the models as a more accurate way to represent the search distributions. Recently, a number of neural-network models that compute approximations of posterior (latent variable) distributions have been introduced. In this paper, we investigate the use of the variational autoencoder (VAE), a class of neural-network based generative model, for modeling and sampling search distributions as part of an estimation of distribution algorithm. We show that VAE can capture dependencies between decision variables and objectives. This feature is proven to improve the sampling capacity of model based EAs. Furthermore, we extend the original VAE model by adding a new, fitness-approximating network component. We show that it is possible to adapt the architecture of these models and we present evidence of how to extend VAEs to better fulfill the requirements of probabilistic modeling in EAs. While our results are not yet competitive with state of the art probabilistic-based optimizers, they represent a promising direction for the application of generative models within EDAs.

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.

Permutation problems are combinatorial optimization problems whose solutions are naturally codified as permutations. Due to their complexity, motivated principally by the factorial cardinality of the search space of solutions, they have been a recurrent topic for the artificial intelligence and operations research community. Recently, among the vast number of metaheuristic algorithms, new advances on estimation of distribution algorithms (EDAs) have shown outstanding performance when solving some permutation problems. These novel EDAs implement distance-based exponential probability models such as the Mallows and Generalized Mallows models. In this article, we present a Matlab package, perm_mateda, of estimation of distribution algorithms on permutation problems, which has been implemented as an extension to the Mateda-2.0 toolbox of EDAs. Particularly, we provide implementations of the Mallows and Generalized Mallows EDAs under the Kendall’s-τ, Cayley, and Ulam distances. In addition, four classical permutation problems have also been implemented: Traveling Salesman Problem, Permutation Flowshop Scheduling Problem, Linear Ordering Problem, and Quadratic Assignment Problem.

Estimation of Distribution Algorithms have proved to be very competitive for solving combinatorial and continuous optimisation problems. However, there are problems for which they have not been extensively developed: we refer to constrained optimisation problems. Existing proposals approach these problems by (i) modifying the sampling strategy of the probabilistic model to allow feasible solutions or (ii) adopting general approaches used in the context of heuristic optimisation such as penalisation. Nonetheless, from a theoretical point of view, little progress have been given in the context of EDAs when developing algorithms designed specifically to solve constrained problems. In this paper, we propose developing EDAs by introducing probability models defined exclusively on the space of feasible solutions. In this sense, we give a first approach by taking the Graph Partitioning Problem (GPP) as a case of study, and present a probabilistic model defined exclusively on the feasible region of solutions: a square lattice probability model. The experiments conducted on a benchmark of 22 artificial instances confirm the effectiveness of the proposal in terms of quality of solutions and execution time.

In evolutionary computation, it is common practice to use sets of instances as test-beds for evaluating and comparing the performance of new optimisation algorithms. In some cases, real-world instances are available, and, thus, they are used to constitute the experimental benchmark. Unfortunately, this is not the general case. Due to the difficulties for obtaining real-world instances, or because the optimisation problems defined in the literature are not exactly as those defined in the industry, practitioners are forced to create artificial instances. In this paper, we study some aspects related to the random generation of artificial instances. Particularly, we elaborate on the assumption that states that sampling uniformly at random in the space of parameters is equivalent to sampling uniformly at random in the space of functions. Illustrated with some experiments, we prove that for some type of algorithms this assumption does not hold.

Advances in evolutionary computation have demonstrated that Evolutionary Algorithms (EAs) proposed in this area are a solid alternative for solving combinatorial and continuous optimization problems. Despite their success in innumerable real-world scenarios, EAs depend on a set of input parameters that characterize their performance and need to be adjusted. In fact, identifying and setting the most appropriate parameters for an EA is a complex task, which, in some cases, can be as difficult as the optimization problem at hand. Recently, parameter tuning has attracted the interest of the research community, designing and proposing techniques that (1) help the algorithm to perform to its best, and (2), indirectly, make fairer comparisons of different methods. In this manuscript, we propose a novel offline parameter tuning algorithm based on Bayesian Optimization, a sequential design strategy for global optimization. In order to illustrate the validity of the proposed method, we considered as a case of study the Hybrid Kernel EDA, an EA that is characterized by 6 parameters. We ran the algorithm with the parameters tuned by means of Bayesian Optimization, and compared the results with those obtained by setting the parameters by hand (using some prior knowledge). Experiments were carried out on a benchmark of 60 instances of the permutation flowshop scheduling problem. Experimental results show that, in general, Hybrid Kernel EDA obtains better results when using the parameters tuned by means of Bayesian Optimization.

This paper proposes a new method for the design and analysis of multi-objective unconstrained binary quadratic programming (mUBQP) instances, commonly used for testing discrete multi-objective evolutionary algorithms (MOEAs). These instances are usually generated considering the sparsity of the matrices and the correlation between objectives but randomly selecting the values for the matrix cells. Our hypothesis is that going beyond the use of objective correlations by considering different types of variables interactions in the generation of the instances can help to obtain more diverse problem benchmarks, comprising harder instances. We propose a parametric approach in which small building blocks of deceptive functions are planted into the matrices that define the mUBQP. The algorithm for creating the new instances is presented, and the difficulty of the functions is tested using variants of a decomposition-based MOEA. Our experimental results confirm that the instances generated by planting deceptive blocks require more function evaluations to be solved than instances generated using other methods.

In this paper, we propose a tunable generator of instances of permutation-based combinatorial optimization problems. Our approach is based on a probabilistic model for permutations, called the generalized Mallows model. The generator depends on a set of parameters that permits the control of the properties of the output instances. Specifically, in order to create an instance, we solve a linear programming problem in the parameters, where the restrictions allow the instance to have a fixed number of local optima and the linear function encompasses qualitative characteristics of the instance. We exemplify the use of the generator by giving three distinct linear functions that produce three landscapes with different qualitative properties. After that, our generator is tested in two different ways. First, we test the flexibility of the model by producing instances similar to benchmark instances. Second, we account for the capacity of the generator to create different types of instances according to the difficulty for population-based algorithms. We study the influence of the input parameters in the behaviors of these algorithms, giving an example of a property that can be used to analyze their performance.

In the past few years, clustering has become a popular task associated with time series. The choice of a suitable distance measure is crucial to the clustering process and, given the vast number of distance measures for time series available in the literature and their diverse characteristics, this selection is not straightforward. With the objective of simplifying this task, we propose a multi-label classification framework that provides the means to automatically select the most suitable distance measures for clustering a time series database. This classifier is based on a novel collection of characteristics that describe the main features of the time series databases and provide the predictive information necessary to discriminate between a set of distance measures. In order to test the validity of this classifier, we conduct a complete set of experiments using both synthetic and real time series databases and a set of five common distance measures. The positive results obtained by the designed classification framework for various performance measures indicate that the proposed methodology is useful to simplify the process of distance selection in time series clustering tasks.

Recently, distance-based exponential probability models have demonstrated their validity in the context of estimation of distribution algorithms when solving permutationbased combinatorial optimisation problems. However, despite their successful performance, some of these models are unimodal, and, therefore, they might not be flexible enough to model the different modalities that may be represented in heterogeneous populations. In this paper, we address the particular case of the Generalized Mallows models under the Cayley distance, and propose mixtures of these models in the context of estimation of distribution algorithms. In order to evaluate their competitiveness, we considered the quadratic assignment problem as a case of study, and conducted experiments over a set of 90 instances for four different configurations of mixtures. Results reveal that the EDA with mixtures is able to outperform the Generalized Mallows EDA, especially in large instances.

In this paper we propose a method for the generation of instances of the MNK-landscapes that maximize different measures used to characterize multi-objective problems. In contrast to previous approaches, the introduced algorithm works by modifying the neighborhood structure of the variables of the MNK-landscape while keeping fixed the local parameters of its functions. A variant of the algorithm is presented to deal with situations in which the exhaustive enumeration of search space is unfeasible. We show how the introduced method can be used to generate instances with an increased number of solutions in the Pareto front. Furthermore, we investigate whether direct optimization of the correlation between objectives can be used as an indirect method to increase the size of the Pareto fronts of the generated instances.

Recently, distance-based exponential probability models, such as Mallows and Generalized Mallows, have demonstrated their validity in the context of estimation of distribution algorithms (EDAs) for solving permutation problems. However, despite their successful performance, these models are unimodal, and therefore, they are not flexible enough to accurately model populations with solutions that are very sparse with regard to the distance metric considered under the model.

The high performance computing landscape is shifting from collections of homogeneous nodes towards heterogeneous systems, in which nodes consist of a combination of traditional out-of-order execution cores and accelerator devices. Accelerators, built around GPUs, many-core chips, FPGAs or DSPs, are used to offload compute-intensive tasks. The advent of this type of systems has brought about a wide and diverse ecosystem of development platforms, optimization tools and performance analysis frameworks. This is a review of the state-of-the-art in performance tools for heterogeneous computing, focusing on the most popular families of accelerators: GPUs and Intel's Xeon Phi. We describe current heterogeneous systems and the development frameworks and tools that can be used for developing for them. The core of this survey is a review of the performance models and tools, including simulators, proposed in the literature for these platforms.

Recently, probability models on rankings have been proposed in the field of estimation of distribution algorithms in order to solve permutation-based combinatorial optimisation problems. Particularly, distance-based ranking models, such as Mallows and Generalized Mallows under the Kendall's-τ distance, have demonstrated their validity when solving this type of problems. Nevertheless, there are still many trends that deserve further study. In this paper, we extend the use of distance-based ranking models in the framework of EDAs by introducing new distance metrics such as Cayley and Ulam. In order to analyse the performance of the Mallows and Generalized Mallows EDAs under the Kendall, Cayley and Ulam distances, we run them on a benchmark of 120 instances from four well known permutation problems. The conducted experiments showed that there is not just one metric that performs the best in all the problems. However, the statistical test pointed out that Mallows-Ulam EDA is the most stable algorithm among the studied proposals.

The aim of this paper is two-fold. First, we introduce a novel general estimation of distribution algorithm to deal with permutation-based optimization problems. The algorithm is based on the use of a probabilistic model for permutations called the generalized Mallows model. In order to prove the potential of the proposed algorithm, our second aim is to solve the permutation flowshop scheduling problem. A hybrid approach consisting of the new estimation of distribution algorithm and a variable neighborhood search is proposed. Conducted experiments demonstrate that the proposed algorithm is able to outperform the state-of-the-art approaches. Moreover, from the 220 benchmark instances tested, the proposed hybrid approach obtains new best known results in 152 cases. An in-depth study of the results suggests that the successful performance of the introduced approach is due to the ability of the generalized Mallows estimation of distribution algorithm to discover promising regions in the search space.

Estimation of distribution algorithms are known as powerful evolutionary algorithms that have been widely used for diverse types of problems. However, they have not been extensively developed for permutation-based problems. Recently, some progress has been made in this area by introducing probability models on rankings to optimize permutation domain problems. In particular, the Mallows model and the Generalized Mallows model demonstrated their effectiveness when used with estimation of distribution algorithms. Motivated by these advances, in this paper we introduce a Thurstone order statistics model, called Plackett-Luce, to the framework of estimation of distribution algorithms. In order to prove the potential of the proposed algorithm, we consider two different permutation problems: the linear ordering problem and the flowshop scheduling problem. In addition, the results are compared with those obtained by the Mallows and the Generalized Mallows proposals. Conducted experiments demonstrate that the Plackett-Luce model is the best performing model for solving the linear ordering problem. However, according to the experimental results, the Generalized Mallows model turns out to be very robust obtaining very competitive results for both problems, especially for the permutation flowshop scheduling problem.

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].

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.

In this paper we investigate the question of transfer learning in evolutionary optimization using estimation of distribution algorithms. We propose a framework for transfer learning between related optimization problems by means of structural transfer. Different methods for incrementing or replacing the (possibly unavailable) structural information of the target optimization problem are presented. As a test case we solve the multi-marker tagging single-nucleotide polymorphism (SNP) selection problem, a real world problem from genetics. The introduced variants of structural transfer are validated in the computation of tagging SNPs on a database of 1167 individuals from 58 human populations worldwide. Our experimental results show significant improvements over EDAs that do not incorporate information from related problems.

The identification of the specific genes that influence particular phenotypes is a common problem in genetic studies. In this paper we address the problem of determining the influence of gene joint expression in synapse predictability. The question is posed as an optimization problem in which the conditional entropy of gene subsets with respect to the synaptic connectivity phenotype is minimized. We investigate the use of single- and multi-objective estimation of distribution algorithms and focus on real data from C. elegans synaptic connectivity. We show that the introduced algorithms are able to compute gene sets that allow an accurate synapse predictability. However, the multi-objective approach can simultaneously search for gene sets with different number of genes. Our results also indicate that optimization problems defined on constrained binary spaces remain challenging for the conception of competitive estimation of distribution algorithm.

The successful application of estimation of distribution algorithms (EDAs) to solve different kinds of problems has reinforced their candidature as promising black-box optimization tools. However, their internal behavior is still not completely understood and therefore it is necessary to work in this direction in order to advance their development. This paper presents a methodology of analysis which provides new information about the behavior of EDAs by quantitatively analyzing the probabilistic models learned during the search. We particularly focus on calculating the probabilities of the optimal solutions, the most probable solution given by the model and the best individual of the population at each step of the algorithm. We carry out the analysis by optimizing functions of different nature such as Trap5, two variants of Ising spin glass and Max-SAT. By using different structures in the probabilistic models, we also analyze the impact of the structural model accuracy in the quantitative behavior of EDAs. In addition, the objective function values of our analyzed key solutions are contrasted with their probability values in order to study the connection between function and probabilistic models. The results not only show information about the internal behavior of EDAs, but also about the quality of the optimization process and setup of the parameters, the relationship between the probabilistic model and the fitness function, and even about the problem itself. Furthermore, the results allow us to discover common patterns of behavior in EDAs and propose new ideas in the development of this type of algorithms.

Which problems a search algorithm can effectively solve is a fundamental issue that plays a key role in understanding and developing algorithms. In order to study the ability limit of estimation of distribution algorithms (EDAs), this paper experimentally tests three different EDA implementations on a sequence of additively decomposable functions (ADFs) with an increasing number of interactions among binary variables. The results show that the ability of EDAs to solve problems could be lost immediately when the degree of variable interaction is larger than a threshold. We argue that this phase-transition phenomenon is closely related with the computational restrictions imposed in the learning step of this type of algorithms. Moreover, we demonstrate how the use of unrestricted Bayesian networks rapidly becomes inefficient as the number of sub-functions in an ADF increases. The study conducted in this paper is useful in order to identify patterns of behavior in EDAs and, thus, improve their performances.

Estimation of Distribution Algorithms are a class of evolutionary algorithms characterized by the use of probabilistic models. These algorithms have been applied successfully to a wide set of artificial and real-world problems, achieving competitive results in most scenarios. Nevertheless, there are some problems whose solutions can be naturally represented as a permutation, for which EDAs have not been extensively developed. Although some work has been done in this area, most of the approaches are adaptations of EDAs designed for problems based on integer or real domains, and only a few algorithms have been specifically designed to deal with permutation-based problems. In this paper, we present an EDA that learns probability distributions over permutations. Particularly, our approach is based on the use of k-order marginals. In addition, we carry out some preliminary experiments over classical permutation-based problems in order to study the performance of the proposed k-order marginals EDA.

In many optimization problems, regardless of the domain to which it belongs, the structural component that the interactions among variables provides can be seen as a network. The impact that the topological characteristics of that network has, both in the hardness of the problem and in the performance of the optimization techniques, constitutes a very important subject of research. In this paper, we study the behavior of estimation of distribution algorithms (EDAs) in functions whose structure is defined by using different network topologies which include grids, small-world networks and random graphs. In order to do that, we use several descriptors such as the population size, the number of evaluations as well as the structures learned during the search. Furthermore, we take measures from the field of complex networks such as clustering coefficient or characteristic path length in order to quantify the topological properties of the function structure and analyze their relation with the behavior of EDAs. The results show that these measures are useful to have better understanding of this type of algorithms which have exhibited a high sensitivity to the topological characteristics of the function structure. This study creates a link between EDAs based on Bayesian networks and the emergent field of complex networks.

In this paper we quantitatively analyze the probability distributions generated by an EDA during the search. In particular, we record the probabilities to the optimal solution, the solution with the highest probability and that of the best individual of the population, when the EDA is solving a trap function. By using different structures in the probabilistic models we can analyze the influence of the structural model accuracy on the aforementioned probability values. In addition, the objective function values of these solutions are contrasted with their probability values in order to study the connection between the function and the probabilistic model. The results provide new information about the behavior of the EDAs and they open a discussion regarding which are the minimum (in)dependences necessary to reach the optimum.

This paper introduces a evolutionary computation method that applies Bayesian classifiers to optimization problems. This approach is based on Estimation of Distribution Algorithms (EDAs) in which Bayesian or Gaussian networks are applied to the evolution of a population of individuals (i.e. potential solutions to the optimization problem) in order to improve the quality of the individuals of the next generation. Our new approach, called Evolutionary Bayesian Classifier-based Optimization Algorithm (EBCOA), employs Bayesian classifiers instead of Bayesian or Gaussian networks in order to evolve individuals to a fitter population. In brief, EBCOAs are characterized by applying Bayesian classification techniques – usually applied to supervised classification problems – to optimization in continuous domains. We propose and review in this paper different Bayesian classifiers for implementing our EBCOA method, focusing particularly on EBCOAs applying naïve Bayes, semi-na¨ive Bayes, and tree augmented na¨ive Bayes classifiers. This work presents a deep study on the behavior of these algorithms with classical optimiztion problems in continuous domains. The different parameters used for tuning the performance of the algorithms are discussed, and a comprehensive overview of their influence is provided. We also present experimental results to compare this new method with other state of the art approaches of the evolutionary computation field for continuous domains such as Evolutionary Strategies (ES) and Estimation of Distribution Algorithms (EDAs).

Estimation of Distribution Algorithms (EDAs) are a set of optimization techniques that have been successfully applied to different kinds of problems. In this paper, we deal with the creation of multivariate calibration models in quantitative chemistry. For this purpose, we use parallel implementations of two EDAs (EBNABIC and UMDA), using different approaches to create a calibration model using data obtained from controlled reactions. Once the calibration model has been trained, it can be used to predict initial concentrations for some species taking part in new reactions. The results show that these new approaches are able to obtain good-quality calibration models. Moreover, the use of parallel algorithms allows researchers to complete experiments faster and to study a wider set of alternative solutions.

This paper proposes new parallel versions of some estimation of distribution algorithms (EDAs). Focus is on maintenance of the behavior of sequential EDAs that use probabilistic graphical models (Bayesian networks and Gaussian networks), implementing a master-slave workload distribution for the most computationally intensive phases: learning the probability distribution and, in one algorithm, "sampling and evaluation of individuals." In discrete domains, we explain the parallelization of EBNA/sub BIC/ and EBNA/sub PC/ algorithms, while in continuous domains, the selected algorithms are EGNA/sub BIC/ and EGNA/sub EE/. Implementation has been done using two APIs: message passing interface and POSIX threads. The parallel programs can run efficiently on a range of target parallel computers. Experiments to evaluate the programs in terms of speed up and efficiency have been carried out on a cluster of multiprocessors. Compared with the sequential versions, they show reasonable gains in terms of speed.