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 two main 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 in practical engineering applications, such as the multicast transmission in the Internet. The large dimensions of our sample networks require the adoption of an efficient grid based parallel implementation of the Steiner GAs. Furthermore, a local search technique, which complements the global search capability of the GA, is implemented by means of a heuristic method. Finally, a further mutation operator is added to 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.

LO PRESTI, G., LO RE, G., STORNIOLO, P., URSO, A.M. (2004). A Grid Enabled Parallel Hybrid Genetic Algorithm for the SPN. In LECTURE NOTES IN COMPUTER SCIENCE (pp. 156-163) [10.1007/978-3-540-24685-5_20].

A Grid Enabled Parallel Hybrid Genetic Algorithm for the SPN

LO PRESTI, Giuseppe;LO RE, Giuseppe;
2004-01-01

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 two main 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 in practical engineering applications, such as the multicast transmission in the Internet. The large dimensions of our sample networks require the adoption of an efficient grid based parallel implementation of the Steiner GAs. Furthermore, a local search technique, which complements the global search capability of the GA, is implemented by means of a heuristic method. Finally, a further mutation operator is added to 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.
2004
LO PRESTI, G., LO RE, G., STORNIOLO, P., URSO, A.M. (2004). A Grid Enabled Parallel Hybrid Genetic Algorithm for the SPN. In LECTURE NOTES IN COMPUTER SCIENCE (pp. 156-163) [10.1007/978-3-540-24685-5_20].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/5174
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact