Machine learning based predictions are increasingly used in sensitive decision-making applications that directly affect our lives. This has led to extensive research into ensuring the fairness of classifiers. Beyond just fair classification, emerging legislation now mandates that when a classifier delivers a negative decision, it must also offer actionable steps an individual can take to reverse that outcome. This concept is known as algorithmic recourse. Nevertheless, many researchers have expressed concerns about the fairness guarantees within the recourse process itself. In this work, we provide a theoretical characterization of unfairness in algorithmic recourse, formally linking fairness guarantees in recourse and classification, and highlighting limitations of the standard equal cost paradigm. We then introduce a novel fairness framework based on social burden, along with a practical algorithm (MISOB), broadly applicable under real-world conditions. Empirical results on real-world datasets show that MISOB reduces the social burden across all groups without compromising overall classifier accuracy.

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.

As automated classification systems become increasingly prevalent, concerns have emerged over their potential to reinforce and amplify existing societal biases. In the light of this issue, many methods have been proposed to enhance the fairness guarantees of classifiers. Most of the existing interventions assume access to group information for all instances, a requirement rarely met in practice. Fairness without access to demographic information has often been approached through robust optimization techniques, which target worst-case outcomes over a set of plausible distributions known as the uncertainty set. However, their effectiveness is strongly influenced by the chosen uncertainty set. In fact, existing approaches often overemphasize outliers or overly pessimistic scenarios, compromising both overall performance and fairness. To overcome these limitations, we introduce SPECTRE, a minimax-fair method that adjusts the spectrum of a simple Fourier feature mapping and constrains the extent to which the worst-case distribution can deviate from the empirical distribution. We perform extensive experiments on the American Community Survey datasets involving 20 states. The safeness of SPECTRE comes as it provides the highest average values on fairness guarantees together with the smallest interquartile range in comparison to state-of-the-art approaches, even compared to those with access to demographic group information. In addition, we provide a theoretical analysis that derives computable bounds on the worst-case error for both individual groups and the overall population, as well as characterizes the worst-case distributions responsible for these extremal performances.

The learning using privileged information paradigm leverages relevant features unavailable at deployment time for model training. In this paper, we propose a multi-task privileged framework that combines two types of tasks. First, the privileged-prediction task involves using regular features (available in both training and deployment) to predict privileged information, working as an intermediate step to guide the learning process. Second, the main learning objective, the target task, uses the predicted privileged information along with the regular features to make the final target prediction. Furthermore, knowledge distillation techniques are included within the target task to enhance the knowledge transfer of privileged information. Experimental results show improvements in tabular datasets and image-related problems compared to state-of-the-art approaches. Additionally, we analyze misclassification causes and refine the proposed multi-task privileged learning to reduce errors.

Advances in large models, reinforcement learning, and open-endedness have accelerated progress toward autonomous agents that can learn and interact in the real world. To achieve this, flexible tools are needed to create rich, yet computationally efficient, environments. While scalable 2D environments fail to address key real-world challenges like 3D navigation and spatial reasoning, more complex 3D environments are computationally expensive and lack features like customizability and multi-agent support. This paper introduces Craftium, a highly customizable and easy-to-use platform for building rich 3D single- and multi-agent environments. We showcase environments of different complexity and nature: from single- and multi-agent tasks to vast worlds with many creatures and biomes, and customizable procedural task generators. Benchmarking shows that Craftium significantly reduces the computational cost of alternatives of similar richness, achieving +2K steps per second more than Minecraft-based frameworks.

Multiple supervised learning scenarios are composed by a sequence of classification tasks. For instance, multi-task learning and continual learning aim to learn a sequence of tasks that is either fixed or grows over time. Existing techniques for learning tasks that are in a sequence are tailored to specific scenarios, lacking adaptability to others. In addition, most of existing techniques consider situations in which the order of the tasks in the sequence is not relevant. However, it is common that tasks in a sequence are evolving in the sense that consecutive tasks often have a higher similarity. This paper presents a learning methodology that is applicable to multiple supervised learning scenarios and adapts to evolving tasks. Differently from existing techniques, we provide computable tight performance guarantees and analytically characterize the increase in the effective sample size. Experiments on benchmark datasets show the performance improvement of the proposed methodology in multiple scenarios and the reliability of the presented performance guarantees.

The paradigm of learning using privileged information leverages privileged features present at training time, but not at prediction, as additional training information. The privileged learning process is addressed through a knowledge distillation perspective: information from a teacher learned with regular and privileged features is transferred to a student composed exclusively of regular features. While most approaches assume perfect knowledge for the teacher, it can commit mistakes. Assuming that, we propose a novel privileged distillation framework with a double contribution. Firstly, a designed function to imitate the teacher when it classifies correctly and to differ in cases of misclassification. Secondly, an adaptation of the cross-entropy loss to appropriately penalize the instances where the student outperforms the teacher. Its effectiveness is empirically demonstrated on datasets with imperfect teachers, significantly enhancing the performance of state-of-the-art frameworks. Furthermore, necessary conditions for successful privileged learning are presented, along with a dataset categorization based on the information provided by the privileged features. • Necessary conditions for a successful privileged learning based on information theory. • New categorization of the datasets derived from the information offered by the privileged features. • A novel privileged learning framework, Teacher Privileged Distillation (TPD), to deal with imperfect teachers.

We analyze three permutation-based combinatorial optimization problems in Fourier space, namely, the quadratic assignment problem, the linear ordering problem (LOP), and the symmetric and nonsymmetric traveling salesperson problem (STSP). In previous studies, one can find a number of theorems with necessary conditions that the Fourier coefficients of the aforementioned problems must satisfy. In this manuscript, we prove the sufficiency of these conditions, which implies that they constitute the exact characterization of the problems in Fourier space. In addition, the Fourier coefficients of the LOP and the symmetric and non-STSP are completely characterized by showing certain proportionality patterns that they must follow. Taking the characterization in Fourier space of the problems as a basis, we study classes of equivalent instances of the LOP and the symmetric and non-STSP, considering that two instances are equivalent if they have the same objective function. Furthermore, we give canonical representations for each problem in such a way that the input matrices have the minimum number of nonzero parameters.

