Unlike multiobjective optimization (MOO), multimodal multiobjective optimization (MMMOO) should approximate the entire Pareto set, even if a portion of it maps onto the entire Pareto front. This study introduces a novel evolution strategy with adaptive fitness sharing (AFS) for MMMOO. The method, called, AFS-MMMO-ES, calculates an overall fitness for each solution in the selection pool based on its rank-wise hypervolume contribution, Pareto rank, and niche count in the decision space. Since the optimal niche radius is problem-dependent, this study introduces a novel strategy for on-the-fly adaptation of the niche radius. Simulations on meticulously designed test problems are performed to confirm the efficacy and reliability of this strategy in learning the optimal niche radius, as well as its significant impact on enhancing robustness and performance. Furthermore, AFS-MMMO-ES can easily reflect the relative importance of decision space diversity based on the decision-maker’s preference, a practically important feature that has been overlooked in this research field. Finally, the performance of AFS-MMMO-ES is assessed and compared with several successful MMMOO methods on a widely accepted test suite for MMMOO. Comparisons of numerical results reveal the robustness and superiority of AFS-MMMO-ES over its competitors.

We present a Deep Reinforcement Learning (DRL) agent that successfully completes the first several hours of Pokémon Red, a classic Game Boy JRPG that exposes significant challenges as a testbed for agents, including multitasking, long horizons of tens of thousands of steps, hard exploration, and a vast array of potential policies. Our agent completes an initial segment of the game, up to Cerulean City, a location requiring progression through two cities, battle-filled passages, a maze-like cave, and defeating the first gym leader. Our experiments include various ablations that reveal vulnerabilities in reward shaping. We argue that long-form games like Pokémon hold strong potential for future research, presenting long-term coherent reasoning challenges absent from simpler arcade games. Our environment wrapper, training algorithm, human replay data, and pretrained agent are available at (REDACTED FOR REVIEW).

This paper develops and analyses a novel quantum combinatorial game: quantum checkers (named Cheqqers). The concepts of superposition, entanglement, measurements and interference from quantum mechanics are integrated into the game of checkers by adding new types of legal moves. The addition of these new rules is done gradually by introducing several levels of 'quantumness'. Quantum checkers provides a framework for interpolating between a known and solved classical game and a more complex quantum game, and serves as 1) a benchmark for AI players learning to play quantum games and 2) an interesting game for human players that allows them to build intuition for quantum phenomena. We provide the initial analysis on the complexity of this game using random agents and a Monte Carlo tree search agent.

We present a procedural content generation (PCG) pipeline for Celeste, a complex 2D platformer with horizontal and vertical movement and with limited prior AI framework development. Our approach utilizes a Markov Chain-based model to capture the game's unique structural and gameplay elements, generating playable levels that adhere to Celeste's design principles. We implemented post-processing steps to enhance playability and strategically place game elements. Our evaluation metrics focused on playability and interestingness, with results that indicate success in replicating the desired gameplay experience for beginner players. The evaluation involved 12 players of different skill levels, providing insight into the effectiveness of our generated content. Although some limitations were observed, such as occasional lack of creativity and difficulty in controlling challenge levels, our pipeline demonstrates promise as a foundation for a Celeste AI framework. This study contributes to the broader field of PCG for complex platformers and opens avenues for level generation in which agent-based evaluation is not feasible.

Background: There is great interest in agentic LLMs, large language models that act as agents. Objectives: We review the growing body of work in this area and provide a research agenda. Methods: Agentic LLMs are LLMs that (1) reason, (2) act, and (3) interact. We organize the literature according to these three categories. Results: The research in the first category focuses on reasoning, reflection, and retrieval, aiming to improve decision making; the second category focuses on action models, robots, and tools, aiming for agents that act as useful assistants; the third category focuses on multi-agent systems, aiming for collaborative task solving and simulating interaction to study emergent social behavior. We find that works mutually benefit from results in other categories: retrieval enables tool use, reflection improves multi-agent collaboration, and reasoning benefits all categories. Conclusions: We discuss applications of agentic LLMs and provide an agenda for further research. Important applications are in medical diagnosis, logistics and financial market analysis. Meanwhile, self-reflective agents playing roles and interacting with one another augment the process of scientific research itself. Further, agentic LLMs provide a solution for the problem of LLMs running out of training data: inference-time behavior generates new training states, such that LLMs can keep learning without needing ever larger datasets. We note that there is risk associated with LLM assistants taking action in the real world—safety, liability and security are open problems—while agentic LLMs are also likely to benefit society.

Memory Gym presents a suite of 2D partially observable environments, namely Mortar Mayhem, Mystery Path, and Searing Spotlights, designed to benchmark memory capabilities in decision-making agents. These environments, originally with finite tasks, are expanded into innovative, endless formats, mirroring the escalating challenges of cumulative memory games such as “I packed my bag”. This progression in task design shifts the focus from merely assessing sample efficiency to also probing the levels of memory effectiveness in dynamic, prolonged scenarios. To address the gap in available memory-based Deep Reinforcement Learning baselines, we introduce an implementation within the open-source CleanRL library that integrates Transformer-XL (TrXL) with Proximal Policy Optimization. This approach utilizes TrXL as a form of episodic memory, employing a sliding window technique. Our comparative study between the Gated Recurrent Unit (GRU) and TrXL reveals varied performances across our finite and endless tasks. TrXL, on the finite environments, demonstrates superior effectiveness over GRU, but only when utilizing an auxiliary loss to reconstruct observations. Notably, GRU makes a remarkable resurgence in all endless tasks, consistently outperforming TrXL by significant margins. Website and Source Code: https://marcometer.github.io/jmlr_2024.github.io/

This research study explores the emotional responses evoked during game play and interactions with non-player characters (NPCs) in a mystery-solving game. Structured around three phases-introduction, collaboration, and feedback-, the game uses large language models (LLMs) to simulate varying emotional states in NPCs, from neutrality to expressions of anger, joy, and more. Players’ emotional responses to the game play and interaction with the NPCs are captured through the dialogue they input. Language models are used to extract emotion scores from these in-game conversations. This study aims to enhance our understanding of emotional dynamics within gaming environments, in order to further inform the design of emotionally engaging experiences. Additionally, it underscores the potential of language models for scientific inquiries in human-computer interaction.

We make a first step towards terrain-adaptive PCGML in Minecraft by introducing an automated system to create “volume-to-volume” datasets suitable for machine learning by leveraging handwritten black-box Minecraft settlement generation algorithms. Using this system, we create ten terrain-adaptive Minecraft ML datasets - including ones based on the currently best-performing algorithm submitted to the Generative Design in Minecraft (GDMC) competition. Finally, we train and qualitatively evaluate various GAN-based volume-to-volume models on all ten of our datasets. Although we do not obtain good results in all cases, we demonstrate that terrain-adaptive PCGML in Minecraft is indeed feasible.

