Ants can colour graphs
Journal of the Operational Research SocietyPublished 1 March 1997
Davide Costa, Alain Hertz
Citations501
SJR quartileQ1
SJR score0.92
SNIP1.26
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.
TL;DR
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.
Abstract
AbstractIn the last few years researchers have shown how insect colonies can be seen as a natural model of collective problem solving. The analogy between the behaviour of ants looking for food and the well known travelling salesman problem has recently given rise to promising solution methods. We present in this paper an evolutionary search procedure for tackling assignment type problems. The algorithm repeatedly constructs feasible solutions of the problem under study by taking account of two complementary notions, namely the trace factor and the desirability factor. The use of such search principles will be illustrated for graph colouring problems. The results obtained have proven satisfactory when compared with those existing in the literature.Keywords: ant algorithmassignment type problemcollective performanceevolutionary methodgraph colouring
Keywords
Computer ScienceDecision SciencesEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
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.
Communications of the ACMNew methods to color the vertices of a graph
1,564 Citations1979Daniel Brélaz
An exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs and the new heuristic methods, the classical methods, and the exact method are compared.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
844 Citations1991David S. Johnson, C. Aragon +2 more
This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization.
ComputingUsing tabu search techniques for graph coloring
660 Citations1987Alain Hertz, D. de Werra
It is shown that tabu search techniques provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.
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.
Communications of the ACMEfficient and portable combined random number generators
487 Citations1988Pierre L’Ecuyer
An efficient way to combine two or more Multiplicative Linear Congruential Generators (MLCGs) is presented and a generator whose period is the least common multiple of the individual periods is produced.
Journal of Research of the National Bureau of StandardsA graph coloring algorithm for large scheduling problems
486 Citations1979Frank Thomson Leighton
A new graph coloring algorithm is presented and shown to exhibit O(n 2) time behavior for most sparse graphs and thus is found to be particularly well suited for use with large-scale scheduling problems.
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.
Annals of Operations ResearchGenetic and hybrid algorithms for graph coloring
307 Citations1996Charles Fleurent, Jacques A. Ferland
It is illustrated that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies.
European Journal of Operational ResearchSome experiments with simulated annealing for coloring graphs
204 Citations1987M. Chams, Alain Hertz +1 more
Methods of thermodynamical simulation used for combinatorial optimization problems are described and an approach to partition of the node set into as few independent sets as possible is combined with other techniques for graph coloring.
Annals of Operations ResearchGenetic algorithms: Foundations and applications
146 Citations1989Gunar E. Liepins, Michael R. Hilliard
Five successful applications and three classes of problems for which genetic algorithms are ill suited are illustrated: ordering problems, smooth optimization problems, and “totally indecomposable” problems.
Statistics and ComputingGenetic algorithms and scatter search: unsuspected potentials
138 Citations1994Fred Glover
It is demonstrated that the opportunity exists to develop more advanced procedures that make fuller use of scatter search strategies and their recent extensions.
Journal of HeuristicsEmbedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
91 Citations1995Daniel Costa, Alain Hertz +1 more
An evolutionary procedure for solving general optimization problems that combines efficiently the mechanism of a simple descent method and of genetic algorithms is presented.
Infoscience (Ecole Polytechnique Fédérale de Lausanne)Méthodes de résolution constructives, séquentielles et évolutives pour des problèmes d'affectation sous contraintes
6 Citations1995Daniel Costa