In this work, by using an adiabatic principle and the Maximum Cut Problem, we investigate the evolution of problem instances from a given initial instance to a given final instance. The path followed goes from one instance to the next by using a statistical concept of distance such that the transition is smooth in the sense that this distance is short. In other words, the process takes place in the instance space by following a trajectory of minimal change. During the process we study the evolution of the similarity between consecutive instances and the movement of the global optima. In particular, we investigated whether a smooth path in the instance space always exists between the initial and the final instance. This allow us to discuss a number of statistical results that are of general interest for the understanding of the instance space of difficult combinatorial optimization problems.

In this paper, we introduce SMorph, a new methodology for combinatorial optimization that works in the instance space of the problem at hand. Indeed, given the problem instance to solve, SMorph builds a simplified instance whose optimum is easy to locate, then it iteratively evolves this instance towards the target one by alternating two steps: optimization and smooth transformation of the current instance. The knowledge acquired in each iteration is transferred to next one, while the entire process is designed with the aim of improving the last optimization step. Although the abstract search scheme of SMorph is general enough to be instantiated for a variety of combinatorial optimization problems, here we present an implementation for the well-known Linear Optimization Problem (LOP). Experiments have been conducted on a set of commonly adopted benchmark instances of the LOP, and the results validate the proposed approach.

In contrast with random uniform instances, industrial SAT instances of large size are solvable today by state-of-the-art algorithms. It is believed that this is the consequence of the non-random structure of the distribution of variables into clauses. In order to produce benchmark instances resembling those of real-world formulas with a given structure, generative models have been proposed. In this paper we study the MAX-3SAT problem with model-generated instances having a power-law distribution. Specifically, we target the regions in which computational difficulty undergoes an easy/hard phase transition as a function of clause density and of the power-law exponent. Our approach makes use of a sampling technique to build a graph model (a local optima network) in which nodes are local optima and directed edges are transitions between optima basins. The objective is to relate the structure of the instance fitness landscape with problem difficulty through the transition. We succeed in associating the transition with straightforward network metrics, thus providing a novel and original fitness landscape view of the computational features of the power-law model and its phase transition.

The Local Optima Networks represent combinatorial landscapes as graphs, where nodes are local optima and edges are transitions between optima. It brings a new set of metrics to characterize them. Here we investigate the behavior of random walks on such oriented and weighted networks using NK landscapes and QAP instances as examples. We show that random walks are useful to characterize the structure of the corresponding LONs and give interesting information about the relationships between search difficulty and LON structure.

In the past decade, thanks to abundant data and adequate software tools, complex networks have been thoroughly investigated in many disciplines. Most of this work has dealt with networks in which distances do not have physical meaning and are just dimensionless quantities measured in terms of edge hops. However, in many cases the physical space in which networks are embedded and the actual distances between nodes are important, such as in geographical and transportation networks. The Random Geometric Graph (RGG) is a standard spatial network model that plays a role for spatial networks similar to the one played by the Erdös-Rényi random graph for relational ones. In this work we present an extension of the RGG construction to define a new model to build bi-dimensional spatial networks based on energy as realistic constraint to create the links. The constructed networks have several properties in common with those of actual social networks.

Inherent networks of potential energy surfaces proposed in physical chemistry inspired a compact network characterization of combinatorial fitness landscapes. In these so-called Local Optima Networks (LON), the nodes correspond to the local optima and the edges quantify a measure of adjacency - transition probability between them.

Local Optima Networks (LONs) have been recently proposed as an alternative model of combinatorial fitness landscapes. The model compresses the information given by the whole search space into a smaller mathematical object that is the graph having as vertices the local optima and as edges the possible weighted transitions between them. A new set of metrics can be derived from this model that capture the distribution and connectivity of the local optima in the underlying configuration space. This paper departs from the descriptive analysis of local optima networks, and actively studies the correlation between network features and the performance of a local search heuristic. The NK family of landscapes and the Iterated Local Search metaheuristic are considered. With a statistically-sound approach based on multiple linear regression, it is shown that some LONs' features strongly influence and can even partly predict the performance of a heuristic search algorithm. This study validates the expressive power of LONs as a model of combinatorial fitness landscapes.

In previous work, we have introduced a network based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima network. The vertices of this graph are the local optima of the given fitness landscape, while the arcs are transition probabilities between local optima basins. Here, we extend this formalism to neutral fitness landscapes, which are common in difficult combinatorial search spaces. The study is based on two neutral variants of the well-known NK family of landscapes (where N stands for the chromosome length, and K for the number of gene epistatic interactions within the chromosome). By using these two NK variants, probabilistic (NKp), and quantified NK (NKq), in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are consistent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality, in landscapes with percolating neutral networks, may enhance heuristic search. Our current methodology requires the exhaustive enumeration of the underlying search space. Therefore, sampling techniques should be developed before this analysis can have practical implications. We argue, however, that the proposed model offers a new perspective into the problem difficulty of combinatorial optimization problems and may inspire the design of more effective search heuristics.