This study introduces novel tunable benchmark test problems for continuous box-constrained multimodal optimization (MMO). It first introduces a new approach to control the non-uniformity of distribution of global minima, a notable challenge in MMO. Then, it builds upon an existing procedure to create composite functions in which the severity of two distinguishable groups of MMO challenges can be controlled: i) challenges shared with global optimization (GO), such as ill-conditioning, and ii) challenges specific to MMO, such as non-uniform distribution of global minima. Eight new scalable and tunable MMO functions are then proposed, based on which a test suite of 16 continuous MMO test problems is suggested. This test suite is designed to be i) comprehensive, which means they simulate most, if not all, prominent challenges associated with MMO, ii) discriminating, which means test problems can disclose the gap between the performance of diverse MMO methods, and iii) illuminating, which means test problems can reveal and compare strengths and weaknesses of MMO methods. The code of these problems is made available in two different programming languages to encourage its adoption by the research community.

Experimental research is an essential component in the field of evolutionary computation (EC). The scientific method requires that empirical results are reproducible. Reproducibility of experiments also helps later researchers build upon the work of previous researchers. Interest in improving reproducibility in computer science and other empirical sciences has grown in recent years and there is a growing number of works analyzing current and best practices, obstacles and guidelines, effectiveness of journal policies, etc. Reproducibility issues in the context of EC have been a topic of discussion for a long time in the context of best practices for empirical research, but there are few studies analyzing reproducibility in EC research, and reproducibility studies themselves are extremely rare. There is room for improvement to attain the minimum standards for reproducibility encouraged in other scientific fields. Reproducibility goes beyond making implementation of algorithms publicly available. Challenges for reproducibility in EC research arise from the stochastic nature of the algorithms and, sometimes, the problems, which require multiple runs to analyze expected behavior and variance; sensitivity of the results to the computational environment, parameter settings, or implementation details; and the generalizability of conclusions to different instances of the same or related problems.This special issue of Evolutionary Computation on reproducibility features three exceptional papers that highlight different aspects of reproducibility and how to achieve it in practice.In “Using Decomposed Error for Reproducing Implicit Understanding of Algorithms” (10.1162/evco_a_00321), Caitlin A. Owen, Grant Dick, and Peter A. Whigham propose an error decomposition framework to improve the reproducibility of experiments in evolutionary machine learning. This framework takes into account information about bias, variance due to internal algorithmic choices, and variance due to training data, from multiple runs. The authors examine the behavior of three evolutionary machine learning approaches with this framework, which provides a fine-grained analysis on the decomposition of errors, and allow them to pinpoint mismatched expectations about algorithm behavior.In “The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond” (10.1162/evco_a_00333), Anna V. Kononova, Diederick Vermetten, Fabio Caraffini, Madalina-A. Mitran, and Daniela Zaharie argue that the strategy for dealing with infeasible solutions in constrained optimization problems has a significant impact on the reproducibility of experiments in heuristic optimization, and this impact grows with the dimensionality of the problem.In “A Practical Methodology for Reproducible Experimentation: An Application to the Double-Row Facility Layout Problem” (10.1162/evco_a_00317), Raúl Martín-Santamaría, Sergio Cavero, Alberto Herrán, Abraham Duarte, and J. Manuel Colmenar provide a methodology, and the software implementing it, for carrying out experiments with stochastic optimization methods. They illustrate the methodology on the double-row facility layout problem, reproducing previous results and ensuring that their own new results are fully reproducible.We believe that there is an ongoing cultural shift within computer science in general and within EC in particular, with both reviewers and funding agencies expecting and rewarding reproducibility efforts. The submission guidelines of Evolutionary Computation encourage authors to “ensure reproducibility.” Other journals have adopted “reproducibility boards” and “reproducibility badges.” Some conferences and journals have already gone a step further and require that experiments are reproducible by reviewers before publication. As a result of these efforts, we expect that the good practice standards in EC regarding reproducibility will improve in the next decade.

This work examines the feasibility of using Language Models (LMs) to generate chatter that stays in context based on persona descriptions. We clearly distinguish between chatter and dialogue, explain why we believe that chatter yields more promise for integration, and experimentally show that in 500 generated samples the majority (79%) of responses stayed in context. Additionally, we coarsely check that most (≈70%) consumer gaming hardware has enough random access memory (RAM) to store a small 7B 4-bit quantized LM model such as LLama.cpp on top of a demanding AAA game. Finally, we outline our vision for the future of games and language models and their potential synergies.

Procedural city generation that focuses on believability and adaptability to random terrain is a difficult challenge in the field of Procedural Content Generation (PCG). Dozens of researchers compete for a realistic approach in challenges such as the Generative Settlement Design in Minecraft (GDMC), in which our method has won the 2022 competition. This was achieved through a decentralised, iterative planning process that is transferable to similar generation processes that aims to produce "organic" content procedurally.

Non-parametric episodic memory can be used to quickly latch onto high-rewarded experience in reinforcement learning tasks. In contrast to parametric deep reinforcement learning approaches in which reward signals need to be back-propagated slowly, these methods only need to discover the solution once, and may then repeatedly solve the task. However, episodic control solutions are stored in discrete tables, and this approach has so far only been applied to discrete action space problems. Therefore, this paper introduces Continuous Episodic Control (CEC), a novel non-parametric episodic memory algorithm for sequential decision making in problems with a continuous action space. Results on several sparse-reward continuous control environments show that our proposed method learns faster than state-of-the-art model-free RL and memory-augmented RL algorithms, while maintaining good long-run performance as well. In short, CEC can be a fast approach for learning in continuous control tasks.1

While deep reinforcement learning has shown important empirical success, it tends to learn relatively slow due to slow propagation of rewards information and slow update of parametric neural networks. Non-parametric episodic memory, on the other hand, provides a faster learning alternative that does not require representation learning and uses maximum episodic return as state-action values for action selection. Episodic memory and reinforcement learning both have their own strengths and weaknesses. Notably, humans can leverage multiple memory systems concurrently during learning and benefit from all of them. In this work, we propose a method called Two-Memory reinforcement learning agent (2M) that combines episodic memory and reinforcement learning to distill both of their strengths. The 2M agent exploits the speed of the episodic memory part and the optimality and the generalization capacity of the reinforcement learning part to complement each other. Our experiments demonstrate that the 2M agent is more data efficient and outperforms both pure episodic memory and pure reinforcement learning, as well as a state-of-the-art memory-augmented RL agent. Moreover, the proposed approach provides a general framework that can be used to combine any episodic memory agent with other off-policy reinforcement learning algorithms.1

