Diffusion models have demonstrated remarkable success in modeling high-dimensional probability distributions within machine learning. Their potential for modeling search distributions in combinatorial optimization, however, remains largely unexplored. This paper bridges this gap by integrating diffusion models into Estimation of Distribution Algorithms (EDAs). We propose two novel EDAs: a diffusion-by-denoising EDA (Diff-EDA) and a diffusion-by-deblending EDA (DbD-EDA), both adapted for discrete optimization. Key adaptations include the use of Gumbel-Softmax for discrete variables, fitness-guided sampling, and tailored loss functions. Through extensive experiments on benchmark additive functions and combinatorial problem instances (SAT, Ising, UBQP), we validate the effectiveness of the proposed algorithms. Our results show that diffusion-based EDAs can outperform classical EDAs based on probabilistic graphical models and contemporary neural-network-based EDAs, particularly on problems with complex variable interactions. This work establishes a new direction for EDAs, demonstrating that diffusion models can provide a powerful and flexible framework for learning and sampling from search distributions in evolutionary optimization.

Recent advances in Scientific Machine Learning have shown that second-order methods can enhance the training of Physics-Informed Neural Networks (PINNs), making them a suitable alternative to traditional numerical methods for Partial Differential Equations (PDEs). However, second-order methods induce large memory requirements, making them scale poorly with the model size. In this paper, we define a local Mixture of Experts (MoE) combining the parameter-efficiency of ensemble models and sparse coding to enable the use of second-order training. Our model -- PINN Balls -- also features a fully learnable domain decomposition structure, achieved through the use of Adversarial Adaptive Sampling (AAS), which adapts the DD to the PDE and its domain. PINN Balls achieves better accuracy than the state-of-the-art in scientific machine learning, while maintaining invaluable scalability properties and drawing from a sound theoretical background.

In scheduling problems common in the industry and various real-world scenarios, responding in real-time to disruptive events is important. Recent methods propose the use of deep reinforcement learning (DRL) to learn policies capable of generating solutions under this constraint. However, current DRL approaches struggle with large instances, which are common in real-world scenarios. The objective of this paper is to introduce a new DRL method for solving the flexible job-shop scheduling problem, with a focus on these type of instances. The approach is based on the use of heterogeneous graph neural networks to a more informative graph representation of the problem. This novel modeling of the problem enhances the policy’s ability to capture state information and improve its decision-making capacity. Additionally, we introduce two novel approaches to enhance the performance of the DRL approach: the first involves generating a diverse set of scheduling policies, while the second combines DRL with dispatching rules (DRs) constraining the action space, with a variable degree of freedom depending on the chosen policy. Experimental results on two public benchmarks show that our approach outperforms DRs and achieves superior results compared to three state-of-the-art DRL methods, particularly for large instances.

Publisher Copyright: © 2024 The Authors

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.

Unattributed-identity multi-target regression (UIMTR) is defined as a multi-target regression problem in which the identity of the target and predictor variables is not predefined. It is a problem that can be found in several real-world applications. For example, when historical data is available from a set of devices, but real-time data can only be requested from a subset of them (so called sentinels). For estimating real-time status of non-sentinels, it will be necessary to generate multi-target regression models. Therefore, attributing the identity of the real-time communicators (sentinels), i.e., the predictor variables, is a critical aspect. Moreover, unlike classical feature selection problems, the set of target variables is determined after applying the selection methods and not before, thus, some adaptations are necessary. We introduce three novel methods to solve the UIMTR and, after extensive evaluation, we demonstrate: (i) the feasibility of the methods, (ii) the usefulness of the approach, and (iii) the improvement over other classical techniques. The results have been evaluated from three perspectives: (i) the quality of the predictions, (ii) the stability of the methods and (iii) the execution time .

