This paper focuses on the collective cognition of robotic swarms. The robotic swarms perform tasks that are beyond the capability of a single robot by collective behavior that emerge from local interactions. However, due to the lack of the capability of a single robot, it is necessary for robotic swarms to collectively perceive the environment. In this paper, we develop controllers for a robotic swarm to accomplish a complex cognitive task, namely the collective foraging task with poison. In this task, robots have to both collectively distinguish two objects, namely foods and poisons, and cooperatively transport foods to the nest. We applied an evolutionary robotics approach with covariance matrix adaptation evolution strategy to develop controllers for robotic swarms. The results of computer simulations show that collective cognition behavior was successfully generated, which allows the robots to transport only foods. In addition, we also perform experiments to examine the scalability of the developed controllers.

Sudoku puzzles are logical number placement puzzle games. They are classified as combinatorial optimization problems and are NP-complete. To solve problems in this complexity class, metaheuristic approaches, such as genetic algorithms (GAs), are often adopted. However, conventional GAs with random swap mutations suffer from slow convergence, especially in extremely difficult sudoku puzzles, in which only a few given numbers are provided. This paper proposes a GA with sophisticated genetic mutations that mitigate the worsening of fitness values. The comparisons between the conventional method and the proposed method are conducted mainly from the viewpoints of success rate.

An artificial bee colony (ABC) algorithm is one of numerous swarm intelligence algorithms that employs the foraging behavior of honeybee colonies. To improve the convergence performance and search speed of finding the best solution using this approach, we propose a levy flight-based hybrid ABC algorithm in this paper. To evaluate the performance of the standard and proposed ABC algorithms, we implemented numerical optimization problems based on the IEEE Congress on Evolutionary Computation 2013 test suite. The proposed ABC algorithm demonstrated competitive performance on these optimization problems as compared to standard ABC, differential evolution, and particle swarm optimization algorithms with dimension sizes of 10, 30, and 50, respectively.

Swarm robotic systems are a type of multi-robot systems which generally consist of many homogeneous autonomous robots without any type of global controllers. Swarm robotics aims at designing desired collective behaviors through many interactions with other robots or their environment. Since a robotic swarm is controlled by an emergent way such as a result of self-organization by using robot learning or artificial evolution, no method has been known to grasp the macroscopic collective behavior in a practical sense, according to the best of our knowledge. In this paper, we propose a novel method for analyzing the collective behavior by introducing the concept of behavioral sequence, which stems from ethology. Analysis about behavioral sequence reveals the transition of robot's action from the viewpoint of specialization and helps us to understand the role of subgroups in a robotic swarm. Applying this method, we observe collective behavior in a foraging task of autonomous mobile robots.

A swarm robotics system is a distributed system consisting of many homogeneous autonomous robots without a global controller. In this paper, we apply a swarm robotics system to the cooperative food-foraging problem, in which autonomous cooperation is necessary to carry out the foraging task. Supposing that each robot in a swarm has an artificial neural network as its behavioral controller, the evolutionary robotics approach is adopted for robot learning. However, we quickly discover that this approach is inadequate because the conventional evolutionary robotics approach does not coordinate a sufficiently adaptive collective behavior within a limited number of evaluations. As a consequence, we instead apply the incremental evolution approach to develop a sophisticated cooperative collective behavior. The results of a series of computer simulations demonstrate that the incremental evolution approach is effective for solving this difficult type of problem.

The field of multi-robot systems (MRS) deals with groups of autonomous robots and is attracting much research interest from robotics researchers. MRSs are expected to achieve tasks that are difficult to perform by an individual robot. In MRS, reinforcement learning (RL) is a promising approach for the distributed control of each robot. RL allows robots to learn mappings from their states to their actions through rewards or payoffs obtained through interactions with their environment. Theoretically, the environment of an MRS is nonstationary, and therefore rewards or payoffs received by learning robots depend not only on their own actions but also on the actions of other robots. From this perspective, our research group has been developing a technique that segments state and action spaces simultaneously and autonomously to extend the adaptability of an MRS to dynamic environments. To improve learning performance, we introduce a mechanism of selecting either of the two state spaces: one is represented by a parametric model for exploration, while the other is represented by a nonparametric model for exploitation. The proposed technique is expected to show better learning performance and robustness against an unpredicted environmental change. We investigate our proposed technique by conducting computer simulations of a cooperative box-pushing task with six autonomous mobile robots.