Developers face a time-consuming task when creating quests in video games. To ease this burden, Procedural Content Generation (PCG) techniques can be used to automatically generate quests. While PCG has been applied to various areas of game development, it can be difficult to create meaningful narratives for quests. This paper presents a new method for generating engaging quests by combining PCG with Natural Language Processing (NLP) using the models BERT and GPT-2 in a case study game called QuestVille. The paper details the implementation of these models and the challenges encountered. The results suggest that the use of BERT and GPT-2 has potential for creating compelling narrative content. Advancements in AI research may improve on the limitations discussed.

Many human-AI authoring tools are used in a playful way, while being primarily designed for task-achievement—not playfulness. We argue that playfulness is an important yet overlooked factor of user behaviour and experience when interacting with such tools. Motivating and rewarding playfulness as an exploratory, task-agnostic, open, and subversive attitude can support the satisfaction of more diverse user goals, and have a strong, positive effect on the user experience, the emerging human-AI interaction, and the resulting artefact. In this paper, we motivate the importance of playfulness as user experience in human-AI authoring tools, and propose concrete strategies to design for playfulness in the human user through UI design, in the AI through algorithms, or through interventions to their dialog. We conclude with an outlook of the research agenda.

Procedural Content Generation (PCG) in games has become more common in recent years. Procedural narrative, however, is still tricky, as designers fear that applying PCG to narrative means that they lose control over the system. In this paper, we attempt to tackle procedural generation of quests, a specific type of narrative, like in the Role Playing Games genre. To this end, we present StoryWorld, an Event-driven simulation of Items, Locations, Characters, and their Memories and Desires. Its modularity makes it easy to add new items and events. Future work could see its memory system made more realistic.

Computer Systems, Imagery and Media

Reinforcement Learning (RL) is one of the most dynamic research areas in Game AI and AI as a whole, and a wide variety of games are used as its prominent test problems. However, it is subject to the replicability crisis that currently affects most algorithmic AI research. Benchmarking in Reinforcement Learning could be improved through verifiable results. There are numerous benchmark environments whose scores are used to compare different algorithms, such as Atari. Nevertheless, reviewers must trust that figures represent truthful values, as it is difficult to reproduce an exact training curve. We propose improving this situation by providing access to the original evaluation data to validate study results. To that end, we rely on the concept of replay traces. These allow re-simulation of action sequences in deterministic RL environments and, in turn, enable reviewers to verify, re-use, and manually inspect evaluation results without needing large compute clusters. It also permits validation of presented reward graphs, an inspection of individual episodes, and re-use of result data (baselines) for proper comparison in follow-up papers. We offer plug-and-play code that works with Gym so that our measures fit well in the existing RL and reproducibility eco-system. Our approach is freely available, easy to use, and adds minimal overhead, as replay traces allow a data compression ratio of up to $\approx 10^{4}$: 1 (94 GB to 8 MB for Atari Pong) compared to a regular MDP trace used in offline RL datasets. The paper presents proof-of-concept results for a variety of games.

Autonomously trained agents that are supposed to play video games reasonably well rely either on fast simulation speeds or heavy parallelization across thousands of machines running concurrently. This work explores a third way that is established in robotics, namely sim-to-real transfer, or if the game is considered a simulation itself, sim-to-sim transfer. In the case of Rocket League, we demonstrate that single behaviors of goalies and strikers can be successfully learned using Deep Reinforcement Learning in the simulation environment and transferred back to the original game. Although the implemented training simulation is to some extent inaccurate, the goalkeeping agent saves nearly 100% of its faced shots once transferred, while the striking agent scores in about 75% of cases. Therefore, the trained agent is robust enough and able to generalize to the target domain of Rocket League.

The GDMC AI settlement generation challenge is a procedural content generation (PCG) competition about producing an algorithm that can create a settlement in the game Minecraft. In contrast to the majority of AI competitions, the GDMC entries are evaluated by human experts on several criteria such as adaptability, functionality, evocative narrative, and visual aesthetics – all of which represent challenges to state-of-the-art PCG systems. This paper contains a collection of written experiences with this competition, by participants, judges, organizers and advisors. We asked people to reflect both on the artifacts themselves, and on the competition in general. The aim of this paper is to offer a shareable and edited collection of experiences and qualitative feedback which have the potential to push forward PCG and computational creativity, but would be lost once the individual assessments are compressed to scalar ratings. We reflect upon organizational issues for AI competitions, and discuss the future of the GDMC competition.

Multimodal optimization problems (MMOPs) are common problems with multiple optimal solutions. In this article, a novel method of population division, called nearest-better-neighbor clustering (NBNC), is proposed, which can reduce the risk of more than one species locating the same peak. The key idea of NBNC is to construct the raw species by linking each individual to the better individual within the neighborhood, and the final species of the population is formulated by merging the dominated raw species. Furthermore, a novel algorithm is proposed called NBNC-PSO-ES, which combines the advantages of better exploration in particle swarm optimization (PSO) and stronger exploitation in the covariance matrix adaption evolution strategy (CMA-ES). For the purpose of demonstrating the performance of NBNC-PSO-ES, several state-of-the-art algorithms are adopted for comparisons and tested using typical benchmark problems. The experimental results show that NBNC-PSO-ES performs better than other algorithms.

Nearest-Better Clustering (NBC) is an emergent niching technique in Swarm and Evolutionary Computation for optimization, which does not need to fix the number or radius of clusters in advance. The key idea of NBC is to first link each individual to its nearest better neighbor to form a spanning tree of all individuals in the population, and then partition all individuals into clusters by deleting the longer edges in the spanning tree. In this paper, a survey on the Nearest-Better Clustering algorithms and applications in multimodal and dynamic optimization is provided. First, the basic NBC algorithm is introduced. Second, the improvements of the basic NBC are detailed. Third, multimodal and dynamic optimization algorithms powered by NBC are enlisted and discussed.

Decades of research have been invested in making computer programs for playing games such as Chess and Go. This paper introduces a board game, Tetris Link, that is yet unexplored and appears to be highly challenging. Tetris Link has a large branching factor and lines of play that can be very deceptive, that search has a hard time uncovering. Finding good moves is very difficult for a computer player, our experiments show. We explore heuristic planning and two other approaches: Reinforcement Learning and Monte Carlo tree search. Curiously, a naive heuristic approach that is fueled by expert knowledge is still stronger than the planning and learning approaches. We, therefore, presume that Tetris Link is more difficult than expected. We offer our findings to the community as a challenge to improve upon.

