Üst-sezgiseller için alana özgü dil tasarımı
A domain specific language for hyper-heuristics
Yazar: HİLAL KEVSER CORA
Danışman: DOÇ. DR. ŞİMA UYAR
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Ö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.

Abstract:
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.