ST encoding: An efficient scheme for encoding trees in genetic algorithms

Sheng Yuan Tseng, Yueh Min Huang, Chang Chun Lin

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Graph optimization problems are usually difficult and time-consuming NP problems. Genetic algorithms have been proven to be an efficient technique for solving these problems. Well-designed chromosomes and appropriate operators are key factors that determine the performance of such genetic algorithms. This study proposes a novel scheme, sequence and topology encoding, for encoding trees and three associated operators. Experiments on different scales of minimum spanning tree problems are conducted to compare the performance of the proposed encoding scheme with that of the Prüfer number, which is the best encoding scheme so far. The results indicate that the proposed encoding scheme is an efficient scheme for encoding trees in genetic algorithms.

Original languageEnglish
Pages (from-to)49-57
Number of pages9
JournalJournal of Internet Technology
Issue number1
Publication statusPublished - 2007 Jan 1

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'ST encoding: An efficient scheme for encoding trees in genetic algorithms'. Together they form a unique fingerprint.

Cite this