A study on metaheuristic algorithms for solving sudoku puzzles
Metasezgisel algoritmalar ile sudoku bulmacalarını çözmek üzerine bir çalışma
- Tez No: 424400
- Danışmanlar: YRD. DOÇ. DR. AİŞE ZÜLAL ŞEVKLİ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Fatih Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 110
Özet
Sudoku son yıllarda popülarite kazanmış iyi bilinen bir bulmacadır. Son zamanlarda, Sudoku bulmacalarını çözmek için geliştirilen sezgisel algoritma uygulamalarında büyük bir artış vardır. Bu tezde, Sudoku bulmacalarını çözmek için Genel Değişken Komşuluk Arama (GDKA) algoritması tabanlı iki yeni model önerilmiştir. Filitresiz-DKA adlı birinci model birçok değişimli bileşenler üzerine tasarlanmıştır. Filitresiz-DKA için iki tane başlatma metodu ve Sudoku'nun arama alanına uygun dört komşuluk yapısı önerilmiştir. İkinci model olan Filitreli-DKA ise Sudoku çözümü için yeni bir yaklaşım kullanır. Algoritmanın filitreleme safhası arama alanından kısmi mümkün olmayan çözümlerin sayısını azaltır. Mutasyon tabanlı yeni komşuluk yapısı ile de yerel arama yapılır. Her iki modelde, komşuluk yapıları farklı yerel arama stratejileri kullanarak uygulanmıştır. Modellerin en iyi konfigürasyonlarını bulmak için başlatma, komşuluk yapıları ve yerel arama üzerindeki stratejilerin birçok kombinasyonları test edilmiştir. Önerilen en iyi konfigürasyonlu iki model önceki çalışmalarda kullanılan 57 tane iyi bilinen Sudoku bulmacaları ile test edilmiştir. Deneysel sonuçlar göstermiştir ki Filitreli-DKA, Filitresiz-DKA ya göre daha fazla başarı oranı ile olmak üzere her iki modelde tüm bulmacaları çözmeyi başarmışlardır. Önerilen modellerimiz sadece 2 bulmaca dışında tüm bulmacaları önceki çalışmaların başarı oranlarına göre daha iyi başarı oranı ve çalışma zamanı bakımında daha iyi performans sağlayarak çözmüşlerdir.
Özet (Çeviri)
Sudoku is a well-known puzzle that has achieved international popularity in the latest decades. Recently, there are explosive growths in the application of metaheuristic algorithms for solving Sudoku puzzles. In this thesis, two novel models based on General Variable Neighborhood Search (GVNS) algorithm are proposed to solve Sudoku puzzles. The first model which is called as Unfiltered-VNS is designed on many alternated components. Two initialization methods and four neighborhood structures which are all proper for the search area of Sudoku are proposed for Unfiltered-VNS. The Filtered-VNS which is a second model uses a new approach to solve Sudoku. Filtering phase of the algorithm reduces the number of partial infeasible solutions from the searching area. Local search is performed by a novel mutation based neighborhood structure. In the both models, the neighborhood structures implemented by using different local search improvements strategies. Many combinations of strategies on initializations, neighborhood structures and local search have been tested in order to find the best configuration of the models. Proposed two models with best configurations are tested on 57 well-known Sudoku benchmarks which have been used in previous studies. The experimental results indicate that our both models can solve all benchmarks with Filtered-VNS generates better solution quality than Unfiltered-VNS. Except two over 57 benchmarks, Filtered-VNS provides better solution quality in terms of success rates and better performance in terms of CPU time than solution quality and performance of the previous studies.
Benzer Tezler
- Büyük boyutlu veriler için metasezgisel yöntemler ile öznitelik indirgemede yeni bir yaklaşım geliştirilmesi
Developing a new approach to feature selection with metaheuristic methods for large scale data
ESİN AYŞE ZAİMOĞLU
Doktora
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. NİLÜFER YURTAY
- Sosyal örümcek algoritmasıyla sosyal ağlarda duygu analizi
Sentiment analysis in social networks with social spider optimization algorithm
VAHTETTİN CEM BAYDOĞAN
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
DOÇ. DR. BİLAL ALATAŞ
- Çoklu depolu araç rotalama probleminin hibrid algoritmalar yöntemiyle çözülmesi
Solving multi-depot vehicle routing problems via hybrid algorithms
GÜLŞEN APAK
- Geliştirilmiş SPEA2 ile envanter probleminin çözümü
Inventory optimization with a novel SPEA2 algorithm
ALİ BAYRAKDAR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Aydın ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ILHAM HUSEYINOV
- P-hub center and routing network design problem and solution algorithms
P-ana dağıtım üssü merkez ve rotalama ağ tasarımı problemı ve çözüm algorıtmaları
ABDUL KADER KASSOUMEH
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET ARSLAN
DR. ÖĞR. ÜYESİ ZÜHAL KARTAL