Routing in Telecommunications Networks with ``Smart'' Ant-Like Agents
RePEc: Research Papers in EconomicsPublished 1 January 1998
Eric Bonabeau, Florian Hénaux, Sylvain Gu 'erin, Dominique Snyers, Pascale Kuntz, Guy Théraulaz
Citations103
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
A simple mechanism is presented, based on ant-like agents, for routing and load balancing in telecommunications networks, following the initial works of Appleby and Stewart (1994) and Schoonderwoerd et al. (1997). In the present work, agents are very similar to those proposed by Schoonderwoerd et al. (1997), but are supplemented with a simplified dynamic programming capability, initially experimented by Gu\'erin (1997) with more complex agents, which is shown to significantly improve the network's relaxation and its response to perturbations.
Keywords
Computer Science
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Ant system: optimization by a colony of cooperating agents
11,908 Citations1996Marco Dorigo, Vittorio Maniezzo +1 more
IEEE Transactions on Evolutionary ComputationAnt colony system: a cooperative learning approach to the traveling salesman problem
7,994 Citations1997Marco Dorigo, Luca Maria Gambardella
The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and it is concluded comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.
Distributed Optimization by Ant Colonies
2,580 Citations1992Alberto Colorni, Marco Dorigo +3 more
A distributed problem solving environment is introduced and its use to search for a solution to the travelling salesman problem is proposed.
Operations ResearchA Method for Solving Traveling-Salesman Problems
1,532 Citations1958G. A. Croes
A method of solution for the traveling-salesman problem that is applicable to both symmetric and asymmetric problems with random elements, and does not use subjective decisions, so that it can be completely mechanized.
Physica D Nonlinear PhenomenaThe decay of turbulence in the burgers model
1,055 Citations1981S. S. Moiseev, A. Toor +1 more
A dynamical model for the immune system is described that is based on the network hypothesis of Jerne, and is simple enough to simulate on a computer, and has a strong similarity to an approach to learning and artificial intelligence introduced by Holland, called the classifier system.
MAX-MIN Ant System and local search for the traveling salesman problem
825 Citations2002Thomas Stützle, Holger H. Hoos
The results clearly show that MAX-MIN Ant System has the property of effectively guiding the local search heuristics towards promising regions of the search space by generating good initial tours.
ePubWU Institutional Repository (Wirtschaftsuniversität Wien)A new rank based version of the Ant System. A computational study.
802 Citations1997B. Bullnheimer, Richard F. Hartl +1 more
It turns out that the new rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior.
Adaptive BehaviorAnt-Based Load Balancing in Telecommunications Networks
744 Citations1997Ruud Schoonderwoerd, Owen Holland +2 more
A novel method of achieving load balancing in telecommunications networks using ant-based control, which is shown to result in fewer call failures than the other methods, while exhibiting many attractive features of distributed control.
Trends in Ecology & EvolutionSelf-organization in social insects
714 Citations1997Eric Bonabeau, Guy Théraulaz +3 more
This description does not rely on individual complexity to account for complex spatiotemporal features that emerge at the colony level, but rather assumes that intractions among simple individuals can produce highly structured collective behaviours.
Ethology Ecology & EvolutionCollective patterns and decision-making
671 Citations1989J. L. Deneubourg, Simon Goss
Autocatalytic interactions between the members of an animal group or society, and particularly chemically or visually mediated allelomimesis, can be an important factor in the organisation of their collective activity.
Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)Ant system for Job-shop scheduling
618 Citations1994Alberto Colorni, Marco Dorigo +2 more
This paper shows how a new heuristic called ant system, in which the search task is distributed over many simple, loosely interacting agents, can be successfully applied to find good solutions of job-shop scheduling problems.
Elsevier eBooksAnt-Q: A Reinforcement Learning approach to the traveling salesman problem
601 Citations1995Luca Maria Gambardella, Marco Dorigo
Ant-Q algorithms were inspired by work on the ant system (AS), a distributed algorithm for combinatorial optimization based on the metaphor of ant colonies and are applied to the solution of symmetric and asymmetric instances of the traveling salesman problem.
Journal of the Operational Research SocietyAnts can colour graphs
501 Citations1997Davide Costa, Alain Hertz
An evolutionary search procedure for tackling assignment type problems that repeatedly constructs feasible solutions of the problem under study by taking account of two complementary notions, namely the trace factor and the desirability factor is presented.
Applying the ANT System to the Vehicle Routing Problem
412 Citations1999B. Bullnheimer, Richard F. Hartl +1 more
A recently proposed metaheuristic, the Ant System, is used to solve the Vehicle Routing Problem in its basic form, i.e., with capacity and distance restrictions, one central depot and identical vehicles.
ScienceAn Economics Approach to Hard Computational Problems
385 Citations1997Bernardo A. Huberman, Rajan M. Lukose +1 more
This method, based on notions of risk in economics, offers a computational portfolio design procedure that can be used for a wide range of problems, including the combinatorics of DNA sequencing and the completion of tasks in environments with resource contention, such as the World Wide Web.
An Investigation of Some Properties of an Ant Algorithm
357 Citations1992Alberto Colorni, Marco Dorigo +3 more
Some properties of Ant-cycle, the up to now best performing of the ant algorithms, are analyzed and its performance when varying the values of control parameters is compared with some TSP specialized algorithms.
Lecture notes in computer scienceThe ant colony metaphor for searching continuous design spaces
337 Citations1995George Bilchev, Ian C. Parmee
An ant colony model for continuous space optimisation problems is presented and it is shown that by integrating the Pareto optimality concept within the selection mechanism in GAs and Ant Colony it is possible to treat both hard and soft constraints.
Insectes SociauxCollective decision making through food recruitment
334 Citations1990R Beckers, J. L. Deneubourg +2 more
A series of experiments shows how the andLasius niger uses its trail recruitment system to select between two food sources, simultaneously presented with to 1M sucrose solution and when offered a 1M solution together with a 0.1M solution.
ScienceCoordination in Distributed Building
220 Citations1995Guy Théraulaz, Eric Bonabeau
A formal model of distributed building is presented that was inspired by the observation of wasp colonies, and algorithms have been obtained that allow a swarm of simple agents, moving randomly on a three-dimensional cubic lattice, to build coherent structures.
CERN Document Server (European Organization for Nuclear Research)Routing in Communications Networks
189 Citations1995Martha Steenstrup
This paper presents a meta-analysis of routing in ATM Networks, high-speed networks, and circuit-swITCHing networks that addresses the challenge of adaptive routing in the rapidly changing environment.
NatureNew optimization methods from physics and biology
154 Citations1987David G. Bounds
Research in spin-glass physics, population genetics, and neural network dynamics has provided powerful methods for finding near-global optima of functions that have many local optima and may also give new insights into combinatorial optimization problems.
Physical review. A, General physicsDynamics of computational ecosystems
151 Citations1989Jeffrey O. Kephart, Tad Hogg +1 more
RePEc: Research Papers in EconomicsAdaptive Task Allocation Inspired by a Model of Division of Labor in Social Insects
138 Citations1998Eric Bonabeau, Andrej Sobkowski +2 more
A recently proposed model of division of labor in a colony of primitively eusocial wasps, based on a simple reinforcement of response thresholds, can be transformed into a decentralized adaptive algorithm of task allocation.
BT Technology JournalMobile Software Agents for Control in Telecommunications Networks
132 Citations2000Steve Appleby, S. Steward
Distributed control can, in principle, have advantages in terms of speed of response and robustness over centralised control, but these benefits are not realised automatically and distribution of control can also result in sub-optimal performance since global information is not normally available to each controlling process.