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
- 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
1994
DinAnkara ÜniversitesiSiyaset Bilimi ve Kamu Yönetimi Ana Bilim Dalı
PROF. DR. MEHMET ALİ AĞAOĞULLARI
- Reliability analysis of adaptive control systems
Adaptif denetim sistemlerinde güvenilirlik analizi
GÜLÇİN ARMAĞAN
Yüksek Lisans
İngilizce
1994
Elektrik ve Elektronik MühendisliğiDokuz Eylül ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SUHA BAYINDIR
- Yüksek binalarda asansörlerin tasarımı ve değerlendirilmesi için bir uzman sistem
An Expert system for the design and evaluation of the elevators in high buildings
NURAY ÇANKAYA
- Betonarme yapı elemanlarının çelik lamalarla güçlendirilmesi ve birleştirilmesi; deneysel inceleme
The strengthening and joining method for structural concrete members by using plates; experimental study
MAHMUT KÖSE
- Prefabrike yuvalı temelin dış yükler altındaki davranışının incelenmesi
Başlık çevirisi yok
METİN AYDOĞAN
Yüksek Lisans
Türkçe
1998
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. METİN AYDOĞAN