A comparative study of tree encodings for evolutionary computing

Date

2005

Author

Saka, Esin

Metadata

Show full item record

Item Usage Stats

19
views

8
downloads

Cite This

One of the most important factors on the success of evolutionary algorithms (EAs) about trees is the representation of them. The representation should exhibit efficiency, locality and heritability to enable effective evolutionary computing. Neville proposed three different methods for encoding labeled trees. The first one is similar with Prüfer's encoding. In 2001, it is reported that, the use of Prüfer numbers is a poor representation of spanning trees for evolutionary search, since it has low locality for random trees. In the thesis Neville's other two encodings, namely Neville branch numbers and Neville leaf numbers, are studied. For their performance in EA their properties and algorithms for encoding and decoding them are also examined. Optimal algorithms with time and space complexities of O(n) , where n is the number of nodes, for encoding and decoding Neville branch numbers are given. The localities of Neville's encodings are investigated. It is shown that, although the localities of Neville branch and leaf numbers are perfect for star type trees, they are low for random trees. Neville branch and Neville leaf numbers are compared with other codings in EAs and SA for four problems: 'onemax tree problem', 'degree-constrained minimum spanning tree problem', 'all spanning trees problem' and 'all degree constrained spanning trees problem'. It is shown that, neither Neville nor Prüfer encodings are suitable for EAs. These encodings are suitable for only tree enumeration and degree computation. Algorithms which are timewise and spacewise optimal for 'all spanning trees problem' (ASTP) for complete graphs, are given by using Neville branch encoding. Computed time and space complexities for solving ASTP of complete graphs are O(nn-2) and O(n) if trees are only enumerated and O(nn-1) and O(n) if all spanning trees are printed , respectively, where n is the number of

Subject Keywords

Electronic computers.

URI

http://etd.lib.metu.edu.tr/upload/3/12606317/index.pdf
https://hdl.handle.net/11511/15250

Collections

Graduate School of Natural and Applied Sciences, Thesis