Abstract Generalization is a key property of machine learning models to perform accurately on unseen data. Conversely, in the field of scientific machine learning (SciML), generalization entails not only predictive accuracy but also the capacity of the model to encapsulate underlying physical principles. In this paper, we delve into the concept of generalization for Physics-informed neural networks (PINNs) by investigating the consistency of the predictions of a PINN outside of its training domain. Through the lenses of a novel metric and statistical analysis, we study the scenarios in which a PINN can provide consistent predictions outside the region considered for training and hereinafter assess whether the algorithmic setup of the model can influence its potential for generalizing. Our results highlight why overparametrization is not a crucial component in SciML while encouraging overfitting on the training data. Despite being counterintuitive, the outcome of our analysis serves as a guideline for training PINNs for engineering applications.

With the advent of new loads and generation on the low voltage grid, voltage fluctuation has increased, especially in active distribution grids with a high penetration of distributed resources and a large deployment of electric vehicles. The coordination of different technologies has emerged as the best way for voltage regulation, among others, smart inverters, open soft points or transformers with on-load regulation capability. This paper proposes a novel way to model the control strategies for the automatic voltage controller of On-Load Tap-Changer transformers. The purpose is to standardize and simplify the way these strategies are represented, in order to facilitate (i) their selection by Distribution System Operators, (ii) their future integration with other systems, and (iii) to increase the ability to anticipate On-Load Tap-Changer behavior. The proposal has been validated using real data, obtaining an accuracy of 99.15% in the tap changer positions. A unified framework is also introduced, which allows the proposed functional representation to be combined with the On-Load Tap-Changer controller behavior estimation. A experimental validation has been carried out where more than 150 000 strategies have been simulated, finally determining the one that best fits the objectives. Note to Practitioners—Historically, on-load tap-changing transformers have been used in high-voltage substations. However, with the integration of electric vehicles and the penetration of distributed energy resources, the need to implement this type of solution in low-voltage substations has grown. However, the characteristics and requirements are not the same, for example, given their nature, low voltage grids are more unbalanced and are often regulated to ensure the quality of supply. Therefore, inheriting the control strategies of traditional on-load tap changers may pose a serious risk. This paper proposes a novel unified framework that facilitates the modeling and simulation of almost any control strategy for distribution transformers with on-load tap changers. This will allow the choice of control parameters that minimize voltage deviation from the voltage setpoint and maximize device lifetime. Our proposal can be considered as a solution to the uncertainty of which control parameters to use. It can be performed before commissioning, based on historical data, or a posteriori, based on the collected data.

Regular vine copulas (R-vines) provide a comprehensive framework for modeling high-dimensional dependencies using a hierarchy of trees and conditional pair-copulas. While the graphical structure of R-vines is traditionally derived from data, this work introduces a novel approach by utilizing a (conditional) pairwise dependence list. Our primary goal is to construct R-vine graphs that include the maximum possible number of dependence relationships specified in such lists. To tackle this optimization challenge, characterized by exponential growth in the search space and the structural constraints of R-vines, we propose two distinct methodologies: A 0-1 linear programming formulation and a Genetic Algorithm (GA). Additionally, the Randomized Constructive Technique (RCT) is employed to generate the initial population of the GA, serving as a baseline for our comparison. Experimental results reveal the superior performance of the GA over the RCT in terms of success rate, incorporating more relationships than RCT into the constructed R-vine graphs and achieving near-optimal or optimal graph structures.

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.

Classification problems where there exist multiple class variables that need to be jointly predicted are known as Multi-dimensional classification problems. If the labels of these class variables are organized as hierarchies, we can take advantage of specific strategies designed for the Hierarchical classification paradigm. In this paper we present the Multi-dimensional hierarchical classification (MDHC) paradigm, a result of the combination of Multi-dimensional and Hierarchical classification paradigms. We propose four MDHC learning strategies which are designed to exploit the particularities of this new paradigm, combining characteristics of Multi-dimensional and Hierarchical classification strategies. Along with these strategies, we present a framework for classifier comparison in which we use a set of performance measures specifically designed for MDHC, and a procedure to create MDHC synthetic scenarios. Using this framework and the performance measures presented, we study how characteristics of the MDHC problems influence the performance of the different MDHC strategies proposed, and compare them to other non-MDHC strategies.

