Evolutionary Systems
AntBeePath: A Hybrid Bio-Inspired Algorithm for Path Determination
Lamartin, Joao Paulo (Salvador University - UNIFACS) | Martins, Joberto (Salvador University - UNIFACS)
AntBeePath is a hybrid bio-inspired algorithm based on the behavior of ants and honeybees aimed at the resolution of the problem of finding the shortest paths for a given network topology. The algorithm, in brief, combines the pheromone release mechanism of existing Ant Colony Optimization (ACO) algorithms with a new bio-inspired mechanism based on the recruitment strategy of bees. Three versions of the algorithm were developed incrementally. Proof-of-concept results indicate that the AntBeePath Decay Hybrid Chain version is more efficient than the other developed versions and, beyond that, presented an improved performance in relation to an equivalent ACO algorithm. The results suggest that a hybrid algorithm, combining the ant’s pheromone release with the new bio-inspired mechanism of bee recruitment along with a stagnation control mechanism can result in a new bio-inspired algorithm for path determination with improved characteristics.
Investigating Neglect Benevolence and Communication Latency During Human-Swarm Interaction
Walker, Phillip (University of Pittsburgh) | Kolling, Andreas (Carnegie Mellon University) | Nunnally, Steven (University of Pittsburgh) | Chakraborty, Nilanjan (Carnegie Mellon University) | Lewis, Michael (University of Pittsburgh) | Sycara, Katia (Carnegie Mellon University)
In practical applications of robot swarms with bio-inspired behaviors, a human operator will need to exert control over the swarm to fulfill the mission objectives. In many operational settings, human operators are remotely located and the communication environment is harsh. Hence, there exists some latency in information (or control command) transfer between the human and the swarm. In this paper, we conduct experiments of human-swarm interaction to investigate the effects of communication latency on the performance of a human-swarm system in a swarm foraging task. We develop and investigate the concept of neglect benevolence, where a human operator allows the swarm to evolve on its own and stabilize before giving new commands. Our experimental results indicate that operators exploited neglect benevolence in different ways to develop successful strategies in the foraging task. Furthermore, we show experimentally that the use of a predictive display can help mitigate the adverse effects of communication latency.
POWERPLAY: Training an Increasingly General Problem Solver by Continually Searching for the Simplest Still Unsolvable Problem
Most of computer science focuses on automatically solving given computational problems. I focus on automatically inventing or discovering problems in a way inspired by the playful behavior of animals and humans, to train a more and more general problem solver from scratch in an unsupervised fashion. Consider the infinite set of all computable descriptions of tasks with possibly computable solutions. The novel algorithmic framework POWERPLAY (2011) continually searches the space of possible pairs of new tasks and modifications of the current problem solver, until it finds a more powerful problem solver that provably solves all previously learned tasks plus the new one, while the unmodified predecessor does not. Wow-effects are achieved by continually making previously learned skills more efficient such that they require less time and space. New skills may (partially) re-use previously learned skills. POWERPLAY's search orders candidate pairs of tasks and solver modifications by their conditional computational (time & space) complexity, given the stored experience so far. The new task and its corresponding task-solving skill are those first found and validated. The computational costs of validating new tasks need not grow with task repertoire size. POWERPLAY's ongoing search for novelty keeps breaking the generalization abilities of its present solver. This is related to Goedel's sequence of increasingly powerful formal theories based on adding formerly unprovable statements to the axioms without affecting previously provable theorems. The continually increasing repertoire of problem solving procedures can be exploited by a parallel search for solutions to additional externally posed tasks. POWERPLAY may be viewed as a greedy but practical implementation of basic principles of creativity. A first experimental analysis can be found in separate papers [53,54].
A Biomimetic Approach Based on Immune Systems for Classification of Unstructured Data
Hamou, Mohamed, Amine, Abdelmalek, Lokbani, Ahmed Chaouki
In this paper we present the results of unstructured data clustering in this case a textual data from Reuters 21578 corpus with a new biomimetic approach using immune system. Before experimenting our immune system, we digitalized textual data by the n-grams approach. The novelty lies on hybridization of n-grams and immune systems for clustering. The experimental results show that the recommended ideas are promising and prove that this method can solve the text clustering problem.
Improved Local Search in Artificial Bee Colony using Golden Section Search
Sharma, Tarun Kumar, Pant, Millie, Singh, V. P.
Artificial bee colony (ABC), an optimization algorithm is a recent addition to the family of population based search algorithm. ABC has taken its inspiration from the collective intelligent foraging behavior of honey bees. In this study we have incorporated golden section search mechanism in the structure of basic ABC to improve the global convergence and prevent to stick on a local solution. The proposed variant is termed as ILS-ABC. Comparative numerical results with the state-of-art algorithms show the performance of the proposal when applied to the set of unconstrained engineering design problems. The simulated results show that the proposed variant can be successfully applied to solve real life problems.
Parallel ACO with a Ring Neighborhood for Dynamic TSP
Pintea, Camelia-M., Crisan, Gloria Cerasela, Manea, Mihai
The current paper introduces a new parallel computing technique based on ant colony optimization for a dynamic routing problem. In the dynamic traveling salesman problem the distances between cities as travel times are no longer fixed. The new technique uses a parallel model for a problem variant that allows a slight movement of nodes within their Neighborhoods. The algorithm is tested with success on several large data sets.
Embracing the Bias of the Machine: Exploring Non-Human Fitness Functions
Eigenfeldt, Arne (Simon Fraser University)
Autonomous aesthetic evaluation is the Holy Grail of generative music, and one of the great challenges of computational creativity. Unlike most other computational activities, there is no notion of optimality in evaluating creative output: there are subjective impressions involved, and framing obviously plays a big role. When developing metacreative systems, a purely objective fitness function is not available: the designer is thus faced with how much of their own aesthetic to include. Can a generative system be free of the designer’s bias? This paper presents a system that incorporates an aesthetic selection process that allows for both human-designed and non-human fitness functions.
Limitations of Choice-Based Interactive Evolution for Game Level Design
Liapis, Antonios (IT University of Copenhagen) | Yannakakis, Georgios N. (IT University of Copenhagen) | Togelius, Julian (IT University of Copenhagen)
This paper presents a tool geared towards the collaboration of a human and an artificial designer for the creation of game content. The framework combines procedural content generation using stochastic search with user input in the form of an initial goal statement as well as preference of generated results. Feedback from industry experts in a pilot user experiment showcased the limitations of this approach and the protocol chosen for evaluating the authoring tool. The limitations are discussed with respect to the suitability of interactive evolution for creative design and the design of experimental protocols for evaluating authoring tools for games.
RRT-Based Game Level Analysis, Visualization, and Visual Refinement
Bauer, Aaron William (University of Washington) | Popović, Zoran (University of Washington)
Automating parts of game creation benefits both professional and amateur game designers and much previous work has already made progress on this front. In this paper we tackle automating level design. We describe a general graph-based representation for game levels and present a preliminary system that leverages this representation. Our system automatically explores existing levels of a 2D platform game using the rapidly-exploring random tree (RRT) algorithm and constructs a compact graph representation from this exploration. Our system can also modify a graph representation on-the-fly to reflect user-directed changes to the existing level structure. This work constitutes an initial step toward the larger goal of automating level design in a general way.
Algorithmically Flexible Style Composition Through Multi-Objective Fitness Functions
Murray, Skyler (Brigham Young University) | Ventura, Dan (Brigham Young University)
Creating a musical fitness function is largely subjective and can be critically affected by the designer's biases. Previous attempts to create such functions for use in genetic algorithms lack scope or are prejudiced to a certain genre of music. They also are limited to producing music strictly in the style determined by the programmer. We show in this paper that musical feature extractors, which avoid the challenges of qualitative judgment, enable creation of a multi-objective function for direct music production. The main result is that the multi-objective fitness function enables creation of music with varying identifiable styles. To demonstrate this, we use three different multi-objective fitness functions to create three distinct sets of musical melodies. We then evaluate the distinctness of these sets using three different approaches: a set of traditional computational clustering metrics; a survey of non-musicians; and analysis by three trained musicians.