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.
|Titolo della pubblicazione ospite||LECTURE NOTES IN COMPUTER SCIENCE|
|Numero di pagine||8|
|Stato di pubblicazione||Published - 2004|