The EasyLocal Project
What is EasyLocal
EasyLocal is an object-oriented framework that can be used as a general tool for the development of local search algorithms in C++ and Java. The basic idea of EasyLocal is to capture the essential features of most local search metaheuristics, and their possible compositions. This allows the user to address the design and implementation issues of new heuristics in a more principled way. Furthermore, the framework can easily be customized by an expert user allowing the development of new metaheuristics, and its architecture fully supports the reuse of code.
EasyLocal relies on a few "Design Patterns", which are abstract structures of classes, commonly present in O-O systems, that have been precisely identified and classified. The framework is based on two of them, namely the "Template Method", to specify and implement the invariant parts of various search algorithms, and the "Strategy Method", for the communication between the main solver and its component classes.
The architecture of EasyLocal
The classes of the framework are split in four categories, and are organized in a hierarchy of abstraction levels as shown in the Figure below. Each layer of the hierarchy relies on the services supplied by lower levels and provides a set of more abstract operations.
The problem representation belongs to the lowest level of the hierarchy and must be defined in terms of a set of Basic Data classes (computing capabilities are not required). They maintain the states of the search space, the moves, and the input/output data. The Basic Data classes are supplied to the other classes of the framework by means of template instantiation.
The local search problem is then embodied in what we call Helpers. These classes perform actions related to some specific aspects of the search, such as maintaining the states or exploring the neighborhood of a solution.
The Runners represent the algorithmic core of the framework. They are responsible for performing a run of a local search metaheuristic, starting from an initial state and leading to a final one. Each runner has many data objects for representing the state of the search (current state, best state, current move, number of iterations, ...), and it maintains links to all the helpers, which are invoked for performing problem-related tasks on its own data. Several common metaheuristics have already been implemented within EasyLocal; e.g., Hill Climbing, Simulated Annealing and Tabu Search.
The Solvers represent the external software layer of EasyLocal. They control the search by generating the initial solutions, and deciding how, and in which sequence, runners have to be activated (e.g., tandem, multistart, hybrid search). This allows, for instance, to design new combinations of basic metaheuristics and/or hybrid methods. In addition, solvers communicate with the external environment, by getting the input and delivering the output, and they are linked to one or more runners and to some of the helpers.
A sketch on using EasyLocal
In order to use the framework, the user has to define the data classes (i.e., the template instantiations) and the derived helper classes which encode the specific problem description. Runners and solvers are then provided by the framework by means of templates instantiation, and they need only to be set with the links to the suitable helpers.
How to obtain EasyLocal
Unfortunately, the framework is still under development, therefore some parts of its code are unstable and not well documented.Yet, we believe that making a public release of the framework could help us to improve our code and to share ideas with other researchers. For this reason, we decided to excerpt the core classes of EasyLocal, and to release an abridged (hopefully stable) version of the framework to be used for research or educational purposes.