Surrogates provide a cheap solution evaluation and offer significant leverage for optimizing computationally expensive problems. Usually, surrogates only approximate the original function. Recently, the perfect linear surrogates were proposed that ideally represent the original function. These surrogates do not mimic the original function. In fact, they are another (correct) representation of it and enable a wide range of possibilities, e.g., discovering the optimized function for problems where the direct transformation of the encoded solution into its evaluation is not available. However, many real-world problems can not be represented by linear models, making the aforementioned surrogates inapplicable. Therefore, we propose the Limited Monotonical Perfect Surrogate (LyMPuS), which overcomes this difficulty and enables the comparison of two solutions that differ by a single variable. Our proposition is suitable for limiting the cost of expensive local search procedures. The proposed surrogate is parameterless and can be trained on the fly without any separate surrogate-building step. It uses only the necessary fitness evaluations, and the already-paid costs are not wasted when the model is updated. Finally, it offers low-cost missing-linkage detection and low-cost linkage discovery, guaranteed to find a missing dependency in no more than $2\lceil\log_2(n)\rceil$ steps.

In optimization problems, some variable subsets may have a joint non-linear or non-monotonical influence on the function value. Therefore, knowledge of variable dependencies may be crucial for effective optimization, and many state-of-the-art optimizers leverage it to improve performance. However, some real-world problem instances may be the subject of noise of various origins. In such a case, variable dependencies relevant to optimization may be hard or impossible to tell using dependency checks sufficient for problems without noise, making highly effective operators, e.g., Partition Crossover (PX), useless. Therefore, we use Statistical Linkage Learning (SLL) to decompose problems with noise and propose a new SLL-dedicated mask construction algorithm. We prove that if the quality of the SLL-based decomposition is sufficiently high, the proposed clustering algorithm yields masks equivalent to PX masks for the noise-free instances. The experiments show that the optimizer using the proposed mechanisms remains equally effective despite the noise level and outperforms state-of-the-art optimizers for the problems with high noise.

In complex problems, variable subsets may have a joint non-monotonical influence on function value. Therefore, variation operators in many single-objective (SO) state-of-the-art optimizers leverage such dependent variable sets to improve effectiveness and efficiency. In multi-objective optimization (MO), we optimize multiple objective functions and each may have different dependencies. Thus, choosing relevant dependencies to improve a solution is challenging in MO. To overcome this difficulty, we can transform the MO problem into a set of SO problems (that may be infinite) and discover the dependencies for each SO problem separately. However, dependency discovery is expensive, even for a single problem. Performing it for each SO problem separately seems unacceptable. Moreover, the dependencies of the scalarized problem are neither necessarily a subset nor a superset of the dependencies of all objective functions, making choosing appropriate dependencies impossible. Two variables dependent in all objective functions can be independent in their scalarization, and two variables independent in all objective functions can be dependent in their scalarization. Therefore, we propose the bi-objective non-monotonicity check (BONM). BONM is a linkage learning technique that uses only a single check to discover weight vector ranges for which a given variable pair is dependent concerning the non-monotonicity check. Limiting our proposition only to scalarization using weight vectors may deteriorate its applicability for the MO problems with concave Pareto fronts. Nevertheless, it enables using gray-box-dedicated operators in the black-box setting for MO problems. Finally, the proposed parameter-less optimizer that employs BONM significantly outperforms the competing state-of-the-art MO optimizers.

Gray-box optimization proposes effective and efficient optimizers of general use. To this end, it leverages information about variable dependencies and the subfunction-based problem representation. These approaches were already shown effective by enabling tunnelling between local optima even if these moves require the modification of many dependent variables. Tunnelling is useful in solving the maximum satisfiability problem (MaxSat), which can be reformulated to Max3Sat. Since many real-world problems can be brought to solving the MaxSat/Max3Sat instances, it is important to solve them effectively and efficiently. Therefore, we focus on Max3Sat instances for which tunnelling fails to introduce improving moves between locally optimal high-quality solutions and the region of globally optimal solutions. We analyze the features of such instances on the ground of phase transitions. Based on these observations, we propose manipulating clause-satisfiability characteristics that allow connecting high-quality solutions distant in the solution space. We utilize multi-satisfiability characteristics in the optimizer built from typical gray-box mechanisms. The experimental study shows that the proposed optimizer can solve those Max3Sat instances that are out of the grasp of state-of-the-art gray-box optimizers. At the same time, it remains effective for instances that have already been successfully solved by gray-box.

Gray-box optimization employs Walsh decomposition to obtain non-linear variable dependencies and utilize them to propose masks of variables that have a joint non-linear influence on fitness value. These masks significantly improve the effectiveness of variation operators. In some problems, all variables are non-linearly dependent, making the aforementioned masks useless. We analyze the features of the real-world instances of such problems and show that many of their dependencies may have noise-like origins. Such noise-caused dependencies are irrelevant to the optimization process and can be ignored. To identify them, we propose extending the use of Walsh decomposition by measuring variable dependency strength that allows the construction of the weighted dynamic Variable Interaction Graph (wdVIG). wdVIGs adjust the dependency strength to mixed individuals. They allow the filtering of irrelevant dependencies and re-enable using dependency-based masks by variation operators. We verify the wdVIG potential on a large benchmark suite. For problems with noise, the wdVIG masks can improve the optimizer's effectiveness. If all dependencies are relevant for the optimization, i.e., the problem is not noised, the influence of wdVIG masks is similar to that of state-of-the-art structures of this kind.

