Geri Dön

Üst-sezgiseller için alana özgü dil tasarımı

A domain specific language for hyper-heuristics

PDF İndir

  1. Tez No: 350652
  2. Yazar: HİLAL KEVSER CORA
  3. Danışmanlar: DOÇ. DR. ŞİMA UYAR
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2013
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 115

Özet

Üst sezgiseller alt seviye sezgisellerle işlem yapan metodolojilerdir. Alt seviye sezgiselleri seçmek veya üretmek için kullanılırlar. Üst sezgisellerle ilgili çalışma yapan kişilerin tasarladıkları algoritmaları gerçeklemeleri için yüksek düzey programlama dillerini bilmeleri gerekmektedir. Programlama bilgisi olmayan araştırmacılar bu açıdan zorluk çekmekte, çözmek istedikleri problemleri ve çözümlerini iyi ifade edememektedir. Alana özgü diller belirli bir alan için özel olarak tasarlanmış dillerdir. Kullanıldıkları alanda mevcut olan kavramlar dilin bir parçasını oluşturmaktadır. Bu açıdan genel amaçlı dillerle kıyaslandıklarında alanla ilgili kavramlar daha kolay ve anlaşılır bir biçimde ifade edilebilmektedir. Alana özgü dilleri kullanarak program yazmak hiç programlama bilmeyen kişiler için daha kolay olmaktadır. Bu çalışmada üst sezgiseller için alana özgü bir dil geliştirilmiştir. Alana özgü dil geliştirmek için Eclipse tabanlı Spoofax dil geliştirme aracı kullanılmıştır. Geliştirilen dilin söz dizimi ve kod üretme kuralları Spoofax üzerinde tanımlanmıştır. Spoofax geliştirilen dilde yazılmış ifadeleri tanımlanan kod üretme kurallarından yola çıkarak Java koduna dönüştürmektedir. Üst sezgiseller için alana özgü bir geliştirmeden önce bu alanda kapsamlı bir literatür araştırması yapıldı. Literatür araştırmasıyla birlikte alana özgü terimler, kavramlar ve yöntemler tespit edildi. Üst sezgisellerle ilgili yazılmış program kodları incelendi ve üst sezgisel algoritmaları Java dili kullanarak gerçeklendi. Böylece tasarlanan dilde ihtiyaç duyulan yapılar belirlendi. Bu tecrübelerden yola çıkarak dilin söz dizimi ve kod üretme kuralları tanımlandı. Geliştirilen dil ile belirli yöntemler kullanarak sezgisel seçmek, seçilen sezgiseli çözüm adaylarına uygulamak ve üretilen yeni çözümleri değerlendirmek mümkündür. Geliştirilen dil sayesinde, üst sezgisel alanında çalışan araştırmacılar genel amaçlı bir dil öğrenmek zorunda kalmadan algoritmalarını gerçekleyebilirler.

Özet (Çeviri)

