Swarm Intelligence

Modelling natural processes requires the implementation of an expressive representation of the involved entities and their interactions. We present

swarm graph grammars

(SGGs) as a bio-inspired modelling framework that integrates aspects of formal grammars, graph-based representation and multi-agent simulation. In SGGs, the substitution of subgraphs that represent locally defined agent interactions drive the computational process of the simulation. The generative character of formal grammars is translated into an agent’s

metabolic

interactions, i.e. creating or removing agents from the system. Utilizing graphs to describe interactions and relationships between pairs or sets of agents offers an easily accessible way of modelling biological phenomena. Property graphs emerge through the application of local interaction rules; we use these graphs to capture various aspects of the interaction dynamics at any given step of a simulation.

The multilinear rank of a tensor is one of the possible generalizations for the concept of matrix rank. In this paper, we are interested in finding the best low multilinear rank approximation of a given tensor. This problem has been formulated as an optimization problem over the Grassmann manifold [14] and it has been shown that the objective function presents multiple minima [15]. In order to investigate the landscape of this cost function, we propose an adaptation of the Particle Swarm Optimization algorithm (PSO). The Guaranteed Convergence PSO, proposed by van den Bergh in [23], is modified, including a gradient component, so as to search for optimal solutions over the Grassmann manifold. The operations involved in the PSO algorithm are redefined using concepts of differential geometry. We present some preliminary numerical experiments and we discuss the ability of the proposed method to address the multimodal aspects of the studied problem.

Division of labour in multi-robot systems or multi-robot task allocation (MRTA) is a challenging research issue. We propose to solve this MRTA problem using a set of previously published generic rules for division of labour derived from the observation of ant, human and robotic social systems. These bottom-up rules describe the phenomenon of self-regulated division of labour in terms of attractive fields between robots and tasks. The concrete form of these rules, the

attractive filed model

, avoids the strong dependence on local interactions found in many existing approaches to MRTA. We present experimental results that constitute a first validation of attractive filed model as a mechanism for MRTA and as a multi-disciplinary model of self-organisation in social systems. Our experiments used 16 e-puck robots in a 2m x 2m area.

We propose a new approach to the simultaneous cooperative localization of a group of robots capable of sensing their own motion on the plane and the relative position of nearby robots. In the last decade, the use of distributed optimal Kalman filters (KF) to solve this problem have been studied extensively. In this paper, we propose to use a sub-optimal Kalman filter (denoted by EA). EA requires significantly less computation and communication resources then KF. Furthermore, in some cases, EA provides better localization.

In this paper EA is analyzed in a soft “thermodynamic” fashion i.e. relaxing assumptions are used during the analysis. The goal is not to derive hard lower or upper bounds but rather to characterize the robots expected behavior. In particular, to predict the expected localization error. The predictions were validated using simulations. We believe that this kind of analysis can be beneficial in many other cases.

The Ant Colony Optimization (ACO) metaheuristic embodies a large set of algorithms which have been successfully applied to a wide range of optimization problems. Although ACO practitioners have a long tradition in solving combinatorial optimization problems, many other researchers have recently developed a variety of ACO algorithms for dealing with continuous optimization problems. One of these algorithms is the so-called ACO

$_{\Bbb{R}}$

, which is one of the most relevant ACO algorithms currently available for continuous optimization problems. Although ACO

$_{\Bbb{R}}$

has been found to be successful, to the authors’ best knowledge its use in high-dimensionality problems (i.e., with many decision variables) has not been documented yet. Such problems are important, because they tend to appear in real-world applications and because in them, diversity loss becomes a critical issue. In this paper, we propose an alternative ACO

$_{\Bbb{R}}$

algorithm (DACO

$_{\Bbb{R}}$

) which could be more appropriate for large scale unconstrained continuous optimization problems. We report the results of an experimental study by considering a recently proposed test suite. In addition, the parameters setting of the algorithms involved in the experimental study are tuned using an

ad hoc

tool. Our results indicate that our proposed DACO

$_{\Bbb{R}}$

is able to improve both, the quality of the results and the computational time required to achieve them.

In order to summarize and represent graphically multidimensional data in statistics, projection pursuit methods look for projection axes which reveal structures, such as possible groups or outliers, by optimizing a function called projection index. To determine these possible interesting structures, it is necessary to choose an optimization method capable to find not only the global optimum of the projection index but also the local optima susceptible to reveal these structures. For this purpose, we suggest a metaheuristic which does not ask for many parameters to settle and which provokes premature convergence to local optima. This method called Tribes is a hybrid Particle Swarm Optimization method (PSO) based on a stochastic optimization technique developed in [2]. The computation is fast even for big volumes of data so that the use of the method in the field of projection pursuit fulfills the statistician expectations.

In this work we propose a hybrid ant colony optimisation algorithm as an alternative search engine in the GOLD protein-ligand docking framework [4]. The approach treats the placement of a ligand molecule in the protein’s binding site as a discrete assignment problem and a geometric point fitting procedure generates protein-ligand complex conformations from this representation. As in PLANTS [5,6], we combine this approach with a local search in the continuous search space of the objective function. Continuous solutions are finally reassigned to approximate solutions of the discrete assignment problem resulting in a high-performing optimisation approach. We discuss certain aspects of the hybridisation strategy including the integration of

heuristic information

into the search process and compare the performance to the

genetic algorithm

currently used in GOLD.

