Çizelgeleme problemlerine üst-sezgisel algoritmalar temelli yeni bir algoritmik yaklaşım
A new algorithmic approach to timetabling problems based on hyper-heuristic algorithms
Yazar: CEVRİYE ALTINTAŞ
Danışman: PROF. DR. TUNCAY YİĞİT
Süleyman Demirel Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Ders çizelgeleme =   ; Metasezgiseller = Metaheuristics ; Sınav çizelgeleme = Examination scheduling

Özet:
Optimizasyon algoritmalarının tasarımı derin bir problem analizi gerektiren uzun bir süreçtir. Algoritmaların verilen bir problem örneğini etkili bir şekilde çözmesi beklenir. Ancak, bu algoritmaların bütün problemlere uygulanması oldukça zordur. Meta-sezgiseller bu sorun ile baş etmeye çalışmaktadırlar. Bununla birlikte birçok çalışmada, meta-sezgiseller problem-bağımlı yöntemler olarak uygulanmıştır. Üst-sezgiseller ise arama ve optimizasyon algoritmalarından farklı olarak problem-bağımsız çözüm fırsatları verir. Üst-sezgiseller zor arama problemlerini çözmek için otomatik sezgisel tasarım amacı doğrultusundaki bir dizi yaklaşımdan oluşmaktadır. Stratejik araştırmalardaki zorluk, uygulanabilir arama yöntemlerinin daha genel olarak geliştirilmesidir. Üst-sezgisel terimi oldukça yenidir; ilk olarak 2000 yılında kombinatoryal optimizasyon kavramı kapsamında sezgiselleri seçen sezgiseller olarak tanımlanmıştır. Ancak, otomatik sezgisellerin tasarımı fikri yeni değildir ve başlangıç noktası 1960'lara kadar gözlemlenebilir. Üst-sezgisel tanımı son zamanlarda arama problemlerini çözmek için üretilen veya seçilen sezgiseller için bir öğrenme mekanizması veya arama yöntemi olarak genişletilmiştir. İki temel üst-sezgisel kategorisi vardır: sezgisel seçim ve sezgisel üretim. Üst-sezgisellerin en önemli özellikleri verilen problem için direkt olarak çözüm uzayı üzerinde arama yapmak yerine sezgisellerin veya sezgisel bileşenlerin arama uzayında işlem yapmalarıdır. Bu tezde üst-sezgiseller için bilimsel yazındaki çalışmalar ve üst-sezgisel yaklaşımları detaylı olarak incelenerek yeni yöntemler geliştirilecektir. Ayrıca üniversite çizelgeleme problemleri için üst-sezgisel yaklaşımları kullanan çözümler gerçekleştirilecek, üniversite mekân kullanım analizleri yapılacak ve gelecekteki araştırmalar tartışılacaktır.

Abstract:
Designing a optimisation algorithm is a time-consuming process requiring an in-depth analysis of the problem. The resulting algorithm is expected to be effective for solving a given set of target problem instances. However, since the algorithm is dedicated, it is hard to adapt and to apply to other problems. Meta-heuristics were brought in to cope with this drawback. Nevertheless, in most of the meta-heuristic studies, the employed meta-heuristics have been implemented as rather problem-dependent methodologies. Hyperheuristics furnish problem-independent management opportunities differently from such search and optimisation algorithms. Hyper-heuristics comprise a set of approaches which are motivated by the goal of automating the design of heuristic methods to solve hard computational search problems. An underlying strategic research challenge is to develop more generally applicable search methodologies. The term hyper-heuristic is relatively new; it was first used in 2000 to describe heuristics to choose heuristics in the context of combinatorial optimisation. However, the idea of automating the design of heuristics is not new; it can be traced back to the 1960s. The definition of hyper-heuristics has been recently extended to refer to a search method or learning mechanism for selecting or generating heuristics to solve computational search problems. Two main hyperheuristic categories can be considered: heuristic selection and heuristic generation. The distinguishing feature of hyper-heuristics is that they operate on a search space of heuristics (or heuristic components) rather than directly on the search space of solutions to the underlying problem that is being addressed. This paper presents a critical discussion of the scientific literature on hyper-heuristics including their origin and intellectual roots, a detailed account of the main types of approaches, and an overview of some related areas. This thesis presents an investigation into the use of hyper-heuristic approaches to improve solutions for university timetabling problems. Current research trends and directions for future research are also discussed.