Geri Dön

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ı

  1. Tez No: 166895
  2. Yazar: ESİN SAKA
  3. Danışmanlar: DOÇ. DR. GÖKTÜRK ÜÇOLUK, DOÇ. DR. İSMAİL HAKKI TOROSLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. 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
  7. Yıl: 2005
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 82

Ö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

  1. Tez No

    853218

    Ökzetik (auxetic) çok hücreli kiriş yapıların eğilme davranışı

    Bending behaviour of auxetic multicellular beam structures

    MEHMET FATİH KAHRAMAN

    Doktora

    Türkçe

    Türkçe

    2024

    Makine MühendisliğiSakarya Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. KENAN GENEL

  2. Tez No

    36289

    Tek tanrılı dinler karşısında kadın. (Hristiyanlık'ta ve İslamiyet'te kadının statüsüne karşılaştırmalı bir yaklaşım)

    Women versus monotheistic religions. (A comparative study of women's status in christianity and İslam)

    FATMAGÜL BERKTAY

    Doktora

    Türkçe

    Türkçe

    1994

    DinAnkara Üniversitesi

    Kamu Yönetimi ve Siyaset Bilimi Ana Bilim Dalı

    PROF. DR. MEHMET ALİ AĞAOĞULLARI

  3. Tez No

    562748

    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

    İngilizce

    2019

    İngiliz Dili ve EdebiyatıBingöl Üniversitesi

    İngiliz Dili ve Edebiyatı Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ EMİNE YEŞİM BEDLEK

  4. Tez No

    202097

    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

    Türkçe

    2007

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    PROF. DR. TURHAN TUNALI

  5. Tez No

    840875

    A comparative study of machine learning classification alorithms on acceleration data

    Hızlanma verileri üzerinde makine eğitimi sınıflandırma aloritmalarının karşılaştırmalı bir çalışması

    MUHAMMAD AHMED MAJEED

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÜsküdar Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. NURİ BİNGÖL

    DR. ÖĞR. ÜYESİ FAYYAZ AHMAD

Geri Dön