This paper investigates the emergent properties of a self-organized dynamic network for structured population-based metaheuristics. The system displays complex and emergent behavior whose most visible trait is the self-organization of the population into dynamic clusters. Furthermore, relevant variables that describe the system display 1/f noise, which is a characteristic of many complex systems. These properties were previously detected with a time-invariant population (i.e., individuals with fixed fitness vales). In this work, the investigation is extended to dynamic populations (time-varying fitness values), a scenario that models more accurately the behavior of population-based metaheuristics. Several types of fitness variation rules were tested. The experiments show that dynamic populations also display the self-organizing properties and the behavioral patterns of the stationary fitness version, as long as the intensity of the changes is kept below a certain level.

Optimization algorithms deployed on unstable computational environments must be resilient to the volatility of computing nodes. Different fault-tolerance mechanisms have been proposed for this purpose. We focus on the use of island-based multimemetic algorithms, namely memetic algorithms which explicitly represent and evolve memes alongside solutions, endowed with self-scaling capabilities. These strategies dynamically resize populations in order to react to system fluctuations. In this context, we study the joint use of different self-healing strategies, aimed to compensating the harm that the loss of computing nodes produces. Firstly, we consider the use of probabilistic models in order to self-sample the current population when it has to be resized, thus minimizing distortions in the convergence of the population and the progress of the search. Then, we complement the previous approach with the use of rewiring strategies intended to keep a rich connectivity in the system along time. We perform an extensive empirical assessment of those strategies on three different problems, considering a simulated computational environment featuring diverse degrees of instability. It is shown that these self-healing strategies provide a performance improvement and interact synergistically with each other, in particular in scenarios with large volatility.

The classical approach of competitive coevolution (CC) applied in games tries to exploit an arms race between coevolving populations that belong to the same species (or at least to the same biotic niche), namely strategies, rules, tracks for racing, or any other. This paper proposes the coevolution of entities belonging to different realms (namely biotic and abiotic) via a competitive approach. More precisely, we aim to coevolutionarily optimize both virtual players and game content. From a general perspective, our proposal can be viewed as a method of procedural content generation combined with a technique for generating game AI. This approach can not only help game designers in game creation but also generate content personalized to both specific players' profiles and game designer's objectives (e.g., create content that favors novice players over skillful players). As a case study we use Planet Wars, the real-time strategy (RTS) game associated with the 2010 Google AI Challenge contest, and demonstrate (via an empirical study) the validity of our approach.

Procedural content generation (PCG) is a research field on the rise, with numerous papers devoted to this topic. This paper presents a PCG method based on a self-adaptive evolution strategy for the automatic generation of maps for the real-time strategy (RTS) game Planet Wars. These maps are generated in order to fulfill the aesthetic preferences of the user, as implied by her assessment of a collection of maps used as training set A topological approach is used for the characterization of the maps and their subsequent evaluation: the sphere-of-influence graph (SIG) of each map is built, several graph-theoretic measures are computed on it, and a feature selection method is utilized to determine adequate subsets of measures to capture the class of the map. A multiobjective evolutionary algorithm is subsequently employed to evolve maps, using these feature sets in order to measure distance to good (aesthetic) and bad (non-aesthetic) maps in the training set. The so-obtained results are visually analyzed and compared to the target maps using a Kohonen network.

This paper presents a study on the effects of dynamic and partially connected 2-dimensional topologies on the performance of the particle swarm optimization (PSO). The swarm is positioned on 2-dimensional grids of nodes and the particles move through the nodes according to a simple rule. Meanwhile, the von Neumann neighborhood is used to decide which particles influence each individual. Structures with growing size are tested on a classical benchmark and compared to several configurations such as lbest, gbest and the standard von Neumann configuration. The results show that the partially connected grids with von Neumann neighborhood structure performs more consistently when compared to lbest, gbest and the standard von Neumann topology.