In this paper we present an experimental setup to model the pheromone trail based foraging behaviour of ants using a special phosphorescent glowing paint. We have built two custom addons for the e-puck robot that allow for trail laying and following on the glowing floor, as well as a way for the robots to mimic the ants capability of using polarization patterns as a means of navigation. Using simulations we show that our approach allows for efficient pathfinding between nest and potential food sources. Experimental results show that our trail and sun compass add-on boards are accurate enough to allow a single robot to lay and follow a trail repeatedly.

In the last few years a significant number of ant colony optimization (ACO) algorithms have been proposed for tackling multi-objective optimization problems. In this paper, we propose a software framework that allows to instantiate the most prominent multi-objective ACO (MOACO) algorithms. More importantly, the flexibility of this MOACO framework allows the application of automatic algorithm configuration techniques. The experimental results presented in this paper show that such an automatic configuration of MOACO algorithms is highly desirable, given that our automatically configured algorithms clearly outperform the best performing MOACO algorithms that have been proposed in the literature. As far as we are aware, this paper is also the first to apply automatic algorithm configuration techniques to multi-objective stochastic local search algorithms.

This paper presents a simple decentralised morphology control mechanism for a swarm of self-assembling robots. Each robot in the system is fully autonomous and controlled using a behaviour-based approach with only infrared-based local sensing and communications. A graph-based recruitment strategy is proposed to guide the growth of 2D planar organisms, and local communications are used to self-organise the behaviours of robots during the morphogenesis process. The effectiveness of the approach has been verified, in simulation, for a diverse set of target structures.

We introduce a novel multi-agent patrolling strategy. By assumption, the swarm of agents performing the task consists of very low capability ant-like agents. The agents have little memory, they can not communicate and their sensing abilities are local. Furthermore, the agents do not possess any knowledge regarding the graph or the swarm size. However, the agents may mark the graph vertices with pheromone stamps which can later be sensed. These markings are used as a primitive form of distributed memory and communication. The proposed strategy is a bundle of two algorithms. A single agent (the “leader”) is responsible of finding a short cycle which covers the graph, and this is achieved using a “cycle finding” algorithm. All other agents follow that cycle while maintaining even gaps between them using a “spreading algorithm”. We prove that the algorithms converge within a finite expected time. After convergence, the maximum time lag between two successive visits to any vertex using the proposed strategy is at most

$4\frac{k}{k-1}\frac{l_{max}}{l_{min}}$

times the optimal, where the optimal time is bounded from below by

$\frac{n\cdot l_{min}}{k}$

, and where

l

max

(

l

min

) is the longest (shortest) edge in the graph and

k

is the swarm size.

The “cycle finding” algorithm is robust i.e. in case the graph changes, the leader autonomously finds a new patrolling route. The “spreading algorithm” is scalable and robust. In case the patrolling cycle or the number of agents change during run (e.g. as a result of an agent break down) the agents autonomously redeploy uniformly over the patrolling cycle.

Finding ways to engineer morphogenesis in biological systems, to direct the development of a multicellular organism according to desired specifications, will require both high-level understanding of organizing principles in such systems and low-level understanding of how basic tools can be reliably implemented in real cells. Past work has assumed low-level capabilities appropriate to computing agents but not necessarily to biology. Here I discuss potential ways of implementing low-level primitives based on capabilities for which evidence exists in biological systems, with the goal of developing a basis for engineering developmental processes that will be realizable in wetware. I focus on the use of biologically realistic morphogen gradients to produce structures of desired size, provide positional information, and trigger genetic cascades that lead to the growth of more complex structures.

Activator-inhibitor models have been widely used to explain several morphogenetic processes. They have also been used to engineer algorithms for computer graphics, distributed systems and networks. These models are known to be robust to perturbations such as the removal of peaks of chemicals. However little has been reported about their actual quantitative performance under such disruptions.

In this paper we experimentally evaluate the robustness of two well-known activator-inhibitor models in the presence of attacks that remove existing activator peaks. We focus on spot patterns used as distributed models for cluster head computation, and on their potential implementation in chemical computing. For this purpose we derive the corresponding chemical reactions, and simulate the system deterministically.

Our results show that there is a trade-off between both models. The chemical form of the first one, the Gierer-Meinhardt model, is slow to recover due to the depletion of a required catalyst. The second one, the Activator-Substrate model, recovers more quickly but is also more dynamic as peaks may slowly move. We discuss the implications of these findings when engineering algorithms based on morphogenetic models.

We present a set of experiments in which a robotic swarm manages to collectively explore the environment, forming a path to navigate between two target areas, which are too distant to be perceived by an agent at the same time. Robots within the path continuously move back and forth between the two locations, exploiting visual interactions with their neighbours. The global group behaviour is obtained through an evolutionary process and presents emergent properties like robustness, path optimisation and scalability, which recall ants trail formation.

Ant-Miner is an ant-based algorithm for the discovery of classification rules. This paper proposes four extensions to Ant-Miner: 1) we allow the use of a logical negation operator in the antecedents of constructed rules; 2) we use stubborn ants, an ACO-variation in which an ant is allowed to take into consideration its own personal past history; 3) we use multiple types of pheromone, one for each permitted rule class, i.e. an ant would first select the rule class and then deposit the corresponding type of pheromone; 4) we allow each ant to have its own value of the

α

and

β

parameters, which in a sense means that each ant has its own individual personality. Empirical results show improvements in the algorithm’s performance in terms of the simplicity of the generated rule set, the number of trials, and the predictive accuracy.

