Ant Colony Optimization and Swarm Intelligence

In this paper we present a study of several Ant Colony Optimization (ACO) algorithms for the Set Covering Problem. In our computational study we emphasize the influence of different ways of defining the heuristic information on the performance of the ACO algorithms. Finally, we show that the best performing ACO algorithms we implemented, when combined with a fine-tuned local search procedure, reach excellent performance on a set of well known benchmark instances.

The basic tasks in Digital Signal Processing systems can be expressed as summation of products. In this paper such operation is analyzed in terms of parallel distributed computation starting from an improvement of the Modified Booth Algorithm able to avoid useless sub-operation in the process of multiplication. We show how a such reformulation can take advantages from the cooperation between cells of a small colony statistically achieving shorter computation time. The interaction among cells, based on simple social rules typical of Swarm Intelligence systems, leads to a full exploitation of cells computational capabilities obtaining a more efficient usage of their computational resources in a so important task. In this paper a preliminary VLSI implementation and theoretical results are presented to show the feasibility of this approach.

This paper presents how the Ant Colony Optimization (ACO) metaheuristic can be extended to continuous search domains and applied to both continuous and mixed discrete-continuous optimization problems. The paper describes the general underlying idea, enumerates some possible design choices, presents a first implementation, and provides some preliminary results obtained on well-known benchmark problems. The proposed method is compared to other ant, as well as non-ant methods for continuous optimization.

Designing an optimal overlay communication network for a set of processes on the Internet is a central problem of peer-to-peer (P2P) computing. Such a network defines membership and allows for members to disseminate information within the group. The network has to be robust and the available bandwidth has to be utilized in an optimal manner to allow for maximally efficient communication. This problem can be formulated as a dynamic optimization problem where classical combinatorial optimization techniques must face the further challenge of time-varying input data. ACO systems appear to be particularly fit for this class of problems, being able to construct an internal model of the instance to face and to exploit it for fast adaptation to modified contexts.This paper proposes to use elements resulting from mathematical techniques, in this case Lagrangean relaxation, in an ACO framework in order to achieve sound hot start states for fast response to varying network structures.

In this paper we consider the application of an Ant Colony Optimisation (ACO) metaheuristic on the Set Packing Problem (SPP) which is a NP-hard optimisation problem. For the proposed algorithm, two solution construction strategies based on exploration and exploitation of solution space are designed. The main difference between both strategies concerns the use of pheromones during the solution construction. The selection of one strategy is driven automatically by the search process. A territory disturbance strategy is integrated in the algorithm and is triggered when the convergence of the ACO stagnates. A set of randomly generated numerical instances, involving from 100 to 1000 variables and 100 to 5000 constraints, was used to perform computational experiments. To the best of our knowledge, only one other metaheuristic (Greedy Randomized Adaptative Search Procedure, GRASP) has been previously applied to the SPP. Consequently, we report and discuss the effectiveness of ACO when compared to the best known solutions and including those provided by GRASP. Optimal solutions obtained with Cplex on the smaller instances (up to 200 variables) are indicated with the calculation times. These experiments show that our ACO heuristic outperforms the GRASP heuristic. It is remarkable that the ACO heuristic is made up of simple search techniques whilst the considered GRASP heuristic is more evolved.

The difficulty to solve multiple objective combinatorial optimization problems with traditional techniques has urged researchers to look for alternative, better performing approaches for them. Recently, several algorithms have been proposed which are based on the Ant Colony Optimization metaheuristic. In this contribution, the existing algorithms of this kind are reviewed and experimentally tested in several instances of the bi-objective traveling salesman problem, comparing their performance with that of two well-known multi-objective genetic algorithms.

An ant colony optimization algorithm using a library of partial solutions for knowledge incorporation from previous iterations is introduced. Initially, classical ant colony optimization algorithm runs for a small number of iterations and the library of partial solutions is initialized. In this library, variable size solution segments from a number of elite solutions are stored and each segment is associated with its parent’s objective function value. There is no particular distribution of ants in the problem space and the starting point for an ant is the initial point of the segment it starts with. In order to construct a solution, a particular ant retrieves a segment from the library based on its goodness and completes the rest of the solution. Constructed solutions are also used to update the memory. The proposed approach is used for the solution of TSP and QAP for which the obtained results demonstrate that both the speed and solution quality are improved compared to conventional ACO algorithms.