MasterMind is a puzzle in which a hidden string of symbols must be discovered by producing query strings which are compared with the hidden one; the result of this comparison (in terms of number of correct positions and colors) is fed back to the player that is trying to crack the code (codebreaker). Methods for solving this puzzle are usually compared in terms of the number of query strings (guesses) made and the total time needed to produce those strings. In this paper we focus on the latter by trying to find a combination of parameters that is, first, uniform and independent of the problem size, and second, adequate to find a fast solution that is, at the same time, good enough. The key to this combination of parameters will be the consistent set size, that is, the maximum number of combinations that are sought before being scored and played as a guess. Having found in previous papers that the consistent set size has an influence on speed, we will concentrate on small sizes and test them through two different scoring methods from literature: most parts and entropy to find out the influence of that parameter on the outcome and which method scales better. With this we try to find out which method and size yield the best results an are effectively able to? find solutions for sizes not approached so far in a reasonable time.

This work presents the experimental results obtained with a distributed computing system created by mapping an evolutionary algorithm to the CouchDB object store. The framework decouples the population from the evolutionary algorithm and -through the API that CouchDB provides- allows the distributed and asynchronous operation of clients written in different programming languages. In this paper we present tests which prove that the novel algorithm design still performs as good as a canonical evolutionary algorithm and discover what are the main issues concerning it, what kind of speedups should we expect, and how all this affects the fundamental evolutionary algorithms concepts.

The MasterMind puzzle is an interesting problem to be approached via evolutionary algorithms, since it is at the same time a constrained and a dynamic problem, and has eventually a single solution. In previous papers we have presented and evaluated different evolutionary algorithms to this game and shown how their behavior scales with size, looking mainly at the game-playing performance. In this paper we fine-tune the parameters of the evolutionary algorithms so that the worst case number of evaluations, and thus the average and median, are improved, resulting in a better solution in a more reliably predictable time.

Several methods have been developed to generate terrains under constraints to control terrain features, but most of them use strict restrictions. However, there are situations were more flexible restrictions are sufficient, such as ensuring that terrains have enough accessible area, which is an important trait for video games. Many terrains, generated with Genetic Terrain Program technique, based only on the desired accessibility parameters presented a single large non-accessible area. In an attempt to solve this problem a new fitness function, based on obstacles edge length, is presented on this paper. Results showed that the new metric suits our goal and also produces many terrains with novelty and aesthetic appeal. Terrains produced this way are already being used on Chapas video game.

In this paper we compare different policies to select individuals to migrate in an island model. Our thesis is that choosing individuals in a way that exploits differences between populations can enhance diversity, and improve the system performance. This has lead us to propose a family of policies that we call multikulti, in which nodes exchange individuals different "enough" among them. In this paper we present a policy according to which the receiver node chooses the most different individual among the sample received from the sending node. This sample is randomly built but only using individuals with a fitness above a threshold. This threshold is previously established by the receiving node. We have tested our system in two problems previously used in the evaluation of parallel systems, presenting different degree of difficulty. The multikulti policy presented herein has been proved to be more robust than other usual migration policies, such as sending the best or a random individual.

A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply bucket elimination is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques impractical on large scale problems. In response to this situation, we present a memetic algorithm for WCSPs in which bucket elimination is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. As a case study, we have applied these algorithms to the resolution of the maximum density still life problem, a hard constraint optimization problem based on Conway's game of life. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.

This paper presents a statistical parameter analysis of the ant colony optimization algorithm that was implemented to solve the bi-criteria military path-finding problem. Three parameters have been studied using analysis of variance (ANOVA) in order to identify their influence in the results and the most suitable values for them: number of ants, number of iterations and exploration/exploitation factor. In addition, a mean analysis has been performed in order to complete the conclusions obtained. The study has yielded optimal values for the parameters under study, and some internal relationships between them have been identified.

