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ı: Belirtilmemiş.
Ö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
- Görüntü sınıflandırması için evrişimsel sinir ağı-metasezgisel algoritmalar tabanlı yeni bir hibrit yaklaşım geliştirilmesi
Development of a novel hybrid approach based on convolutional neural networks-metaheuristic algorithms for image classification
SEDA VAROL
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMalatya Turgut Özal ÜniversitesiEnformatik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SONER KIZILOLUK
- Metasezgisel arama algoritmalarında yakınsama denklemi tasarımı için yeni bir yöntemin geliştirilmesi
Development of a new method for approximation equation design in metaheuristic search algorithms
MEHMET KATI
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
PROF. DR. HAMDİ TOLGA KAHRAMAN
- Bir İHA'nın üst sezgisel algoritmalarla enerji yönetimi ve eniyilemesi
Energy management and optimization based on meta-heuristic algorithms for a UAV
HASAN ÇINAR
Doktora
Türkçe
2022
Uçak MühendisliğiGebze Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. İLYAS KANDEMİR
- Kesikli eniyileme problemleri için yeni bir iyileştirilmiş yasaklı arama algoritması
An improved tabu search algorithm for solving discrete optimization problems
ALİ YİĞİT SABANER
Yüksek Lisans
Türkçe
2025
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. GÜRKAN ÖZTÜRK
- 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