Bees organize their foraging activities as a social and communicative effort, indicating both the direction, distance and quality of food sources to their fellow foragers through a ”dance” inside the bee hive (on the ”dance floor”). In this paper we present a novel routing algorithm, BeeHive, which has been inspired by the communicative and evaluative methods and procedures of honey bees. In this algorithm, bee agents travel through network regions called foraging zones. On their way their information on the network state is delivered for updating the local routing tables. BeeHive is fault tolerant, scalable, and relies completely on local, or regional, information, respectively. We demonstrate through extensive simulations that BeeHive achieves a similar or better performance compared to state-of-the-art algorithms.

Pheromone information is used in Ant Colony Optimization (ACO) to guide the search process and to transfer knowledge from one iteration of the optimization algorithm to the next. Typically, in ACO all decisions that lead an ant to a good solution are considered as of equal importance and receive the same amount of pheromone from this ant (assuming the ant is allowed to update the pheromone information). In this paper we show that the decisions of an ant are usually made under situations with different strength of competition. Thus, the decisions of an ant do not have the same value for the optimization process and strong pheromone update should be prevented when competition is weak. We propose a measure for the strength of competition that is based on Kullback-Leibler distances. This measure is used to control the update of the pheromone information so that solutions components that correspond to decisions that were made under stronger competition receive more pheromone. We call this update procedure competition controlled pheromone update. The potential usefulness of competition controlled pheromone update is shown first on simple test problems for a deterministic model of ACO. Then we show how the new update method can be applied for ACO algorithms.

This paper addresses the design of control policies for groups of up to 16 simple autonomous mobile robots (called s-bots) for the cooperative transport of heavy objects of different shapes and sizes. The s-bots are capable of establishing physical connections with each other and with the object (called prey). We want the s-bots to self-assemble into structures which pull or push the prey towards a target location.The s-bots are controlled by neural networks that are shaped by artificial evolution. The evolved controllers perform quite well, independently of the shape and size of the prey, and allow the group to transport the prey towards a moving target. Additionally, the controllers evolved for a relatively small group can be applied to larger groups, making possible the transport of heavier prey. Experiments are carried out using a physics simulator, which provides a realistic simulation of real robots, which are currently under construction.

The search process of a metaheuristic is sometimes misled. This may be caused by features of the tackled problem instance, by features of the algorithm, or by the chosen solution representation. In the field of evolutionary computation, the first case is called deception and the second case is referred to as bias. In this work we formalize the notions of deception and bias for ant colony optimization. We formally define first order deception in ant colony optimization, which corresponds to deception as being described in evolutionary computation. Furthermore, we formally define second order deception in ant colony optimization, which corresponds to the bias introduced by components of the algorithm in evolutionary computation. We show by means of an example that second order deception is a potential problem in ant colony optimization algorithms.

Communication is often required for coordination of collective behaviours. Social insects like ants, termites or bees make use of different forms of communication, which can be roughly classified in three classes: indirect (stigmergic) communication, direct interaction and direct communication. The use of stigmergic communication is predominant in social insects (e.g., the pheromone trails in ants), but also direct interactions (e.g., antennation in ants) and direct communication can be observed (e.g., the waggle dance of honey bee workers). Direct communication may be beneficial when a fast reaction is expected, as for instance, when a danger is detected and countermeasures must be taken. This is the case of hole avoidance, the task studied in this paper: a group of self-assembled robots – called swarm-bot – coordinately explores an arena containing holes, avoiding to fall into them. In particular, we study the use of direct communication in order to achieve a reaction to the detection of a hole faster than with the sole use of direct interactions through physical links. We rely on artificial evolution for the synthesis of neural network controllers, showing that evolving behaviours that make use of direct communication is more effective than exploiting direct interactions only.

We consider a swarm of simple ant-robots (or a(ge)nts) on the plane, which are anonymous, homogeneous, memoryless and lack communication capabilities. Their sensors are range-limited and they are unable to measure distances. Rather, they can only acquire the directions to their neighbors. We propose a simple algorithm, which makes them gather in a small region or a point. We discuss three variants of the problem: A continuous-space discrete-time problem, a continuous-time limit of that problem, and a discrete-space discrete-time analog. Using both analysis and simulations, we show that, interestingly, the system’s global behavior in the continuous-time limit is fundamentally different from that of the discrete-time case, due to hidden “Zenoness” in it.