Finding binary sequences with low auto correlation is a very hard problem with many practical applications. In this paper we analyze several meta heuristic approaches to tackle the construction of this kind of sequences. We focus on two different local search strategies, steepest descent local search (SDLS) and tabu search (TS), and their use both as stand-alone techniques and embedded within a memetic algorithm (MA). Plain evolutionary algorithms are shown to perform worse than stand-alone local search strategies. However, a MA endowed with TS turns out to be a state-of-the-art algorithm: it consistently finds optimal sequences in considerably less time than previous approaches reported in the literature.

No abstract available.

Branch-and-bound (BnB) and memetic algorithms represent two very different approaches for tackling combinatorial optimization problems. However, these approaches are compatible. In this correspondence, a hybrid model that combines these two techniques is considered. To be precise, it is based on the interleaved execution of both approaches. Since the requirements of time and memory in BnB techniques are generally conflicting, a truncated exact search, namely, beam search, has opted to be carried out. Therefore, the resulting hybrid algorithm has a heuristic nature. The multidimensional 0-1 knapsack problem and the shortest common supersequence problem have been chosen as benchmarks. As will be shown, the hybrid algorithm can produce better results in both problems at the same computational cost, especially for large problem instances.

Branch-and-bound and evolutionary algorithms represent two very different approaches for tackling combinatorial optimization problems. These approaches are not incompatible though. In this paper, we consider a hybrid model that combines these two techniques. To be precise, it is based on the interleaved execution of both approaches, and has a heuristic nature. The multidimensional 0-1 knapsack problem has been chosen as benchmark. As it is shown, the hybrid algorithm can produce better results at the same computational cost, especially for larger problem instances.

Allelic representations are based on characterizing points of the search space as variable-size feature sets. Recombination processes are studied here from the point of view of this kind of representations. We focus on the structure of the information units manipulated during the process, and in the algorithmic aspects of this manipulation. In this sense, we provide a generic algorithmic template whose sufficiency is established. Moreover, the syntactic properties of the information units manipulated are analyzed and exemplified. This is done within the framework of forma analysis.

Parallel genetic algorithms (PGAs) have been traditionally used to overcome the intense use of CPU and memory that serial GAs need to solve complex problems. Non-parallel GAs can be classified into two classes: panmictic and structured-population algorithms. The difference relies on whether any individual in the population can mate with any other one or not. In this work they both are considered as two reproductive loop types executed in the islands of a parallel distributed GA. Our aim is to extend the existing studies on more conventional sequential islands to other kinds of evolution. A key issue in such a distributed PGA is the migration policy. The paper investigates the influence of the migration frequency and the migrant selection in a ring of islands performing either steady-state or cellular GAs. The study uses different problem types, namely deceptive, multimodal, NP-complete, and epistatic search landscapes, in order to provide a wide spectrum of problem difficulty to sustain the results. Large isolation values and random selection of the migrants are shown to provide a better success rate and a lower number of visited points. Also, some differences are pointed out in the behavior of panmictic and structured populations. Finally, the results show the advantages of an asynchronous migration step in the distributed GA.

This paper analyzes the detection of stagnation states in iterated local search algorithms. This is done considering elements such as the population size, the length of the encoding and the number of observed non-improving iterations. This analysis isolates the features of the target problem within one parameter for which three different estimations are given: two static a priori estimations and a dynamic approach. In the latter case, a stochastic reverse hill climbing algorithm is used to extract information from the fitness landscape. The applicability of these estimations is studied and exemplified on different problems.

This paper analyzes different representations for permutation flowshop problems. This is done using forma analysis to assess the quality of these representations with respect to makespan optimization. Classical recombination operators are studied and empirically evaluated in this context. It is shown that the best operators work on representations in which absolute positions of tasks are relevant. Subsequently, some new operators operating on these representations are proposed. These new operators are designed to exhibit specific properties regarding implicit mutation and forma transmission. Their performance is shown to be competitive with traditional operators.