Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Frequently Asked Questions
Frequently Asked Questions
Communities & Collections
Communities & Collections
A comparative study of tree encodings for evolutionary computing
Download
index.pdf
Date
2005
Author
Saka, Esin
Metadata
Show full item record
Item Usage Stats
3
views
1
downloads
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