Despite the remarkable performance and generalization levels of deep learning models in a wide range of artificial intelligence tasks, it has been demonstrated that these models can be easily fooled by the addition of imperceptible yet malicious perturbations to natural inputs. These altered inputs are known in the literature as adversarial examples. In this paper, we propose a novel probabilistic framework to generalize and extend adversarial attacks in order to produce a desired probability distribution for the classes when we apply the attack method to a large number of inputs. This novel attack paradigm provides the adversary with greater control over the target model, thereby exposing, in a wide range of scenarios, threats against deep learning models that cannot be conducted by the conventional paradigms. We introduce four different strategies to efficiently generate such attacks, and illustrate our approach by extending multiple adversarial attack algorithms. We also experimentally validate our approach for the spoken command classification task and the Tweet emotion classification task, two exemplary machine learning problems in the audio and text domain, respectively. Our results demonstrate that we can closely approximate any probability distribution for the classes while maintaining a high fooling rate and even prevent the attacks from being detected by label-shift detection methods.

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.

Human-machine interaction is increasingly dependent on speech communication, mainly due to the remarkable performance of Machine Learning models in speech recognition tasks. However, these models can be fooled by adversarial examples, which are inputs intentionally perturbed to produce a wrong prediction without the changes being noticeable to humans. While much research has focused on developing new techniques to generate adversarial perturbations, less attention has been given to aspects that determine whether and how the perturbations are noticed by humans. This question is relevant since high fooling rates of proposed adversarial perturbation strategies are only valuable if the perturbations are not detectable. In this paper we investigate to which extent the distortion metrics proposed in the literature for audio adversarial examples, and which are commonly applied to evaluate the effectiveness of methods for generating these attacks, are a reliable measure of the human perception of the perturbations. Using an analytical framework, and an experiment in which 36 subjects evaluate audio adversarial examples according to different factors, we demonstrate that the metrics employed by convention are not a reliable measure of the perceptual similarity of adversarial examples in the audio domain.

The main objective of the EMPATHIC project has been the design and development of a virtual coach to engage the healthy-senior user and to enhance well-being through awareness of personal status. The EMPATHIC approach addresses this objective through multimodal interactions supported by the GROW coaching model. The paper summarizes the main components of the EMPATHIC Virtual Coach (EMPATHIC-VC) and introduces a demonstration of the coaching sessions in selected scenarios.

An End-Of-Turn Detection Module (EOTD-M) is an essential component of automatic Spoken Dialogue Systems. The capability of correctly detecting whether a user’s utterance has ended or not improves the accuracy in interpreting the meaning of the message and decreases the latency in the answer. Usually, in dialogue systems, an EOTD-M is coupled with an Automatic Speech Recognition Module (ASR-M) to transmit complete utterances to the Natural Language Understanding unit. Mistakes in the ASR-M transcription can have a strong effect on the performance of the EOTD-M. The actual extent of this effect depends on the particular combination of ASR-M transcription errors and the sentence featurization techniques implemented as part of the EOTD-M. In this paper we investigate this important relationship for an EOTD-M based on semantic information and particular characteristics of the speakers (speech profiles). We introduce an Automatic Speech Recognition Simulator (ASR-SIM) that models different types of semantic mistakes in the ASR-M transcription as well as different speech profiles. We use the simulator to evaluate the sensitivity to ASR-M mistakes of a Long Short-Term Memory network classifier trained in EOTD with different featurization techniques. Our experiments reveal the different ways in which the performance of the model is influenced by the ASR-M errors. We corroborate that not only is the ASR-SIM useful to estimate the performance of an EOTD-M in customized noisy scenarios, but it can also be used to generate training datasets with the expected error rates of real working conditions, which leads to better performance.

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.

The traveling thief problem (TTP) has emerged as a realistic multi-component problem that poses a number of challenges to traditional optimizers. In this paper we propose different ways to incorporate dynamic programming (DP) as a local optimization operator of population-based approaches to the biobjective TTP. The DP operators use different characterizations of the TTP instance to search for packing plans that improve the best current solutions. We evaluate the efficiency of the DP-based operators using TTP instances of up to 33810 cities and 338100 items, and compare the results of the DP operators with state-of-the-art algorithms for these instances. Our results show that DP-based approaches, applied individually and in combination with other types of operators, can produce good approximations of the Pareto sets for these problems.

