1. Introduction

1.1. Heuristics and Hyper-Heuristics

When solving a large optimization problem, or a complex constraint satisfaction problem, there is little chance of finding an algorithm who solves the problem exactly in a reasonable time. Some optimization problems also have a continuous search space. Unless one can make some strong assumptions one cannot search a continuous search space and find the exact solution.

Heuristics are a family of algorithms who aim to find an approximate solution but in a reasonable time. Sometimes designers of a heuristic can provide some guarantees on the quality of the result and the time it takes to compute that result.

The design of a heuristic however takes a lot of time and requires skilled programmers to implement them. Therefore good heuristics are quite expensive. In order to tackle this problem, one tries to generalize the concept of a heuristic: Hyper-Heuristics. Hyper-heuristics are a family of algorithms who take as input a description of the problem together with a set of heuristic components. A component is for instance a shake algorithm: an algorithm that slightly modifies a solution to another one. By executing several of these components on an initial solution, one hopes in the end the hyper-heuristic will return a good solution.

Note that a hyper-heuristic is problem independent: the hyper-heuristic knows nothing about the exact problem it is solving, it only can decide which heuristic should be called and obtains information about the quality of the solution at that moment. One aims to solve problems by selecting heuristics who will significantly improve the quality.

One however can claim the concept of a hyper-heuristic doesn't solve the real problems. First of all, one now needs to implement a hyper-heuristic, a program who is way more complicated since it should work for a large set of problems. Furthermore a programmer needs to implement the heuristic components as well. These heuristic components have a large impact on the performance of the hyper-heuristic as stated by Misir et al. Finally there is little fundamental research on hyper-heuristics available, especially regarding guaranteed quality of solutions.

Todays hyper-heuristics cannot be compared objectively. Different papers solve different problems using different heuristic components. At the moment no library exists with a substantial amount of various optimization problems.

ZincOxide aims to tackle these challenges. The project includes the automatic design and implementation of heuristic parts, together with the formal design and implementation of a hyper-heuristic. Furthermore we will develop a website where one can publish optimization problems written in MiniZinc.

2. Project description

In the introduction we said we wanted to tackle some issues regarding todays hyper-heuristics. In this section, we will make this statement more precise by giving an overview of the different tasks involved in ZincOxide.

2.1. Test bench

We already described the lack of a broad test bench to test hyper-heuristic performance. We aim to tackle this by providing one ourselves. Instead of building a page where we publish a large collection of problems we made a website where researchers can provide test instances as well. Of course we will build an initial test bench, but it is the intention that the test bench will eventually become self maintaining.

2.2. Automatic model transformation

In order to specify a problem, one uses a model: a formal description of the problem. There is however a one-to-many mapping: one problem can result in a large number of models describing that problem. The decision on how to model a problem however, will strongly influence the performance of the solver. Therefore research sometimes try different models. We want to build a program who automatically modifies one model into another one or at least semi-automatic. Generating multiple models also enables channeling: one can convert a solution represented by one model to the equivalent solution in another model at runtime and thus exploiting the best of both models.

2.3. Automatic heuristic generation

One cannot test a large variety of problems manually since that would imply that one needs to design and implement heuristic components for all these problems. As a solution, one could generate these components automatically as well. A problem with todays approach is that they use problem instance data: data of single instances. Some algorithm - for example a genetic algorithm - then tries to learn which heuristic components fit the users needs. Changes are realistic however that such a genetic algorithm will not fully "understand" the nature of the problem: exceptional cases are missing and the test-instances imply a prior distribution on how a problem looks like. By generating heuristic components based on a formal description of the problem class however, we expect to improve the process and potentially provide some guarantees on how well heuristics may/can perform.

2.4. Formal hyper-heuristic

We plan do design and implement a hyper-heuristic based on a formal model. This model should give guarantees (probably statistically) on the quality of the obtained solutions and give a justification for the design decisions.

2.5. Problem specific knowledge

One of the reasons why human programs can implement solvers (both exact and heuristically) who outperform automatically generated ones is that humans think more semantically. For instance if one says "the amount of machines", we automatically know that the number is larger or equal to zero. A program can never reason about these assumption unless they are stated formally. Therefore we plan to expand the MiniZinc language allowing an efficient representation of such knowledge.

Besides specifying such information, we need to obtain it as well. We will do this in two ways:
  • Information specified in scientific journals.
  • Data mining techniques that can generate assumptions based on the test instances.

2.6. Program specialization

The generated heuristic components and hyper heuristic will probably waste some computational resources for the interaction between the two systems: unnecessary information is calculated and/or stored and moved between the systems. This information is problem specific, but already (implicitly) known at both sides. By eliminating the use of computational resources for such interaction, we hope to improve the overall performance. We will do this using the classical program specification methodologies together with possible new technology.

2.7. Parallelism

We do not expect that the discussed improvements (problem specific knowledge and program specialization) will result in a program who will outperform manually implemented (hyper-)heuristics. Humans have the ability to think out of the box and thus have a broader view on the problem. We expect however to compensate this loss of performance by implementing a parallel variant of the system. One can of course claim that a human can implement such a system as well. However the development costs rise for each parallel implementation. We hope to implement such a system only once and thus reduce the costs. Furthermore we aim to use speed-up theory to provide a formal explanation on the results.

3. Directions

The source code of the project is available on a GitHub repository. There is also a Website describing the state of the project. Finally this blog will give regular updates as well together with comment on (recent) publications.

Last edited Sep 27, 2013 at 5:08 PM by KommuSoft, version 3