The idea of transfer in reinforcement learning (TRL) is intriguing: being able to transfer knowledge from one problem to another problem without learning everything from scratch. This promises quicker learning and learning more complex methods. To gain an insight into the field and to detect emerging trends, we performed a database search. We note a surprisingly late adoption of deep learning that starts in 2018. The introduction of deep learning has not yet solved the greatest challenge of TRL: generalization. Transfer between different domains works well when domains have strong similarities (e.g. MountainCar to Cartpole), and most TRL publications focus on different tasks within the same domain that have few differences. Most TRL applications we encountered compare their improvements against self-defined baselines, and the field is still missing unified benchmarks. We consider this to be a disappointing situation. For the future, we note that: (1) A clear measure of task similarity is needed. (2) Generalization needs to improve. Promising approaches merge deep learning with planning via MCTS or introduce memory through LSTMs. (3) The lack of benchmarking tools will be remedied to enable meaningful comparison and measure progress. Already Alchemy and Meta-World are emerging as interesting benchmark suites. We note that another development, the increase in procedural content generation (PCG), can improve both benchmarking and generalization in TRL.

The papers in this special section focus on team artificial intelligence (AI) in games. Computer controlled players excel in a wide range of environments, from traditional board games, like chess and Go, to fast arcade environments like Super Mario Bros. and one versus one fighting. One of the topical issues of today’s research efforts aims at intelligent team behavior, relevant for a wide variety of games, including real-time strategy games, team sports, multiplayer online battle arena (MOBA), and even tabletop games like Hanabi. The notion of team behavior is very rich, ranging from the ability to exhibit a clear and consistent strategy of an AI-controlled team to the capability of “melting into” a group of human-controlled teammates and supporting their coordinated actions. Consequently, design goals of an AI system can be driven by a variety of considerations, including efficiency, creativity, believability, synergism, and contribution of the AI to the overall entertainment value of the game.

Churn describes customer defection from a service provider. This can be observed in online freemium games, where users can leave without further notice. Game companies are looking for methods to detect and predict churn to enable management reaction. The recorded data of games can be analyzed for this purpose. In this article, we conducted a case study based on data from the freemium game The Settlers Online. Churn detection was achieved by application of four different labeling approaches, based on common churn and disengagement definitions within the game analytics literature. In order to model predictive classifiers, features were computed from the raw game data. Eight different machine learning algorithms returning binary classifications were applied. The results were compared for all algorithms regarding all labeling approaches. Random forests with sliding windows were the best solution in our case, returning area under curve values higher than 0.99, thereby enabling prediction accuracies of 97% in our dataset. The results were confirmed by tests on an independent dataset and in our discussion, we offer guidance on the interplay of feature engineering, labeling approaches-in particular, disengagement-and machine learning algorithms for churn prediction. Our recommendations are valuable for game companies and academics, who pursue similar studies.

The Obstacle Tower Challenge is the task to master a procedurally generated chain of levels that subsequently get harder to complete. Whereas the most top performing entries of last year's competition used human demonstrations or reward shaping to learn how to cope with the challenge, we present an approach that performed competitively (placed 7th) but starts completely from scratch by means of Deep Reinforcement Learning with a relatively simple feed-forward deep network structure. We especially look at the generalization performance of the taken approach concerning different seeds and various visual themes that have become available after the competition, and investigate where the agent fails and why. Note that our approach does not possess a short-term memory like employing recurrent hidden states. With this work, we hope to contribute to a better understanding of what is possible with a relatively simple, flexible solution that can be applied to learning in environments featuring complex 3D visual input where the abstract task structure itself is still fairly simple.

Live Action Role-Playing (LARP) games and similar experiences are becoming a popular game genre. Here, we discuss how artificial intelligence techniques, particularly those commonly used in AI for Games, could be applied to LARP. We discuss the specific properties of LARP that make it a surprisingly suitable application field, and provide a brief overview of some existing approaches. We then outline several directions where utilizing AI seems beneficial, by both making LARPs easier to organize, and by enhancing the player experience with elements not possible without AI.

With hybrid board games rising in popularity and game AI algorithms becoming more sophisticated, there is potential in involving AI to create novel game experiences and tools that can support developers. However, examples of hybrid board games that involve AI remain relatively sparse. In this work, we propose that creating a taxonomy of AI in hybrid board games can help the development of games that occupy as-of-yet unexplored areas of the design space. By mapping out different dimensions through which the involvement of AI in such games can be understood, we seek to encourage further academic discussions and applied explorations.

Choosing automatically the right algorithm using problem descriptors is a classical component of combinatorial optimization. It is also a good tool for making evolutionary algorithms fast, robust and versatile. We present Shiwa, an algorithm good at both discrete and continuous, noisy and noise-free, sequential and parallel, black-box optimization. Our algorithm is experimentally compared to competitors on YABBOB, a BBOB comparable testbed, and on some variants of it, and then validated on several real world testbeds.

Procedural Content Generation of game content has been vastly improved over the last years and is more and more adopted also in the game industry. It relies mostly on evolutionary and related optimization methods but usually only treats a single of the many available facets as visuals, levels, audio, etc. The problem of how to combine several facets of generation is largely unsolved, but nevertheless very important. One of its subproblems is that we currently do not know in advance how users will react to machine-generated combinations. Based on a simple maze game with exchangeable visuals and audio styles we test how users receive ‘usual’ and ‘unusual’ facet compositions by means of rank trace based annotations of their own play-throughs. By means of machine learning techniques, we establish a model in order to learn and predict user reactions. Understanding the effects of facet composition on the user is fundamental if we want to rise evolutionary generation of content to the next level.

We continue recent work on the definition of multimodality in multiobjective optimization (MO) and the introduction of a test bed for multimodal MO problems. This goes beyond well-known diversity maintenance approaches but instead focuses on the landscape topology induced by the objective functions. More general multimodal MO problems are considered by allowing ellipsoid contours for single-objective subproblems. An experimental analysis compares two MO algorithms, one that explicitly relies on hypervolume gradient approximation, and one that is based on local search, both on a selection of generated example problems. We do not focus on performance but on the interaction induced by the problems and algorithms, which can be described by means of specific characteristics explicitly designed for the multimodal MO setting. Furthermore, we widen the scope of our analysis by additionally applying visualization techniques in the decision space. This strengthens and extends the foundations for Exploratory Landscape Analysis (ELA) in MO.