As Brazil transitions toward a liberalized electricity market, energy portfolio managers face increasing complexity when evaluating new contracts. The growing presence of non-controllable renewable sources, alongside consumers with diverse and uncertain demand patterns, intensifies volume and shape risks in energy trading. This study proposes an Explainable Artificial Intelligence-based methodology to help decision-makers incorporate new power generators and consumers into energy portfolios. The approach begins by clustering historical time series data from wind and solar generation units and consumers to identify typical behavioral profiles. These clusters become labels for training supervised classification models that predict a new participant’s likely profile based on spatial and temporal features. Of the tested models, the Multilayer Perceptron achieved the highest performance. To address the opacity of the black-box model, we apply the Local Rule-based Explainer, which produces interpretable, rule-based explanations and counterfactual examples. It enables stakeholders to understand the rationale behind each classification and to assess how minor feature changes impact predictions. By combining high-accuracy prediction with transparent model interpretation, the proposed methodology improves shape and volume risk assessment in energy contracting. It also gives actionable insights to support strategic decisions in a dynamic, decentralized energy market.

Coma is a prolonged state of unconsciousness in which a patient exhibits no response to external stimuli. The electroencephalogram (EEG) is a non-invasive exam that measures electrical brain activity through electrodes placed on the scalp, providing real-time insights into neural dynamics. EEG is essential for assessing coma depth, detecting neurological deterioration, and predicting patient outcomes. While deep learning techniques such as convolutional neural networks (CNNs) and long short-term memory (LSTM) networks have been applied to coma prognosis, state-of-the-art architectures like transformers remain largely unexplored in this context. To address this gap, we propose EEGTransformer, a transformer-based architecture designed for the prognostic assessment of comatose patients using EEG signals. EEGTransformer leverages the self-attention mechanism to capture long-range dependencies in EEG sequences while benefiting from multiple attention heads to enhance contextual representation. We evaluate the proposed approach on a real-world dataset comprising dozens of EEG recordings. The results show that EEGTransformer achieves a macro F1 score of 0.88, outperforming state-of-the-art deep learning models, including a CNN-LSTM model and another transformer-based approach. Furthermore, a visual analysis of the learned latent representations reveals a significantly improved class separability compared to existing methods. These findings highlight the potential of transformers for EEG-based biomedical analysis, representing a significant advancement in coma prognosis.

One of the main approaches for solving Large-Scale Global Optimization (LSGO) problems is embedding a decomposition strategy into a Cooperative Co-Evolution (CC) framework. Decomposing an LSGO problem into smaller subproblems and optimizing them separately using a CC framework was shown to be effective when a considered problem is partially separable. Components in CC frameworks are usually disjoint. Thus, the existence of the perfect decomposition of such problems allows of the optimization of independent components. However, for overlapping problems, the perfect, unique decomposition does not exist due to the existence of shared variables. Despite this, each variable is usually assigned to a single component, and the assignment does not change during a whole framework run. In this paper, we propose a new CC framework that allows multiple assignments of shared variables. Allocating computational resources to each of its components is influenced by other components that share variables with it. According to experimental results, our proposed method outperforms the state-of-the-art LSGO-dedicated optimization methods, including other CC frameworks, when overlapping LSGO problems are considered.

Hyperspectral imaging brings important opportunities in a variety of fields due to the unprecedented amount of information it captures in numerous narrow and contiguous spectral bands. However, the high spectral and spatial dimensionality of hyperspectral images makes them challenging to transfer, store, and ultimately analyze, while only a subset of bands may be significant in specific downstream applications in Earth observation. In this article, we tackle this issue and introduce CANNIBAL---a band selection algorithm based on unsupervised clustering of inter-band dependencies captured in weighted Variable Interaction Graphs, which are a side-effect of the optimization performed by the Genetic Algorithm with Linkage Learning. We apply CANNIBAL to two downstream tasks of hyperspectral unmixing and segmentation. Our experimental study revealed that it outperforms other band selection algorithms and allows us to dramatically reduce the number of bands without negatively affecting the quality of downstream models. Finally, CANNIBAL offers a high level of flexibility, as it can be both parametric and non-parametric, depending on a use case.

In pseudo-Boolean optimization, a variable interaction graph represents variables as vertices, and interactions between pairs of variables as edges. In black-box optimization, the variable interaction graph may be at least partially discovered by using empirical linkage learning techniques. These methods never report false variable interactions, but they are computationally expensive. The recently proposed local search with linkage learning discovers the partial variable interaction graph as a side-effect of iterated local search. However, information about the strength of the interactions is not learned by the algorithm. We propose local search with linkage learning 2, which builds a weighted variable interaction graph that stores information about the strength of the interaction between variables. The weighted variable interaction graph can provide new insights about the optimization problem and behavior of optimizers. Experiments with NK landscapes, knapsack problem, and feature selection show that local search with linkage learning 2 is able to efficiently build weighted variable interaction graphs. In particular, experiments with feature selection show that the weighted variable interaction graphs can be used for visualizing the feature interactions in machine learning. Additionally, new transformation operators that exploit the interactions between variables can be designed. We illustrate this ability by proposing a new perturbation operator for iterated local search.

