A Grid Enabled Parallel Hybrid Genetic Algorithm for the SPN

Giuseppe Lo Re, Giuseppe Lo Presti

Risultato della ricerca: Chapter

Abstract

This paper presents a combination of a parallel Genetic Algorithm (GA) and a local search methodology for the Steiner Problem in Networks (SPN). Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for twomain reasons: the dimension and the features of the networks adopted in the experiments and the aim from which it has been originated.The reason that aimed this work was namely to assess deterministic and computationally inexpensive algorithms which can be used inpractical engineering applications, such as the multicast transmission in the Internet. The large dimensions of our sample networks requirethe adoption of an efficient grid based parallel implementation of the Steiner GAs. Furthermore, a local search technique, which complementsthe global search capability of the GA, is implemented by means of a heuristic method. Finally, a further mutation operator is addedto the GA replacing the original genome with the solution achieved by the heuristic, providing thus a mechanism like the genetically modified organisms in nature. Although the results achieved cannot be applied directly to the problem we investigate, they can be used to validate other methodologies that can find better applications in the telecommunication field.
Lingua originaleEnglish
Titolo della pubblicazione ospiteLECTURE NOTES IN COMPUTER SCIENCE
Pagine156-163
Numero di pagine8
Stato di pubblicazionePublished - 2004

Fingerprint

Entra nei temi di ricerca di 'A Grid Enabled Parallel Hybrid Genetic Algorithm for the SPN'. Insieme formano una fingerprint unica.

Cita questo