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

249
views

85
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

Suggestions

OpenMETU
Core

A mathematical contribution of statistical learning and continuous optimization using infinite and semi-infinite programming to computational statistics Özöğür-Akyüz, Süreyya; Weber, Gerhard Wilhelm; Department of Scientific Computing (2009) A subfield of artificial intelligence, machine learning (ML), is concerned with the development of algorithms that allow computers to “learn”. ML is the process of training a system with large number of examples, extracting rules and finding patterns in order to make predictions on new data points (examples). The most common machine learning schemes are supervised, semi-supervised, unsupervised and reinforcement learning. These schemes apply to natural language processing, search engines, medical diagnosis,...
Comparison of rough multi layer perceptron and rough radial basis function networks using fuzzy attributes Vural, Hülya; Alpaslan, Ferda Nur; Department of Computer Engineering (2004) The hybridization of soft computing methods of Radial Basis Function (RBF) neural networks, Multi Layer Perceptron (MLP) neural networks with back-propagation learning, fuzzy sets and rough sets are studied in the scope of this thesis. Conventional MLP, conventional RBF, fuzzy MLP, fuzzy RBF, rough fuzzy MLP, and rough fuzzy RBF networks are compared. In the fuzzy neural networks implemented in this thesis, the input data and the desired outputs are given fuzzy membership values as the fuzzy properties أlow...
Evolving aggregation behaviors for swarm robotics systems: a systematic case study Bahçeci, Erkin; Şahin, Erol; Department of Computer Engineering (2005) Evolutionary methods are shown to be useful in developing behaviors in robotics. Interest in the use of evolution in swarm robotics is also on the rise. However, when one attempts to use artificial evolution to develop behaviors for a swarm robotic system, he is faced with decisions to be made regarding some parameters of fitness evaluations and of the genetic algorithm. In this thesis, aggregation behavior is chosen as a case, where performance and scalability of aggregation behaviors of perceptron control...
A hypercomputational approach to the agent causation theory of free will Mersin, Serhan; Sayan, Erdinç; Department of Cognitive Sciences (2006) Hypercomputation, which is the general concept embracing all machinery capable of carrying out more tasks than Turing Machines and beyond the Turing Limit, has implications for various fields including mathematics, physics, computer science and philosophy. Regarding its philosophical aspects, it is necessary to reveal the position of hypercomputation relative to the classical computational theory of mind in order to clarify and broaden the scope of hypercomputation so that it encompasses some phenomena whic...
A pattern classification approach for boosting with genetic algorithms Yalabık, Ismet; Yarman Vural, Fatoş Tunay; Üçoluk, Göktürk; Şehitoğlu, Onur Tolga (2007-11-09) Ensemble learning is a multiple-classifier machine learning approach which produces collections and ensembles statistical classifiers to build up more accurate classifier than the individual classifiers. Bagging, boosting and voting methods are the basic examples of ensemble learning. In this study, a novel boosting technique targeting to solve partial problems of AdaBoost, a well-known boosting algorithm, is proposed. The proposed system finds an elegant way of boosting a bunch of classifiers successively ...

Citation Formats

E. Saka, “A comparative study of tree encodings for evolutionary computing,” M.S. - Master of Science, Middle East Technical University, 2005.