Ad-hoc wireless sensor networks have been an active research topic for the last several years. Sensor networks are distinguished from traditional networks by characteristics such as deeply embedded routers, highly dynamic networks, resource-constrained nodes, and unreliable and asymmetric links. Ant routing has shown good performance for communication networks; in this paper, we show why the existing ant-routing algorithms do not work well for sensor networks. Three new ant-routing algorithms are proposed and performance evaluations for these algorithms on a real application are conducted on a routing simulator for sensor networks.

Ant Colony Optimisation algorithms perform competitively with other meta-heuristics for many types of optimisation problems, but unfortunately their performance does not always degrade gracefully when the problem contains hard constraints. Many industrially relevant problems, such as fleet routing, rostering and timetabling, are typically subject to hard constraints. A complementary technique for solving combinatorial optimisation problems is Constraint Programming (CP). CP techniques are specialized for solving hard constraints, but they may be inefficient as an optimisation method if the feasible space is very large. A hybrid approach combining both techniques therefore holds the hope to combine these complementary advantages. The paper explores how such an integration can be achieved and presents a hybrid search method CPACS derived by embedding CP into ACS. We have tested CPACS on job scheduling problems. Initial benchmark results are encouraging and suggest that CPACS has the biggest advantage over the individual methods for problems of medium tightness, where the constraints cause a highly fragmented but still very large search space.

The building behaviour of termites has previously been modelled mathematically in two dimensions. However, physical and logistic constraints were not taken into account in these models. Here, we develop and test a three-dimensional agent-based model of this process that places realistic constraints on the diffusion of pheromones, the movement of termites, and the integrity of the architecture that they construct. The following scenarios are modelled: the use of a pheromone template in the construction of a simple royal chamber, the effect of wind on this process, and the construction of covered pathways. We consider the role of the third dimension and the effect of logistic constraints on termite behaviour and, reciprocally, the structures that they create. For instance, when agents find it difficult to reach some elevated or exterior areas of the growing structure, building proceeds at a reduced rate in these areas, ultimately influencing the range of termite-buildable architectures.

This paper studies the behavior of ants when moving in an artificial network composed of several interconnected paths linking their nest to a food source. The ant responses when temporarily blocking the access to some branches of the maze were observed in order to study which factors influenced their local decisions about the paths to follow. We present a mathematical model based on experimental observations that simulates the motion of ants through the network. In this model, ants communicate through the deposition of a trail pheromone that attracts other ants. In addition to the trail laying/following process, several other aspects of ant behavior were modeled. The paths selected by ants in the simulations were compared to those selected by ants in the experiments. The results of the model were encouraging, indicating that the same behavioral rules can lead ants to find the shortest paths under different environmental conditions.

In this paper we propose the Multi-type Ant Colony system, which is an extension of the well known Ant System. Unlike the Ant System the ants are of a predefined type. In the Multi-type Ant Colony System ants have the same goal as their fellow types ants, however are in competition with the ants of different types. The collaborative behavior between identical type ants is modeled the same way as in ant systems, i.e. ants are attracted to pheromone of ants of the same type. The competition between different types is obtained because ants are repulsed by the pheromone of ants of other types. This paradigm is interesting for applications where collaboration as well as competition is needed in order to obtain good solutions. In this paper we illustrate the algorithm on the problem of finding disjoint paths in graphs. A first experiment shows on a simple graph two ants types that find successfully two completely disjoint paths. A second experiment shows a more complex graph where the number of required disjoint paths exceeds the number of possible disjoint paths. The results show that the paths found by the ants are distributed proportionally to the cost of the paths. A last experiment shows the influence of the exploration parameter on a complex graph. Good results are obtained if the exploration parameter is gradually decreased.