The engineering of grown systems poses fundamentally different system integration challenges than ordinary engineering of static designs. On the one hand, a grown system must be capable of surviving not only in its final form, but at every intermediate stage, despite the fact that its subsystems may grow unevenly or be subject to different scaling laws. On the other hand, the ability to grow offers much greater potential for adaptation, either to changes in the environment or to internal stresses developed as the system grows. I observe that the ability of subsystems to tolerate stress can be used to transform incremental adaptation into the dynamic discovery of viable growth trajectories for the system as a whole. Using this observation, I propose an engineering approach based on

functional blueprints

, under which a system is specified in terms of desired performance and means of incrementally correcting deficiencies. I demonstrate this approach by applying it to integrate simplified models of tissue growth and vascularization, then further demonstrate how the composed system may itself be modulated for use as a component in a more complex design.

Particles in the standard particle swarm optimization (PSO) algorithms, and most of its modifications, follow the same behaviours. That is, particles implement the same velocity and position update rules. This means that particles exhibit the same search characteristics. A heterogeneous PSO (HPSO) is proposed in this paper, where particles are allowed to follow different search behaviours selected from a behaviour pool, thereby efficiently addressing the exploration–exploitation trade-off problem. A preliminary empirical analysis is provided to show that much can be gained by using heterogeneous swarms.

To obtain peak performance from optimization algorithms, it is required to set appropriately their parameters. Frequently, algorithm parameters can take values from the set of real numbers, or from a large integer set. To tune this kind of parameters, it is interesting to apply state-of-the-art continuous optimization algorithms instead of using a tedious, and error-prone, hands-on approach. In this paper, we study the performance of several continuous optimization algorithms for the algorithm parameter tuning task. As case studies, we use a number of optimization algorithms from the swarm intelligence literature.

We consider two variants of the task of spreading a swarm of agents uniformly on a ring graph. Ant-like

oblivious

agents having limited capabilities are considered. The agents are assumed to have little memory, they all execute the same algorithm and no direct communication is allowed between them. Furthermore, the agents do not possess any global information. In particular, the size of the ring (

n

) and the number of agents in the swarm (

k

) are unknown to them. The agents are assumed to operate on an unweighted ring graph. Every agent can measure the distance to his two neighbors on the ring, up to a limited range of

V

edges.

The first task considered, is uniformly spread dynamical (i.e. in motion) deployment on the ring. We show that if either the ring is unoriented, or the visibility range is less than

$\left\lfloor n/k\right\rfloor $

, this is an impossible mission for the agents. Then, for an oriented ring and

$V\geq\left\lceil n/k\right\rceil $

, we propose an algorithm which achieves the deployment task within the optimal time. The second task discussed, called quiescent spread, requires the agents to spread uniformly over the ring and stop moving. We prove that under our model in which every agent can measure the distance only to his two neighbors, this task is impossible. Subsequently, we propose an algorithm which achieves quiescent and almost uniform spread.

The algorithms we present are scalable and robust. In case the environment (the size of the ring) or the number of agents changes during the run, the swarm adapts and re-deploys without requiring any outside interference.

Many combinatorial real-world problems are mostly dynamic. They are dynamic in the sense that the global optimum location and its value change over the time, in contrast to static problems. The task of the optimization algorithm is to track this shifting optimum. Particle Swarm Optimization (PSO) has been previously used to solve continuous dynamic optimization problems, whereas only a few works have been proposed for combinatorial ones. One of the most interesting dynamic problems is the Dynamic Vehicle Routing Problem (DVRP). This paper presents a Multi-Adaptive Particle Swarm Optimization (MAPSO) for solving the Vehicle Routing Problem with Dynamic Requests (VRPDR). In this approach the population of particles is split into a set of interacting swarms. Such a multi-swarm helps to maintain population diversity and good tracking is achieved. The effectiveness of this approach is tested on a well-known set of benchmarks, and compared to other metaheuristics from literature. The experimental results show that our multi-swarm optimizer significantly outperforms single solution and population based metaheuristics on this problem.

Stochastic local search algorithms require finding an appropriate setting of their parameters in order to reach high performance. The parameter tuning approaches that have been proposed in the literature for this task can be classified into two families:

on-line

and

off-line

tuning. In this paper, we compare the results we achieved with these two approaches. In particular, we report the results of an experimental study based on a prominent ant colony optimization algorithm,

$\mathcal{MAX}$

–

$\mathcal{MIN}$

Ant System, for the traveling salesman problem. We observe the performance of on-line parameter tuning for different parameter adaptation schemes and for different numbers of parameters to be tuned. Our results indicate that, under the experimental conditions chosen here, off-line tuned parameter settings are preferable.

In this paper, we study how an opinion dynamics model can be the core of a collective decision-making mechanism for swarm robotics. Our main result is that when opinions represent action choices, the opinion associated with the action that is the fastest to execute spreads in the population. Moreover, the spread of the best choice happens even when only a minority is initially advocating for it. The key elements involved in this process are consensus building and positive feedback. A foraging task that involves collective transport is used to illustrate the potential of the proposed approach.

Honeybees coordinate foraging efforts across vast areas through a complex system of advertising and recruitment. One mechanism for coordination is the waggle dance, a movement pattern which carries positional information about food sources. However, recent evidence suggests that recruited foragers may not use the dance’s positional information to the degree that has traditionally been believed. We model bee colony foraging to investigate the value of sharing food source position information in different environments. We find that in several environments, relying solely on private information about previously encountered food sources is more efficient than sharing information. Relying on private information leads to a greater diversity of forage sites and can decrease over-harvesting of sources. This is beneficial in environments with small quantities of nectar per flower, but may be detrimental in nectar-rich environments. Efficiency depends on both the environment and a balance between exploiting high-quality food sources and oversubscribing them.