Recent studies highlight the effectiveness of Bayesian methods in assessing algorithm performance, particularly in fairness and bias evaluation. We present Uncertainty Matters, a multi-objective uncertainty-aware algorithmic comparison framework. In fairness focused scenarios, it models sensitive group confusion matrices using Bayesian updates and facilitates joint comparison of performance (e.g., accuracy) and fairness metrics (e.g., true positive rate parity). Our approach works seamlessly with common evaluation methods like K-fold cross-validation, effectively addressing dependencies among the K posterior metric distributions. The integration of correlated information is carried out through a procedure tailored to the classifier’s complexity. Experiments demonstrate that the insights derived from algorithmic comparisons employing the Uncertainty Matters approach are more informative, reliable, and less influenced by particular data partitions. Code for the paper is publicly available at \url{https://github.com/abarrainkua/UncertaintyMatters}.

This work introduces a growable and modular neural network architecture that naturally avoids catastrophic forgetting and interference in continual reinforcement learning. The structure of each module allows the selective combination of previous policies along with its internal policy accelerating the learning process on the current task. Unlike previous growing neural network approaches, we show that the number of parameters of the proposed approach grows linearly with respect to the number of tasks, and does not sacrifice plasticity to scale. Experiments conducted in benchmark continuous control and visual problems reveal that the proposed approach achieves greater knowledge transfer and performance than alternative methods.

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.

Multimodal multiobjective optimization problems (MMOPs) have recently received considerable attention since they emerge in many real-world applications (e.g., in multiobjective knapsack problems and flow shop scheduling). However, MMOPs constitute a very particular class of problem. Indeed, looking for an adequate Pareto front (PF) representation is insufficient. MMOPs contain multiple subsets within the Pareto optimal Set, each independently mapping to the same Pareto Front. So, traditional multiobjective evolutionary algorithms (MOEAs) are inappropriate for solving MMOPs. This has motivated the design of algorithms which are suitable for addressing MMOPs. This paper proposes modifying MMOEA/DC, which is an algorithm specifically designed for solving MMOPs, that adopts a dual clustering method in both decision and objective space. Particularly, we were interested in using clustering in decision space, which allows classifying solutions into multiple local clusters. Our proposed approach modifies the neighborhood definition in order to provide more robustness to the algorithm as well as to improve the clustering process in decision space and to reduce the influence of the control parameters. The efficiency of the proposed framework is validated by comparing its performance on test instances of two test suites (MMF and MMMPO) with respect to the original MMOEA/DC and other state-of-the-art algorithms designed for solving MMOPs.

Many exact and metaheuristic algorithms presented in the literature are tested by comparing their performance in different sets of instances. However, it is known that when these sets of instances are generated randomly, they neither have nor fulfill the features the authors believe they do, which implies that wrong conclusions were made. In this paper, we reinforce the importance of analyzing randomly generated instances by sampling the problem coefficients uniformly at random. We generate instances of the Unconstrained Binary Quadratic Problem and the Number Partitioning Problem. In both cases, we verify that the generated set of instances do not represent a uniform set of instances of the problem. We have conducted several experiments to quantify the number of different rankings of solutions that the problems can generate. We have classified those rankings according to how often each ranking is sampled, how many local optimal solutions each ranking has, and how similar they are.

Combinatorial optimization seeks to uncover efficient algorithms for solving complex problem instances. While achieving the ultimate goal of universal optimization remains a challenge, progress in this direction yields valuable insights for the field. A critical initial step involves taxonomizing problems and instances through a common representation. In this presentation, we employ the Fourier transform framework to investigate permutation-based combinatorial optimization problems. Specifically, we examine the Fourier coefficients of various special cases of the quadratic assignment problem, revealing their inherent characteristics. Leveraging this decomposition, we explore the transition of the linear ordering problem from being tractable (P) to becoming NP-hard, shedding light on the intricacies of this transformation. Through this analysis, we advance our understanding of permutation-based combinatorial optimization, paving the way for potential algorithmic breakthroughs.

Previous works have shown that studying the characteristics of the Quadratic Assignment Problem (QAP) is a crucial step in gaining knowledge that can be used to design tailored meta-heuristic algorithms. One way to analyze the characteristics of the QAP is to decompose its objective function into a linear combination of orthogonal sub-functions that can be independently studied. In particular, this work focuses on a decomposition approach that has attracted considerable attention: the Elementary Landscape Decomposition (ELD).

Designing efficient local search based algorithms requires to consider the specific properties of the problems. We introduce a simple and efficient strategy, the Extended Reach, that escapes from local optima obtained from a best improvement local search and apply it to the linear ordering problem (LOP), the traveling salesperson problem (TSP) and the quadratic assignment problem (QAP). This strategy is based on two landscape properties observed in the literature. First, it considers that a local optimum is usually located in the frontier of its own attraction basin, and thus, it is enough to inspect the second order neighbors to reach a (better) solution inside an attraction basin of a better local optimum. Second, taking into account that for the LOP and specific neighborhoods it is possible to discard solutions without the need of being evaluated, we extend this result to the TSP with the 2-opt neighborhood to avoid the unnecessary evaluation of solutions. Efficient ways of evaluating the second order neighbors are also presented, based on the cost differences, reducing significantly the computation cost. Experimental results on random and benchmark instances show that our strategy, indeed, escapes from local optima despite its simplicity.

For a sequence of classification tasks that arrive over time, it is common that tasks are evolving in the sense that consecutive tasks often have a higher similarity. The incremental learning of a growing sequence of tasks holds promise to enable accurate classification even with few samples per task by leveraging information from all the tasks in the sequence (forward and backward learning). However, existing techniques developed for continual learning and concept drift adaptation are either designed for tasks with time-independent similarities or only aim to learn the last task in the sequence. This paper presents incremental minimax risk classifiers (IMRCs) that effectively exploit forward and backward learning and account for evolving tasks. In addition, we analytically characterize the performance improvement provided by forward and backward learning in terms of the tasks’ expected quadratic change and the number of tasks. The experimental evaluation shows that IMRCs can result in a significant performance improvement, especially for reduced sample sizes.

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.

Multivariate time series often contain missing values for reasons such as failures in data collection mechanisms. Since these missing values can complicate the analysis of time series data, imputation techniques are typically used to deal with this issue. However, the quality of the imputation directly affects the performance of downstream tasks. In this paper, we propose a selective imputation method that identifies a subset of timesteps with missing values to impute in a multivariate time series dataset. This selection, which will result in shorter and simpler time series, is based on both reducing the uncertainty of the imputations and representing the original time series as good as possible. In particular, the method uses multi-objective optimization techniques to select the optimal set of points, and in this selection process, we leverage the beneficial properties of the Multi-task Gaussian Process (MGP). The method is applied to different datasets to analyze the quality of the imputations and the performance obtained in downstream tasks, such as classification or anomaly detection. The results show that much shorter and simpler time series are able to maintain or even improve both the quality of the imputations and the performance of the downstream tasks.

A probabilistic framework for streaming novelty detection is proposed and illustrated with a mixture of Gaussian distributions that models the set of classes. Instances are predicted based on the probability of belonging to each of the classes. Those for which the model cannot provide confident predictions are introduced into a fixed-sized buffer. When the buffer is full, an Expectation Maximization (EM) algorithm is run to search for new emerging classes in the buffer, and update the current model. The EM algorithm has to deal with an scenario where both probability distributions and instances are available. To overcome this issue, the probability distributions (classes) are weighted. The weights are inferred using a meta-regression model which has been pretrained and supplied with the proposed algorithm. Experiments have been run using synthetic datasets to have a close control over the class arrival strategies, the shape, and the overlapping degree between classes. It is shown that when the assumptions of the probabilistic model are fulfilled, the proposed method outperforms literature non-parametric approaches. Furthermore it obtains competitive results in the case of non-Gaussian classes. The experiments reveal, for the first time, the high sensitivity of the novelty detection algorithms to the class arrival strategies.

This paper deals with imbalanced time series classification problems. In particular, we propose to learn time series classifiers that maximize the minimum recall of the classes rather than the accuracy. Consequently, we manage to obtain classifiers which tend to give the same importance to all the classes. Unfortunately, for most of the traditional classifiers, learning to maximize the minimum recall of the classes is not trivial (if possible), since it can distort the nature of the classifiers themselves. Neural networks, in contrast, are classifiers that explicitly define a loss function, allowing it to be modified. Given that the minimum recall is not a differentiable function, and therefore does not allow the use of common gradient-based learning methods, we apply and evaluate several smooth approximations of the minimum recall function. A thorough experimental evaluation shows that our approach improves the performance of state-of-the-art methods used in imbalanced time series classification, obtaining higher recall values for the minority classes, incurring only a slight loss in accuracy.

We decompose the linear ordering problem into a P and an NP-hard component by means of the Fourier transform. That is, we prove that the objective function can be expressed as the sum of two objective functions, one of which is associated with a P problem (an exact polynomial time algorithm is proposed to solve it), while the other is associated with an NP-hard problem. Based on this decomposition, we evaluate how different constructive algorithms whose behaviour only depends on univariate information degrade when the problem transits from P to NP-hard. A number of experiments are conducted with reduced dimensions, where the global optimum of the problems is known, giving different weights to the NP-hard component, while the weight of the P component is fixed.

The statistical characteristics of instance-label pairs often change with time in practical scenarios of supervised classification. Conventional learning techniques adapt to such concept drift accounting for a scalar rate of change by means of a carefully chosen learning rate, forgetting factor, or window size. However, the time changes in common scenarios are multidimensional, i.e., different statistical characteristics often change in a different manner. This paper presents adaptive minimax risk classifiers (AMRCs) that account for multidimensional time changes by means of a multivariate and high-order tracking of the time-varying underlying distribution. In addition, differently from conventional techniques, AMRCs can provide computable tight performance guarantees. Experiments on multiple benchmark datasets show the classification improvement of AMRCs compared to the state-of-the-art and the reliability of the presented performance guarantees.

Two-stage fuzzy methodology for the optimal planning of selection of temporary logistics hubs (TLHs) is developed. At the first stage, a q-rung orthopair fuzzy TOPSIS approach is developed to form and present expert knowledge about opening temporary logistics hubs. Fuzzy TOPSIS-based approach allows to determine the order of opening of TLHs and to provide post-disaster decision-making. At the second stage, by help of the built fuzzy TOPSIS aggregation a new objective function is given. By use of the built criterion TLHs’ total identification level of the order of establishment can be maximized, and together with the criterion concerning minimization of the selected TLHs’ quantity, poses a multi-objective facility location set covering problem. The offered approach is demonstrated by the example of temporary logistics y. The analysis of the results obtained revealed the importance of taking into account the opinions of multiple decision-makers for ensuring coordination in service delivery in disaster region.

In recent years, natural disasters such as earthquakes, floods, tsunamis, tornadoes, and others have resulted in a significant increase in loss of life and material property. They can cause severe and lasting damage to countries. When the suitable candidate places of shelters' (Shelter Sites (SSs)) location are selected, a group of sites should be selected from them that in some sense better meet the requirements such as: maximizing the reliability index of the selection of shelters, minimizing costs, maximizing evacuation coverage, etc. Ensuring timely evacuation of victims from disaster-affected areas is one of the most important tasks of the emergency management system. We assume fuzziness in the facility location problems’ models, because there is insufficient amount of objective information on disaster region data. A fuzzy multi-objective emergency shelters’ location and victims’ evacuation problem (FMOESLVEP) in the disaster-stricken region is constructed. The model objectives include (1) maximizing the total selection reliability index of opened shelters; (2) minimizing overall costs, including fixed costs for opening shelters, transportation costs for victims, and maintenance costs, (3) minimizing monotonous waiting times for total evacuation of victims, and (4) minimizing the number of open shelters. Objective functions (1) and (3) are novel and their construction and study issues are one of the important tasks of this work.

The consequences of natural disasters have significantly increased the loss of human life and material damage in recent years. Such disasters as earthquakes, tsunamis, tornadoes and others can cause serious and lasting damage to regions and countries. Therefore, it is important to know how the transport fleets are organized and managed in the disaster areas, as it makes a crucial contribution to the efficiency of the relief distribution process. When the suitable places of distribution centers (DCs) are selected, a group of places should be selected from them that in some sense better meet the requirements such as: maximizing the reliability index of the selection of DCs, minimizing costs, maximizing demand coverage etc. Given the issues outlined in this study, we will consider a fuzzy multi-objective emergency location and vehicle routing problem (FMOELVRP). It is essential to allocate disaster affected areas and vehicles for DCs. It generates routes from DC to disaster-affected areas, taking into account distributed demand-supply. The purposes of the model are: (1) maximizing the total selection reliability index of opened DCs, (2) minimizing the fixed costs to establish DCs and the vehicle travelling cost, (3) minimizing the maximum travel time of the vehicle routes, and (4) maximizing the minimum possibilistic reliability of the routes for all service vehicles in the process. Objective functions of (1) and (4) are novel and their construction and study issues are one of the important tasks of this work. The input to the mathematical model of the system are objective data, as well as expert evaluations. The outputs of the system will solve the FMOELVRP for disasters’ zones. The Intelligent Support System for the FMOELVRP in disaster zones will be developed in our future research.

In the field of optimization and machine learning, the statistical assessment of results has played a key role in conducting algorithmic performance comparisons. Classically, null hypothesis statistical tests have been used. However, recently, alternatives based on Bayesian statistics have shown great potential in complex scenarios, especially when quantifying the uncertainty in the comparison. In this work, we delve deep into the Bayesian statistical assessment of experimental results by proposing a framework for the analysis of several algorithms on several problems/instances. To this end, experimental results are transformed to their corresponding rankings of algorithms, assuming that these rankings have been generated by a probability distribution (defined on permutation spaces). From the set of rankings, we estimate the posterior distribution of the parameters of the studied probability models, and several inferences concerning the analysis of the results are examined. Particularly, we study questions related to the probability of having one algorithm in the first position of the ranking or the probability that two algorithms are in the same relative position in the ranking. Not limited to that, the assumptions, strengths, and weaknesses of the models in each case are studied. To help other researchers to make use of this kind of analysis, we provide a Python package and source code implementation athttps://zenodo.org/record/6320599.

Handling nonlinear constraints in continuous optimization is challenging, and finding a feasible solution is usually a difficult task. In the past few decades, various techniques have been developed to deal with linear and nonlinear constraints. However, reaching feasible solutions has been a challenging task for most of these methods. In this article, we adopt the framework of estimation of distribution algorithms (EDAs) and propose a new algorithm (EDA++) equipped with some mechanisms to deal with nonlinear constraints. These mechanisms are associated with different stages of the EDA, including seeding, learning, and mapping. It is shown that, besides increasing the quality of the solutions in terms of objective values, the feasibility of the final solutions is guaranteed if an initial population of feasible solutions is seeded to the algorithm. The EDA with the proposed mechanisms is applied to two suites of benchmark problems for constrained continuous optimization and its performance is compared with some state-of-the-art algorithms and constraint-handling methods. Conducted experiments confirm the speed, robustness, and efficiency of the proposed algorithm in tackling various problems with linear and nonlinear constraints.

The$K$-means algorithm is one of the most popular clustering methods. However, it is a well-known fact that its performance, in terms of quality of the obtained solution and computational load, highly depends upon its initialization phase. For this reason, different initialization techniques have been developed throughout the years to enable its fast convergence to competitive solutions. In this sense, it is common practice to re-start the$K$-means algorithm several times via one of these techniques and keep the solution with the lowest error. Unfortunately, such a choice is still likely to be a poor approximation of the optimal set of centroids. In this article, we introduce a cheap Split-Merge step that can be used to re-start the$K$-means algorithm after reaching a fixed point. Under some settings, one can show that this approach reduces the error of the given fixed point without requiring any further iteration of the$K$-means algorithm. Moreover, experimental results show that this strategy is able to generate approximations with an associated error that is hard to reach for different multi-start methods, such as multi-start Forgy$K$-means,$K$-means++ and Hartigan$K$-means, while also computing a lower amount of distances than the previous algorithms.

In this paper we pursue the use of the Fourier transform for a general analysis of combinatorial optimization problems. While combinatorial optimization problems are defined by means of different notions like weights in a graph, set of numbers, distance between cities, etc., the Fourier transform allows to put all of them in the same framework, the Fourier coefficients. This permits its comparison looking for similarities and differences. Particularly, the Walsh transform has recently been used over pseudo-boolean functions in order to design new surrogate models in the black-box scenario and to generate new algorithms for the linkage discovery problem, among others, presenting very promising results. In this paper we focus on binary problems and the Walsh transform. After presenting the Walsh decomposition and some main properties, we compute the transform of the Unconstrained Binary Quadratic Problem and several particular cases of this problem such as the Max-Cut Problem and the Number Partitioning Problem. The obtained Walsh coefficients not only reinforce the similarities and differences among the problems which are known in the literature, but given a set of Walsh coefficients we can say whether or not they are produced by any of the problems analyzed. Finally, a geometrical interpretation of the space of Walsh coefficients with maximum order 2 and the subspace of each analyzed problem is presented.

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.

Many Pareto-based multiobjective evolutionary algorithms require ranking the solutions of the population in each iteration according to the dominance principle, which can become a costly operation particularly in the case of dealing with many-objective optimization problems. In this article, we present a new efficient algorithm for computing the nondominated sorting procedure, called merge nondominated sorting (MNDS), which has a best computational complexity of$O(N\log N)$and a worst computational complexity of$O(MN^{2})$, with$N$being the population size and$M$being the number of objectives. Our approach is based on the computation of thedominance set, that is, for each solution, the set of solutions that dominate it, by taking advantage of the characteristics of the merge sort algorithm. We compare MNDS against six well-known techniques that can be considered as the state-of-the-art. The results indicate that the MNDS algorithm outperforms the other techniques in terms of the number of comparisons as well as the total running time.

The increase in the number of features that need to be analyzed in a wide variety of areas, such as genome sequencing, computer vision, or sensor networks, represents a challenge for the K -means algorithm. In this regard, different dimensionality reduction approaches for the K -means algorithm have been designed recently, leading to algorithms that have proved to generate competitive clusterings. Unfortunately, most of these techniques tend to have fairly high computational costs and/or might not be easy to parallelize. In this article, we propose a fully parallelizable feature selection technique intended for the K -means algorithm. The proposal is based on a novel feature relevance measure that is closely related to the K -means error of a given clustering. Given a disjoint partition of the features, the technique consists of obtaining a clustering for each subset of features and selecting the m features with the highest relevance measure. The computational cost of this approach is just O(m·max{n·K,logm}) per subset of features. We additionally provide a theoretical analysis on the quality of the obtained solution via our proposal and empirically analyze its performance with respect to well-known feature selection and feature extraction techniques. Such an analysis shows that our proposal consistently obtains the results with lower K -means error than all the considered feature selection techniques: Laplacian scores, maximum variance, multicluster feature selection, and random selection while also requiring similar or lower computational times than these approaches. Moreover, when compared with feature extraction techniques, such as random projections, the proposed approach also shows a noticeable improvement in both error and computational time.

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.

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.

The linear ordering problem (LOP) is one of the classical NP-Hard combinatorial optimization problems. Motivated by the difficulty of solving it up to optimality, in recent decades a great number of heuristic and meta-heuristic algorithms have been proposed. Despite the continuous work on this problem, there is still room nowadays for designing strategies that beat the state-of-the-art algorithms, and take a step forward in terms of the quality of the obtained solutions.In this paper, two novel schemes are presented. The first algorithm consists of an iterated local search algorithm that carries out an organized exploration of the search space. The second scheme is an extension of the previous algorithm that, based on the properties of the LOP, proposes an exact procedure that allows us to improve the quality of the solutions systematically. Conducted experiments on one of the hardest LOP benchmarks (xLOLIB) show that 77 new best results were found out of 78 instances. The described strategies also provide innovative ideas for developing more advanced algorithms for solving the LOP.

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.

Majority voting is a popular and robust strategy to aggregate different opinions in learning from crowds, where each worker labels examples according to their own criteria. Although it has been extensively studied in the binary case, its behavior with multiple classes is not completely clear, specifically when annotations are biased. This paper attempts to fill that gap. The behavior of the majority voting strategy is studied in-depth in multi-class domains, emphasizing the effect of annotation bias. By means of a complete experimental setting, we show the limitations of the standard majority voting strategy. The use of three simple techniques that infer global information from the annotations and annotators allows us to put the performance of the majority voting strategy in context.

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 the field of evolutionary computation, it is usual to generate artificial benchmarks of instances that are used as a test-bed to determine the performance of the algorithms at hand. In this context, a recent work on permutation problems analyzed the implications of generating instances uniformly at random (u.a.r.) when building those benchmarks. Particularly, the authors analyzed instances as rankings of the solutions of the search space sorted according to their objective function value. Thus, two instances are considered equivalent when their objective functions induce the same ranking over the search space. Based on the analysis, they suggested that, when some restrictions hold, the probability to create easy rankings is higher than creating difficult ones. In this paper, we continue on that research line by adopting the framework of local search algorithms with the best improvement criterion. Particularly, we empirically analyze, in terms of difficulty, the instances (rankings) created u.a.r. of three popular problems: Linear Ordering Problem, Quadratic Assignment Problem and Flowshop Scheduling Problem. As the neighborhood system is critical for the performance of local search algorithms three different neighborhood systems have been considered: swap, interchange and insert. Conducted experiments reveal that (1) by sampling the parameters uniformly at random we obtain instances with a non-uniform distribution in terms of difficulty, (2) the distribution of the difficulty strongly depends on the pair problem-neighborhood considered, and (3) given a problem, the distribution of the difficulty seems to depend on the smoothness of the landscape induced by the neighborhood and on its size.

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.

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.

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.

It is my pleasure to welcome you to Donostia / San Sebastian for the 2017 IEEE Congress on Evolutionary Computation (CEC).

The applicability of time series data mining in many different fields has motivated the scientific community to focus on the development of new methods towards improving the performance of the classifiers over this particular class of data. In this context the related literature has extensively shown that dynamic time warping is the similarity measure of choice when univariate time series are considered. However, possible statistical coupling among different dimensions make the generalization of this metric to the multivariate case all but obvious. This has ignited the interest of the community in new distance definitions capable of capturing such inter-dimension dependences. In this paper we propose a simple dynamic time warping based distance that finds the best weighted combination between the dependent - where multivariate time series are treated as whole - and independent approaches - where multivariate time series are just a collection of unrelated univariate time series - of the time series to be classified. A benchmark of four heuristic wrappers, namely, simulated annealing, particle swarm optimization, estimation of distribution algorithms and genetic algorithms are used to evolve the set of weighting coefficients towards maximizing the cross-validated predictive score of the classifiers. In this context one of the most recurring classifiers is nearest neighbor. This classifier is couple with a distance that as afore mentioned, in most cases, have been dynamic time warping. The performance of the proposed approach is validated over datasets widely utilized in the related literature, from which it is concluded that the obtained performance gains can be enlarged by properly decoupling the influence of each dimension in the definition of the dependent dynamic time warping distance.

In space environment, perturbations make the spacecraft lose its predefined orbit in space. One of these undesirable changes is the in-plane rotation of space orbit, denominated as orbital precession. To overcome this problem, one option is to correct the orbit direction by employing low-thrust trajectories. However, in addition to the orbital perturbation acting on the spacecraft, a number of parameters related to the spacecraft and its propulsion system must be optimized. This article lays out the trajectory optimization of orbital precession missions using Evolutionary Algorithms (EAs). In this research, the dynamics of spacecraft in the presence of orbital perturbation is modeled. The optimization approach is employed based on the parametrization of the problem according to the space mission. Numerous space mission cases have been studied in low and middle Earth orbits, where various types of orbital perturbations are acted on spacecraft. Consequently, several EAs are employed to solve the optimization problem. Results demonstrate the practicality of different EAs, along with comparing their convergence rates. With a unique trajectory model, EAs prove to be an efficient, reliable and versatile optimization solution, capable of being implemented in conceptual and preliminary design of spacecraft for orbital precession missions.

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.

Weakly supervised classification tries to learn from data sets which are not certainly labeled. Many problems, with different natures of partial labeling, fit this description. In this paper, the novel problem of learning from positive-unlabeled proportions is presented. The provided examples are unlabeled, and the only class information available consists of the proportions of positive and unlabeled examples in different subsets of the training data set. We present a methodology that adapts to the different levels of class uncertainty to learn Bayesian network classifiers using an expectation-maximization strategy. It has been tested in a variety of artificial scenarios with different class uncertainty, as well as compared with two naive strategies that do not consider all the available class information. Finally, it has also been successfully tested in real data, collected from the embryo selection problem in assisted reproduction.

This issue marks the first anniversary issue since I was honored to serve as the Editor-in-Chief (EiC) of the IEEE Transactions on Neural Networks and Learning Systems (TNNLS). I am happy to report that we had a very successful year and here are a few highlights that I would like to share with the community.•The latest impact factor of TNNLS is 4.854 according to the Journal Citation Reports. This marks a record high impact factor for our journal and places TNNLS as the number one scholarly publication in Computer Science (Hardware & Architecture), number three in Computer Science (Theory & Methods), and number ten in Electrical and Electronic Engineering journals.

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.

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.

This paper introduces sparse representation into spectral clustering and provides a sparse spectral clustering framework via a multiobjective evolutionary algorithm. In contrast to conventional spectral clustering, the main contribution of this paper is to construct the similarity matrix using a sparse representation approach by modeling spectral clustering as a constrained multiobjective optimization problem. Specific operators are designed to obtain a set of high quality solutions in the optimization process. Furthermore, we design a method to select a tradeoff solution from the Pareto front using a measurement called ratio cut based on an adjacency matrix constructed by all the nondominated solutions. We also extend the framework to the semi-supervised clustering field by using the semi-supervised information brought by the labeled samples to set some constraints or to guide the searching process. Experiments on commonly used datasets show that our approach outperforms four well-known similarity matrix construction methods in spectral clustering, and one multiobjective clustering algorithm. A practical application in image segmentation also demonstrates the efficiency of the proposed algorithm.

The uncertain capacitated arc routing problem is a challenging problem in which the demands of tasks, the costs of edges, and the presence of tasks and edges are uncertain. The objective of this problem is to find a robust optimal solution for a finite set of possible scenarios. In this paper, we propose a novel robust optimization approach, called an estimation of distribution algorithm (EDA) with stochastic local search (SLS), to tackle this problem. The proposed method integrates an EDA with a novel two phase SLS procedure to minimize the maximal total cost over a set of different scenarios. The SLS procedure avoids excessive fitness evaluations of unpromising moves in local search. Our experimental results on two sets of benchmark problems (a total of 55 problem instances) showed that the proposed approach outperformed existing state-of-the-art algorithms.

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.

In recent years, the performance of semisupervised learning (SSL) has been theoretically investigated. However, most of this theoretical development has focused on binary classification problems. In this paper, we take it a step further by extending the work of Castelli and Cover to the multiclass paradigm. In particular, we consider the key problem in SSL of classifying an unseen instance x into one of K different classes, using a training data set sampled from a mixture density distribution and composed of l labeled records and u unlabeled examples. Even under the assumption of identifiability of the mixture and having infinite unlabeled examples, labeled records are needed to determine the K decision regions. Therefore, in this paper, we first investigate the minimum number of labeled examples needed to accomplish that task. Then, we propose an optimal multiclass learning algorithm, which is a generalization of the optimal procedure proposed in the literature for binary problems. Finally, we make use of this generalization to study the probability of error when the binary class constraint is relaxed.

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.

An artificial bioindicator system is developed in order to solve a network intrusion detection problem. The system, inspired by an ecological approach to biological immune systems, evolves a population of agents that learn to survive in their environment. An adaptation process allows the transformation of the agent population into a bioindicator that is capable of reacting to system anomalies. Two characteristics stand out in our proposal. On the one hand, it is able to discover new, previously unseen attacks, and on the other hand, contrary to most of the existing systems for network intrusion detection, it does not need any previous training. We experimentally compare our proposal with three state-of-the-art algorithms and show that it outperforms the competing approaches on widely used benchmark data.

Learning from crowds is a classification problem where the provided training instances are labeled by multiple (usually conflicting) annotators. In different scenarios of this problem, straightforward strategies show an astonishing performance. In this paper, we characterize the crowd scenarios where these basic strategies show a good behavior. As a consequence, this study allows to identify those scenarios where non-basic methods for combining the multiple labels are expected to obtain better results. In this context, we extend the learning from crowds paradigm to the multidimensional (MD) classification domain. Measuring the quality of the annotators, the presented EM-based method overcomes the lack of a fully reliable labeling for learning MD Bayesian network classifiers: As the expertise is identified and the contribution of the relevant annotators promoted, the model parameters are optimized. The good performance of our proposal is demonstrated throughout different sets of experiments.

Most researchers employed common functional models when managing scheduling problems with controllable processing times. However, in many complicated manufacturing systems with a high diversity of jobs, these functional resource models fail to reflect their specific characteristics. To fulfill these requirements, we apply a more general model, the discrete model. Traditional functional models can be viewed as special cases of such model. In this paper, the discrete model is implemented on a problem of minimizing the weighted resource allocation subject to a common deadline on a single machine. By reducing the problem to a partition problem, we demonstrate that it is NP-complete, which addresses the difficult issue of the guarantee of both the solution quality and time cost. In order to tackle the problem, we develop an estimation of distribution algorithm based on an approximation of the Boltzmann distribution. The approximation strategy represents a tradeoff between complexity and solution accuracy. The results of the experiments conducted on benchmarks show that, compared with other alternative approaches, the proposed algorithm has competitive behavior, obtaining 74 best solutions out of 90 instances.

Evolutionary algorithm-based unmanned aerial vehicle (UAV) path planners have been extensively studied for their effectiveness and flexibility. However, they still suffer from a drawback that the high-quality waypoints in previous candidate paths can hardly be exploited for further evolution, since they regard all the waypoints of a path as an integrated individual. Due to this drawback, the previous planners usually fail when encountering lots of obstacles. In this paper, a new idea of separately evaluating and evolving waypoints is presented to solve this problem. Concretely, the original objective and constraint functions of UAVs path planning are decomposed into a set of new evaluation functions, with which waypoints on a path can be evaluated separately. The new evaluation functions allow waypoints on a path to be evolved separately and, thus, high-quality waypoints can be better exploited. On this basis, the waypoints are encoded in a rotated coordinate system with an external restriction and evolved with JADE, a state-of-the-art variant of the differential evolution algorithm. To test the capabilities of the new planner on planning obstacle-free paths, five scenarios with increasing numbers of obstacles are constructed. Three existing planners and four variants of the proposed planner are compared to assess the effectiveness and efficiency of the proposed planner. The results demonstrate the superiority of the proposed planner and the idea of separate evolution.

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.

Path planning technique is vital to Unmanned Aerial Vehicle (UAV). Evolutionary Algorithms (EAs) have been widely used in planning path for UAV. In these EA-based path planners, Cartesian coordinate system and polar coordinate system are commonly used to codify the path. However, either of them has its drawback: Cartesian coordinate systems result in an enormous search space, whilst polar coordinate systems are unfit for local modifications resulting e.g., from mutation and/ or crossover. In order to overcome these two drawbacks, we solve the UAV path planning in a new coordinate system. As the new coordinate system is only a rotation of Cartesian coordinate system, it is inherently easy for local modification. Besides, this new coordinate system has successfully reduced the search space by explicitly dividing the mission space into several subspaces. Within this new coordinate system, an Estimation of Distribution Algorithms (EDAs) based path planner is proposed in this paper. Some experiments have been designed to test different aspects of the new path planner. The results show the effectiveness of this planner.

SUMMARY In this paper, we propose and evaluate improved first fit (IFF), a fast implementation of the first fit contiguous partitioning strategy. It has been devised to accelerate the process of finding contiguous partitions in space‐shared parallel computers in which the nodes are arranged forming multidimensional cubic networks. IFF uses system status information to drastically reduce the cost of finding partitions with the requested shape. The use of this information, i combined with the early detection of zones where requests cannot be allocated, remarkably improves the search speed in large networks. An exhaustive set of simulation‐based experiments have been carried out to test IFF against other algorithms implementing the same partitioning strategy. Results, using synthetic and real workloads, show that IFF can be several orders of magnitude faster than competitor algorithms. Copyright © 2013 John Wiley & Sons, Ltd.

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.

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

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.

Null hypothesis significance tests and their p-values currently dominate the statistical evaluation of classifiers in machine learning. Here, we discuss fundamental problems of this research practice. We focus on the problem of comparing multiple fully specified classifiers on a small-sample test set. On the basis of the method by Quesenberry and Hurst, we derive confidence intervals for the effect size, i.e. the difference in true classification performance. These confidence intervals disentangle the effect size from its uncertainty and thereby provide information beyond the p-value. This additional information can drastically change the way in which classification results are currently interpreted, published and acted upon. We illustrate how our reasoning can change, depending on whether we focus on p-values or confidence intervals. We argue that the conclusions from comparative classification studies should be based primarily on effect size estimation with confidence intervals, and not on significance tests and p-values.

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.

Multiple sclerosis is an autoimmune disorder of the central nervous system and potentially the most common cause of neurological disability in young adults. The clinical disease course is highly variable and different multiple sclerosis subtypes can be defined depending on the progression of the severity of the disease. In the early stages, the disease subtype is unknown, and there is no information about how the severity is going to evolve. As there are different treatment options available depending on the progression of the disease, early identification has become highly relevant. Thus, given a new patient, it is important to diagnose the disease subtype. Another relevant information to predict is the expected time to reach a severity level indicating that assistance for walking is required. Given that we have to predict two correlated class variables: disease subtype and time to reach certain severity level, we use multidimensional Bayesian network classifiers because they can model and exploit the relations among both variables. Besides, the obtained models can be validated by the physicians using their expert knowledge due to the interpretability of Bayesian networks. The learning of the classifiers is made by means of a novel multiobjective approach which tries to maximize the accuracy of both class variables simultaneously. The application of the methodology proposed in this paper can help a physician to identify the expected progression of the disease and to plan the most suitable treatment.

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.

Haplotype data are especially important in the study of complex diseases since it contains more information than genotype data. However, obtaining haplotype data is technically difficult and costly. Computational methods have proved to be an effective way of inferring haplotype data from genotype data. One of these methods, the haplotype inference by pure parsimony approach (HIPP), casts the problem as an optimization problem and as such has been proved to be NP-hard. We have designed and developed a new preprocessing procedure for this problem. Our proposed algorithm works with groups of haplotypes rather than individual haplotypes. It iterates searching and deleting haplotypes that are not helpful in order to find the optimal solution. This preprocess can be coupled with any of the current solvers for the HIPP that need to preprocess the genotype data. In order to test it, we have used two state-of-the-art solvers, RTIP and GAHAP, and simulated and real HapMap data. Due to the computational time and memory reduction caused by our preprocess, problem instances that were previously unaffordable can be now efficiently solved.

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 the machine learning field, the performance of a classifier is usually measured in terms of prediction error. In most real-world problems, the error cannot be exactly calculated and it must be estimated. Therefore, it is important to choose an appropriate estimator of the error. This paper analyzes the statistical properties, bias and variance, of the kappa-fold cross-validation classification error estimator (kappa-cv). Our main contribution is a novel theoretical decomposition of the variance of the kappa-cv considering its sources of variance: sensitivity to changes in the training set and sensitivity to changes in the folds. The paper also compares the bias and variance of the estimator for different values of kappa. The experimental study has been performed in artificial domains because they allow the exact computation of the implied quantities and we can rigorously specify the conditions of experimentation. The experimentation has been performed for two classifiers (naive Bayes and nearest neighbor), different numbers of folds, sample sizes, and training sets coming from assorted probability distributions. We conclude by including some practical recommendation on the use of kappa-fold cross validation.

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.

A haplotype is a DNA sequence that is inherited from one parent. They are especially important in the study of complex diseases since they contain more information than genotype data, so the next high priority phase in human genomics involves the development of a full haplotype map of human genome. However, obtaining haplotype data is technically difficult and expensive. One of the computational methods for obtaining haplotype data from genotype data is the pure parsimony criterion, an approach known as haplotype inference by pure parsimony (HIPP). It has been proved to be an NP-hard problem. We present a new preprocessing method which drastically decreases the number of relevant haplotypes. Several algorithms need to preprocess data; for big problem instances this key procedure is even more important than the process. This preprocessing was eventually tested on real and simulated data applying a tabu search, and the performance of the resulting algorithm showed it to be competitive with the best actual solvers.

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.

The three papers in this special issue focus on evolutionary algorithms based on probabilistic models.

With the rapid growth of mobile communications, solving the channel assignment problem has now become a new challenge in research. In this paper, we present the channel assignment problem (CAP) from a multi-objective approach. From this new idea, the communication system can be easily managed in case of an unexpected rise in demand in some particular cells. We carry out the experiments with the Philadelphia problem.

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.

Multi-dimensional classification is a generalization of supervised classification that considers more than one class variable to classify. In this paper we review the existing multi-dimensional Bayesian classifiers and introduce a new one: the KDB multi-dimensional classifier. Then we define different classification rules for multi-dimensional scope. Finally, we introduce a structural learning approach of a multi-dimensional Bayesian classifier based on the multi-objective evolutionary algorithm NSGA-II. The solution of the learning approach is a Pareto front representing different multi-dimensional classifiers and their accuracy values for the different classes, so a decision maker can easily choose the classifier which is more interesting for the particular problem and domain.

Among the tasks in software testing, test data generation is particularly difficult and costly. In recent years, several approaches that use metaheuristic search techniques to automatically obtain the test inputs have been proposed. Although work in this field is very active, little attention has been paid to the selection of an appropriate search space. The present work describes an alternative to this issue. More precisely, two approaches which employ an Estimation of Distribution Algorithm as the metaheuristic technique are explained. In both cases, different regions are considered in the search for the test inputs. Moreover, to depart from a region near to the one containing the optimum, the definition of the initial search space incorporates static information extracted from the source code of the software under test. If this information is not enough to complete the definition, then a grid search method is used. According to the results of the experiments conducted, it is concluded that this is a promising option that can be used to enhance the test data generation process.

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.

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

This paper considers a Bayesian model-averaging (MA) approach to learn an unsupervised naive Bayes classification model. By using the expectation model-averaging (EMA) algorithm, which is proposed in this paper, a unique naive Bayes model that approximates an MA over selective naive Bayes structures is obtained. This algorithm allows to obtain the parameters for the approximate MA clustering model in the same time complexity needed to learn the maximum-likelihood model with the expectation-maximization algorithm. On the other hand, the proposed method can also be regarded as an approach to an unsupervised feature subset selection due to the fact that the model obtained by the EMA algorithm incorporates information on how dependent every predictive variable is on the cluster variable.

The portfolio optimization problem uses mathematical approaches to model stock exchange investments. Its aim is to find an optimal set of assets to invest on, as well as the optimal investments for each asset. In the present work, the problem is treated as a multi-objective optimization problem. Three well-known optimization techniques greedy search, simulated annealing and ant colony optimization are adapted to this multi-objective context. Pareto fronts for five stock indexes are collected, showing the different behaviors of the algorithms adapted. Finally, the results are discussed.

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.

Editorial de la revista Evolutionary Computation (2005, 13, 1)

Many optimization problems are what can be called globally multimodal, i.e., they present several global optima. Unfortunately, this is a major source of difficulties for most estimation of distribution algorithms, making their effectiveness and efficiency degrade, due to genetic drift. With the aim of overcoming these drawbacks for discrete globally multimodal problem optimization, this paper introduces and evaluates a new estimation of distribution algorithm based on unsupervised learning of Bayesian networks. We report the satisfactory results of our experiments with symmetrical binary optimization problems.

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.

This paper proposes using estimation of distribution algorithms for unsupervised learning of Bayesian networks, directly as well as within the framework of the Bayesian structural EM algorithm. Both approaches are empirically evaluated in synthetic and real data. Specifically, the evaluation in real data consists in the application of this paper's proposals to gene expression data clustering, i.e., the identification of clusters of genes with similar expression profiles across samples, for the leukemia database. The validation of the clusters of genes that are identified suggests that these may be biologically meaningful.

This paper introduces a novel enhancement for unsupervised learning of conditional Gaussian networks that benefits from feature selection. Our proposal is based on the assumption that, in the absence of labels reflecting the cluster membership of each case of the database, those features that exhibit low correlation with the rest of the features can be considered irrelevant for the learning process. Thus, we suggest performing this process using only the relevant features. Then, every irrelevant feature is added to the learned model to obtain an explanatory model for the original database which is our primary goal. A simple and, thus, efficient measure to assess the relevance of the features for the learning process is presented. Additionally, the form of this measure allows us to calculate a relevance threshold to automatically identify the relevant features. The experimental results reported for synthetic and real-world databases show the ability of our proposal to distinguish between relevant and irrelevant features and to accelerate learning, while still obtaining good explanatory models for the original database.