Runtime analysis of evolutionary algorithms with complex fitness evaluation mechanisms
Başlık çevirisi mevcut değil.
- Tez No: 717823
- Danışmanlar: Belirtilmemiş.
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: The University of Nottingham
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 111
Özet
Özet yok.
Özet (Çeviri)
Evolutionary algorithms (EAs) are bio-inspired general purpose optimisation methods which are applicable to a wide range of problems. The performance of an EA can vary considerably according to the problem it tackles. Runtime analyses of EAs rigorously prove bounds on the expected computational resources required by the EA to solve a given problem. A crucial component of an EA is the way it evaluates the quality (i.e. fitness) of candidate solutions. Different fitness evaluation methods may drastically change the efficiency of a given EA. In this thesis, the effects of different fitness evaluation methods on the performance of evolutionary algorithms are investigated. A major contribution of this thesis is the first runtime analyses of EAs on bi-level optimisation problems. The performances of different EAs on The Generalised Minimum Spanning Tree Problem and The Generalised Travelling Salesperson Problem are analysed to illustrate how bi-level problem structures can be exploited to delegate part of the optimisation effort to problem-specific deterministic algorithms. Different bi-level representations are considered and it is proved that one of them leads to fixed-parameter evolutionary algorithms for both problems with respect to the number of clusters. Secondly, a new mathematical tool called the level-based theorem is presented. The theorem is a high level analytical tool which provides upper bounds on the runtime of a wide range of non-elitist population-based algorithms with independent sampling and using sophisticated high arity variation operators such as crossover. The independence of this new tool from the objective function allows runtime analyses of EAs which use complicated fitness evaluation methods. As an application of the level-based theorem, we conduct, for the first time, runtime analyses of non-elitist genetic algorithms on pseudo-Boolean test functions and also 1 on three classical combinatorial optimisation problems. The last major contribution of this thesis is the illustration of how the level-based theorem can be used to design genetic algorithms with guaranteed runtime bounds. The well-known graph problems Single Source Shortest Path and All-Pairs Shortest Path are used as test beds. The used fitness evaluation method is tailored to incorporate the optimisation approach of a well known problem-specific algorithm and it is rigorously proved that the presented EA optimises both problems efficiently. The thesis is concluded with a discussion of the wider implications of the presented work and future work directions are explored.
Benzer Tezler
- Heuristic algorithms for solving chemical shift assignment problem in protein structure determination
Sezgisel algoritmalar ile protein yapı belirlemesindeki kimyasal kayma atama probleminin çözümü
EMEL MADEN YILMAZ
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA UYAR
PROF. DR. PETER GÜNTERT
- Esnek hesaplama tekniklerine dayalı blok modellerin geliştirilmesi ve başarım analizi
Development and performance analysis of block models based on soft computing techniques
SELÇUK METE
Doktora
Türkçe
2018
Elektrik ve Elektronik MühendisliğiErciyes ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ŞABAN ÖZER
- Scalable analysis of large-scale system logs for anomaly detection
Başlık çevirisi yok
MERVE ASTEKİN
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÖzyeğin ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
DOÇ. DR. HASAN SÖZER
- Cam elyaf takviyeli kompozit malzemelerin modal analizi
Modal analysis of glass fiber reinforced composite materials
GÖKHAN ERDOĞAN
Yüksek Lisans
Türkçe
2016
Makine Mühendisliğiİstanbul ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. YENER TAŞKIN
- Rijndael blok şifresini J2ME'de gerçekleme metotlarının analizi
The analysis of the methods of implementing the rijndael block cipher on J2ME
AYSEL UYAR
Yüksek Lisans
Türkçe
2005
Elektrik ve Elektronik MühendisliğiGebze Yüksek Teknoloji EnstitüsüElektronik Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. SERDAR ERDEM