Population members of the classical PSO quickly converge onto a smaller region of the objective function landscape, which helps to refine the discovered optimum, but the searching ability of the algorithm collapses. This paper proposes modification to the way information flows between the global best particle and the rest of the particles to resist particles clustering. Particles are ranked according to their fitness value such that each rank is single particle and a particle learns only from the particle one rank above. Global best particle learns only from its own experience. The proposed version of PSO is named as RPSO and experiments on test bed functions show not only RPSO particles resisted clustering but stability has also been observed in RPSO results. The downside of RPSO was its slow rate of convergence, which was improved by nominating certain particles from the whole population as diggers with learning topology of the classical PSO. This version was named RPSO-D and experiments were conducted to show its superiority over the classical PSO, both in terms of stability and rate of convergence.

In this work, we propose a method for self-organized adaptive task partitioning in a swarm of robots. Task partitioning refers to the decomposition of a task into less complex subtasks, which can then be tackled separately. Task partitioning can be observed in many species of social animals, where it provides several benefits for the group. Self-organized task partitioning in artificial swarm systems is currently not widely studied, although it has clear advantages in large groups. We propose a fully decentralized adaptive method that allows a swarm of robots to autonomously decide whether to partition a task into two sequential subtasks or not. The method is tested on a simulated foraging problem. We study the method’s performance in two different environments. In one environment the performance of the system is optimal when the foraging task is partitioned, in the other case when it is not. We show that by employing the method proposed in this paper, a swarm of autonomous robots can reach optimal performance in both environments.

Many biological systems are composed of unreliable components which self-organize efficiently into systems that can tackle complex problems. One such example is the true slime mold

Physarum polycephalum

which is an amoeba-like organism that seeks food sources and efficiently distributes nutrients throughout its cell body. The distribution of nutrients is accomplished by a self-assembled resource distribution network of small tubes with varying diameter which can evolve with changing environmental conditions without any global control. In this paper, we use a phenomenological model for the tube evolution in slime mold and map it to a path formation protocol for wireless sensor networks. By selecting certain evolution parameters in the protocol, the network may evolve toward single paths connecting data sources to a data sink. In other parameter regimes, the protocol may evolve toward multiple redundant paths. We present detailed analysis of a small model network. A thorough understanding of the simple network leads to design insights into appropriate parameter selection. We also validate the design via simulation of large-scale realistic wireless sensor networks using the QualNet network simulator.

In this paper, we have proposed two novel algorithms based on Ant Colony Optimization (ACO) for finding near-optimal solutions for the Multi-dimensional Multi-choice Knapsack Problem (MMKP). MMKP is a discrete optimization problem, which is a variant of the classical 0-1 Knapsack Problem and is also an NP-hard problem. Due to its high computational complexity, exact solutions of MMKP are not suitable for most real-time decision-making applications e.g. QoS and Admission Control for Adaptive Multimedia Systems, Service Level Agreement (SLA) etc. Although ACO algorithms are known to have scalability and slow convergence issues, here we have augmented the traditional ACO algorithm with a unique random local search, which not only produces near-optimal solutions but also greatly enhances convergence speed. A comparative analysis with other state-of-the-art heuristic algorithms based on public MMKP dataset shows that, in all cases our approaches outperform others. We have also shown that our algorithms find near optimal (within 3% of the optimal value) solutions within milliseconds, which makes our approach very attractive for large scale real time systems.

Ant colony optimization (ACO) has been widely used for different combinatorial optimization problems. In this paper, we investigate ACO algorithms with respect to their runtime behavior for the traveling salesperson (TSP) problem. We present a new construction graph and show that it has a stronger local property than the given input graph which is often used for constructing solutions. Later on, we investigate ACO algorithms for both construction graphs on random instances and show that they achieve a good approximation in expected polynomial time.

In this paper, a Cooperative Network Game (CNG) is introduced. In this game, all players have the same goal: display a video content in real time, with no cuts and low buffering time. Inspired in cooperation and symmetry, all players should apply the same strategy, resulting in a fair play. For each strategy we shall define a score, and the search of the best one characterizes a Combinatorial Optimization Problem (COP). In this research we show that this search can be translated into a suitable Assymmetric Traveling Salesman Problem (ATSP). An Ant Colony Optimization (ACO) approach is defined, obtaining highly competitive solutions for the CNG. Finally, we play the game in a real context, using a new strategy in a Peer-to-Peer (P2P) platform, obtaining better results than previous strategies.

Ant algorithms are usually derived from a stochastic modeling based on some specific probability laws. We consider in this paper a full deterministic model of “logistic ants” which uses chaotic maps to govern the behavior of the artificial ants. We illustrate and test this approach on a TSP instance, and compare the results with the original Ant System algorithm. This change of paradigm —deterministic versus stochastic— implies a novel view of the internal mechanisms involved during the searching and optimizing process of ants.

In many experimental setting, we are concerned with finding the optimal experimental design,

i.e.

the configuration of predictive variables corresponding to an optimal value of the response. However, the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function. In this paper, we investigate the combination of statistical modeling and optimization algorithms to better explore the combinatorial search space and increase the performance of classical approaches. To this end, we propose a Model based Ant Colony Design (MACD) based on statistical modelling and Ant Colony Optimization. We apply the novel technique to a simulative case study related to Synthetic Biology.