Gray-box optimization requires user-supported information about inter-variable dependencies to propose more effective optimizers for hard combinatorial problems. In Black-box optimization, such information is unavailable. Therefore, the Gray-box operators are only usable in Black-box scenarios if an optimizer can discover the inter-variable dependencies independently. Empirical Linkage Learning (ELL) techniques are guaranteed to discover only the true dependencies, which led to proposing the Dark Gray-box optimizers class. Such optimizers use ELL to construct Empirical Variable Interaction Graph (eVIG), which may miss some dependencies but contains only the true ones. eVIG allows using Gray-box operators in Black-box scenarios. ELL techniques are computationally expensive. Therefore, the recently proposed Local Search with Linkage Learning (LSwLL) is promising because it makes ELL a no-cost technique. However, LSwLL has some disadvantages. First, it can decompose only the problems of additive nature. Second, LSwLL removes ELL costs, but in some optimization scenarios, it may be expensive itself. Therefore, we propose the First Improvement Hill Climber with Linkage Learning (FIHCwLL). FIHCwLL decomposes additive and non-additive problems, and its overall costs are frequently lower than LSwLL (although ELL is not no-cost anymore). We introduce FIHCwLL into two state-of-the-art model-building optimizers, creating two new Dark Gray-box optimizers of significantly improved effectiveness.

Next-generation genetic algorithms (GAs) should explore information from the problem structure whenever possible. Variable interactions can be inferred using linkage learning. Statistical linkage learning techniques were shown to improve GAs' effectiveness significantly in many problems, but may eventually report false linkages. On the other hand, empirical linkage learning (ELL) techniques discover only true variable dependencies. However, traditional ELL techniques are computationally expensive. We introduce the genetic algorithm with linkage learning (GAwLL), which discovers an empirical weighted variable interaction graph (VIGw) as a side-effect of the optimization performed by a GA, making it a no-cost ELL technique. Vertices of the VIGw represent decision variables and weights indicate the strength of the interaction between variables. The VIGw allows us to obtain new insights about the optimization problem and can be used to design genetic operators that efficiently explore the information about variable dependencies. Experiments with NK landscapes show that GAwLL is able to efficiently build the empirical VIGw. We also present an interesting machine learning application, where the VIGw represents a feature interaction network. By using GAwLL, the feature interaction network is built as a side-effect of evolutionary feature selection.

Machine learning algorithms have been increasingly used to solve problems related to financial markets. Predicting the price or trends of assets in different markets is the subject of several studies. As other emerging markets, the Brazilian energy market has grown in number of traded volume and players, providing a business environment that can be explored through price trend forecasting techniques. The formation of prices of energy products depends on several factors. As the source of energy production in Brazil is predominantly through hydroelectric plants, information on water storage and natural flow between hydroelectric plants can directly impact price fluctuations. We propose a new strategy based on machine learning and complex networks for predicting the price trend in energy markets. The new strategy uses storage and flow data from the most important water stations in a hydroelectric power network. For this, we developed a feature selection method based on complex networks to identify and filter the main storage stations of the Brazilian water network. Data from the selected stations are then used as input for machine learning algorithms. We use three methods to extract centrality metrics from storage stations. Experimental results indicate that better performance is obtained by the proposed strategy, when compared to two baseline methods using different machine learning algorithms. The better performance is confirmed by a financial analysis of the results when simulating the investment strategies using algotrading.

Coma can be caused by different health conditions. Sometimes, patients are admitted to intensive care unit (ICU) without the cause of the coma being known. Knowing the coma etiology of a patient is very important for prognosis and treatment. Classification of electroencephalogram (EEG) signals by deep learning is proposed to help predict the coma etiology of ICU patients. EEG is a cheap noninvasive technique that can be used for the diagnostics and evaluation of neurological diseases. The objective is to classify coma etiology into one of four categories: Traumatic Brain Injury (TBI), Metabolic Coma, Stroke, and Other. A deep learning model based on convolutional neural networks (CNNs) is proposed to classify the EEG signals, using information from two different sources: i) intermediate layers of CNN + long-short term memory network (LSTM); ii) additional features from patients and statistical measures extracted from EEG signals. Outputs of the LSTM and additional features are inserted as additional inputs to the first dense layer of the CNN. The proposed model was compared to six other approaches, some of which incorporated additional features from patients or statistical measures from EEG signals, while others did not. Experimental results show that inserting patient information, like age and genre, as input to the first dense layer improve the predictive performance of the classification model. Moreover, this work suggests new possibilities to assist physicians in the detection of the coma etiology, especially those in small and far health units.

Gray-box optimization employs the knowledge about the true direct gene dependencies represented by the Variable Interaction Graph (VIG). This knowledge is utilized in many ways, e.g., for improving the fitness computation efficiency and proposing more effective operators for Genetic Algorithms (GAs). In the Black-box optimization, the underlying problem structure is not known. Therefore, linkage learning techniques were proposed to at least approximate gene relations and improve the evolutionary search. However, since these techniques are based on predictions, they were not suitable for building VIG. The proposition of Empirical Linkage Learning (ELL) has changed the situation. In ELL, the prediction that two genes are dependent is replaced by certainty. Additionally, ELL techniques are proven never to mark two independent genes as dependent. Therefore, we use ELL to build the empirical VIG and propose the fusion of ELL and the Gray-box operators. On this base, we propose two new mechanisms that detect (with certainty) the missing linkage between two groups of genes and the fact that the population is stuck. We integrate these mechanisms with a Gray-box operator (partition crossover) in the proposed Dark Gray Genetic Algorithm that is shown highly competitive to other state-of-the-art GAs.

