engleski

Evolutionary Algorithm for Steiner Tree Optimization

Steiner problem in graphs represents a search for the minimal-length tree connecting a subset of nodes in an undirected graph with nonnegative edge costs, G=(N,E,c). In this work we present an algorithm for obtaining nearly optimal Steiner trees in sparse graphs. Concept of coding of Steiner trees in the algorithm is simple and important for the formulation of a set of genetic operators used in a search. The structure of the algorithm and its main operators is described. Results obtained on a set of SPG instances from the OR-library are presented and discussed

Steiner problem in graphs; evolutionary algorithm; search control; OR-library

nije evidentirano