—The design process is often characterized by and realized through the iterative steps of evaluation and refinement. When the process is based on a single creative domain such as visual art or audio production, designers primarily take inspiration from work within their domain and refine it based on their own intuitions or feedback from an audience of experts from within the same domain. What happens, however, when the creative process involves more than one creative domain such as in a digital game? How should the different domains influence each other so that the final outcome achieves a harmonized and fruitful communication across domains? How can a computational process orchestrate the various computational creators of the corresponding domains so that the final game has the desired functional and aesthetic characteristics? To address these questions, this paper identifies game facet orchestration as the central challenge for artificial-intelligence-based game generation, discusses its dimensions, and reviews research in automated game generation that has aimed to tackle it. In particular, we identify the different creative facets of games, propose how orchestration can be facilitated in a top-down or bottom-up fashion, review indicative preliminary examples of orchestration, and conclude by discussing the open questions and challenges ahead.

During the recent decades, many niching methods have been proposed and empirically verified on some available test problems. They often rely on some particular assumptions associated with the distribution, shape, and size of the basins, which can seldom be made in practical optimization problems. This study utilizes several existing concepts and techniques, such as taboo points, normalized Mahalanobis distance, and the Ursem's hill-valley function in order to develop a new tool for multimodal optimization, which does not make any of these assumptions. In the proposed method, several subpopulations explore the search space in parallel. Offspring of a subpopulation are forced to maintain a sufficient distance to the center of fitter subpopulations and the previously identified basins, which are marked as taboo points. The taboo points repel the subpopulation to prevent convergence to the same basin. A strategy to update the repelling power of the taboo points is proposed to address the challenge of basins of dissimilar size. The local shape of a basin is also approximated by the distribution of the subpopulation members converging to that basin. The proposed niching strategy is incorporated into the covariance matrix self-adaptation evolution strategy (CMSA-ES), a potent global optimization method. The resultant method, called the covariance matrix self-adaptation with repelling subpopulations (RS-CMSA), is assessed and compared to several state-of-the-art niching methods on a standard test suite for multimodal optimization. An organized procedure for parameter setting is followed which assumes a rough estimation of the desired/expected number of minima available. Performance sensitivity to the accuracy of this estimation is also studied by introducing the concept of robust mean peak ratio. Based on the numerical results using the available and the introduced performance measures, RS-CMSA emerges as the most successful method when robustness and efficiency are considered at the same time.

When selecting the best suited algorithm for an unknown optimization problem, it is useful to possess some a priori knowledge of the problem at hand. In the context of single-objective, continuous optimization problems such knowledge can be retrieved by means of Exploratory Landscape Analysis (ELA), which automatically identifies properties of a landscape, e.g., the so-called funnel structures, based on an initial sample. In this paper, we extract the relevant features (for detecting funnels) out of a large set of landscape features when only given a small initial sample consisting of 50 x D observations, where D is the number of decision space dimensions. This is already in the range of the start population sizes of many evolutionary algorithms. The new Multiple Peaks Model Generator (MPM2) is used for training the classifier, and the approach is then very successfully validated on the Black-Box Optimization Benchmark (BBOB) and a subset of the CEC 2013 niching competition problems.

In single-objective optimization different optimization strategies exist depending on the structure and characteristics of the underlying problem. In particular, the presence of so-called funnels in multimodal problems offers the possibility of applying techniques exploiting the global structure of the function. The recently proposed Exploratory Landscape Analysis approach automatically identifies problem characteristics based on a moderately small initial sample of the objective function and proved to be effective for algorithm selection problems in continuous black-box optimization. In this paper, specific features for detecting funnel structures are introduced and combined with the existing ones in order to classify optimization problems regarding the funnel property. The effectiveness of the approach is shown by experiments on specifically generated test instances and validation experiments on standard benchmark problems.

We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the "best" one? and the second one is: which algorithm should I use for my real-world problem? Both are connected and neither is easy to answer. We present a theoretical framework for designing and analyzing the raw data of such benchmark experiments. This represents a first step in answering the aforementioned questions. The 2009 and 2010 BBOB benchmark results are analyzed by means of this framework and we derive insight regarding the answers to the two questions. Furthermore, we discuss how to properly aggregate rankings from algorithm evaluations on individual problems into a consensus, its theoretical background and which common pitfalls should be avoided. Finally, we address the grouping of test problems into sets with similar optimizer rankings and investigate whether these are reflected by already proposed test problem characteristics, finding that this is not always the case.

In this paper we investigate the ability of selection methods to enforce niching on multi modal problems. Using theoretical properties where possible, and relying on a sound experimental analysis, we show that the conventional single-objective optimization and novelty search are extreme cases of selection, striving only for quality or diversity. However, in between these well known cases, there are many more possibilities, of which we review eight (including the aforementioned two). Multiobjective selection approaches provide a well-balanced trade-off' between exploration and exploitation. For the multiobjectivization, we recommend to use nearest-better-neighbor information instead of the common nearest-neighbor approaches.

This paper presents an overview of the existing work on AI for real-time strategy (RTS) games. Specifically, we focus on the work around the game StarCraft, which has emerged in the past few years as the unified test bed for this research. We describe the specific AI challenges posed by RTS games, and overview the solutions that have been explored to address them. Additionally, we also present a summary of the results of the recent StarCraft AI competitions, describing the architectures used by the participants. Finally, we conclude with a discussion emphasizing which problems in the context of RTS game AI have been solved, and which remain open.

The steady supply of new optimization methods makes the algorithm selection problem (ASP) an increasingly pressing and challenging task, specially for real-world black-box optimization problems. The introduced approach considers the ASP as a cost-sensitive classification task which is based on Exploratory Landscape Analysis. Low-level features gathered by systematic sampling of the function on the feasible set are used to predict a well-performing algorithm out of a given portfolio. Example-specific label costs are defined by the expected runtime of each candidate algorithm. We use one-sided support vector regression to solve this learning problem. The approach is illustrated by means of the optimization problems and algorithms of the BBOB'09/10 workshop.