Using a recently proposed model for combinatorial landscapes, Local Optima Networks (LON), we conduct a thorough analysis of two types of instances of the Quadratic Assignment Problem (QAP). This network model is a reduction of the landscape in which the nodes correspond to the local optima, and the edges account for the notion of adjacency between their basins of attraction. The model was inspired by the notion of `inherent network' of potential energy surfaces proposed in physical-chemistry. The local optima networks extracted from the so called uniform and real-like QAP instances, show features clearly distinguishing these two types of instances. Apart from a clear confirmation that the search difficulty increases with the problem dimension, the analysis provides new confirming evidence explaining why the real-like instances are easier to solve exactly using heuristic search, while the uniform instances are easier to solve approximately. Although the local optima network model is still under development, we argue that it provides a novel view of combinatorial landscapes, opening up the possibilities for new analytical tools and understanding of problem difficulty in combinatorial optimization.

We study the evolution of cooperation using the Prisoner's Dilemma as a metaphor of the tensions between cooperators and non-cooperators, and evolutionary game theory as the mathematical framework for modeling the cultural evolutionary dynamics of imitation in a population of unrelated individuals. We investigate the interplay between network reciprocity (a mechanism that promotes cooperation in the Prisoner's Dilemma by restricting interactions to adjacent sites in spatial structures or neighbors in social networks) and conformity (the tendency of imitating common behaviors). We confirm previous results on the improved levels of cooperation when both network reciprocity and conformity are present in the model and evolution is carried on top of degree-homogeneous graphs, such as rings and grids. However, we also find that scale-free networks are no longer powerful amplifiers of cooperation when fair amounts of conformity are introduced in the imitation rules of the players. Such weakening of the cooperation-promoting abilities of scale-free networks is the result of a less biased flow of information in such topologies, making hubs more susceptible of being influenced by lessconnected neighbors.

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces (Doye, 2002). We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small NK landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.

Evolutionary Learning proceeds by evolving a population of classifiers, from which it generally returns (with some notable exceptions) the single best-of-run classifier as final result. In the meanwhile, Ensemble Learning, one of the most efficient approaches in supervised Machine Learning for the last decade, proceeds by building a population of diverse classifiers. Ensemble Learning with Evolutionary Computation thus receives increasing attention. The Evolutionary Ensemble Learning (EEL) approach presented in this paper features two contributions. First, a new fitness function, inspired by co-evolution and enforcing the classifier diversity, is presented. Further, a new selection criterion based on the classification margin is proposed. This criterion is used to extract the classifier ensemble from the final population only (Off-EEL) or incrementally along evolution (On-EEL). Experiments on a set of benchmark problems show that Off-EEL outperforms single-hypothesis evolutionary learning and state-of-art Boosting and generates smaller classifier ensembles.

Useful information about scientific collaboration structures and patterns can be inferred from computer databases of published papers. The genetic programming bibliography is the most complete reference of papers on GP. In addition to locating publications, it contains coauthor and coeditor relationships from which a more complete picture of the field emerges. We treat these relationships as undirected small world graphs whose study reveals the community structure of the GP collaborative social network. Automatic analysis discovers new communities and highlights new facets of them. The investigation reveals many similarities between GP and coauthorship networks in other scientific fields but also some subtle differences such as a smaller central network component and a high clustering.

No abstract available.

We show that scale-free topologies have a positive impact on the performance of gossiping algorithms in peer-to-peer overlay networks. This result is important in the context of ad hoc networks, where each node participates in controlling the network topology. Our study shows that, when combined with such topologies, typical gossiping algorithms tend to require fewer messages and experience smaller latency than when combined with other topologies, such as rings or grids. This suggests that the topology control scheme should aim at producing an overlay network that exhibits scale-free characteristics.

We present discrete stochastic mathematical models for the growth curves of synchronous and synchronous evolutionary algorithms with populations structured ccording to a random graph. We show that, to good approximation, randomly structured and panmictic populations have the some growth behavior. Furthermore, we show that global selection intensity depends on the update policy. The validity of the models is confirmed by comparison with experimental results of simulations. We also present experimental results on small-world nd scale-free population graph topologies. We show that they lead to qualitatively similar results. However, the different nature of the nodes can be exploited to obtain more varied evolutionary behavior.

We present an approach to genetic programming difficulty based on a statistical study of program fitness landscapes. The fitness distance correlation is used as an indicator of problem hardness and we empirically show that such a statistic is adequate in nearly all cases studied here. However, fitness distance correlation has some known problems and these are investigated by constructing an artificial landscape for which the correlation gives contradictory indications. Although our results confirm the usefulness of fitness distance correlation, we point out its shortcomings and give some hints for improvement in assessing problem hardness in genetic programming.

In this paper, we present quantitative models for the selection pressure of cellular evolutionary algorithms on regular one- and two-dimensional (2-D) lattices. We derive models based on probabilistic difference equations for synchronous and several asynchronous cell update policies. The models are validated using two customary selection methods: binary tournament and linear ranking. Theoretical results are in agreement with experimental values, showing that the selection intensity can be controlled by using different update methods. It is also seen that the usual logistic approximation breaks down for low-dimensional lattices and should be replaced by a polynomial approximation. The dependence of the models on the neighborhood radius is studied for both topologies. We also derive results for 2-D lattices with variable grid axes ratio.

In This work we study cellular evolutionary algorithms, a kind of decentralized heuristics, and the importance of the induced exploration/exploitation balance on different problems. It is shown that, by choosing synchronous or asynchronous update policies, the selection pressure, and thus the exploration/exploitation tradeoff, can be influenced directly, without using additional ad hoc parameters. Synchronous algorithms of different neighborhood-to-topology ratio, and asynchronous update policies are applied to a set of benchmark problems. Our conclusions show that the update methods of the asynchronous versions, as well as the ratio of the decentralized algorithm, have a marked influence on its convergence and on its accuracy.

New techniques for dynamically changing the size of populations during the execution of genetic programming systems are proposed. Two models are presented, allowing to add and suppress individuals on the basis of some particular events occurring during the evolution. These models allow to find solutions of better quality, to save considerable amounts of computational effort and to find optimal solutions more quickly, at least for the set of problems studied here, namely the artificial ant on the Santa Fe trail, the even parity 5 problem and one instance of the symbolic regression problem. Furthermore, these models have a positive effect on the well known problem of bloat and act without introducing additional computational cost.

A new technique for saving computing resources when using genetic programming is presented in this work. Instead of directly fighting bloat $the main factor explaining the large computational cost required for the evaluation of generations - by acting on individuals, we apply a new operator to the whole population: the plague. By removing some individuals every generation, we compensate for the increase in size of individuals, thus saving computing time when looking for solutions.

This paper presents a study that evaluates the influence of the parallel genetic programming (GP) models in maintaining diversity in a population. The parallel models used are the cellular and the multipopulation one. Several measures of diversity are considered to gain a deeper understanding of the conditions under which the evolution of both models is successful. Three standard test problems are used to illustrate the different diversity measures and analyze their correlation with performance. Results show that diversity is not necessarily synonym of good convergence.

The fitness distance correlation coefficient has been shown to be a reasonable measure to quantify problem difficulty in genetic algorithms and genetic programming for a wide set of problems. In this paper we present an hand-tailored function for which fitness distance correlation fails to correctly predict problem difficulty in genetic programming. This counterexample proves that fitness distance correlation, although reliable, is not an infallible measure to quantify problem difficulty.

In this paper we present a study of parallel and distributed genetic programming models and their relationships with the bloat phenomenon. The experiments that we have performed have also allowed us to find an interesting link between the number of processes, subpopulations and the model we should use when applying parallelism to GP. We study the synchronous and asynchronous version of the island-model in GP domain.

This paper contains a modern vision of the parallelization techniques used for evolutionary algorithms (EAs). The work is motivated by two fundamental facts: 1) the different families of EAs have naturally converged in the last decade while parallel EAs (PEAs) are still lack of unified studies; and 2) there is a large number of improvements in these algorithms and in their parallelization that raise the need for a comprehensive survey. We stress the differences between the EA model and its parallel implementation throughout the paper. We discuss the advantages and drawbacks of PEAs. Also, successful applications are mentioned and open problems are identified. We propose potential solutions to these problems and classify the different ways in which recent results in theory and practice are helping to solve them. Finally, we provide a highly structured background relating to PEAs in order to make researchers aware of the benefits of decentralizing and parallelizing an EA.

We present a study on a couple of real-life problems using Parallel and Distributed Genetic Programming (PADGP). The aim is to confirm the presence of an optimal parameter range of values, which has been observed on benchmark problems. This range of values establishes a relationship between two important parameters in PADGP: the number of individuals and the total number of subpopulations we use when solving a problem. The simulations presented confirm the existence of the optimal parameter range of values which allows us to extend conclusions about the existence of this region for different classes of problems, and thus to link different PADGP and also GP parameters.

Genetic programming (GP) has proved useful in optimization problems. The way of representing individuals in this methodology is particularly good when we want to construct decision trees. Decision trees are well suited to representing explicit information and relationships among parameters studied. A set of decision trees could make up a decision support system. In this paper we set out a methodology for developing decision support systems as an aid to medical decision making. Above all, we apply it to diagnosing the evolution of a burn, which is a really difficult task even for specialists. A learning classifier system is developed by means of multipopulation genetic programming (MGP). It uses a set of parameters, obtained by specialist doctors, to predict the evolution of a burn according to its initial stages. The system is first trained with a set of parameters and results of evolutions which have been recorded over a set of clinic cases. Once the system is trained, it is useful for deciding how new cases will probably evolve. Thanks to the use of GP, an explicit expression of the input parameter is provided. This explicit expression takes the form of a decision tree which will be incorporated into software tools that help physicians In their everyday work.

We present an environment for distributed genetic programming using MPI. Genetic programming is a stochastic evolutionary learning methodology that can greatly benefit from parallel/distributed implementations. We describe the distributed system, as well as a user-friendly graphical interface to the tool. The usefulness of the distributed setting is demonstrated by the results obtained to date on several difficult problems, two of which are described in the text.

Finding good random number generators (RNGs) is a hard problem that is of crucial import in several fields, ranging from large-scale statistical physics simulations to hardware self-test. In this paper, we employ the cellular programming evolutionary algorithm to automatically generate two-dimensional cellular automata (CA) RNGs. Applying an extensive suite of randomness tests to the evolved CAs, we demonstrate that they rapidly produce high-quality random-number sequences. Moreover, based on observations of the evolved CAs, we are able to handcraft even better RNGs, which not only outperform previously demonstrated high-quality RNGs, but can be potentially tailored to satisfy given hardware constraints.

Scheduling the production for plating machines is a tedious and difficult task of critical importance for the economic exploitation of this equipment. The paper describes a promising approach to solving a simple version of this problem, namely cyclical hoist scheduling, based on evolutionary algorithms. The issues of solution encoding and specialised genetic operators are discussed and some preliminary results are presented.

Parallel evolutionary algorithms, over the past few years, have proven empirically worthwhile, but there seems to be a lack of understanding of their workings. In this paper we concentrate on cellular (fine-grained) models, our objectives being: (1) to introduce a suite of statistical measures, both at the genotypic and phenotypic levels, which are useful for analyzing the workings of cellular evolutionary algorithms; and (2) to demonstrate the application and utility of these measures on a specific example-the cellular programming evolutionary algorithm. The latter is used to evolve solutions to three distinct (hard) problems in the cellular-automata domain: density, synchronization, and random number generation. Applying our statistical measures, we are able to identify a number of trends common to all three problems (which may represent intrinsic properties of the algorithm itself), as well as a host of problem-specific features. We find that the evolutionary algorithm tends to undergo a number of phases which we are able to quantitatively delimit. The results obtained lead us to believe that the measures presented herein may prove useful in the general case of analyzing fine-grained evolutionary algorithms.

If one considers life on Earth since its very beginning, three levels of organization can be distinguished: the phylogenetic level concerns the temporal evolution of the genetic programs within individuals and species, the ontogenetic level concerns the developmental process of a single multicellular organism, and the epigenetic level concerns the learning processes during an individual organism's lifetime. In analogy to nature, the space of bio-inspired hardware systems can be partitioned along these three axes-phylogeny, ontogeny and epigenesis (POE)-giving rise to the POE model. This paper is an exposition and examination of bio-inspired systems within the POE framework, with our goals being: (1) to present an overview of current-day research, (2) to demonstrate that the POE model can be used to classify bio-inspired systems, and (3) to identify possible directions for future research, derived from a POE outlook. We discuss each of the three axes separately, considering the systems created to date and plotting directions for continued progress along the axis in question.

Presents an integrated approach for modelling the behaviour of financial markets with artificial neural networks (ANNs). The method allows the forecasting of financial time series. Its originality lies in the fact that it is based on statistics and macroeconomics principles, integrating fundamental economic knowledge in a multivariate, nonlinear time-series ANN model. The core of the work is a feasibility analysis, which is seldom attempted in ANN work, consisting of a series of different univariate and multivariate, linear and nonlinear statistical tests. The enhancement of prior work is a sensitivity analysis with bootstrap as part of the feasibility analysis. The feasibility analysis evaluates the "a priori" chance of forecasting the defined system and helps in defining the topology of the ANN. The method is applied to a real-life case study with a few data samples.