Parallel processing using graphic processing units (GPUs) have attracted much research interest in recent years. Parallel computation can be applied to genetic algorithms (GAs) in terms of the processes of individuals in a population. This paper describes the implementation of GAs in the compute unified device architecture (CUDA) environment. CUDA is a general-purpose computation environment for GPUs. The major characteristic of this study is that a steady-state GA is implemented on a GPU based on concurrent kernel execution. The proposed implementation is evaluated through four test functions; we find that the proposed implementation method is 3.0-6.0 times faster than the corresponding CPU implementation.

Swarm robotics (SR) is the research field of multirobot systems, which consist of many homogeneous autonomous robots without any types of global controllers. Generally, since a task given to this system cannot be achieved by a single robot, cooperative behavior is expected to emerge in a robotic swarm by a certain mechanism, which is through the interactions among robots or with an environment. In this paper, an evolutionary robotics approach, in which robot controllers are designed by evolving artificial neural networks, is adopted. Among the many approaches to evolving artificial neural networks, two approaches, NEAT and MBEANN are adopted for conducting computer simulations. Although a conventional neural network has a fixed topology and evolves only with its synaptic weights, NEAT and MBEANN evolve not only with their synaptic weights, but also with their topologies. As a benchmark for swarm robotics, cooperative package-pushing problems using ten autonomous robots are conducted to evaluate their performance. The behavioral characteristics that emerge are then discussed.

Fitness landscapes which include neutrality have been conceptualized as containing neutral networks. Since the introduction of this concept, EC researchers have expected that a population can move along neutral networks without getting trapped on local optima. On the other hand, it has been demonstrated in tunably neutral NK landscapes that neutrality does not affect the ruggedness, although it does reduce the number of local optima. These show that the effects of neutrality are still contentious issues. This paper investigates the effects of neutrality and ruggedness on topologies of fitness andscapes. A neutral network of a fitness landscape is described in a mathematical form based on Harvey's original definition with minor modifications. Our results demonstrate that landscapes with a higher degree of neutrality have the larger sizes of neutral networks. For landscapes with the lowest degree of ruggedness, all networks lead to the networks of the highest fitness via any networks. For landscapes with a higher degree of ruggedness, there are few contact points between the networks of high fitness and the ones of the highest fitness, which seem to be isolated, deceptive or rugged.

A computational method for the implementation of an evolutionary multi-robotics (EMR) problem in grid computing environments is discussed. Due to the synchronization requirements of Evolutionary Algorithms (EAs), when the EMR problem is deployed in the grid environment there is a higher waiting time overhead because of medium-grained tasks. The round-robin replication remote work queue (R3Q) is adopted to reduce both the synchronous waiting time and communication time. In the current research, the performance of the grid scheduling is evaluated using uniform computational granularity despite that many problems such as EMR have nonuniform computational granularity. Therefore, in order to evaluate R3Q on nonuniform computational granularity, the cooperative object pushing EMR problem is adopted; and R3Q is compared with grid scheduling algorithms Work Queue (WQ), and list scheduling with round-robin order replication (RR). Our results show that R3Q is effective for tasks which have nonuniform computational granularity.

A computational method for implementation of evolution strategies (ES) in grid computing environments is discussed. In this paper, list scheduling with round-robin order replication (RR) is adopted to reduce waiting times due to synchronization in ES. However, RR is suitable for coarse grained tasks. For ES as medium-grained tasks, we propose a new technique to reduce the communication overhead, called the remote work queue (RWQ) method. We then define round robin replication remote work queue (R3Q) as RWQ with RR. Our results show that R3Q can reduce both the synchronous waiting time and communication time, and provides efficient forced termination of tasks compared to other methods.

In recent years, not only ruggedness but also neutrality has been recognized as an important feature of a fitness landscape for genetic search. As it has been reported that the evolutionary dynamics on a fitness landscape with neutrality is clearly different from the canonical explanations, ruggedness alone might be inadequate describing it. Another measure, i.e., neutrality is required. In this paper, we proposed the use of the Nei's standard genetic distance, which originates from population genetics, for estimating the degree of neutrality in fitness landscapes after minor modifications. Several computer simulations were conducted with an evolutionary robotics problem in order to investigate the validity of the proposed approach. The results suggest to us that the Nei's genetic distance is a reliable method for estimating the degree of neutrality on real-world problems.

Different from standard genetic algorithms where each individual is evaluated separately according to predefined objective function(s), one most notable characteristic of coevolutionary genetic algorithms (CGA) is that evaluation procedures require more than one individual and an individual's fitness is depending on its interactions with its partners. In consequence, the implemented partnering strategies can have significant effects on the dynamical behaviour of CGA as well as their optimization performance. Infinite population models of CGA consisting of two populations coevolving on two-bit landscapes are described and investigated in the context of four well-applied partnering strategies. It is shown that even in these simplest models, the dynamical behaviour of CGA changes dramatically according to different evolutionary scenarios that deserves our attention from the perspective of coevolutionary algorithms designing.