Heuristic search algorithms have been successfully applied to solve many problems in practice. Their design, however, has increased in complexity as the number of parameters and choices for operators and algorithmic components is also expanding. There is clearly the need for providing the final user with automated tools to assist the tuning, design and assessment of heuristic optimisation methods. In recent years a growing number workshops and tracks has been held to address these issues. In 2010, the Parallel Problem Solving from Nature (PPSN) conference hosted two workshops, which decided to joint efforts to organise this journal special issue. The workshop “Self-Tuning, Self-Configuring and Self-Generating Search Heuristics,” distinguished three general processes in automated heuristic design: 1) tuning: the process of adjusting the algorithm's control parameters, 2) configuring: the process of selecting and using existing algorithmic components such as search operators, construction heuristics or acceptance criteria, and 3) generating: the process of creating altogether new heuristics (or heuristic components) from the basic sub-components of previously existing methods. Machine learning, meta-modelling and multilevel search approaches can and have been applied to automate these three processes. The workshop introduced the term ‘Self-* Search’, which is now the name of a track in GECCO, which started in 2011 and is also being held this year. The other workshop “Methods for the Assessment of Computational Systems” stressed the idea that the experimental analysis of computational systems inspired by nature can be made more sound and effective by the use of appropriate experimental methods. More severe requirements have been transmitted to draw objective conclusions from computational experiments, while at the same time the design and configuration of the computational systems can be improved by profitable ways of looking into the data collected.The quest for methods to automate the design and assessment of heuristic search methods is spawning a considerable amount of interdisciplinary research, mainly between the fields of computer science, artificial intelligence, optimization, statistics and machine learning. This special issue gathers contributions at the interface of these topics. It comprises five high quality papers that were selected after a rigorous reviewing process.The first two articles are related to the automatic, online configuration of heuristic search methods. Adaptive memetic algorithms (Ong et al., 2006) and selective hyper-heuristics (Burke et al., 2010) have developed separately. However, they share key research issues. In particular, they need to provide adaptive mechanisms to autonomously guide the choice of operators during the search. In the case of memetic algorithms, the choice is among a set of memes, which are generally local search heuristics. In the case of hyper-heuristics, the choice may involve different types of heuristics, such as constructive heuristics, mutational heuristics or neighborhood moves, crossovers and local search heuristics. Both algorithmic schemes require mechanisms for assigning rewards to operators according to their past performance and select which operator to apply at each decision point according to the computed qualities. These mechanisms have been also studied within the evolutionary computation community using the term Adaptive Operator Selection (Fialho et al., 2010).The first paper, “Estimating Meme Fitness in Adaptive Memetic Algorithms for Combinatorial Problems” by J. Smith studies two fundamental issues when assigning credit to search operators. First, whether it is better to assign credit to a meme based on an estimate of the extreme, or the mean benefit it causes. It has been found that, when the operator choice is related to mutation in a standard evolutionary algorithm, “extremal” versions that reward occasional large jumps rather than small steady improvements, produce better results. However, in the case of memes, which by design cause local improvement, the opposite was found in this study. The second issue concerns whether the aggregation of feedback from the search process should be global or local to some part of the solution space. Results suggest that local reward schemes outperform their global counterparts in combinatorial spaces, in contrast to continuous spaces. This study therefore confirms that the performance of credit assignment mechanisms depends on both the nature of the search space and the type of search operator.The paper “Hyper-Heuristics with Low Level Parameter Adaptation” by Z. Ren, H. Jiang, J. Xuan, and Z. Luo incorporates a search-based mechanism for adapting the parameters of the low-level heuristics in a hyper-heuristic framework. Traditionally, selective hyper-heuristics adaptively select the choice of fixed low-level heuristics. But clearly, some of these heuristics are parameterised (for example, the rate of a mutation operator). The proposed framework, then, simultaneously adapt the choice of low-level heuristics and their parameters, with improved results. It also proposes a mechanisms to separate the low-level heuristics into intensification and diversification heuristics, which helps to reduce the heuristic search space and improves efficiency.Parameter tuning of evolutionary algorithms is attracting more and more interest. In particular, the Sequential Parameter Optimization (SPO) is an established parameter tuning framework (Bartz-Beielstein et al., 2005). It uses the available budget (e.g., number of function evaluations) sequentially. Information from the exploration of the search space guides the search by building meta models. New design points are determined based on predictions from these meta models. The meta models are refined stepwise to improve knowledge about the search space. SPO provides techniques to cope with noise and guarantees comparable confidence for search points. It collects information to learn from this tuning process, e.g., integrated exploratory data analysis and provides mechanisms both for interactive and automated tuning. The following two papers discuss essential ways to improve SPO related algorithms by embedding transformations and resampling techniques. Their results are in no way restricted to parameter tuning or SPO.Since data from optimization runs are non-normal, transformations are tools of choice. The paper “On the Effect of Response Transformations in Sequential Parameter Optimization,” by T. Wagner and S. Wessing enhances the SPO framework by introducing transformation steps before the actual modeling. Based on design-of-experiments techniques, they analyze the effect of integrating different transformations. They demonstrate that in particular a rank transformation of the responses provides significant improvements. A deeper analysis of the resulting models and additional experiments with adaptive procedures indicate that the rank and the Box-Cox transformation are able to improve the properties of the result distributions with respect to symmetry and normality of the residuals.The paper “Resampling Methods for Meta-Model Validation, with Recommendations for Evolutionary Computation” by B. Bischl, O. Mersmann, H. Trautmann, and C. Weihs summarizes basic resampling methods from statistics, puts them into the context of meta-model validation and extensively discusses their advantages and disadvantages together with common pitfalls users shall avoid. Meta-model validation is then discussed as a supportive technique within evolutionary algorithms, also providing some concrete examples.Finally, the paper “An Experimental Approach to the Comparison of Continuous Metaheuristics Based on Landscape Topology” by R. Morgan and M. Gallagher extends previous work of the authors on Max-Set of Gaussians (MSG) problem generators. Two Estimation of Distribution type Evolutionary Algorithms (EDA) with different abilities to adapt to problem properties are compared on various randomly determined ridge landscapes, which are constructed by means of a modification of the MSG generator. The article also suggests two visualization tools that shall be helpful for the experimental analysis of non-deterministic optimization algorithms: heatmaps and parameterized difference plots. After detecting typical landscapes that favor either one or the other algorithm, the authors undertake a meta-search in the problem parameter space, maximizing the performance difference of the algorithms, thereby further enhancing the algorithm-problem interaction knowledge for this case.The guest editors wish to thank the contributing authors for their interesting submissions and the reviewers for their constructive feedback and detailed comments. We hope this special issue will promote the cross-fertilisation of ideas in assessing the performance and designing more autonomous and user-friendly heuristic search algorithms.

In this paper we present a coevolutionary algorithm designed to be used as a computational tool to assist in red teaming studies. In these applications, analysts seek to understand the strategic and tactical options available to each side in a conflict situation. Combining scenario simulations with a coevolutionary search of parameter space is an approach that has many attractions. We argue that red teaming applications are sufficiently different from many others where coevolution is used so that specially designed algorithms can bring advantages. We illustrate by presenting a new algorithm that simultaneously evolves strong strategies along with dangerous counter-strategies. We test the new algorithm on two example problems: an abstract problem with some difficult characteristics; and a practical red teaming scenario. Experiments show that the new algorithm is able to solve the abstract problem well, and that it is able to provide useful insights on the red teaming scenario.