Few applications of ACO algorithms to multiobjective problems have been presented so far and it is not clear how to design an effective ACO algorithms for such problems. In this article, we study the performance of several ACO variants for the biobjective Quadratic Assignment Problem that are based on two fundamentally different search strategies. The first strategy is based on dominance criteria, while the second one exploits different scalarizations of the objective function vector. Further variants differ in the use of multiple colonies, the use of local search, and the pheromone update strategy. The experimental results indicate that the use of local search procedures and the correlation between objectives play an essential role in the performance of the variants studied in this paper.

Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of ant colonies that has empirically shown its effectiveness in the resolution of hard combinatorial optimization problems like the Traveling Salesman Problem (TSP). Still, very little theory is available to explain the reasons underlying ACO’s success. An ACO alternative called Omicron ACO (OA), first designed as an analytical tool, is presented. This OA is used to explain the reasons of elitist ACO’s success in the TSP, given a globally convex structure of its solution space.

A general-purpose, simulation-based algorithm S-ACO for solving stochastic combinatorial optimization problems by means of the ant colony optimization (ACO) paradigm is investigated. Whereas in a prior publication, theoretical convergence of S-ACO to the globally optimal solution has been demonstrated, the present article is concerned with an experimental study of S-ACO on two stochastic problems of fixed-routes type: First, a pre-test is carried out on the probabilistic traveling salesman problem. Then, more comprehensive tests are performed for a traveling salesman problem with time windows (TSPTW) in the case of stochastic service times. As a yardstick, a stochastic simulated annealing (SSA) algorithm has been implemented for comparison. Both approaches are tested at randomly generated problem instances of different size. It turns out that S-ACO outperforms the SSA approach on the considered test instances. Some conclusions for fine-tuning S-ACO are drawn.

We present a new kind of heuristic guidance as an extension to the Population-based Ant Colony Optimization (P-ACO) implemented in hardware on a Field Programmable Gate Array (FPGA). The heuristic information is obtained by transforming standard heuristic information into small time-scattered heuristic-vectors of favourable ant decisions. This approach is suited for heuristics which allow for an a priori calculation of the heuristics information. Using the proposed method, an ant can build-up a solution in quasi-linear time. Experimental studies measure the performance of the time-scattered heuristic. A comparison with the standard heuristic and candidate lists is also given.

Ad hoc networks consist of mobile nodes that autonomously establish connectivity via multihop wireless communications. Swarm intelligence refers to complex behaviors that emerge from very simple individual behaviors and interactions. In this paper, we describe the ANSI project that adopts swarm intelligence as an adaptive distributed control mechanism to design multicast routing, topology control, and energy conservation protocols for mobile ad hoc networks.

We consider the problem of designing a reliable network defined as follows: Given an undirected graph, the objective of the problem is to find a minimum cost network configuration such that the flow balance equations are satisfied and the network is two-edge connected. The cost function for each edge consists of a fixed component and a variable component, which is proportional to the flow passing through the edge. We present a novel ant colony approach for the solution of the above problem. Computational experience is reported.

To use AntNet-FA globally, the ability of routing algorithms must be clear. The Internet has special topology and a hierarchy (AS and router). The topology have power-laws or scale-free property in other words. In this paper, we focused on the network topology and we applied AntNet algorithm to the network such as the Internet. We examined a node should use either a Loop-Free algorithm or a non-Loop-Free algorithm depending on its degree in heavy traffic condition. The Loop-Free feature means that when an ant decides to visit an adjacent node, then the ant selects the next node from its unvisited node. The non-Loop-Free algorithm is the same to the original AntNet. As a result, we found that network topology affects the ability of AntNet algorithms.

In this paper, a new Ant System approach to the Period Vehicle Routing Problem (PVRP) is presented. In PVRP, visit days have to be assigned to customers in order to find efficient routes over the period. We suggest a new technique for defining the initial solution and a novel strategy to update the pheromone trails that is especially suited for solving large scale problems. An illustrative example for a waste collection system involving 202 localities in the municipality of Viseu, Portugal, demonstrates the effectiveness of the model.

A new method for global minimization of continuous functions has been proposed based on Ant Colony Optimization. In contrast with the previous researches on continuous ant-based methods, the proposed scheme is purely pheromone-based. The algorithm has been applied to several standard test functions and the results are compared with those of two other meta-heuristics. The overall results are compatible, in good agreement and in some cases even better than the two other methods. In addition the proposed algorithm is much simpler, which is mainly due to its simpler structure. Also it has fewer control parameters, which makes the parameter settings process easier than many other methods.