Perturbing solutions is a key factor in iterated local search (ILS). The standard approach for perturbing a solution is to randomly change a fixed number of decision variables from the current local optimum. Finding suitable values of perturbation strength is difficult. It is desirable that consecutive local optima generated by ILS be close to each other and correlated in fitness. However, if the perturbation is too small, we can get stuck in the same local optimum. We propose a new perturbation strategy for ILS applied to pseudo-Boolean optimization problems where decision variables that interact are perturbed. These interactions are identified in a variable interaction graph (VIG), that is available in gray-box optimization. For black-box optimization, we propose a local search strategy that estimates an empirical VIG. Theoretical and experimental results show that perturbation based on the VIG is efficient in random and adjacent NK landscapes. Results also show that the proposed local search strategy was able to build empirical VIGs with more than 97% of the edges of the true VIG.

An optimal recombination operator for two-parent solutions provides the best solution among those that take the value for each variable from one of the parents (gene transmission property). If the solutions are bit strings, the offspring of an optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. Exploring this hyperplane is computationally costly, in general, requiring exponential time in the worst case. However, when the variable interaction graph of the objective function is sparse, exploration can be done in polynomial time. In this article, we present a recombination operator, called Dynastic Potential Crossover (DPX), that runs in polynomial time and behaves like an optimal recombination operator for low-epistasis combinatorial problems. We compare this operator, both theoretically and experimentally, with traditional crossover operators, like uniform crossover and network crossover, and with two recently defined efficient recombination operators: partition crossover and articulation points partition crossover. The empirical comparison uses NKQ Landscapes and MAX-SAT instances. DPX outperforms the other crossover operators in terms of quality of the offspring and provides better results included in a trajectory and a population-based metaheuristic, but it requires more time and memory to compute the offspring.

Iterative Partial Transcription (IPT) is an important recombination operator for Traveling Salesman Problem (TSP), and is a key component in the LKH inexact solver for the TSP. IPT shares many characteristics with Partition Crossover for the TSP. However, the standard implementation of IPT searches for all common subchains of sizes from 4 to n/2 between two parent tours and thus has a time complexity of O(n2) in the worst case. In this paper, an efficient implementation of IPT is proposed that uses a special data structure called the Extended Edge Table (EET) to find the recombination components. We prove that the proposed technique is approximately equivalent to IPT and has a time complexity of O(n). The performance of the two implementations of IPT is compared based on some random and benchmark TSP instances to establish the efficiency of the proposed algorithm.

Partition crossover (PX) is an efficient recombination operator for gray-box optimization. PX is applied in problems where the objective function can be written as a sum of subfunctions fl(.). In PX, the variable interaction graph (VIG) is decomposed by removing vertices with common variables. Parent variables are inherited together during recombination if they are part of the same connected recombining component of the decomposed VIG. A new way of generating the recombination graph is proposed here. The VIG is decomposed by removing edges associated with subfunctions fl(.) that have similar evaluation for combinations of variables inherited from the parents. By doing so, the partial evaluations of fl(.) are taken into account when decomposing the VIG. This allows the use of partition crossover in continuous optimization. Results of experiments where local optima are recombined indicate that more recombining components are found. When the proposed epsilon-PX (ePX) is compared with other recombination operators in Genetic Algorithms and Differential Evolution, better performance is obtained when the epistasis degree is low.

Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of [Formula: see text] reachable offspring, where [Formula: see text] is the number of recombining components. This article introduces a new GPX2 operator, which finds more recombining components than GPX or Iterative Partial Transcription (IPT). We also show that GPX2 has O([Formula: see text]) runtime complexity, while also introducing new enhancements to reduce the execution time of GPX2. Finally, we experimentally demonstrate the efficiency of GPX2 when it is used to improve solutions found by the multitrial Lin-Kernighan-Helsgaum (LKH) algorithm. Significant improvements in performance are documented on large ([Formula: see text]) and very large ([Formula: see text]) instances of the Traveling Salesman Problem.

Environmental changes are traditionally considered intrinsic in evolutionary dynamic optimization. However, by ignoring that changes can instead be induced, we are ignoring that environmental changes can be eventually beneficial. To investigate the impact of artificial changes on the optimization speed up, we propose a framework for inducing artificial changes in any pseudo-Boolean or continuous optimization in this paper. Seven types of changes can be induced. Knowing when and how the changes occur allows us to design new strategies for evolutionary algorithms. Through computational experiments and illustrative examples, the impact of introducing changes in the optimization process is investigated. Experimental results indicate that changing the environments according to the proposed framework can lead to higher speed up, but not for all problems and change types. The best performance was obtained by change types that introduce plateaus and/or modify the gradient of regions of the fitness landscape around the current best solution. By doing this, the evolutionary dynamics is modified, eventually allowing the population to escape faster from local optima and reach new zones of the fitness landscape. Given a pseudo-Boolean or continuous optimization static problem, the proposed framework can be used to dynamically change the problem to speed up the optimization.

