Linear linkage encoding in genetic algorithms

Abstract

Doğ rusal Bağ lantı Gü sterimi (DBG) evrimsel algoritmalar (EA) icin yakın zamandag g o şü ü şü u uonerilen bir gü sterim seklidir. Bu gü sterim daha once veri kü meleme probleminin cozü mü ndeo ş o ukullanılmıstır. Diğ er gruplama problemleri icin de uygundur. Bu tezde, bu yeni gü sterimş g ş oüsekli iki gruplama problemi uzerinde incelenmistir. Bu calısmanın ana odak noktası DBG ileş ş şşkullanılabilecek genetik uzmanların incelenmesidir. Cizge boyama problemi icin DBG ileş şüuyumlu basarım arttırıcı caprazlama uzmanları onerilmis ve var olanlar ile karsılastırılmıstır.ş ş ş şş şGeleneksel caprazlama uzmanları, yerlestirme bulussal yü ntemleriyle beraber kutu paketlemeş ş ş oproblemi uzerinde denenmistir. Ë sonuclar doğ rusal bağ lantı gü steriminin uygun genetikü ş Ilk ş g g ouzmanlar kullanıldığ ında gruplama problemleri icin basarılı bir aday olduğ unu gü stermistir.g ş ş g o ş

Linear Linkage Encoding (LLE) is a recently proposed representation scheme forevolutionary algorithms (EA). This representation has been previously used to solve dataclustering problem. It is also suitable for other grouping problems. In this thesis, this newencoding scheme is investigated on two other grouping problems; graph coloring and binpacking. The main focus of this work is to investigate genetic operators suitable for LLE.Performance enhancing crossover operators for graph coloring problem based on LLE areproposed and compared to the existing ones. Traditional crossover operators with additionalplacement heuristics are tested on bin packing problem. Initial results show that LinearLinkage Encoding is a viable candidate for grouping problems whenever appropriate geneticoperators are chosen.