Problems arising on Urban Waste Management are broad and varied. This paper is focused on designing collection routes for urban wastes, a problem existing in most European waste collection systems. The relationship between the real world problem and the Arc Routing literature is established, and the Capacitated Arc Routing Problem is extended to comply with traffic rules. Afterwards, an Ant Algorithm is designed to solve this problem, and its efficiency is tested using the instance sets from the CARP literature and a set of real life instances from the Metropolitan Area of Barcelona. Finally, the integration between the proposed algorithms and a Decision Support System for Urban Waste Management is shown.

In this paper, we describe how we can generate music by simulating moves of artificial ants on a graph where vertices represent notes and edges represent possible transitions between notes. As ants can deposit pheromones on edges, they collectively build a melody which is a sequence of Midi events. Different parameter settings are tested to produce different styles of generated music with several instruments. We also introduce a mechanism that takes into account music files to initialize the pheromone matrix.

In this work, we adopt the concept of backtracking from the Nested Partition (NP) algorithm and apply it to the Max-Min Ant System (MMAS) to solve the Traveling Salesman Problem (TSP). A new type of ants that is called backtracking ants (BA) is used to challenge a subset of the solution feasible space that is expected to have the global optimum solution. The size of this subset is decreased if the BAs find a better solution out of this subset or increased if the BAs fail in their challenge. The BAs don’t have to generate full tours like previous ant systems, which leads to a considerable reduction in the computation effort. A computational experiment is conducted to check the validity of the proposed algorithm.

Complex system simulations can often be represented by an evolving graph which evolves with a one-to-one mapping between vertices and entities and between edges and communications. Performances depend directly on a good load balancing of the entities between available computing devices and on the minimization of the impact of the communications between them. We use competing colonies of numerical ants, each depositing distinctly colored pheromones, to find clusters of highly communicating entities. Ants are attracted by communications and their own colored pheromones, while repulsion interactions between colonies allow to preserve a good distribution.

In case of disaster people want to escape from the dangerous area (a building or an area of a city). Because of changing environment dynamic routing is requested. The main idea is to provide some actors involved in crisis situations with PDAs connected via a wireless network. The PDAs will form a mobile ad-hoc network (MANET). These kinds of networks do not require any existing infrastructure or centralized administration. The challenging tasks in such networks, of dynamically changing collection of wireless mobile nodes, are intelligent routing, bandwidth allocation, and power control techniques. In this paper we introduce a routing algorithm for MANET based on ideas from artificial life (swarm intelligence). We implemented the algorithm and compared its performance with the well-known AntNet.

Various clustering methods based on the behaviour of real ants have been proposed. In this paper, we develop a new algorithm in which the behaviour of the artificial ants is governed by fuzzy IF–THEN rules. Our algorithm is conceptually simple, robust and easy to use due to observed dataset independence of the parameter values involved.

We present in this paper, a new model for document hierarchical clustering, which is inspired from the self-assembly behavior of real ants. We have simulated the way ants build complex structures with different functions by connecting themselves to each other. Ants may thus build “chains of ants” or form “drops of ants”. The artificial ants that we have defined will similarly build a tree. Each ant represents one document. The way ants move, disconnect or connect themselves depends on the similarity between these documents. The result obtained is presented as a hierarchical structure with a series of HTML files with hyperlinks.

Parameters inverse model of concrete gravity dams is usually formulated as an optimization problem with continuous variables, thus inverse procedures require optimization of an objective function. Ant colony optimization (ACO) is a novel technique proposed mainly for solving discrete optimization problems. In this paper, we attempt to present an adaptation and application of the ACO technique to the parameters inverse of concrete gravity dams. For this purpose, we firstly discretized the search space of mechanical parameters so that a parameters inverse problem was transformed into a combinatorial optimization problem. Secondly, according to the characteristics of the parameters inverse model, we adapted the ACO to the parameters inverse by redefining trail intensity and visibility. Lastly, we gave an example to test the adapted ant colony optimization (AACO) and the results show the AACO can optimize the inverse model validly and efficiently.

Physical A* (PHA*) and its multi-agent version MAPHA* [3,4] are algorithm that find the shortest path between two points in an unknown real physical environment with one or many mobile agents. Previous work assumed a complete sharing of knowledge between agents. Here we apply this algorithm to a more restricted model of communication which we call large pheromones, where agents communicate by writing and reading data at nodes of the graph that constitutes their environment. Unlike small pheromones where only a limited amount of data can be written at each node, the large pheromones model assumes no limitation on the size of the pheromones and thus each agent can write its entire knowledge at a node. We show that with this model of communication the behavior of a multi-agent system is almost as good as with complete knowledge sharing.