We introduce ACOPHY, a novel framework to apply Ant Colony Optimization (ACO) for phylogenetic reconstruction. ACOPHY overcomes a main drawback of other attempts to reconstruct phylogenies by defining a compact ACO graph that is nicely coupled with the tree space. The proposed graph allows the ants to walk globally through the tree space. Thus, ACOPHY can be generally applied to all well-known optimality criteria in phylogenetics. We compared ACOPHY with the traditional phylogenetic method PHYLIP and obtained slightly better results. This is promising since our current implementation of ACOPHY is still at the proof of concept stage. We list a number of points where ACOPHY can be improved. Once the improvements are integrated, we hope for competitive performance against other recent phylogenetic inference methods.

An Ant Colony System (ACS) looking for cocyclic Hadamard matrices over dihedral groups

D

4

t

is described. The underlying weighted graph consists of the rooted trees described in [1], whose vertices are certain subsets of coboundaries. A branch of these trees defines a

D

4

t

-Hadamard matrix if and only if two conditions hold: (i)

I

i

 = 

i

 − 1 and, (ii)

c

i

 = 

t

, for every 2 ≤ 

i

 ≤ 

t

, where

I

i

and

c

i

denote the number of

i

-paths and

i

-intersections (see [3] for details) related to the coboundaries defining the branch. The pheromone and heuristic values of our ACS are defined in such a way that condition (i) is always satisfied, and condition (ii) is closely to be satisfied.

Semi-supervised classification methods make use of the large amounts of relatively inexpensive available unlabeled data along with the small amount of labeled data to improve the accuracy of the classification. This article presents a novel ‘self-training’ based semi-supervised classification algorithm using the property of aggregation pheromone found in natural behavior of real ants. The proposed algorithm is evaluated with real life benchmark data sets in terms of classification accuracy. Also the method is compared with two conventional supervised classification methods and two recent semi-supervised classification techniques. Experimental results show the potentiality of the proposed algorithm.

Retail is traditionally labour-intensive. Demand-oriented workforce management has great significance due to the amount of competition which enforces a strict cost management while keeping a good service level. Thus, highly flexible working time models are of particular importance. Our project addresses the question how to automatically and simultaneously assign staff to workstations and generate optimised working time models under constraints and on the basis of fluctuating personnel demand. The planning is completed for an entire year in order to assess adapted versions of the evolution strategy and particle swarm optimisation. A commercial constructive method is used as benchmark.

In next generation ad hoc networks, MANETs and WSNs will cohesively integrate to provide a unified ad hoc framework. Such a hybrid network – due to conflicting operational environments – presents unique challenges for routing protocols. A recently proposed BeeSensor protocol inherits relevant features from BeeAdHoc – a bee-inspired protocol for mobile ad hoc networks. In this paper, we would first do requirements engineering of protocols for hybrid networks and then enhance BeeSensor with relevant features to make it suitable for MANETs and WSNs. Finally, we implement enhanced BeeSensor in famous ns-2 simulator and compare its performance with well known MANET protocols namely DSR, AODV and DSDV. The results of our experiments show that BeeSensor – using our mobility model – delivers similar or better performance compared with its competitors in low mobility scenarios. But its performance relatively degrades in high mobility scenarios. Towards the end of the paper, we propose changes that can overcome these shortcomings.

We consider a heterogeneous swarm robotic system composed of wheeled and aerial robots called foot-bots and eye-bots, respectively. The foot-bots are able to physically connect to one another autonomously and thus form collective robotic entities. Eye-bots have a privileged overview of the environment since they can fly and attach to metal ceilings. In this paper, we show how the heterogeneous swarm can benefit from cooperation. By using so-called

spatially targeted communication

, the eye-bot is able to communicate with selected groups of foot-bots and instruct them on how to overcome obstacles in their path by forming morphologies appropriate to the obstacle encountered. We conduct experiments in simulation to quantify separately the benefits of cooperation and of spatially targeted communication.

The development of artificial devices (

nanobots

), working as blood white cells but addressed to the recognition and eventually the destruction of endogenous pathological states, is an ambitious goal. Swarm intelligence can be a key element to successfully tackle the challenges posed by this goal. Here we describe an applicative scenario, based on swarm of nanobots, by sketching the environment in which the nanobots operate, the constraints related to their physical implementation, and the tasks they have to tackle. In this scenario, we propose to use collisions between nanorobots as a way of communication inside the swarm.

Estimation of Distribution Algorithms (EDAs) is an evolutionary computation optimization paradigm that relies the evolution of each generation on calculating a probabilistic graphical model able to reflect dependencies among variables out of the selected individuals of the population. This showed to be able to improve results with GAs for complex problems.

This paper presents a new hybrid approach combining EDAs and particle swarm optimization, with the aim to take advantage of EDAs capability to learn from the dependencies between variables while profiting particle swarm’s optimization ability to keep a sense of ”direction” towards the most promising areas of the search space. Experimental results show the validity of this approach with widely known combinatorial optimization problems.

This article analyses a flocking algorithm that was developed specifically for small and simple swarm robots. It is similar to traditional flocking algorithms for swarm robots, however it does not need communication nor global information. Its only requirements are at least 4 circumferential distance sensors which can have very limited range. This is possible because our algorithm generates

emergent

alignment of flock members. We show an analysis of our simulations and a short overview of a real robot experiment.