Exploratory Landscape Analysis subsumes a number of techniques employed to obtain knowledge about the properties of an unknown optimization problem, especially insofar as these properties are important for the performance of optimization algorithms. Where in a first attempt, one could rely on high-level features designed by experts, we approach the problem from a different angle here, namely by using relatively cheap low-level computer generated features. Interestingly, very few features are needed to separate the BBOB problem groups and also for relating a problem to high-level, expert designed features, paving the way for automatic algorithm selection.

The performance of niching based or related evolutionary algorithms clearly depends on problem properties as e.g. the number of local optima of a problem. We assume there must be more such properties currently not taken into account and, following from practical experience, suggest two more, namely basin size contrast (BSC), the size relation of the largest and the smallest basin, and global to local optima contrast (GLC), the height relation of the global and an average local optimum. We investigate the effect of these problem properties on the performance of different basin identification methods (as subtasks of niching algorithms), namely nearest-better clustering, detect-multimodal, and Jarvis-Patrick clustering, individually, or in combinations. Employing an existing problem generator that enables complete control and knowledge of basins, instances are generated and validated according to predefined property values and the basin identification performance data is modeled in order to detect similarities that may be interpreted as effects of the stated properties. We also give recommendations concerning usage of basin identification methods in different situations. Our approach is strongly related to the recently suggested general idea of exploratory landscape analysis (ELA).

Feature selection is an important prerequisite for music classification which in turn is becoming more and more ubiquitous since entering the digital music age. Automated classification into genres or even personal categories is currently envisioned even for standard mobile devices. However, classifiers often fail to work well with all available features, and simple greedy methods often fail to select good feature sets, making feature selection for music classification a natural field of application for evolutionary approaches in general, and multi-objective evolutionary algorithms in particular. In this work, we study the potential of applying such a multi-objective evolutionary optimization algorithm for feature selection with different objective sets. The result is promising, thus calling for deeper investigations of this approach.

In this paper, we show that sequential parameter optimization (SPO), a method that was designed for (offline) parameter tuning, can be successfully used as a controller for multistart approaches of evolutionary algorithms (EA). We demonstrate this by replacing the restart heuristic of the IPOP-CMA-ES with the SPO algorithm. Experiments on the BBOB 2010 test cases suggest that the performance is at least competitive while the approach provides more options, e.g. setting more than one parameter at once. Essentially, we argue that SPO is a generalization of the IPOP heuristic and that the distinction between tuning and control is---although often useful---an artificial one.

In this work, we develop a simple, graph-based framework, RedTNet, for computational modeling of strategy games and simulations. The framework applies the concept of red teaming as a means by which to explore alternative strategies. We show how the model supports computer-based red teaming in several applications: realtime strategy games and critical infrastructure protection, using an evolutionary algorithm to automatically detect good and often surprising strategies.

The case-specific tuning of parameters of optimization metaheuristics like evolutionary algorithms almost always leads to significant improvements in performance. But if the evaluation of the objective function is computationally expensive, which is typically the case for real-worlds problems, an extensive parameter tuning phase on the original problem is prohibitive. Therefore we have developed another approach: Provided that a (computationally cheap) surrogate model is available that reflects the structural characteristics of the original problem then the parameter tuning can be run on the surrogate problem before using the best parameters thereby identified for the metaheuristic when optimizing the original problem. In this experimental study we aim to assess how many function evaluations on the original problem are necessary to build a surrogate model endowed with the characteristics of the original problem and to develop a methodology that measures to which extent such a matching has been achieved.

In this paper, we overview the 2009 Simulated Car Racing Championship-an event comprising three competitions held in association with the 2009 IEEE Congress on Evolutionary Computation (CEC), the 2009 ACM Genetic and Evolutionary Computation Conference (GECCO), and the 2009 IEEE Symposium on Computational Intelligence and Games (CIG). First, we describe the competition regulations and the software framework. Then, the five best teams describe the methods of computational intelligence they used to develop their drivers and the lessons they learned from the participation in the championship. The organizers provide short summaries of the other competitors. Finally, we summarize the championship results, followed by a discussion about what the organizers learned about 1) the development of high-performing car racing controllers and 2) the organization of scientific competitions.

Any evolutionary technique for multimodal optimization must answer two crucial questions in order to guarantee some success on a given task: How to most unboundedly distinguish between the different attraction basins and how to most accurately safeguard the consequently discovered solutions. This paper thus aims to present a novel technique that integrates the conservation of the best successive local individuals (as in the species conserving genetic algorithm) with a topological subpopulations separation (as in the multinational genetic algorithm) instead of the common but problematic radius-triggered manner. A special treatment for offspring integration, a more rigorous control on the allowed number and uniqueness of the resulting seeds, and a more efficient fitness evaluations budget management further augment a previously suggested naïve combination of the two algorithms. Experiments have been performed on a series of benchmark test functions, including a problem from engineering design. Comparison is primarily conducted to show the significant performance difference to the naïve combination; also the related radius-dependent conserving algorithm is subsequently addressed. Additionally, three more multimodal evolutionary methods, being either conceptually close, competitive as radius-based strategies, or recent state-of-the-art are also taken into account. We detect a clear advantage of three of the six algorithms that, in the case of our method, probably comes from the proper topological separation into subpopulations according to the existing attraction basins, independent of their locations in the function landscape. Additionally, an investigation of the parameter independence of the method as compared to the radius-compelled algorithms is systematically accomplished.

In this paper, two approaches for estimating the generation in which a multi-objective evolutionary algorithm (MOEA) shows statistically significant signs of convergence are introduced. A set-based perspective is taken where convergence is measured by performance indicators. The proposed techniques fulfill the requirements of proper statistical assessment on the one hand and efficient optimisation for real-world problems on the other hand. The first approach accounts for the stochastic nature of the MOEA by repeating the optimisation runs for increasing generation numbers and analysing the performance indicators using statistical tools. This technique results in a very robust offline procedure. Moreover, an online convergence detection method is introduced as well. This method automatically stops the MOEA when either the variance of the performance indicators falls below a specified threshold or a stagnation of their overall trend is detected. Both methods are analysed and compared for two MOEA and on different classes of benchmark functions. It is shown that the methods successfully operate on all stated problems needing less function evaluations while preserving good approximation quality at the same time.

