A comparative study of tree encodings for evolutionary computing
Evrimsel algoritmalar için ağaç yapılarının karşılaştırmalı çalışması
- Tez No: 166895
- Danışmanlar: DOÇ. DR. GÖKTÜRK ÜÇOLUK, DOÇ. DR. İSMAİL HAKKI TOROSLU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: evrimsel algoritmalar, genetik algoritmalar, ağaç yapılarının gösterimi, bir fazla ağaç problemi, derece kısıtlı en küçük tüm ağaç problemi, bütün tüm ağaçlar problemi, derece kısıtlı bütün tüm ağaçlar problemi vıı, evolutionary algorithms, genetic algorithms, tree representation, one-max tree problem, degree constrained minimum spanning tree problem, ail spanning trees problem
- Yıl: 2005
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZ EVRİMSEL ALGORİTMALAR İÇİN AĞAÇ YAPILARININ KARŞILAŞTIRMALI ÇALIŞMASI SAKA, ESİN Yüksek Lisans, Bilgisayar Mühendisliği Bölümü Tez Yöneticisi: Assoc. Prof. Dr. Göktürk Üçoluk Ortak Tez Yöneticisi: Assoc. Prof. Dr. İsmail Hakkı Toroslu TEMMUZ 2005, 82 sayfa Ağaçlarla ilgili evrimsel algoritmaların başarısındaki en önemli faktörlerden birisi ağaç yapılarının gösterimidir. Etkin bir evrimsel hesaplama için, gösterim verimlilik, bölgesellik ve atasallık özelliklerini barındırmalıdır. Neville, etiketli ağaç yapılarının kodlanması için üç çeşit metot sunmuştur. Bunlardan birincisi, Prüfer kodlaması ile benzerdir. 200Î yılında, ağaç yapılarının gösterimi için Prüfer sayılarının kullanımının, Prüfer sayılarının rastgele ağaçlar için düşük bölgeselliği nedeniyle, evrimsel aramada yetersiz bir yöntem olduğu önerilmiştir. Bu tezde, Neville'in diğer iki kodlama yöntemi, yani Neville dal numaraları ve Neville yaprak numaraları çalışıldı. Evrimsel algoritmalardaki performansları için özellikleri, kodlama ve kodlanmış yapıyı oluşturma algoritmaları incelendi. Neville dal numaralarının kodlanması ve kodlanmış yapının oluşturulması için, n düğüm sayısı iken, 0(n)'lik zaman ve yer karmaşıklığına sahip optimal algoritmalar verildi. Nevilie'in kodlanmışlarının bölgeselliği araştırıldı. Neville dal ve yaprak numaralarının bölgeselliğinin yıldız tipi ağaçlar için mükemmel olmasına rağmen, rastgele ağaçlar için düşük olduğu gösterildi. Neville dal ve Neville yaprak numaraları evrimsel algoritmalardaki diğer kodlamalarla dört problem üzerinde karşılaştırıldı: 'bir fazla ağaç problemi', 'derece kısıtlı en küçük tüm ağaç problemi', 'bütün tüm ağaçlar vıproblemi' ve 'derece kısıtlı bütün tüm ağaçlar problemi'. Ne Neville ne de Prüfer kodla- malarının evrimsel algoritmalar için uygun olduğu gösterildi. Bu kodlamalar sadece derece hesaplamalarında ve ağaçların birer birer sayımında uygundur. Bütün tüm ağaçlar problemi (ASTP) için zaman ve yer bakımından tam ağaçlarda optimal algoritmalar, Neville'in dal kod- laması kullanılarak verildi, n düğüm sayısını gösterirken, tam ağaçlarda ASTP'yi çözmek için hesaplanan zaman ve yer karmaşıklıkları, sırasıyla, ağaçlar sadece kod olarak basılırsa 0{nn~2) ve 0{n); ağaçların kendisi basılırsa {^(n“”1) ve 0(n)'dir. Benzer şekilde, tam ağaçlarda 'derece kısıtlı bütün tüm ağaçlar problemi'. 0(nn-1)'lik zaman ve 0(n)'îik yerde çözülebilir.
Özet (Çeviri)
ABSTRACT A COMPARATIVE STUDY OF TREE ENCODINGS FOR EVOLUTIONARY COMPUTING SAKA, ESİN M.Sc, Department of Computer Engineering Supervisor: Assoc. Prof. Dr. Göktürk Üçoluk Co-Supervisor: Assoc. Prof. Dr. Ismail Hakkı Toroslu July 2005, 82 pages 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 meth ods for encoding labeled trees. The first one is similar with Priifer's encoding. In 2001, it is reported that, the use of Priifer numbers is a poor representation of spanning trees for evo lutionary 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 0(n), where n is the number of nodes, for encoding and decoding Neville branch numbers are given. The locali ties 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', 'ail spanning trees problem' and ' all degree constrained spanning trees problem'. It is shown that, neither Neville nor Priifer encodings are suitable for EAs. These encodings are suitable for IVonly tree enumeration and degree computation. Algorithms which are timewise and space- wise 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 com plete graphs are 0(nn~2) and 0(n) if trees are only enumerated and 0{nn~l) and 0{n) if all spanning trees are printed, respectively, where n is the number of nodes. Similarly, 'all degree constrained spanning trees problem' of a complete graph is solvable in 0(nn~1) time and 0(n) space.
Benzer Tezler
- Android işletim sistemlerinde zararlı yazılım tespitine yönelik hibrit analiz ve özellik seçimi temelli yaklaşım
A hybrid analysis and feature selection based approach to malware detection in android operating system
MESUT GÜN
Yüksek Lisans
Türkçe
2026
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖNDER DEMİR
DR. ÖĞR. ÜYESİ ESRA ÇALIK BAYAZIT
- Veri anonimleştirme tekniklerinin makine öğrenmesi ile sınıflandırma performansı üzerindeki etkilerinin karşılaştırmalı analizi
Comparative analysis of the effects of data anonymization techniques on classification performance i̇n machine learning
ZEHRA BEGÜM AKTOLGA
Yüksek Lisans
Türkçe
2026
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiBilişim Sistemleri Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL HAKKI CEDİMOĞLU
- Elmas fiyat tahmini için makine öğrenmesi yöntemlerinin incelenmesi
Investigation of machine learning methods for diamond price prediction
ERKAN ÜNSAL
Yüksek Lisans
Türkçe
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. HUMAR KAHRAMANLI ÖRNEK
- Victims of nationalism: A comparative study of the Lemon Tree and Sevdalinka
Milliyetçiliğin kurbanları: Limon Ağacı ve Sevdalinka üzerine karşılaştırmalı bir çalışma
YÜSRA BOYLU
Yüksek Lisans
İngilizce
2019
İngiliz Dili ve EdebiyatıBingöl Üniversitesiİngiliz Dili ve Edebiyatı Ana Bilim Dalı
DR. ÖĞR. ÜYESİ EMİNE YEŞİM BEDLEK
- Vesikalık fotoğrafların sınıflandırılması için özellik ölçütleri üzerine kıyaslamalı bir çalışma
A comparative study of feature metrics for classification of human passport photos
SİNEM ASLAN
Yüksek Lisans
Türkçe
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı (disiplinlerarası)
PROF. DR. TURHAN TUNALI