A Study of Genetic Algorithms for Approximating the Longest Path in Generic Graphs

D. Portugal, C. H. Antunes and R. Rocha

In Proc. of 2010 IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC’2010), Istambul, Turkey, pages 2539-2544, Oct. 10-13, 2010.

Abstract

Finding the longest simple path in a generic undirected graph is a challenging issue that belongs to the NP-Complete class of problems. Four approaches based on genetic algorithms to solve this problem are presented in this article. The first three algorithms proposed use crossover mechanisms between pairs of solutions based on their intersecting regions and the fourth one uses a mutation mechanism on individual solutions, in which the perturbation applied depends on the state of the system. Simulation experiments have been carried out to validate the distinct approaches, which reveal their good performance and provide hints for their application in robotics, packet networks and other fields.

Index Terms — Genetic algorithms, graph theory, longest path problem.

Full text

You may ask Rui Rocha for an electronic copy of this publication’s full text by e-mail:
.

Please select for your message’s subject ‘Requesting Rui Rocha’s electronic copy’ and include on the message’s body your full name, title and affiliation, why do you need to access the publication and the BibTeX information below.

BibTeX

@INPROCEEDINGS(Portugal_et_al_10,

AUTHOR = "Portugal, D. and Antunes, C. H. and Rocha, R.",

TITLE = "A Study of Genetic Algorithms for Approximating the Longest Path in Generic Graphs",

BOOKTITLE = "Proc. of 2010 IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC’2010)",

ADDRESS = "Istambul, Turkey",

YEAR = "2010",

MONTH = "Oct",

PAGES = "2539-2544"

)

(top of the page)

Last update: 18/10/2010