Popular games often have a high-quality graphic design but quite simple-minded non player characters (NPC). Recently, Computational Intelligence (CI) methods have been discovered as suitable methods to revive NPC, making games more interesting, challenging, and funny. We present a fairly large study of human players on the simple arcade game Pac-Man, controlling the ghosts behaviors by simple strategies, neural networks or evolutionary algorithms. The playerpsilas fun is of course a subjective experience, but we presume that it is related to the psychological flow concept. We deal with the question whether flow is a more reliable measure than asking human players directly for the fun experienced during the game. In order to detect flow, we introduce a measure based on the interaction time fraction between the human-controlled Pac-Man and the ghosts, and compare the outcome to the results of a fun measure suggested by Yannakakis and Hallam [1].

The creation of interesting opponents for human players in computer games is an interesting and challenging task. In contrast to up-to-date computer games, e.g. real time strategy games, learning of non-player-character strategies for older games seems to be easier and not that time-consuming. This way, older games, like the famous arcade game Pac-Man, serve as a test bed for the creation of strategies that are fun to play against. The paper at hand uses computational intelligence methods to accomplish this challenge, namely evolutionary algorithms (EA) and artificial neural networks (ANN). The latter are trained on a model of the game whereas the EA learn good behavior by playing. The performance of these two approaches is compared on the original Pac-Man level as well as on other maps with different properties to test the ability of generalizing the learned strategies.

Evolution Strategies (ES) for black-box optimization of a function f:Rn->R are investigated. Namely, we consider the cumulative step-size adaptation (CSA) for the variance of multivariate zero-mean normal distributions, which are commonly used to sample new candidate solutions within Evolution Strategies (ES). Four simplifications of CSA are proposed and investigated empirically and evaluated statistically. The background for these four new CSA-derivatives, however, is NOT performance tuning, but our aim to accomplish a probabilistic/theoretical runtime analysis of an ES using some kind of a CSA in the near future, and a better understanding of this step-size control mechanisms. Therefore, we consider two test problems, namely the Sphere function without and with Gaussian noise.

For solving multimodal problems by means of evolutionary algorithms, one often resorts to multistarts or niching methods. The latter approach the question: ‘What is else where?’ by an implicit second criterion in order to keep populations distributed over the search space. Induced by a practical problem that appears to be simple but is not easily solved, a multiobjective algorithm is proposed for solving multimodal problems. It employs an explicit diversity criterion as second objective. Experimental comparison with standard methods suggests that the multiobjective algorithm is fast and reliable and that coupling it with a local search technique is straightforward and leads to enormous quality gain. The combined algorithm is still fast and may be especially valuable for practical problems with costly target function evaluations.

Within the present paper, we put forward a novel hybridization between support vector machines and evolutionary algorithms. Evolutionary support vector machines consider the classification task as in support vector machines but use an evolutionary algorithm to solve the optimization problem of determining the decision function. They can explicitly acquire the coefficients of the separating hyperplane, which is often not possible within the classical technique. More important, evolutionary support vector machines obtain the coefficients directly from the evolutionary algorithm and can refer them at any point during a run. In addition, they do not require properties of positive (semi-)definition for kernels within nonlinear learning. The concept can be furthermore extended to handle large amounts of data, a problem frequently occurring e.g. in spam mail detection, one of our test cases. An adapted chunking technique is therefore alternatively used. In addition to two different representations, a crowding variant of the evolutionary algorithm is tested in order to investigate whether the performance of the algorithm is maintained; its global search capabilities would be important for the prospected coevolution of non-standard kernels. Evolutionary support vector machines are validated on four real-world classification tasks; obtained results show the promise of this new approach.

The present paper investigates the hybridization of two well-known multimodal optimization methods, i.e. species conservation and multinational algorithms. The topological species conservation algorithm embraces the vision of the existence of subpopulations around seeds (the best local individuals) and the preservation of these dominating individuals from one generation to another, but detects multimodality by means of the hill-valley mechanism employed by multinational algorithms. The aim is to inherit the strengths of both parent techniques and at the same time overcome their flaws. The species conservation algorithm efficiently keeps track of several good search space regions at once, but is difficult to parametrize without prior problem knowledge. Conversely, the multinational algorithms use many functionevaluations to establish subpopulations, but do not depend onprovided radius parameter values. Experiments with all threealgorithms are made on a wide range of test problems in order toinvestigate their advantages and shortcomings.

Sequential parameter optimization is a heuristic that combines classical and modern statistical techniques to improve the performance of search algorithms. To demonstrate its flexibility, three scenarios are discussed: (1) no experience how to choose the parameter setting of an algorithm is available, (2) a comparison with other algorithms is needed, and (3) an optimization algorithm has to be applied effectively and efficiently to a complex real-world optimization problem. Although sequential parameter optimization relies on enhanced statistical techniques such as design and analysis of computer experiments, it can be performed algorithmically and requires basically the specification of the relevant algorithm's parameters.

A new radii-based evolutionary algorithm (EA) designed for multimodal optimization problems is proposed. The approach can be placed within the genetic chromodynamics framework and related to other EAs with local interaction, e.g. using species formation or clearing procedures. The underlying motivation for modifying the original algorithm was to preserve its ability to search for many optima in parallel while increasing convergence speed, especially for complex problems, through generational selection and different replacement schemes. The algorithm is applied to function optimization and classification; obtained experimental results, in part improved immensely by state-of-the-art parameter tuning (SPO), and encouraged further investigation.

The impact of operator disruption and genetic drift on the extinction of EA subpopulations on multimodal landscapes is estimated by means of idealized two-peak landscape models. To establish upper and lower bounds for extinction times the behavior of an EA that employs (μpluskommaλ) selection and recombination mechanisms is studied, assuming disruptive recombination. Markov chain and statistical simulation studies reveal that panmictic selection mechanisms as used in evolution strategies (ES) do not allow for maintaining several populations of similar fitness at the same time. Moreover, when using comma selection, good individuals might easily get lost if forming the minority of a population, an effect seemingly amplified by recombination. Niching techniques are suggested to facilitate coexistence of populations on distant attractors; conducted studies confirm their aptitude.

This paper describes a novel peer-to-peer (P2P) environment for running distributed Java applications on the Internet. The possible application areas include simple load balancing, parallel evolutionary computation, agent-based simulation and artificial life. Our environment is based on cutting-edge P2P technology. We introduce and analyze the concept of long term memory which provides protection against partitioning of the network. We demonstrate the potentials of our approach by analyzing a simple distributed application. We present theoretical and empirical evidence that our approach is scalable, effective and robust.