Knowledge transfer between tasks can significantly improve the efficiency of machine learning algorithms. In supervised natural language understanding problems, this sort of improvement is critical since the availability of labelled data is usually scarce. In this paper we address the question of transfer learning between related topic classification tasks. A characteristic of our problem is that the tasks have a hierarchical relationship. Therefore, we introduce and validate how to implement the transfer exploiting this hierarchical structure. Our results for a real-world topic classification task show that the transfer can produce improvements in the behavior of the classifiers for some particular problems.

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.

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.

Fitness landscape analysis investigates features with a high influence on the performance of optimization algorithms, aiming to take advantage of the addressed problem characteristics. In this work, a fitness landscape analysis using problem features is performed for a Multi-objective Bayesian Optimization Algorithm (mBOA) on instances of MNK-Iandscape problem for 2, 3, 5 and 8 objectives. We also compare the results of mBOA with those provided by NSGA-III through the analysis of their estimated runtime necessary to identify an approximation of the Pareto front. Moreover, in order to scrutinize the probabilistic graphic model obtained by mBOA, the Pareto front is examined according to a probabilistic view. The fitness landscape study shows that mBOA is moderately or loosely influenced by some problem features, according to a simple and a multiple linear regression model, which is being proposed to predict the algorithms performance in terms of the estimated runtime. Besides, we conclude that the analysis of the probabilistic graphic model produced at the end of evolution can be useful to understand the convergence and diversity performances of the proposed approach.

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.

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.

Multi-objective Estimation of Distribution Algorithms (MOEDAS) have been successfully applied to solve Multi-objective Optimization Problems (MOPs) since they are able to model dependencies between variables of the problem and then sample new solutions to guide the search to promising areas. A state-of-the-art optimizer for single-objective continuous functions that also uses probabilistic modeling is the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Different variants of CMA-ES have been proposed for MOPs however most of them are based on Pareto dominance as the main selection criterion. Recently, a new multi-objective CMA-ES called MOEA/D-CMA was proposed combining the strengths of CMA-ES with those of the multi-objective evolutionary algorithm based on decomposition (MOEA/D). Nowadays, however, researchers on MOEAs agree that combining Pareto and decomposition can be beneficial for the search on MOPs. As a result, a new MOEA has been proposed, called MOEA/DD. This algorithm modifies the MOEA/D by including a new Pareto dominance update mechanism that brings more diversity into the search. In this study, we extend the MOEA/D-CMA by replacing its update mechanism by the one of MOEA/DD. The hypothesis is that this update mechanism will improve the performance of MOEA/D-CMA as it improved MOEA/D. MOEA/D-CMA and MOEA/DD-CMA are implemented and evaluated through an experimental study. The experimental study involves two well-known families of benchmark problems whose objective numbers scale from two to fifteen. Then, an extensive statistical analysis of the results is made to extract sound, statistically supported conclusions about the performance of the algorithms as the number of objectives scales.

The Protein Structure Prediction (PSP) problem is one of the modern most challenging problems from science. Simplified protein models are usually applied to simulate and study some characteristics of the protein folding process. Hence, many heuristic strategies have been applied in order to find simplified protein structures in which the protein configuration has the minimal energy. However, these strategies have difficulties in finding the optimal solutions to the longer sequences of amino-acids, due to the complexity of the problem and the huge amount of local optima. Hyper heuristics have proved to be useful in this type of context since they try to combine different heuristics strengths into a single framework. However, there is lack of work addressing the automated design of hyper-heuristics components. This paper proposes GEHyPSP, an approach which aims to achieve generation, through grammatical evolution, of selection mechanisms and acceptance criteria for a hyper-heuristic framework applied to PSP problem. We investigate the strengths and weaknesses of our approach on a benchmark of simplified protein models. GEHyPSP was able to reach the best known results for 7 instances from 11 that composed the benchmark set used to evaluate the approach.