Partition crossover operators use information about the interaction between decision variables to recombine solutions. The Generalized Asymmetric Partition Crossover (GAPX) was recently proposed for the asymmetric Traveling Salesman Problem (TSP). Unlike former partition crossover operators, GAPX is capable of finding crossover points by splitting vertices of degree 4. GAPX also finds recombining components with more than two crossover points. The first step of GAPX is to define candidate components for recombination by finding connected components in the union graph formed by two parents. Some of the candidate components are infeasible for recombination. However, candidate components can be fused in order to create new recombining components. We introduce a fusion mechanism that allows GAPX to find more recombining components. When k recombining components are found, GAPX generates the best of 2koffspring at cost O(n). When two local optima are recombined by partition crossover, the offspring is very often a local optimum. Fusion can be used to increase k, allowing GAPX to exploit many more offspring. Experimental results show that GAPX with fusion is capable of improving solutions generated by the LKH heuristic. Very good results are also obtained by a hybrid Genetic Algorithm that uses GAPX with fusion.

Data and knowledge representation are fundamental concepts in machine learning. The quality of the representation impacts the performance of a learning model directly. Feature learning transforms or enhances raw data to structures that are effectively exploited by those methods. In recent years, several works have been using complex networks for data representation and analysis. However, no feature learning method has been proposed to enhance such category of representation. Here, we present an unsupervised feature learning mechanism that works on datasets with binary features. First, the dataset is mapped into a feature-sample network. Then, a multi-objective optimization process selects a set of new vertices to produce an enhanced version of the network. The new features depend on a nonlinear function of a combination of preexisting features. Effectively, the process projects the input data into a higher-dimensional space. To solve the optimization problem, we design two metaheuristics based on the lexicographic genetic algorithm and the improved strength Pareto evolutionary algorithm (SPEA2). We show that the enhanced network contains more useful information and can be exploited to improve the performance of machine learning methods. The advantages and disadvantages of each optimization strategy are discussed.

There are two important challenges for local search algorithms when applied to Maximal Satisfiability (MAXSAT). 1) Local search spends a great deal of time blindly exploring plateaus in the search space and 2) local search is less effective on application instances. This second problem may be related to local search's inability to exploit problem structure. We propose a genetic recombination operator to address both of these issues. On problems with well defined local optima, partition crossover is able to "tunnel" between local optima to discover new local optima in O(n) time. The PXSAT algorithm combines partition crossover and local search to produce a new way to escape plateaus. Partition crossover locally decomposes the evaluation function for a given instance into independent components, and is guaranteed to find the best solution among an exponential number of candidate solutions in O(n) time. Empirical results on an extensive set of application instances show that the proposed framework substantially improves two of best local search solvers, AdaptG2WSAT and Sparrow, on many application instances. PXSAT combined with AdaptG2WSAT is also able to outperform CCLS, winner of several recent MAXSAT competitions.

Partition Crossover is a recombination operator for pseudo-Boolean optimization with the ability to explore an exponential number of solutions in linear or square time. It decomposes the objective function as a sum of subfunctions, each one depending on a different set of variables. The decomposition makes it possible to select the best parent for each subfunction independently and the operator provides the best out of 2q solutions, where q is the number of sub-functions in the decomposition. These subfunctions are defined over the connected components of the recombination graph: a subgraph of the objective function variable interaction graph containing only the differing variables in the two parents. In this paper, we advance further and propose a new way to increase the number of linearly independent subfunctions by analyzing the articulation points of the recombination graph. These points correspond to variables that, once flipped, increase the number of connected components. The presence of a connected component with an articulation point increases the number of explored solutions by a factor of, at least, 4. We evaluate the new operator using Iterated Local Search combined with Partition Crossover to solve NK Landscapes and MAX-SAT.

Using a robustness measure based on values of the polar requirement of amino acids, Freeland and Hurst (1998) showed that less than one in one million random hypothetical codes are better than the standard genetic code. In this paper, instead of comparing the standard code with randomly generated codes, we use an optimisation algorithm to find the best hypothetical codes. This approach has been used before, but considering only one objective to be optimised. The robustness measure based on the polar requirement is considered the most effective objective to be optimised by the algorithm. We propose here that the polar requirement is not the only property to be considered when computing the robustness of the genetic code. We include the hydropathy index and molecular volume in the evaluation of the amino acids using three multi-objective approaches: the weighted formula, lexicographic and Pareto approaches. To our knowledge, this is the first work proposing multi-objective optimisation approaches with a non-restrictive encoding for studying the evolution of the genetic code. Our results indicate that multi-objective approaches considering the three amino acid properties obtain better results than those obtained by single objective approaches reported in the literature. The codes obtained by the multi-objective approach are more robust and structurally more similar to the standard code.

Accepted version of publication "NK Hybrid Genetic Algorithm for Clustering", published in IEEE Transactions on Evolutionary Computation