In recent years, not only ruggedness but also neutrality has been recognized as an important feature of a fitness landscape for genetic search. Following that the concept of neutrality in artificial evolution originates from Kimura's neutral theory in natural evolution, it is expected that the dynamics of artificial evolution in the landscapes including neutrality would be described by using techniques in population genetics. Furthermore, new theoretical guidelines might be developed for effective genetic search. In a recent paper, we have discussed the use of the Nei's standard genetic distance, which originates from population genetics, for measuring neutrality of fitness landscapes. In our results, several consistencies with the population genetics have been found by applying the Nei's standard genetic distance to a tunably neutral NK landscape. Computer simulations are systematically conducted by using a standard genetic algorithm in order to clarify the characteristics of the Nei's standard genetic distance. The terraced NK landscape is adopted as a test function.

Multilevel selection theory views natural selection as hierarchy process that acts on any level of biological organizations whenever there exist heritable variation in fitness among units of that level. In this paper, selection schemes of evolutionary algorithms (EAs) are reconsidered from the point of view of the theory, and a novel constraint handling method is introduced in which a two-level selection process, namely within-group selection and between-group selection, is modeled to keep right balance between objective and penalty functions. The method is implemented on 3 group selection models that possessing different population structures and tested using (/spl mu/, /spl lambda/)-evolution strategies on a set of 13 benchmark problems. We show that a proper understanding of multilevel selection theory will help us to design EAs and might also enable us to challenge the old problems from a new angle.

A symbiotic evolutionary algorithm (SymEA) for dynamic facility layout problem (DFLP) is developed and tested. SymEA differs from the existing EA approaches for DFLP in two ways: first, it adopted a coevolutionary multi-population approach, second, the generational replacement strategy (/spl mu/, /spl lambda/)-selection of evolution strategies is used to refine the symbiotic relationship.

This paper experimentally investigates the effect of global recombination operators on multirecombination Evolution Strategies ((/spl mu///spl rho/,/spl lambda/)-ES). For ES, each individual has a pair of real-valued vectors, i.e., object parameters and strategy parameters. We adopt two popular global recombination operators, namely Global Intermediate Recombination (GIR) and Global Discrete Recombination (GDR), and apply GIR or GDR to both object parameters and strategy parameters. Computer simulations are conducted using three types of (/spl mu///spl mu/,/spl lambda/)-ES, which are Classical-ES (CES), Fast-ES (FES) and Robust-ES (RES). We show the advantages of GIR or GDR in CES, FES and RES. Especially, GDR on a pair of an object parameters and a strategy parameters improves the performance of all ESs in our experiments.

The multi-recombinant (/spl mu///spl mu/,/spl lambda/)-evolution strategy (ES) is investigated on a set of real-valued test functions empirically, in order to obtain guidelines for choosing a potential type of recombination in the framework of ESs. Applying the multi-parent versions of intermediate recombination (/spl mu///spl mu//sub I/,/spl lambda/) and discrete recombination (/spl mu///spl mu//sub D/,/spl lambda/) to both objective variables and strategy parameters, five ESs with different recombination mechanisms are adopted. It has been found that, in most cases, robust performance can be obtained when discrete recombination is applied simultaneously to an object variable-strategy parameter pair.

The effect of noise on the evolutionary dynamics of evolutionary programming (EP) is empirically observed using three different statistical values. These are: (1) the averaged best function values, (2) the average of the strategy parameters, and (3) Hotelling's T/sup 2/ of real values. The classical EP (CEP) of D.B. Fogel (1995), the fast EP (FEP) of X. Yao & Y. Liu (1996) and our extended, robust EP (REP) (Y. Matsumura, K. Ohkura & K. Ueda, 1999) are adopted for the observation. We show that REP performs more robustly than CEP and FEP for six noisy test functions.

The effectiveness of applying genetic algorithms to combinatorial optimization has been widely demonstrated using many types of benchmark problems, such as the traveling salesman problems and job-shop scheduling problems. We want to optimize strategies for advertising in newspapers sold in Japan. Our problem is to select appropriate newspapers and find the correct frequency of advertising for a product in order to maximize the level of advertising to which the target audience is exposed, within the constraint of a limited total budget. Advertising problems are typically so large and complex that conventional optimization techniques, such as hill-climbing, cannot find sufficiently cost-effective solutions. We show that a genetic algorithm (GA) approach works well for this type of problem. In addition, we demonstrate, through computer simulations, that an extended GA, called the operon-GA, finds better solutions much faster than a simple GA.