We describe a theory from Herbert Simon that links the structure of complex systems to increased speed of evolution, and argue the position that this theory can be beneficial to evolutionary swarm robotic research. We propose a way of applying this theory to evolutionary swarm robotic systems by manually designing the robot to robot communication mechanisms and keeping these constant, whilst evolving the rest of the robots’ behaviours. This allows for robots to evolve independently of each other without breaking any inter-dependencies that may exist between robots in the swarm. Finally we address potential criticisms of our suggested approach, and outline a course of future research in this area in order to verify our proposal.

Robot swarms provide a way for a number of simple robots to work together to carry out a task. While swarms have been found to be adaptable, fault-tolerant and widely applicable, designing individual robot algorithms so as to ensure effective and correct swarm behaviour is very difficult. In order to assess swarm effectiveness, either experiments with real robots or computational simulations of the swarm are usually carried out. However, neither of these involve a deep analysis of

all

possible behaviours. In this paper we will utilise automated

formal verification

techniques, involving an exhaustive mathematical analysis, in order to assess whether our swarms will indeed behave as required.

Algorithms derived by mimicking the nature are extremely useful for solving many real world problems in different engineering disciplines. Particle swarm optimization (PSO) especially has been greatly acknowledged for its simplicity and efficiency in obtaining good solutions for complex problems. However, premature convergence of the standard PSO and many of its variants is a downside particularly for its application to the inverse problems. This aspect encourages further research in developing efficient algorithms for such problems. In this work, a novel PSO algorithm is proposed by introducing fitness of a new location in the search space into the standard PSO which enables to enhance the success rate of the algorithm. The proposed algorithm uses center of mass of the population to compare the fitness of global best particle in each iteration. The proposed algorithm is applied to solve contaminant transport inverse problem. The performance of different PSO algorithms is compared on synthetic test data and it is shown that the proposed algorithm outperforms its counterparts. Further, accurate design parameters are estimated using the proposed inverse model from the experimental data.

We study self-organized navigation in a heterogeneous robotic swarm consisting of two types of robots: small wheeled robots, called foot-bots, and flying robots that can attach to the ceiling, called eye-bots. The task of foot-bots is to navigate back and forth between a source and a target location. The eye-bots are placed in a chain on the ceiling, connecting source and target using infrared communication. Their task is to guide foot-bots, by giving local directional instructions. The problem we address is how the positions of eye-bots and the directional instructions they give can be adapted, so that they indicate a path that is efficient for foot-bot navigation, also in the presence of obstacles. We propose an approach of mutual adaptation between foot-bots and eye-bots. Our solution is inspired by pheromone based navigation of ants, as eye-bots serve as mobile stigmergic markers for foot-bot navigation.

A challenging problem in molecular biology is the identification of the specific binding sites of transcription factors in the promoter regions of genes referred to as motifs. This paper presents an Ant Colony Optimization approach that can be used to provide the motif finding problem with promising solutions. The proposed approach incorporates a modified form of the Gibbs sampling technique as a local heuristic optimization search step. Further, it searches both in the space of starting positions as well as in the space of motif patterns so that it has more chances to discover potential motifs. The approach has been implemented and tested on some datasets including the Escherichia coli CRP protein dataset. Its performance was compared with other recent proposed algorithms for finding motifs such as MEME, MotifSampler, BioProspector, and in particular Genetic Algorithms. Experimental results show that our approach could achieve comparable or better performance in terms of motif accuracy within a reasonable computational time.

A system based on the adaptation of the search principle used in ant colony optimization (ACO) for multiobjective graph-based data mining (GBDM) is introduced in this paper. Our multiobjective ACO algorithm is designed to retrieve the best substructures in a graph database by jointly considering two criteria, support and complexity. The experimental comparison performed with a classical GBDM method shows the good performance of the new proposal on three datasets.

This paper introduces opportunistic ant-based path management for wireless mesh networks. The idea is to take advantage of the broadcast nature of the wireless medium by deferring the selection of the next-hop to the receivers of an ant. From an Ant Colony Optimization (ACO) viewpoint, the main shift is that the probabilistic forwarding decision rule is no longer executed locally at the transmitting node and in the spatial domain, but in a distributed manner among the potential forwarders and in the time domain. Early simulation results indicate that this approach improves the performance of the system in terms of convergence time, ability to adapt to changes and overhead.

This paper proposes parallelization methods of ACO algorithms on a computing platform with a multi-core processor aiming at fast execution to find acceptable solutions. As an ACO algorithm, we use the cunning Ant System and test on several sizes of TSP instances. As the parallelization method, we use agent level parallelization in one colony using Java thread programming. According to the synchronization and exclusive control modes among threads, we propose three types of parallel ACO algorithms. Among them, that which we call the rough asynchronous parallel model shows the most promising results.

Global optimization methods including Particle Swarm Optimization are usually used to solve optimization problems when the number of parameters is small (hundreds). In the case of inverse problems the objective (or fitness) function used for sampling requires the solution of multiple forward solves. In inverse problems, both a large number of parameters, and very costly forward evaluations hamper the use of global algorithms. In this paper we address the first problem, showing that the sampling can be performed in a reduced model space. We show the application of this idea to a history matching problem of a synthetic oil reservoir. The reduction of the dimension is accomplished in this case by Principal Component analysis on a set of scenarios that are built based on prior information using stochastic simulation techniques. The use of a reduced base helps to regularize the inverse problem and to find a set of equivalent models that fit the data within a prescribed tolerance, allowing uncertainty analysis around the minimum misfit solution. This methodology can be used with other global optimization algorithms. PSO has been chosen because its shows very interesting exploration/exploitation capabilities.