In gray-box optimization, the search algorithms have access to the variable interaction graph (VIG) of the optimization problem. For Mk Landscapes (and NK Landscapes) we can use the VIG to identify an improving solution in the Hamming neighborhood in constant time. In addition, using the VIG, deterministic Partition Crossover is able to explore an exponential number of solutions in a time that is linear in the size of the problem. Both methods have been used in isolation in previous search algorithms. We present two new gray-box algorithms that combine Partition Crossover with highly efficient local search. The best algorithms are able to locate the global optimum on Adjacent NK Landscape instances with one million variables. The algorithms are compared with a state-of-the-art algorithm for pseudo-Boolean optimization: Gray-Box Parameterless Population Pyramid. The results show that the best algorithm is always one combining Partition Crossover and highly efficient local search. But the results also illustrate that the best optimizer differs on Adjacent and Random NK Landscapes.

A genetic algorithm using Edge Assemble Crossover (EAX) is one of the best heuristic solvers for large instances of the Traveling Salesman Problem. We propose using Partition Crossover to recombine solutions produced by EAX. Partition Crossover is a powerful deterministic recombination that is highly exploitive. When Partition Crossover decomposes two parents into q recombining components, partition crossover returns the best of 2q reachable offspring. If two parents are locally optimal, all of the offspring are also locally optimal in a hyperplane subspace that contains the two parents. One disadvantage of Partition Crossover, however, is that it cannot generate new edges. By contrast, the EAX operator is highly explorative; it not only inherits edges from parents, it also introduces new edges into the population of a genetic algorithm. Using both EAX and Partition Crossover together produces better performance, with improved exploitation and exploration.

The best known exact solver for generating provably optimal solutions to the Traveling Salesman Problem (TSP) is the Concorde algorithm. Concorde uses a branch and bound search strategy, as well as cutting planes to reduce the search space. The first step in using Concorde is to obtain a good initial solution. A good solution can be generated using a heuristic solver outside of Concorde, or Concorde can generate its own initial solution using the Chained Lin Kernighan (LK) algorithm. In this paper, we speed up Concorde by improving the initial solutions produced by Chained LK using Partition Crossover. Partition Crossover is a powerful deterministic recombination operator that is able to tunnel between local optima. In every instance we examined, the addition of recombination resulted in an average speed-up of Concorde, and in the majority of cases, the difference in the runtime costs was statistically significant.

Efficient hill climbers have been recently proposed for single- and multi-objective pseudo-Boolean optimization problems. For k-bounded pseudo-Boolean functions where each variable appears in at most a constant number of subfunctions, it has been theoretically proven that the neighborhood of a solution can be explored in constant time. These hill climbers, combined with a high-level exploration strategy, have shown to improve state of the art methods in experimental studies and open the door to the so-called Gray Box Optimization, where part, but not all, of the details of the objective functions are used to better explore the search space. One important limitation of all the previous proposals is that they can only be applied to unconstrained pseudo-Boolean optimization problems. In this work, we address the constrained case for multi-objective k-bounded pseudo-Boolean optimization problems. We find that adding constraints to the pseudo-Boolean problem has a linear computational cost in the hill climber.

The use of good evaluation functions is essential when evolutionary algorithms are employed for clustering. The NK internal clustering validation measure is proposed for hard partitional clustering. The evaluation function is composed of N subfunctions, where N is the number of objects in the dataset. Each subfunction is influenced by a group of K+1 objects. By using neighbourhood relations among connected small groups, density-based regions can be identified. The NK internal clustering validation measure allows the application of partition crossover (PX). PX for hard partitional clustering is also proposed in this work. By using PX, the evaluation function can be decomposed in q partial evaluations. As a consequence, PX deterministically finds the best of 2q possible offspring at the cost of evaluating 2 solutions. In the experiments, the application of PX resulted in a high number of successful recombinations. It was able to improve partitions defined by the best parents.

A partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be directly obtained from partial evaluations of substrings found in the parents. Partition crossover explores the variable interaction graph of the pseudo-Boolean functions in order to partition the variables of the solution vector. Proofs are presented showing that if the differing variable assignments found in the two parents can be partitioned into q non-interacting sets, partition crossover can be used to find the best of 2q possible offspring. Proofs are presented which show that parents that are locally optimal will always generate offspring that are locally optimal with respect to a (more restricted) hyperplane subspace. Empirical experiments show that parents that are locally optimal generate offspring that are locally optimal in the full search space more than 80 percent of the time. Experimental results also show the effectiveness of the proposed crossover when used in combination with a hybrid genetic algorithm.

Local optima networks are a recent model of fitness landscapes. They compress the landscape by representing local optima as nodes, and search transitions among them as edges. Previous local optima networks considered transitions based on mutation; this study looks instead at transitions based on deterministic recombination. We define and analyse networks based on the recently proposed partition crossover for k-bounded pseudo-Boolean functions, using NKq landscapes as a case study. Partition crossover was initially proposed for the travelling salesman problem, where it was found to ``tunnel" between local optima, i.e., jump from local optimum to local optimum. Our network analysis shows that this also happens for NK landscapes: local optima are densely connected via partition crossover. We found marked differences between the adjacent and random interaction NK models. Surprisingly, with the random model, instances have a lower number of local optima on average, but their networks are more sparse and decompose into several clusters. There is also large variability in the size and pattern of connectivity of instances coming from the same landscape parameter values. These network features offer new insight informing why some instances are harder to solve than others.

