An orthogonal genetic algorithm for multimedia multicast routing

Qingfu Zhang*, Yiu Wing Leung

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

253 Citations (Scopus)


Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these applications, it is necessary to determine a multicast tree of minimal cost to connect the source node to the destination nodes subject to delay constraints on multimedia communication. This problem is known as multimedia multicast routing and has been proved to be NP-complete. This paper proposes an orthogonal genetic algorithm for multimedia multicast routing. Its salient feature is to incorporate an experimental design method called orthogonal design into the crossover operation. As a result, it can search the solution space in a statistically sound manner and it is well suited for parallel implementation and execution. We execute the orthogonal genetic algorithm to solve two sets of benchmark test problems. The results indicate that for practical problem sizes, the orthogonal genetic algorithm can find near-optimal solutions within moderate numbers of generations.

Original languageEnglish
Pages (from-to)53-62
Number of pages10
JournalIEEE Transactions on Evolutionary Computation
Issue number1
Publication statusPublished - Apr 1999

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Computational Theory and Mathematics

User-Defined Keywords

  • Genetic algorithm
  • Multimedia multicast routing
  • NP-complete


Dive into the research topics of 'An orthogonal genetic algorithm for multimedia multicast routing'. Together they form a unique fingerprint.

Cite this