Ant colony optimisation, like all other meta-heuristic search processes, requires a set of parameters in order to solve combinatorial problems. These parameters are often tuned by hand by the researcher to a set that seems to work well for the problem under study or a standard set from the literature. However, it is possible to integrate a parameter search process within the running of the meta-heuristic without incurring an undue computational overhead. In this paper, ant colony optimisation is used to evolve suitable parameter values (using its own optimisation processes) while it is solving combinatorial problems. The results reveal for the travelling salesman and quadratic assignment problems that the use of the augmented solver generally performs well against one that uses a standard set of parameter values. This is attributed to the fact that parameter values suitable for the particular problem instance can be automatically derived and varied throughout the search process.

This paper presents a particle swarm optimization algorithm (PSO) to solve the permutation flowshop sequencing problem (PFSP) with makespan criterion. Simple but very efficient local search based on the variable neighborhood search (VNS) is embedded in the PSO algorithm to solve the benchmark suites in the literature. The results are presented and compared to the best known approaches in the literature. Ultimately, a total of 195 out of 800 best-known solutions in the literature is improved by the VNS version of the PSO algorithm.

Constructive metaheuristics explore a tree of constructive decisions, the topology of which is determined by the way solutions are represented and constructed. Some solution representations allow particular solutions to be reached on a greater number of paths in this construction tree than other solutions, which can introduce a bias to the search. A bias can also be introduced by the topology of the construction tree. This is particularly the case in problems where certain solution representations are infeasible. This paper presents an examination of the mechanisms that determine the topologies of construction trees and the implications for ant colony optimisation. The results provide insights into why certain assignment orders perform better in problems such as the quadratic and generalised assignment problems, in terms of both solution quality and avoiding infeasible solutions.

We developed a new optimization algorithm for multiagent coordination based on indirect and unsupervised communication. The mobile agents team task is simply searching and collecting “food items”. The global coherent behavior is emergent, meaning that despite the fact that agents have no global map of the environment and do not directly communicate with each other they coordinate their behavior to achieve a global “goal”. The coordinated response of the agents is the result of indirect communication via local changes in the environment. Each agent records the encountered objects in a memory register and by appropriate weighting of local perception the agent tries to estimate the global spatial distributions of the objects in the environment. The range of spatial and temporal indirect coupling among the agents is controlled via a “memory radius”. We developed an optimized an algorithm that adapts the “memory radius” according to environment changes to minimize the computational time required to achieve the “goal” (piling the objects of the same kind together). Our optimization procedure is based on the correlation feature of the emergent pattern. The maximum speed of feature decreases leads to an optimized dependence of the “memory radius” on simulation time step. We derived also an analytic relationship between the “memory radius” and the time step based on the intermediate steady-state assumption. Numerical simulations confirmed that our analytic relationship coincides with the numerical optimization criterion based on the correlation feature.

This paper introduces the I-SWARM project (Intelligent Small World Autonomous Robots for Micro-manipulation). This project aims at the development and production of a very large-scale artificial swarm (VLSAS) composed of several hundred micro-robots with a proposed size of 2× 2× 1 mm. This will be the first realisation of a swarm with such a large number of robots. The extremely small size of the robots will impose severe limitations on their sensory and computational capabilities which is to be compensated by collective behaviour and emerging swarm effects. This paper presents an overview over one faces in the realisation of such a swarm based on extremely miniaturised robots. Further a new concept for an on-board ego-positioning system is proposed and some initial concepts for simulation and task planning in such a VLSAS are presented.

In this paper we propose a hybrid approach for solving the capacitated vehicle routing problem (CVRP). We combine an Ant Colony System (ACS) with a Savings algorithm and, then, we improve solutions by a local search heuristic. The CVRP is a class of well-known NP-hard combinatorial optimization problem, which can be formally defined as a complete graph G=(V,E) where V={0, ... ,n} is a set of vertices and E is a set of arcs [4]. The vertex {0} represents the depot and the other vertices represent customers. The cost of travel between vertices i and j is denoted d _ij and represents the distance or the travel time. We assume that costs are symmetric(i.e. d _ij = d _ji ), and an unlimited fleet of identical vehicles, each of capacity Q>0, is available. Each customer i has a demand q _i , with 0<q _i ≤ Q. Each customer must be served by a single vehicle and no vehicle can serve a set of customers whose demand exceeds its capacity. The task is to find a set of vehicle routes of minimum cost, where each vehicle used leaves from and returns to the depot. In the following, we explain our algorithm then, we give results and conclusions.