In this study, a domain specific language for developing hyper-heuristic programs is proposed. A domain specific language (DSL) is a programming language which aims to make it easier to develop programs in a certain domain. A well designed DSL provides a more natural notation and more suitable data structures to express solutions to problems of the targeted domain as opposed to a general purpose language (GPL). Although using a GPL in combination with a library or package for the domain is a very common approach, it still assumes a considerable amount of programming knowledge, therefore making it harder to be productive for domain experts who might have limited or no programming skills. The development of a DSL is a difficult task because it requires expertise both in the targeted domain and in programming language design and implementation. The phases of development are outlined as decision, analysis, design and implementation. First, it has to be decided if a new DSL is really needed instead of using existing languages and tools. The advantages of domain related notation and data structures have to be evaluated. In the analysis phase, domain knowledge is gathered from documents, domain experts and existing program codes developed for the domain. Next, the DSL is designed in light of the design patterns which emerged in the analysis phase. And finally, the DSL is implemented by developing a language processor such as an interpreter or a compiler or by embedding it in a GPL. There are many studies about DSL design and implementation. Since developing a new DSL is a complex process, it is recommended to use language development tools or frameworks. Therefore, beside the research on developing DSLs, there are also many studies on developing frameworks to generate and implement DSLs. Domain specific languages can be designed as internal or external. Internal DSLs are integrated into an existing general purpose language and use features of the original language. However, internal DSLs might be complex for non-programmers because they should know syntax and constraints of the host language. These people might feel more confident while using external DSLs. External DSLs also have IDE support like syntax highlighting and code completion which improves productivity. Another decision is whether to design a textual or a graphical DSL. Graphical notation can seem simpler but it cannot cover all domain concepts. Domain concepts can be stated with textual DSLs more clearly. Hyper-heuristics are high-level methodologies which were proposed as an alternative to heuristics tailored to a specific problem domain. There are two types of hyper-heuristics in literature: heuristics to choose heuristics (selection hyper-heuristics) and heuristics to generate heuristics. In this study, we work with only the first type of hyper-heuristics. Therefore, in this work, the term hyper-heuristics refers to selection hyper-heuristics. A hyper-heuristic selects and applies a low-level heuristic without using any problem specific information. Low-level heuristics are heuristics tailored to a specific problem domain. Therefore, low-level heuristics operate on the problem search space, whereas a hyper-heuristic operates on the low-level heuristics search space. Over the years, research on hyper-heuristics has shown an increase. Recently, HyFlex (Hyper-heuristics Flexible framework), a hyper-heuristics framework which provides easy implementation of hyper-heuristics and allows comparisons between them, has been implemented. HyFlex can be used with different hyper-heuristics and different problem domains. In the CHeSC (Cross-domain Heuristic Search Challenge) competitions, the HyFlex framework is used as the underlying system for hyper-heuristic development. CHeSC competitions aim to bring together researchers and practitioners from operational research and computer science fields to develop more general approaches to problem solving across many domains. Since researchers and practitioners come from different fields, programming skills may be a drawback for some. To write hyper-heuristic code working on HyFlex, one needs to have good Java programming skills. To alleviate this requirement and allow the researchers to focus on the hyper-heuristic development phase rather than the details of Java programming, we decided to develop a DSL for hyper-heuristic research. The proposed DSL aims to generate code which can be executed on HyFlex. Hyper-heuristics are composed of two components: heuristic selection schemes and acceptance criteria. Heuristic selection schemes deal with deciding which low-level heuristic to choose and apply to the current candidate solution. Acceptance criteria are used to determine whether to accept or reject the new candidate solution created as a result of applying the selected low-level heuristic. In this study, the Spoofax language development framework, which is integrated into Eclipse, is used. When using this framework, two aspects of the DSL have to be expressed: the grammar and the code generation rules. From these specifications, Spoofax generates the necessary components like the parser and the code generator. It also prepares an environment which supports assistive features like syntax highlighting for the target DSL. The syntax of the language is specified using the SDF notation as required by the Spoofax platform. Some of the reserved keywords of our DSL are best, first, random, select, solution, heuristic, apply and replace, which map to concepts in the hyper-heuristics domain. Other than these, some standard programming language constructs like if-else and loop are also supported. The loop iteration construct can take two forms. Beside the usual counter controlled repetition which allows repeating for a certain number of times, loops can also be limited by the time they are allowed to spend; so the total time available to the program can be divided between loops. This feature is implemented as a convenience for programs developed for the CHeSC competition. While some of these types of general purpose constructs are necessary when expressing hyper-heuristic algorithms, adding too many such constructs might damage the aim of being a DSL and the language might start resembling a GPL. Some higher level features of our DSL are primarily meant for defining new hyper-heuristic operators instead of using standard operators which are already included in the platform. Typically, a program in our DSL starts by setting the environment for later stages, such as configuring a selection heuristic method and an acceptance method. Then a set of initial solutions will be generated and the algorithm will proceed to a loop where the chosen methods will be applied to candidate solutions. The code generation rules are written using the Stratego program transformation language which is integrated into Spoofax. The code generation process produces Java code by applying rewrite rules to terms. Code generation rules are matched with the labels of the production rules. In the code generation phase, our system generates Java code which can be directly executed on the HyFlex platform. The Spoofax framework uses string interpolation for code generation. In this approach, the code to generate is expressed as a template containing references to variables and these variables will be replaced by their values. After editing the code in the editor component of the working environment, code generation is invoked from the menu. An Eclipse Java project is generated automatically when code generation is invoked. Proposed DSL is a domain specific language for developing hyper-heuristic programs, which can be executed on HyFlex. Through examples, how hyper-heuristic programs can be developed using this DSL is illustrated. The examples show that writing a hyper-heuristic program in the proposed DSL is easier than writing the same in Java. Currently, the features provided in our DSL are designed to work with hyper-heuristic development on HyFlex, however, features can be added to make it a more general tool for hyper-heuristic research. The advantage of working with HyFlex is that HyFlex provides the problem domain implementations. Therefore, researchers can focus on hyper-heuristic development rather than implementing the problems to solve. It also allows researchers to benchmark their approaches on standard implementations of these problem domains.

Benzer Tezler

  1. Tez No

    692422

    Hybridization of probabilistic graphical models and metaheuristics for handling dynamism and uncertainty

    Değişimin ve belirsizliğin ele alınması için olasılıksal çizgesel biçelerin ve sezgi-üstlerinin melezleştirilmesi

    GÖNÜL ULUDAĞ

    Doktora

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞE ŞİMA UYAR

  2. Tez No

    496467

    Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon

    Logistic network design and optimization using hyperheuristic methods

    VURAL EROL

    Doktora

    Türkçe

    Türkçe

    2017

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MURAT BASKAK

    PROF. DR. GÜLGÜN KAYAKUTLU

  3. Tez No

    634929

    Sınav çizelgeleme problemleri için üst sezgisel yaklaşımlar

    Hyper-heuri̇sti̇c approaches for examination timetabling problems

    FERDA NUR ARICI

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ERSİN KAYA

  4. Tez No

    386797

    Hyper-heuristics for grouping problems

    Gruplama problemleri için çok hedefli üst buluşsallar

    MURAT BİRBEN

    Yüksek Lisans

    İngilizce

    İngilizce

    2011

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ENDER ÖZCAN

  5. Tez No

    353808

    Hyper-heuristics in dynamic environments

    Dinamik ortamlarda üst-sezgiseller

    BERNA KİRAZ

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYŞE ŞİMA ETANER UYAR

Geri Dön