Estimation of distribution algorithms (EDAs) are evolutionary algorithms that use probabilistic modeling to lead a more efficient search for optimal solutions. While EDAs have been applied to several types of optimization problems, they exhibit some limitations to deal with constrained optimization problems. More study and understanding of how can EDAs deal with these problems is required. In this paper we investigate the application of EDAs to a version of the vehicle routing problem in which solutions should satisfy a number of constraints involving the customers, the fleet vehicle, and the items to be delivered. For this problem, we compare two different representations of the solutions, and apply EDAs that use three probabilistic models with different characteristics. Our results show that the combination of an integer representation with tree-based probabilistic model produces the best results and is able to solve vehicle routing problems that contain over thousands of promising paths.

Empirical analysis of evolutionary algorithms (EAs) behavior is usually approached by computing relatively simple descriptive statistics like mean fitness and mean number of evaluations to convergence, or more theoretically sound statistical tests for finding significant differences between algorithms. However, these analyses do not consider situations where the EA failed to finish due to numerical errors or excessive computational time. Furthermore, the ability of an EA to continuously make search improvements is usually overlooked. In this paper we propose the use of the theory from survival analysis for empirically investigating the behavior of EAs, even in situations where not all the experiments finish in a reasonable time. We introduce two scenarios for the application of survival analysis in EAs. Survival trees, a machine learning technique adapted to the survival analysis scenario, are applied to automatically identify combinations of EA parameters with similar effect in the behavior of the algorithm.

The problem of obtaining maximal nonlinearity in Boolean functions is well researched, both from the cryptographic and the evolutionary computation side. However, the results are still not conclusive enough to be able to show how good a heuristic approach is when tackling this problem. In this paper, we investigate how to obtain the maximal possible nonlinearity in balanced Boolean functions, but we also analyze how difficult is the problem itself. In order to do so, we conduct experiments with Estimation of distribution algorithms as well as the fitness landscape analysis and the deception analysis. Our results indicate that the first difficulties arise from the inappropriate fitness function and representation of solutions coupled with a huge search space. The fitness landscape analysis does not reveal any significant differences that could justify the assumed jump in problem difficulty when going from Boolean functions with 6 inputs to those with 8 inputs. Finally, we show that this problem is not order-1 deceptive.

Probabilistic modeling of selected solutions and incorporation of local search methods are approaches that can notably improve the results of multi-objective evolutionary algorithms (MOEAs). In the past, these approaches have been jointly applied to multi-objective problems (MOPs) with excellent results. In this paper, we introduce for the first time a joint probabilistic modeling of (1) local search methods with (2) decision variables and (3) the objectives in a framework named HMOBEDA. The proposed approach is compared with six evolutionary methods (including a modified version of NSGA-III, adapted to solve combinatorial optimization) on instances of the multi-objective knapsack problem with 3, 4, and 5 objectives. Results show that HMOBEDA is a competitive approach. It outperforms the other methods according to the hypervolume indicator.

Chimera graphs define the topology of one of the first commercially available quantum computers. A variety of optimization problems have been mapped to this topology to evaluate the behavior of quantum enhanced optimization heuristics in relation to other optimizers, being able to efficiently solve problems classically to use them as benchmarks for quantum machines. In this paper we investigate for the first time the use of Evolutionary Algorithms (EAs) on Ising spin glass instances defined on the Chimera topology. Three genetic algorithms (GAs) and three estimation of distribution algorithms (EDAs) are evaluated over 1000 hard instances of the Ising spin glass constructed from Sidon sets. We focus on determining whether the information about the topology of the graph can be used to improve the results of EAs and on identifying which are the characteristics of the Ising instances that influence the success rate of GAs and EDAs. Chimera graphs define the topology of one of the first commercially available quantum computers. A variety of optimization problems have been mapped to this topology to evaluate the behavior of quantum enhanced optimization heuristics in relation to other optimizers, being able to efficiently solve problems classically to use them as benchmarks for quantum machines. In this paper we investigate for the first time the use of Evolutionary Algorithms (EAs) on Ising spin glass instances defined on the Chimera topology. Three genetic algorithms (GAs) and three estimation of distribution algorithms (EDAs) are evaluated over 1000 hard instances of the Ising spin glass constructed from Sidon sets. We focus on determining whether the information about the topology of the graph can be used to improve the results of EAs and on identifying the characteristics of the Ising instances that influence the success rate of GAs and EDAs.

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.

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.