This paper presents a swarm approach to the problem of synchronisation of traffic lights in order to reduce traffic jams in urban scenarios. Other approaches for reducing jams have been proposed. A classical one is to coordinate or synchronise traffic lights so that vehicles can traverse an arterial in one direction, with a specific speed, without stopping. Coordination here means that if appropriate signal plans are selected to run at the adjacent traffic lights, a “green wave” is built so that drivers do not have to stop at junctions. This approach works fine in traffic networks with defined traffic flow patterns like for instance morning flow towards downtown and its similar afternoon rush hour. However, in cities where these patterns are not clear, that approach may not be effective. This is clearly the case in big cities where the business centres are no longer located exclusively downtown.

Quality of Service (QoS) guarantees must be supported in a network that intends to carry real-time and multimedia traffic effectively. The effort of satisfying the QoS different requirements of these applications has resulted in the proposals of several QoS-based frameworks, such as Integrated Services (IntServ) [1], Differentiated Services (DiffServ) [2], and Multi-Protocol Label Switching (MPLS) [6].

The Capacitated Arc Routing Problem (CARP) is a prototypical optimization problem asking a fleet of vehicles to serve a set of customer demands located on the arcs of a network. The problem is closely related to Vehicle Routing Problem (VRP), and in fact every CARP instance can be transformed into an equivalent VRP instance using a graph which has a number of nodes twice the number of customer arcs of the original CARP graph [1] plus one.

In recent past, optimization of dynamic problems has evoked the interest of the researchers in various fields which has resulted in development of several increasingly powerful algorithms. Unlike in static optimization, where the final goal is to find the fixed global optimum, in dynamic optimization the aim is to find and follow the evolution of the global optimum during the entire optimization time.

Road traffic is getting busier and busier each year. Everyone is familiar with traffic congestion on highways and in the city. And everyone will admit that it is a problem that affects us both economically as well as mentally. Furthermore finding your way in an unknown city can be very difficult even with a map. Navigation systems like CARiN can help in such cases. These systems display the route to be followed when the user has set his destination. Most current systems are based on static information. The latest versions are also able to use congestion information to avoid trouble spots. But such information is only available for highways and not in a city. This paper addresses the dynamic routing of traffic in a city. We want to set up a routing system for motor vehicles that guides them through the city using the shortest way in time, taking into account the load on the roads. Furthermore we want the routing system to be distributed, for more robustness and load distribution. Applied in packet switched networks, the Ant-based algorithms have proven to be superior to other distributed routing algorithms. In this paper we will apply a variant of such an algorithm (AntNet), to a traffic network in a city.

The CARP consists on determining a set of vehicle trips with minimum total cost. Each trip starts and ends at the depot, each required edge of the site graph is serviced by one single trip, and the total demand handled by any vehicle does not exceed the capacity Q. The most efficient metaheuristics published so far are a sophisticated taboo search method (CARPET) of Hertz et al. [1] and a hybrid genetic algorithm proposed by Lacomme et al. [2]. In the beginning, no collective memory is used and ants use only heuristic information. Pheromone deposition is proportional to the fitness that can be defined for minimization objectives as the inverse of the solution quality or solution cost. Local search can also be applied to increase the convergence rate. The process is iterated until a lower bound is reached or a maximal number of iterations is carried out.

Our poster describes the architecture and innovative Swarm Intelligence algorithms of the Ant CAFÉ system that extracts and organizes textual evidence that corroborates hypotheses about the state of the world to support Intelligence analysts.

We present two heuristic mesh-partitioning methods, both of which build on the multiple ant-colony algorithm in order to improve the quality of the mesh partitions. The first method augments the multiple ant-colony algorithm with a multilevel paradigm, whereas the second uses the multiple ant-colony algorithm as a refinement to the initial partition obtained by vector quantization. The two methods are experimentally compared with the well-known mesh-partitioning programs.