BACKGROUND: The organization of the canonical code has intrigued researches since it was first described. If we consider all codes mapping the 64 codes into 20 amino acids and one stop codon, there are more than 1.51×10(84) possible genetic codes. The main question related to the organization of the genetic code is why exactly the canonical code was selected among this huge number of possible genetic codes. Many researchers argue that the organization of the canonical code is a product of natural selection and that the code's robustness against mutations would support this hypothesis. In order to investigate the natural selection hypothesis, some researches employ optimization algorithms to identify regions of the genetic code space where best codes, according to a given evaluation function, can be found (engineering approach). The optimization process uses only one objective to evaluate the codes, generally based on the robustness for an amino acid property. Only one objective is also employed in the statistical approach for the comparison of the canonical code with random codes. We propose a multiobjective approach where two or more objectives are considered simultaneously to evaluate the genetic codes. RESULTS: In order to test our hypothesis that the multiobjective approach is useful for the analysis of the genetic code adaptability, we implemented a multiobjective optimization algorithm where two objectives are simultaneously optimized. Using as objectives the robustness against mutation with the amino acids properties polar requirement (objective 1) and robustness with respect to hydropathy index or molecular volume (objective 2), we found solutions closer to the canonical genetic code in terms of robustness, when compared with the results using only one objective reported by other authors. CONCLUSIONS: Using more objectives, more optimal solutions are obtained and, as a consequence, more information can be used to investigate the adaptability of the genetic code. The multiobjective approach is also more natural, because more than one objective was adapted during the evolutionary process of the canonical genetic code. Our results suggest that the evaluation function employed to compare genetic codes should consider simultaneously more than one objective, in contrast to what has been done in the literature.

In the dynamic traveling salesman problem (DTSP), the weights and vertices of the graph representing the TSP are allowed to change during the optimization. This work first discusses some issues related to the use of evolutionary algorithms in the DTSP. When efficient algorithms used for the static TSP are applied with restart in the DTSP, we observe that only some edges are generally inserted in and removed from the best solutions after the changes. This result indicates a possible beneficial use of memory approaches, usually employed in cyclic dynamic environments. We propose a memory approach and a hybrid approach that combines our memory approach with the elitism-based immigrants genetic algorithm (EIGA). We compare these two algorithms to four existing algorithms and show that memory approaches can be beneficial for the DTSP with random changes.

The Generalized Partition Crossover (GPX) constructs new solutions for the Traveling Salesman Problem (TSP) by finding recombining partitions with one entry and one exit in the graph composed by the union of two parent solutions. If there are k recombining partitions in the union graph, 2^k-2 solutions are simultaneously exploited by GPX. Generalized Asymmetric Partition Crossover (GAPX) is introduced; it finds more recombining partitions and can also find partitions for the asymmetric TSP. GAPX does this by locating partitions that cut vertices of degree 4 in the union graph and by finding partitions with multiple entry and exit points, both in O(n) time. GAPX can improve the quality of solutions generated by the Lin-Kernighan-Helsgaun heuristic and improve the state of the art for the asymmetric TSP.

In this work, discrete dynamic optimization problems (DOPs) are theoretically \nanalysed according to the modifications produced in the fitness landscape during the optimization process. Using the proposed analysis framework, the following DOPs are analysed: problems generated by the XOR DOP generator, three versions of the dynamic 0-1 knapsack problem, one problem involving evolutionary robots in dynamic environments, and the random dynamics NK-model. The XOR DOP generator creates benchmark DOPs from any binary static optimization problem, which allows to explore the properties of the static problem in a dynamic environment. Three types of transformations occurring in the fitness landscapes are observed in the DOPs analysed here. They are caused by: i) permutation of solutions in the search space; ii) duplication of solutions; and iii) adding deviations to the fitness of a subset of solutions. The XOR DOP generator creates a special type of permutation that is not found in the other investigated DOPs. In this way, a new benchmark problem generator is proposed here based on the analysis performed, allowing to produce DOPs with six types of fitness landscape transformations, including those similar to the problems investigated in this paper. When compared to the XOR DOP generator, new algorithms can be tested and compared in a wider range of dynamic environments using the new generator. It is important to observe that some of the fitness transformations analysed here, like those caused by the duplication of solutions, are not currently explored in the evolutionary dynamic optimization area.

In the Genetic Algorithm with the standard random immigrants approach, a fixed number of individuals of the current population are replaced by random individuals in every generation. The rate of replaced individuals is defined a priori, and has a great impact on the performance of the algorithm. In this paper we present a new strategy to control the number of random immigrants in Genetic Algorithms applied to the protein structure prediction problem. Instead of using a fixed number of new individuals per generation, the proposed approach increases or decreases the number of new individuals to be inserted in the generation according to a self-organizing process. Results show that with the algorithm can determine the number of replaced individuals per generation in a self-organized way.

The use of evolutionary programming algorithms with self-adaptation of the mutation distribution for dynamic optimization problems is investigated in this paper. In the proposed method, the q-Gaussian distribution is employed to generate new candidate solutions by mutation. A real parameter q, which defines the shape of the distribution, is encoded in the chromosome of individuals and is allowed to evolve. Algorithms with self-adapted mutation generated from isotropic and anisotropic distributions are presented. In the experimental study, the q-Gaussian mutation is compared to Gaussian and Cauchy mutation on three dynamic optimization problems.