We explore the problem space of maximum nonlinearity problems for balanced Boolean functions, examining the symmetry structure and fitness landscapes in the most common (bit string) representation. We present theoretical analyses of well understood aspects, together with detailed enumeration of the 4-bit problem, sampling of the 6-bit problem based on known optima, and sampling of the 8-bit problem based on its fittest known solutions.

This paper proposes a new multiobjective estimation of distribution algorithm (EDA) based on joint probabilistic modeling of objectives and variables. This EDA uses the multidimensional Bayesian network as its probabilistic model. In this way, it can capture the dependencies between objectives, variables and objectives, as well as the dependencies learned between variables in other Bayesian network-based EDAs. This model leads to a problem decomposition that helps the proposed algorithm find better tradeoff solutions to the multiobjective problem. In addition to Pareto set approximation, the algorithm is also able to estimate the structure of the multiobjective problem. To apply the algorithm to many-objective problems, the algorithm includes four different ranking methods proposed in the literature for this purpose. The algorithm is first applied to the set of walking fish group problems, and its optimization performance is compared with a standard multiobjective evolutionary algorithm and another competitive multiobjective EDA. The experimental results show that on several of these problems, and for different objective space dimensions, the proposed algorithm performs significantly better and on some others achieves comparable results when compared with the other two algorithms. The algorithm is then tested on the set of CEC09 problems, where the results show that multiobjective optimization based on joint model estimation is able to obtain considerably better fronts for some of the problems compared with the search based on conventional genetic operators in the state-of-the-art multiobjective evolutionary algorithms.

Symmetry has hitherto been studied piecemeal in a variety of evolutionary computation domains, with little consistency between the definitions. Here we provide formal definitions of symmetry that are consistent across the field of evolutionary computation. We propose a number of evolutionary and estimation of distribution algorithms suitable for variable symmetries in Cartesian power domains, and compare their utility, integration of the symmetry knowledge with the probabilistic model of an EDA yielding the best outcomes. We test the robustness of the algorithm to inexact symmetry, finding adequate performance up to about 1% noise. Finally, we present evidence that such symmetries, if not known a priori, may be learnt during evolution.

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

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.

Brain computer interfaces (BCIs) allow the direct human-computer interaction without the need of motor intervention. To properly and efficiently decode brain signals into computer commands the application of machine-learning techniques is required. Evolutionary algorithms have been increasingly applied in different steps of BCI implementations. In this paper we introduce the use of the covariance matrix adaptation evolution strategy (CMA-ES) for BCI systems based on motor imagery. The optimization algorithm is used to evolve linear classifiers able to outperform other traditional classifiers. We also analyze the role of modeling variables interactions for additional insight in the understanding of the BCI paradigms.

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.

Neurotransmitters used by chemical synapses are stored in synaptic vesicles that accumulate in axon terminals. The number and position of these vesicles have been related to some important functional properties of the synapse. For this reason, an accurate mechanism for semi-automatically counting these small cellular structures will be of great help for neuroscientists. In this paper, we present a Differential Evolution algorithm that quantifies the number of synaptic vesicles in electron micrographs. The algorithm has been tested on several images that have been obtained from the somatosensory cortex of the rat and compared with some traditional approaches for detecting circular structures. Finally, the results have been validated by two independent expert anatomists.

Tumor classification based on gene expression data can be applied to set appropriate medical treatment according to the specific tumor characteristics. In this paper we propose the use of estimation of distribution algorithms (EDAs) to enhance the performance of affinity propagation (AP) in classification problems. AP is an efficient clustering algorithm based on message-passing methods and which automatically identifies exemplars of each cluster. We introduce an EDA-based procedure to compute the preferences used by the AP algorithm. Our results show that AP performance can be notably improved by using the introduced approach. Furthermore, we present evidence that classification of new data is improved by employing previously identified exemplars with only minor decrease in classification accuracy.