The use of technical indicators to derive stock trading signals is a foundation of financial technical analysis. Many of these indicators have several parameters which creates a difficult optimization problem given the highly non-linear and non-stationary nature of a financial time-series. This study investigates a popular financial indicator, Bollinger Bands, and the fine tuning of its parameters via particle swarm optimization under 4 different fitness functions: profitability, Sharpe ratio, Sortino ratio and accuracy. The experiment results show that the parameters optimized through PSO using the profitability fitness function produced superior out-of-sample trading results which includes transaction costs when compared to the default parameters.

The protein structure prediction problem consists in finding good computational algorithms for prediction of protein native states. This paper applies the Particle Swarm Optimization (PSO) algorithm to predict the tertiary structure of proteins in lattice models. We propose a novel discrete PSO variant designed for lattice-based protein folding models. We present three lattice based models and two folding encodings, which are tested in different combinations on six proteins. The results indicate that the new algorithm performs very efficient and finds very good proteins conformations.

We consider the problem of finding and maintaining communication paths in wireless mobile ad hoc networks (MANET). We consider this problem as a bi-objective problem when trying to minimize both the length of the constructed paths and the number link reconnections. We propose two centralized algorithms that help analyse the problem from a dynamic graph point of view. These algorithms give lower bounds for our proposed decentralized ant-based algorithm that constructs and maintains such paths in a MANET.

Ant Colony Optimization (ACO) differs substantially from other meta-heuristics such as Evolutionary Algorithms (EA). Two of its distinctive features are: (i) it is constructive rather than based on iterative improvements, and (ii) it employs problem knowledge in the construction process via the heuristic function, which is essential for its success. In this paper, we introduce the

ACO encoding

, which is a

self-contained algorithmic component

that can be readily used to make available these two particular features of ACO to

any

search algorithm for continuous spaces based on iterative improvements to solve combinatorial optimization problems.

In this paper we discuss the task of efficiently using ant-like robotic agents for covering a connected region on the

$\mbox{\bf Z}^{2}$

grid, whose shape and size are unknown in advance, and which expands at a given rate. This is done using myopic robots, with no ability to directly communicate with each other, where each robot is equipped with only

O

(1) memory. We show that regardless of the algorithm used, and the robots’ hardware and software specifications, the minimal number of robots required in order to enable such coverage is

$\Omega({\sqrt{n}})$

(where

n

is the initial size of the connected region). In addition, we show that when the region expands at a sufficiently slow rate, a team of

$\Theta(\sqrt{n})$

robots could cover it in at most

O

(

n

2

ln

n

) time. Regarding the coverage of non-expanding regions in the grid, we improve the current best known result of

O

(

n

2

) by demonstrating an algorithm of worse case completion time of

$O(\frac{1}{k} n^{1.5} + n)$

, and faster for shapes of perimeter length which is shorter than

O

(

n

).

This paper presents the synthesis of an active control system using a modified particle swarm optimization method. The system’s controller design is analyzed as a minimalization of the building stories’ acceleration. The proposed fitness function is computationally efficient and incorporates the constraints on the system’s stability and the maximum output of actuators. In order to handle the constraints the PSO was modified to take into account the particles’ distance to the best and the worst solutions. The performance of the obtained controller was tested using historical earthquake records. The performed numerical simulations proved that the designed controller is capable of efficient vibrations reduction.

Ant Colony Extended (ACE) is a new framework that allows to apply the ant colony paradigm [1] to solve combinatorial optimization problems, in which the values of each variable are taken from a finite set, and the set of possible solutions is

countably infinite

.

Previously, we applied ACE to autonomous ship manoeuvre planning [2], where the objective was to minimize the time of a manoeuvre. In this problem, as in the TSP and others, the value of the cost function increases monotonically as new elements are added to the solution sequence. We want to check the algorithm for problems that do not exhibit this feature. For this purpose we select a set of multi-modal functions to minimize with ACE: Griewank’s function (F2), Shekel’s foxholes (F3), Michalewicz’ function (F4) and Langerman’s function (F5). All functions are taken from [4].

These functions have many local minima, where algorithms may get stuck.We select the Simple Genetic Algorithm (SGA), and Differential Evolution (DE) to perform a comparison of local minima avoidance.

Metaheuristics in stochastic local search are used in numerical optimization problems in high-dimensional spaces. A characteristic of these metaheuristics is the configuration of the parameters. These parameters are essential for the optimization behavior but depend on the objective function. In this paper we introduce a new approach to automatic parameter configuration of Particle Swarm Optimization (PSO) by classifying features of the objective function. This classification utilizes a decision tree that is trained by 32 different function features. These features result from the characteristics of the underlying function landscape and of the PSO behavior. An efficient set of parameters influences the optimization in speed and performance. In literature standard configurations are introduced for different types of metaheuristics which perform a not optimal but an adequate optimization behavior for most objective functions. PSO is an example for the parameter configuration problem [2]. The swarm behavior depends mainly on the chosen parameter and leads to solutions of different quality, i.e. bad parameter sets can lead to a disadvantageous balance between exploitation and exploration. One problem by choosing the right parameter without knowledge about the objective function is to describe the characteristics of the function which are comparable to another function.

Formation control is an important research topic in swarm robotics, as it enables each swarm robot to concentrate on its task by relying on others [1,2]. This paper is a brief summary of our endeavor for constructing low-cost swarm robots that march in column formation [4].

n

