Çok Amaçlı Evrimsel Algoritmalarla Çizge Tabanlı Sıralı Dizi Demetleme

thumbnail.default.placeholder
Tarih
2008-07-07
Yazarlar
Demir, Nildem Gül
Süreli Yayın başlığı
Süreli Yayın ISSN
Cilt Başlığı
Yayınevi
Fen Bilimleri Enstitüsü
Institute of Science and Technology
Özet
Bu çalışmada, ikili benzerlikler olarak ifade edilen sıralı dizilerin çokamaçlı evrimsel algoritmalar kullanılarak demetlenmesi üzerine odaklanılmıştır. Sıralı dizilerden oluşan bir veri kümesi bir yönsüz, ağırlıklı bir çizge olarak ifade edildiğinde, sıralı diziler çizge üzerindeki düğümlere, onlar arası benzerliklerse kenar uzunluklarına denk düşerler. Bu durumda sıralı dizi demetleme problemi evrimsel algoritmalarla çözülebilecek NP-zor çizge bölümleme problemine dönüştürülür. Sıralı dizilerin demetlenmesi için çizge tabanlı bir çokamaçlı evrimsel algoritma önerilmiş, algoritmanın evrimsel operatörleri, amaç fonksiyonları, genetik temsil ve başlangıç durumuna getirme yöntemi ve temel çokamaçlı evrimsel algoritma bileşenleri değiştirilerek çeşitli varyasyonları gerçeklenmiştir. Sıralı dizi demetleme problemi için en uygun varyasyonun belirlenmesi istatiksel testler ve demetleme kalite göstergeleri aracılığıyla sağlanmıştır.
This dissertation focuses on the clustering of sequences represented as pairwise similarities through multiobjective evolutionary algorithms. The sequence can be expressed through weighted, undirected graphs where each sequence becomes a vertex of the graph and the pairwise similarities or dissimilarities form the edges connecting the corresponding vertices in the graph. Through this representation approach, the sequence clustering problem becomes equivalent to graph partitioning which is an NP-hard problem and can be solved through evolutionary algorithms. To cluster sequences a graph based multiobjective evolutionary algorithm is proposed. By changing the evolutionary operators, objective functions, genetic representation and initialization method different variations of this algorithm is implemented. In order to determine the best variation for the sequence clustering problem quality indicators with statistical tests and cluster validation indices are used.
Açıklama
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2008
Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2008
Anahtar kelimeler
Çokamaçlı evrimsel algoritmalar, çokamaçlı demetleme, sıralı dizi demetleme, çizge demetleme, Multiobjective evolutionary algorithms, multiobjective clustering, sequence clustering, graph clustering
Alıntı