k-order Markov models have been introduced to estimation of distribution algorithms (EDAs) to solve a particular class of optimization problems in which each variable depends on its previous k variables in a given, fixed order. In this paper we investigate the use of regularization as a way to approximate k-order Markov models when $k$ is increased. The introduced regularized models are used to balance the complexity and accuracy of the k-order Markov models. We investigate the behavior of the EDAs in several instances of the hydrophobic-polar (HP) protein problem, a simplified protein folding model. Our preliminary results show that EDAs that use regularized approximations of the k-order Markov models offer a good compromise between complexity and efficiency, and could be an appropriate choice when the number of variables is increased.

The P300 component of the brain event-related-potential is one of the most used signals in brain computer interfaces (BCIs). One of the required steps for the application of the P300 paradigm is the identification of this component in the presence of stimuli. In this paper we propose a direct optimization approach to the P300 classification problem. A general formulation of the problem is introduced. Different classes of optimization algorithms are applied to solve the problem and the concepts of k-best and k-worst ensembles of solutions are introduced as a way to improve the accuracy of single solutions. The introduced approaches are able to achieve a classification rate over 80% on test data.

This paper investigates the use of empirical and Archimedean copulas as probabilistic models of continuous estimation of distribution algorithms (EDAs). A method for learning and sampling empirical bivariate copulas to be used in the context of n-dimensional EDAs is first introduced. Then, by using Archimedean copulas instead of empirical makes possible to construct n-dimensional copulas with the same purpose. Both copula-based EDAs are compared to other known continuous EDAs on a set of 24 functions and different number of variables. Experimental results show that the proposed copula-based EDAs achieve a better behaviour than previous approaches in a 20% of the benchmark functions.

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.

Estimation of distribution algorithms (EDAs) that use marginal product model factorizations have been widely applied to a broad range of mainly binary optimization problems. In this paper, we introduce the affinity propagation EDA (AffEDA) which learns a marginal product model by clustering a matrix of mutual information learned from the data using a very efficient message-passing algorithm known as affinity propagation. The introduced algorithm is tested on a set of binary and nonbinary decomposable functions and using a hard combinatorial class of problem known as the HP protein model. The results show that the algorithm is a very efficient alternative to other EDAs that use marginal product model factorizations such as the extended compact genetic algorithm (ECGA) and improves the quality of the results achieved by ECGA when the cardinality of the variables is increased.

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.

One of the uses of the probabilistic models learned by estimation of distribution algorithms is to reveal previous unknown information about the problem structure. In this paper we investigate the mapping between the problem structure and the dependencies captured in the probabilistic models learned by EDAs for a set of multi-objective satisfiability problems. We present and discuss the application of different data mining and visualization techniques for processing and visualizing relevant information from the structure of the learned probabilistic models. We show that also in the case of multi-objective optimization problems, some features of the original problem structure can be translated to the probabilistic models and unveiled by using algorithms that mine the model structures.

This paper introduces the component weighting approach as a general optimization heuristic to increase the likelihood of escaping from local optima by dynamically modifying the fitness function. The approach is tested on the optimization of the simplified hydrophobic-polar (HP) protein problem using estimation of distribution algorithms (EDAs). We show that the use of component weighting together with statistical information extracted from the set of selected solutions considerably improve the results of EDAs for the HP problem. The paper also elaborates on the use of probabilistic modeling for the definition of dynamic fitness functions and on the use of combinations of models.

The key ideas behind most of the recently proposed Markov networks based EDAs were to factorise the joint probability distribution in terms of the cliques in the undirected graph. As such, they made use of the global Markov property of the Markov network. Here we presents a Markov Network based EDA that exploits Gibbs sampling to sample from the Local Markov property, the Markovianity, and does not directly model the joint distribution. We call it Markovianity based Optimisation Algorithm. Some initial results on the performance of the proposed algorithm shows that it compares well with other Bayesian network based EDAs.