= 5 swarm robots move in file, except the leading one each follows another one and all of them avoid perimeters of an indoor arena. We describe detailed settings of the control program for further studies. Our work focuses on real robots and is thus considered to be complementary to theoretical and simulation studies, cf. [3].

In swarm robotics, the agents are often assumed to be identical. In this abstract, we argue that the cooperation between swarms of different kinds of robots can enhance the capabilities of the robotic system—heterogeneous swarms marry the robustness and parallelism of homogeneous swarms with efficient task specialisation. A key issue in heterogeneous swarm systems is the potential complexity of facilitating cooperation between the different robot types.

The vector-based PSO (VBPSO) [3,4,5] was developed to locate multiple solutions to multi-modal optimization problems. Three versions of the VBPSO were published, and shown to be very efficient in locating mutliple optima. This is despite the fact that the VBPSO algorithms initialize particles using standard pseudo random number generators. The main objective of this article is to show that the perfomance of the VBPSO algorithms can be improved by initializing particles using Sobol sequences [1,2].

This paper introduces three strategies to deploy a swarm of robots in unknown environments for a search task, aiming to reduce the total swarm energy cost with rapid operation for applications such as disaster mitigation. We are motivated by current research on flying robot swarms [10].

In REPLICATOR [2] powerful reconfigurable robots are designed and constructed. Reconfigurable robots can dock together and form robot organisms. Robot organisms have the ability to morph from snakes into spiders, chairs, swarms, wheels. The problem we are facing is:

How to evolve self-organized robot metamorphosis

? The metamorphosis graph

A

 = {

S

,

T

} is a tuple of

S

, the set of all possible robot module configurations, and

T

the set of all transitions between those configurations. A configuration

s

 ∈ 

S

,

s

 = {

R

,

D

} consists out of

R

robots with

D

connections. If

D

 = ⊘,

s

denotes a swarm. A fitness function

f

for reciprocal metamorphosis defines a maximum for a specific cycle in

A

. A metamorphic fitness function is used that defines maximum fitness for a dynamic body form called a

glider

: a snake growing its head, and losing its tail

a

g

 ∈ 

A

. The evolutionary search process needs to find a self-organized solution for a glider in

A

.

Many processes from chemical industries generate wastewater discharges with acidic or alkaline character.These type of discharges often need a neutralization process before their incorporation into the receiving media. This process is complex: it presents many difficulties due to the none-linear response of pH value to the addition of acids or bases. Moreover, it requires considering the variable buffering capacity of system and the changes in loading characteristics [1,2]. The mixture of wastewater discharges usually has an unknown value of buffer capacity and its pH value can not be calculated easily.

The paper presents a hybrid metaheuristic method ACO-H [4] for combinatorial optimization problems that combines two population-based approaches – ant colony optimization (ACO) and

H

-method. ACO is a multi-agent metaheuristic that has been successfully applied to many difficult optimization problems [1].

H

-method is an extension of the discrete downhill simplex method [6] that applies during the search process specially defined segments. Similar to

H

-method ideas were introduced in the context of tabu search and now are known as path relinking [2].

Social organisms form a swarm and forage preys, collectively and effectively [1]. The swarm has to inhibit a variance of foraging frequency for survival, which ensures stable and predictable income. In the previous study, we focused on ”trail pheromone” system which enables robots to communicate one another [2]. In the present study, we analysed statistically the variance of the foraging behaviour of the robot swarm, using repeated (48 trials) computer simulation.We set the individual density as the parameter. The density in Figures, X axis means the number of individuals on the unit field(180 × 180 [cm]). In the simulation, we set 360 × 360[cm] as the field size. When the individual density is low, the variance of the foraging behaviour is larger than expected from the random behaviour(i.e., binomial distribution; Fig. 1). Horizontal lines in Fig. 1 mean expected one from the binomial distribution. As the density goes high, the variance is reduced toward the expected value.

In collective transport, a group of robots has to cooperate in order to transport an object. Collective transport is necessary when transporting the object is hard or impossible for a single robot. The task is particularly difficult when communication bandwidth is limited, there is no access to global information or when using a decentralized approach. In these cases, an effective distributed coordination among the robots is necessary.

This paper reports on a conjecture concerning the statistical behavior of Self- Chord [1], a self-organizing P2P system in which the resource keys are dynamically sorted with an ant algorithm. In Self-Chord (http://self-chord.icar.cnr.it), peers are organized in a logical ring, as in Chord, and a hash function is used to assign an index to every peer, and an access key to every resource. Contrary to Chord though, the values of resource keys are decoupled from those of peer indexes, and are dynamically sorted by ant-inspired agents through statistical

pick

and

drop

operations. This allows Self-Chord to keep the Chord capacity for serving discovery requests in logarithmic time, but leads to many further advantages, among which the possibility of assigning a semantic meaning to keys, a better load balancing among peers, and the efficient execution of range queries.

Soft variable fixing has emerged as one of the main techniques that the area of

matheuristics

can contribute to general metaheuristics. Recent years have in fact witnessed a fruitful interplay of methods that were originally proposed as general metaheuristcs with methods rooted in mathematic programming, which can be applied alone or as hybrids for solving combinatorial optimization problems. In this work, we show how one of the most effective matheuristics techniques, namely soft variable fixing, can be hybridized with Ant Colony Optimization. Specifically, we will combine a standard ACO code with a path relinking operator, implemented by means of soft variable fixing.

The basic particle swarm algorithm was described by Kennedy and Eberhart [4]. In this paper a modified method with time varying inertia coefficient [3] was used where the inertia coefficient

w

goes linearly from

w

start

to

w

end

.