Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms
Metasezgisel algoritmaların etkinliğini arttırmak için esin kaynağı fraktal geometri olan çözüm oluşturma
- Tez No: 641130
- Danışmanlar: PROF. DR. ÇİĞDEM ALABAŞ USLU
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Komşuluk oluşturma, yerel arama, tavlama benzetimi, cantor kümesi, gezgin satıcı problem, kareli atama problemi, Neighbor generation, local search, simulated annealing, cantor set, traveling salesman problem, quadratic assignment problem
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Mühendislik Yönetimi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 142
Özet
Gerçek hayatta karşılaşılan eniyileme problemleri, en iyi çözümün bulunabilmesi için fazla karmaşıktır. Bu yüzden, birçok araştırmacı daha etkin çözüm yöntemleri üzerinde çalışır. Bunun sonucunda metasezgisel algoritmalar 90'lı yılların ortalarından beri dünya çapında popülerlik kazanmıştır. Bir sezgisel algoritmanın etkinliğini ve etkililiğini artırmak için algoritmanın arama kabiliyeti geliştirilmelidir. Bu yüzden, metasezgisellerin geliştirilmesinde yaygın olarak kullanılan yaklaşım, yeni bir algoritma tasarlamak ya da var olan bir algoritmayı iyileştirmektir. Bu yaklaşıma kıyasla daha az üzerine düşülen başka bir yaklaşım ise, yeni bir komşuluk üretme mekanizması tasarlamaktır. Bu çalışmada, permutasyon çözüm gösterimini kullanan tekli-çözüm tabanlı sezgiseller için kullanılan yeni bir komşuluk üretme mekanizması sunulmuştur. Önerilen mekanizma cantor kümesi tabanlı (CB) yöntem olarak adlandırılmıştır. Bu mekanizmanın esin kaynağı, fraktal bir yapı olan cantor kümesi oluşturmak için kullanılan yineleme algoritmasıdır. Mekanizma basitçe şöyle çalışır: bir çözüm gösterimi, yineleme algoritmasının kurallarına göre parçalara ayrılır, ortaya çıkan parçaların sırası rastgele değiştirilir ve parçalar yeniden birleştirilir. CB yöntemi, klasik değiş tokuş (swap) ve yer değiştirme (insertion) mekanizmalarıyla karşılaştırılmış; bu karşılaştırmanın yapılabilmesi için mekanizmalar yerel arama (local search) ve tavlama benzetimi (simulated annealing) algoritmaları içinde kullanılmıştır. En etkin ve etkili tasarımın bulunabilmesi için farklı uygulama şekilleri dikkate alınarak CB yönteminin türleri oluşturulmuştur. Bu türlerin üzerinde deney yapabilmek için gezgin satıcı problemine (TSP, traveling salesman problem) ve kareli atama problemine (QAP, quadratic assignment problem) ait test problemleri kullanılmıştır. TSP ve QAP problemleri, amaç fonksiyonu değerleri cinsinden birbirlerinden çok farklı çözüm uzayı yapılarına sahip oldukları için seçilmişlerdir. Özel olarak, TSP'nin çözüm uzayı çok girintili-çıkıntılı bir yüzeye sahiptir ve büyük değişikliklerle elde edilebilecek komşu çözümlerden olumlu etkilenir. QAP'nin çözüm uzayı düz bir yüzeye sahiptir ve küçük değişikliklerle yaratılan komşu çözümlerden olumlu etkilenir. TSP ve QAP test problemlerini kullanarak CB yönteminin duyarlılığını analiz etmek amaçlanmıştır. CB türlerini analiz etmeye ek olarak, CB türleri, değiş tokuş ve yer değiştirme mekanizmaları ile karşılaştırılmıştır. Değiş tokuş ve yer değiştirme mekanizmaları, literatürde bulunan en temel mekanizmalar oldukları için seçilmişlerdir. Testler sonucunda CB'nin farklı türlerinin TSP ve QAP'ye etkin bir şekilde çözüm buldukları görülmüştür. Sonuç olarak, TSP ve QAP için tutarlı bir şekilde tatmin edici sonuçlar verebilecek genel bir mekanizmanın tasarlanabileceği kararına varılmıştır.
Özet (Çeviri)
Real-life optimization problems are too complex to solve optimally. Therefore, numerous researchers work on more efficient solution methods which led metaheuristic algorithms to gain world-wide popularity since mid-90s. To improve the efficiency and effectiveness of a heuristic algorithm, the searching capability of the algorithm needs to be improved. Hence, the usual approach in improving the science of metaheuristics is to design a novel algorithm or improve an existing algorithm. However, a relatively less explored approach is to design a new neighbor generation mechanism. In this study, a novel neighbor generation mechanism for single solution-based heuristics which use permutation solution representation is presented. The proposed mechanism is called cantor-set based (CB) method. The inspiration for the mechanism is the recursive algorithm that constructs a cantor set which is a fractal shape. Simply, a solution representation is divided based on the recursive algorithm and the resulting pieces are permutated and then combined again to generate neighbors. CB method is embedded into the classical local search (LS) and simulated annealing (SA) algorithms to test its advantages and to compare it with classical swap and insertion neighbor generation mechanisms. Different types of applications are considered to design CB method to find the most effective and efficient design of the method. A set of benchmark problems of the traveling salesman problem (TSP) and quadratic assignment problem (QAP) are used in the experiments to test these applications. TSP and QAP have very different solution spaces considering their objective functions which is why they are chosen as test problems. More specifically TSP has a steep landscape and benefits from drastic changes in neighbor generation while QAP has a flat landscape and requires delicate changes in neighbor generation. Therefore, the aim in using TSP and QAP as test problems is to analyze sensitivity of CB method. In addition to analyzing CB applications, CB method is compared to swap and insertion mechanisms. Swap and insertion are chosen because they are the most used and basic mechanisms that are encountered in the literature. The computational tests show that different applications of CB solve TSP and QAP very efficiently. In the end, it is concluded that it is possible to design a general mechanism that gives consistently good results for both TSP and QAP.
Benzer Tezler
- Değişken yazı karakterlerinin araştırılması ve değişken bir font tasarımı önerisi
Research on variable fonts and proposal for a variable font design
CEYDA KALYONCU
Yüksek Lisans
Türkçe
2020
Güzel SanatlarMimar Sinan Güzel Sanatlar ÜniversitesiGrafik Tasarımı Ana Sanat Dalı
YRD. DOÇ. DR. UMUT SÜDÜAK
- Modern mimarlıkta doğadan etkilenen form ve geleceğe yönelik yaklaşımlar
Nature-inspired forms in modern architecture and futuristic approaches
ÖZKAN ÖZÜLKÜ
Yüksek Lisans
Türkçe
2010
İç Mimari ve DekorasyonMimar Sinan Güzel Sanatlar Üniversitesiİç Mimarlık Ana Bilim Dalı
YRD. DOÇ. DR. BURAK TANSEL
- Endüstri ürünleri tasarımı kapsamında biyomimetik tasarımın yeri ve metodolojisi
Biomimetic design and methodology in the content of industrial product design
HANİFE YILDIZ
Yüksek Lisans
Türkçe
2012
Endüstri Ürünleri Tasarımıİstanbul Teknik ÜniversitesiEndüstri Ürünleri Tasarımı Ana Bilim Dalı
PROF. DR. SEÇİL ŞATIR
- Fraktal geometri konusunun ortaöğretim programına uygulanması
Adaptation of the subject of fractal geometry into the program of lise
COŞKUN ÜSTÜN
Yüksek Lisans
Türkçe
1999
Eğitim ve ÖğretimKaradeniz Teknik ÜniversitesiFen Bilimleri Eğitimi Ana Bilim Dalı
DOÇ. DR. ADNAN BAKİ
- Fraktal yapıların kullanıcı üzerine mekansal algısının irdelenmesi
Examining the user's spatial perception of fractal structures
MERVE GÜLER
Doktora
Türkçe
2024
MimarlıkKTO Karatay ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. GÜZİN DEMİRKAN TÜREL