Simplified lattice models have played an important role in protein structure prediction and protein folding problems. These models can be useful for an initial approximation of the protein structure, and for the investigation of the dynamics that govern the protein folding process. Estimation of distribution algorithms (EDAs) are efficient evolutionary algorithms that can learn and exploit the search space regularities in the form of probabilistic dependencies. This paper introduces the application of different variants of EDAs to the solution of the protein structure prediction problem in simplified models, and proposes their use as a simulation tool for the analysis of the protein folding process. We develop new ideas for the application of EDAs to the bidimensional and tridimensional (2-d and 3-d) simplified protein folding problems. This paper analyzes the rationale behind the application of EDAs to these problems, and elucidates the relationship between our proposal and other population-based approaches proposed for the protein folding problem. We argue that EDAs are an efficient alternative for many instances of the protein structure prediction problem and are indeed appropriate for a theoretical analysis of search procedures in lattice models. All the algorithms introduced are tested on a set of difficult 2-d and 3-d instances from lattice models. Some of the results obtained with EDAs are superior to the ones obtained with other well-known population-based optimization algorithms.

This paper introduces exact learning of Bayesian networks in estimation of distribution algorithms. The estimation of Bayesian network algorithm (EBNA) is used to analyze the impact of learning the optimal (exact) structure in the search. By applying recently introduced methods that allow learning optimal Bayesian networks, we investigate two important issues in EDAs. First, we analyze the question of whether learning more accurate (exact) models of the dependencies implies a better performance of EDAs. Second, we are able to study the way in which the problem structure is translated into the probabilistic model when exact learning is accomplished.

This article reviews machine learning methods for bioinformatics. It presents modelling methods, such as supervised classification, clustering and probabilistic graphical models for knowledge discovery, as well as deterministic and stochastic heuristics for optimization. Applications in genomics, proteomics, systems biology, evolution and text mining are also shown.

In this paper, we investigate two issues related to probabilistic modeling in estimation of distribution algorithms (EDAs). First, we analyze the effect of selection in the arousal of probability dependencies in EDAs for random functions. We show that, for these functions, independence relationships not represented by the function structure are likely to appear in the probability model. Second, we propose an approach to approximate probability distributions in EDAs using a subset of the dependencies that exist in the data. An EDA that employs only malign interactions is introduced. Preliminary experiments presented show how the probability approximations based solely on malign interactions, can be applied to EDAs.

The question of finding feasible ways for estimating probability distributions is one of the main challenges for Estimation of Distribution Algorithms (EDAs). To estimate the distribution of the selected solutions, EDAs use factorizations constructed according to graphical models. The class of factorizations that can be obtained from these probability models is highly constrained. Expanding the class of factorizations that could be employed for probability approximation is a necessary step for the conception of more robust EDAs. In this paper we introduce a method for learning a more general class of probability factorizations. The method combines a reformulation of a probability approximation procedure known in statistical physics as the Kikuchi approximation of energy, with a novel approach for finding graph decompositions. We present the Markov Network Estimation of Distribution Algorithm (MN-EDA), an EDA that uses Kikuchi approximations to estimate the distribution, and Gibbs Sampling (GS) to generate new points. A systematic empirical evaluation of MN-EDA is done in comparison with different Bayesian network based EDAs. From our experiments we conclude that the algorithm can outperform other EDAs that use traditional methods of probability approximation in the optimization of functions with strong interactions among their variables.

The Boltzmann distribution is a good candidate for a search distribution for optimization problems. We compare two methods to approximate the Boltzmann distribution - Estimation of Distribution Algorithms (EDA) and Markov Chain Monte Carlo methods (MCMC). It turns out that in the space of binary functions even blocked MCMC methods outperform EDA on a small class of problems only. In these cases a temperature of T = 0 performed best.

The goal of this research is to analyze how individual learning interacts with an evolutionary algorithm in its search for best candidates for the Busy Beaver problem. To study this interaction, two learning models, implemented as local search procedures, are proposed. Experimental results show that, in highly irregular search spaces that are prone to premature convergence, local search methods are not an effective help to evolution. In addition, one interesting effect related to learning is reported: when the mutation rate is too high, learning acts as a repair, reintroducing some useful information that was lost.