Lee Chang Hoon, Zhang Bupimg Tak, Ahn Sang Hyun, Kwak Ju Hyun, Kim Jae Hoon

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 3, pp. 671-680, Mar. 1998
10.3745/KIPSTE.1998.5.3.671,   PDF Download:

Abstract

Network services, such as teleconferencing, remote diagnostics and education, and CSCW require multicasting. Multicast routing methods can be divided into two categories. One is the shortest path tree method and the other is the minimal Steiner tree method. The latter has an advantage over the former in that only one Steiner tree is needed for group. However, finding a minimal Steiner tree is an NP-complete problem and it is necessary to find an efficient heuristic algorithm. In this paper, we present an evolutionary optimization method for finding minimal Steiner trees without sacrificing too much computational efforts. In particular, we describe a tree-based genetic encoding scheme which is in sharp constant with binary string representations usually adopted in conventional genetic algorithm. Experiments have been performed to show that the presented method can find optimal Steiner trees for given network configurations. Comparitive studies have shown that the evolutionary method finds on average a better solution than other conventional heuristic algorithms.

Statistics
Cite this article