In recent years, several approaches have been developed for genetic algorithms to enhance their performance in dynamic environments. Among these approaches, one kind of methods is to adapt genetic operators in order for genetic algorithms to adapt to a new environment. This paper investigates the effect of the selection pressure on the performance of genetic algorithms in dynamic environments. A hyper-selection scheme is proposed for genetic algorithms, where the selection pressure is temporarily raised whenever the environment changes. The hyper-selection scheme can be combined with other approaches for genetic algorithms in dynamic environments. Experiments are carried out to investigate the effect of different selection pressures on the performance of genetic algorithms in dynamic environments and to investigate the effect of the hyper-selection scheme on the performance of genetic algorithms in combination with several other schemes in dynamic environments. The experimental results indicate that the effect of the hyper-selection scheme depends on the problem under consideration and other schemes combined in genetic algorithms.

This paper proposes a self-adaptation method to control not only the mutation strength parameter, but also the mutation distribution for evolutionary algorithms. For this purpose, the isotropic q-Gaussian distribution is employed in the mutation operator. The q-Gaussian distribution allows to control the shape of the distribution by setting a real parameter q and can reproduce either finite second moment distributions or infinite second moment distributions. In the proposed method, the real parameter q of the q-Gaussian distribution is encoded in the chromosome of an individual and is allowed to evolve. An evolutionary programming algorithm with the proposed idea is presented. Experiments were carried out to study the performance of the proposed algorithm.

Addressing dynamic optimization problems has attracted a growing interest from the evolutionary algorithm community in recent years due to its importance in the applications of evolutionary algorithms in real world problems. In order to study evolutionary algorithms in dynamic environments, one important work is to develop benchmark dynamic environments. This paper proposes two continuous dynamic problem generators. Both generators use linear transformation to move individuals, which preserves the distance among individuals. In the first generator, the linear transformation of individuals is equivalent to change the direction of some axes of the search space while in the second one it is obtained by successive rotations in different planes. Preliminary experiments were carried out to study the performance of some standard genetic algorithms in continuous dynamic environments created by the proposed generators.

This paper proposes a genetic algorithm (GA) with random immigrants for dynamic optimization problems where the worst individual and its neighbours are replaced every generation. In this GA, the individuals interact with each other and, when their fitness is close, as in the case where the diversity level is low, one single replacement can affect a large number of individuals. This simple approach can take the system to a kind of self-organization behavior, known as self-organized criticality (SOC), which is useful to maintain the diversity of the population in dynamic environments and hence allows the GA to escape from local optima when the problem changes. The experimental results show that the proposed GA presents the phenomenon of SOC.

Genetic algorithms (GAs) with gene dependent mutation probability applied to non-stationary optimization problems are investigated in this paper. In the problems studied here, the fitness function changes during the search carried out by the GA. In the GA investigated, each gene is associated with an independent mutation probability. The knowledge obtained during the evolution is utilized to update the mutation probabilities. If the modification of a set of genes is useful when the problem changes, the mutation probabilities of these genes are increased. In this way, the search in the solution space is concentrated into regions associated with the genes with higher mutation probabilities. The class of non-stationary problems where this GA can be interesting and its limitations are investigated.

The problem of fault tolerance in cooperative manipulators rigidly connected to a solid object is addressed in this paper. Four faults are considered: free-swinging joint faults, locked joint faults, incorrect measured joint position, and incorrect measured joint velocity. The faults are first detected by a, fault detection and isolation system. Free-swinging and locked joint faults are isolated using artificial neural networks. The other faults are isolated based on the kinematic constraints imposed on the cooperative system. After the isolation of the faults, the control system is reconfigured. Control laws for the system with passive or locked joints are developed. Results of the fault tolerance system applied in simulations and in a real cooperative system are presented.

To combine sensor information from distributed robot teams, it is critical to know the locations of all the robots relative to each other. This paper presents a novel fault tolerant localization algorithm developed for centimeter-scale robots, called Millibots. To determine their locations, the Millibots measure the distances between themselves with an ultrasonic distance sensor. They then combine these distance measurements with dead reckoning in a maximum likelihood estimator. The focus of this paper is on detecting and isolating measurement faults that commonly occur in this localization system. Such failures include dead reckoning errors when the robots collide with undetected obstacles, and distance measurement errors due to destructive interference between direct and multi-path ultrasound wavefronts. Simulations show that the fault tolerance algorithm accurately detects erroneous measurements and significantly improves the reliability and accuracy of the localization system.

Usually, fault detection and isolation schemes for robotic manipulators use the system mathematical model to generate the residual vector. However, modeling errors could obscure the faults and could be a false alarm source. In this paper a multilayer perceptron trained with backpropagation algorithm is employed to reproduce the robot input/output behavior generating the residual vector. Then, a radial basis function network is utilized to classify the residual vector generating the fault isolation. Three different algorithms have been employed to train this network. The first employs subset selection to choose the radial units from the training patterns. The second utilizes regularization to reduce the variance of the model. The third algorithm also uses regularization but, instead of one penalty term, each radial unit has an individual penalty term. Simulations employing a two-link manipulator are showed demonstrating that the system can detect and isolate correctly faults that occur in nontrained trajectories.