Ants can colour graphs

Davide Costa; Alain Hertz

doi:10.1057/palgrave.jors.2600357

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

Travelling salesman problemAnalogyComputer scienceGraphScheduling (production processes)Mathematical optimizationOperations researchTheoretical computer scienceArtificial intelligenceMathematicsAlgorithmEpistemology

Affiliated Institutions

École Polytechnique FR

Related Publications

Ants can solve constraint satisfaction problems

Christine Solnon

We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artifici...

2002 IEEE Transactions on Evolutionary Com... 193 citations

Solving symmetric and asymmetric TSPs by ant colonies

Luca Maria Gambardella , Marco Dorigo

We present ACS, a distributed algorithm for the solution of combinatorial optimization problems which was inspired by the observation of real colonies of ants. We apply ACS to b...

2002 502 citations

Ant colony system: a cooperative learning approach to the traveling salesman problem

Marco Dorigo , Luca Maria Gambardella

This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...

1997 IEEE Transactions on Evolutionary Com... 7855 citations

An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem

Luca Maria Gambardella , Marco Dorigo

We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple cons...

2000 INFORMS journal on computing 367 citations

Ant system: optimization by a colony of cooperating agents

Marco Dorigo , Vittorio Maniezzo , A. Colorni

An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach...

1996 IEEE Transactions on Systems Man and ... 11674 citations

Publication Info

Year: 1997
Type: article
Volume: 48
Issue: 3
Pages: 295-305
Citations: 500
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Ants can colour graphs

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

500

OpenAlex

Cite This

APA Style

                            
                                    Davide Costa, 
                                
                                    Alain Hertz
                                
                            (1997). 
                            Ants can colour graphs. 
                            Journal of the Operational Research Society
                            , 48
                            (3)
                            , 295-305.
                            https://doi.org/10.1057/palgrave.jors.2600357

Identifiers

DOI: 10.1057/palgrave.jors.2600357