ABSTRACT

The metaheuristics algorithm is increasingly important in solving many kinds of real-life optimization problems but the implementation involves programming difficulties. As a result, many researchers have relied on software framework to accelerate the development life cycle. However, the available software frameworks were mostly designed for rapid development rather than flexible programming. Therefore, in order to extend software functions, this approach involves modifying software libraries which requires the programmers to have in-depth understanding about the internal working structure of software and the programming language. Besides, it has restricted programmers for implementing flexible user-defined low-level hybridization. This paper presents the concepts and formal definition of metaheuristics and its low-level hybridization. In addition, the weaknesses of current programming approaches supported by available software frameworks for metaheuristics are discussed. Responding to the deficiencies, this paper introduces a rapid and flexible software framework with scripting language environment. This approach is more flexible for programmers to create a variety of user-defined low-level hybridization rather than bounded with built-in metaheuristics strategy in software libraries.

1. Introduction

Since the last decade, rapid software development has emerged as a preferable approach in software engineering especially for developing computer applications with complex computations such as distributed, scheduling and optimization systems [1]. The main critical factor for developing such kind of systems is time but complexity of programming development has led to very lengthy completion. As a result, in many aspects, rapid software development is able to provide easier, effective and productive method for each stage of the development. In order to facilitate rapid software development, a lot of innovations and improvements have been studied and invented. The ideas vary from diverse perspectives that include software design [2,3], software architecture [4], software modeling [5] and programming paradigm [6-8].

In the perspectives of programming paradigm, scripting language has been widely accepted by programmers for two reasons. Firstly, scripting language has simpler language structure as compared to other kinds of programming languages. Therefore, scripting language is usable for gluing together different complex algorithms from the low-level implementation of a software library [9]. Secondly, it can be used for developing strong functionality programs in a complex computer application such as distributed and collaborative application [10], grid computing [11] and agent based system [12].

In optimization based software, where the system foundation is structured with complex computational algorithm, scripting language programming is highly applicable for rapid development. Examples of complex computational algorithm for optimization application include metaheuristics and metaheuristics hybridization.

In many cases, metaheuristics hybridization is more useful for different kinds of real life problems [13]. The main intention for metaheuristics hybridization is to compensate one single metaheuristic limit with the strength of other algorithms.

The metaheuristics hybridization techniques can be classified either as high-level or low-level hybridization. The level of hybridization is used to differentiate the strength of combination between the hybrid algorithms [14,15]. In high-level hybridization, the components from different hybrid algorithms are not strongly dependent because the implementation retains original identity or behavior of the hybrid algorithms. In contrast, low-level hybridization requires internal structure modification, which committed with internal components exchange from the hybrid algorithms. Thus, the components from the hybrid algorithms are strongly connected to work together in finding optimal solutions.

The development of metaheuristics hybridization is very lengthy and difficult [5] especially to the low-level hybridization. Thus, in order to reduce the development time and difficulty, programmers might rely on software framework that provides software library for metaheuristics algorithm. Software framework promotes rapid implementation because the configurations for metaheuristics and hybridization in the software library could be simply specified with Graphical User Interface (GUI). GUI provides convenient and easy to learn interface for supporting interactions between software user (programmer) and software framework. However, in implementing low-level hybridization, GUI is not a suitable technique for enabling software library modification because the interactions between GUI functions and other functions is defined by built-in functions and application program interface (API) within the software library [16]. Therefore, in order to implement low-level hybridization with software framework, an easy and flexible programming environment at front-end software should be provided which could be supported by scripting language.

The remainder of this paper is organized as follows: Section 2 presents background of problem related to the software frameworks for metaheuristics. Then, the general concept of metaheuristics and formal definition of low-level hybridization is given in Section 3. The limitations of common programming approaches in software frameworks for metaheuristics are discussed in Section 4. Section 5 explains the proposed software framework before the concluding remarks in Section 6.

2. Background of the Problem

The research on rapid software framework for metaheuristics is still an ongoing research. Generally, there are two major issues in the development of rapid software framework for metaheuristics. These issues include implementation technique and algorithm strategy. Figure 1 shows the related issues.

The first issue is categorized as metaheuristics implementation technique, which can be single or hybrid. Single implementation does not combine one metaheuristic paradigm with other algorithms but hybrid techniques involve cooperation of different algorithms. There are varieties of techniques applied metaheuristics hybridization. Generally, these techniques can be divided into high-level and low-level [14,15]. In high-level hybridization, the hybrid algorithms establish their communication through a well defined interface [14]. Therefore, the implementation does not involve internal structure modifications and retains original behavior of the hybrid algorithms. Besides, the components of hybrid algorithms are not dependent on each other. In contrast, low-level hybridization needs internal structure modification of the different hybrid algorithms. Thus, the original behavior of algorithms would be changed and different components from the hybrid algorithms are strongly connected to each other. Therefore, implementing low-level hybridization is more complicated than high-level hybridization.

Many researchers have agreed that relying on single metaheuristics is quite restricted in achieving best solution for real-life optimization problems [14,15]. Therefore, hybrid metaheuristics have been widely accepted as an effective approach as compared to single implementation. Nevertheless, many of available software frameworks facilitate more functionality on single metaheuristic [5]. This is due to the simpler structures of single metaheuristics. Some of the software frameworks for single implementation are JCLEC [17], JEO [18], TEA [19], JSwarm [20] and NetLogo [21]. JCLEC, JEO and TEA support Genetic Algorithm (GA) while NetLogo and JSwarm facilitate Particle Swarm Optimization (PSO) algorithm only.

However, a number of rapid software frameworks have been invented and introduced for hybrid metaheuristics such a HeuristicLab [22], ParadisEO [23] and Distributed BEAGLE [24]. Unfortunately, many of these software frameworks are majorly developed for highlevel hybridization due to the fact that high-level hybridization is less complicated than low-level. Implementing high-level hybridization with software framework might involve simple configurations of combination that are not modifying internal structure of the hybrid algorithms. Therefore, the programmer can rely on pre-defined hybridization strategies located in software library.

Instead of the implementation techniques, algorithm strategy is the second issue in rapid software framework for metaheuristics. The algorithm strategy can be provided as built-in or user-defined [5]. Built-in strategies only supported pre-defined metaheuristics components in software library, which is less flexible and complex for program amendment. In contrast, user-defined strategies allow programmers to extend or create new metaheuristics components according to their needs. With user-defined, a variety of new algorithm strategy such as hybridization scheme could be created at front-end software framework. As for example, with user-defined high-level hybridization, dynamic parallel algorithms could be implemented as provided in OpenTS software framework [25]. However, no low-level modification involves in implementing user-defined high-level hybridization. Hence the combination configurations could be defined simply with GUI or through template program.

Based on the reviewed literature, it can be concluded that software frameworks for metaheuristics and its hybridization are intentionally developed only to support rapid software development. The frameworks are not governed for flexible programming environment that support low-level hybridization as described in Figure 2. The grey box represents common features provided by the available software frameworks.

In addition, Figure 2 also shows the limitation of the software frameworks in providing user-defined strategy for metaheuristics and its hybridization. User-defined strategy supports high flexibility for programmers to develop low-level metaheuristics hybridization. Many empirical experiments have shown that low-level hybridization is increasingly significant to metaheuristics strategy improvement [5]. However, difficulty in the development might discourage researchers for exploring new strategy.

3. General Concept of Metaheuristics and Low-Level Hybridization

There are fives common questions for using metaheuristics in solving optimization problems. These questions are about the design of metaheuristics components which is composed of encoding method for solution representation, neighborhood structure, search strategy, fitness function and penalty function. Figure 3 shows the relationship of each component.

The encoding and decoding are two essential steps in designing metaheuristics for a particular optimization problem. It must be suitable and relevant to the search operators and solution evaluation technique [26]. Therefore, the encoding and decoding plays an important role in the efficiency and effectiveness of a particular metaheuristics.

The search space consists of a finite set of decision variables for each solution representation. At the first search, the solutions will be randomly selected to go through fitness evaluation process according to a particular search strategy and objective. Different metaheuristics has different search strategy and operators.

Fitness function is an important element of a metaheuristics that formulates the search objective. It describes the quality or fitness of solutions and will guide the search toward better solutions [26]. Depending on the problem, a fitness function might be subjected to some kinds of constraint that is formulated in a penalty function.

The neighborhood structure is relatively important for some kind of metaheuristics. These metaheuristics are classified as single-based metaheuristics such as Simulated Annealing, Tabu Search and Variable Neighborhood Search. Different from population-based, the singlebased metaheuristics implement generation and replacement of solutions from a single solution. The set of solutions for replacement is determined from the solution neighborhood. Therefore, in single-based metaheuristics, the structure of neighborhood plays a crucial role in their performance.

3.1. Metaheuristics Hybridization

Since every metaheuristics has distinct search strategy, each operator or component from different algorithms might be crossover to be new hybrid algorithms with better performance. This process is called metaheuristics hybridization. When a metaheuristic changes its original paradigm by adding new components from other algorithms, it is described as implementing low-level hybridization [15].

In this paper, the metaheuristics that receive new components from other algorithms is referred to as mastermetaheuristics. A master-metaheuristics can be included with new components from one or many sub-metaheuristics. Since the variation of low-level hybridization techniques is too broad, the hybridization techniques focus in this research is limited to hybridization among the family of population-based metaheuristics (p-metaheuristics) only. Besides, the modification process is restricted to be occurred in the search strategy component which is referred to as Proprietary components by [5]. The illustration of low-level hybridization for proprietary components of metaheuristics is given in Figure 4.

The details about low-level hybridization of p-metaheuristics are further described in the next sub-section as a formal definition.

3.2. Formal Definition of Low-Level Hybridization

The low-level hybridization of p-metaheuristics can be formally defined as a composition of (m,s) where:

• The are different algorithms from the set of p-metaheuristics. The parameter

ter m and s are devoted to master-metaheuristics and sub-metaheuristics respectively in which only one m can be integrated with more than one s.

• Each metaheuristic M is composed of general components and proprietary components. While general components are common to all M algorithms, they have distinction with proprietary component.

• S is one of the general components that define solution representation in a search space. The search space consists of a finite set of decision variables where. The type of variables can be in discrete, continuous or mixed form [27].

• Another general component for M is objective function that assigns a cost value MIN and MAX to each solution of S. The set of constraints among the variables is defined in a set of penalty functions where .

• The proprietary components C are exclusive of their respective metaheuristics M which can be crossover into the routine of another metaheuristics M. It creates specific metaheuristics paradigm and characteristics that consists of different parameters with different types T. The parameters can be associated with dynamic or constant value. The dynamic values can be determined by dynamic behaviour either self-adaptive A or time-varying V. The sets of and consist of different functions with different types T. Each function calculates an appropriate parameter value in relation to a particular metaheuristics condition.

4. Programming Approach in Metaheuristics Software Framework

There are two types of programming approaches that can be implemented by programmers when developing metaheuristics with software framework as depicted in Figure 5.

The first type is through GUI approach at front-end software framework. This method is more suitable for simple operations such as to configure algorithms parameters or to call some executable functions but it has limited capability for implementing extensive program modification. Therefore, this approach has insufficient functions for supporting flexible user-defined low-level hybridization. In contrast, the second type of programming approach is related directly to software libraries which are located at back-end software framework. Usually, template program is provided for simple software operations but in order to perform extensive modification, the programmers have to explore and modify some of the software libraries. Although this approach is

highly flexible than GUI, the task for modifying programs in software library is too complicated [5]. Since the process of finding the best hybridization strategy involves repeating tasks include redeveloping and validating, this approach is very costly and time consuming.

The implementation of flexible user-defined low-level hybridization is hindered by the limitation of these programming approaches. The GUI approach restricts users to modify software libraries while the template and software library modification involve tedious and complicated tasks. Nevertheless, these approaches are mostly adapted by the available software frameworks for metaheuristics. Table 1 summarizes the available software frameworks with its programming approaches (GUI, template, software library) and implementation supports (single, high-level hybridization, low level hybridization).

As shown in Table 1, most of available software frameworks provide template programming approach and some software with GUI. Therefore, they are only capable to support single and high-level implementation due to the GUI and template limitations. Although available software frameworks are useful for low-level hybridization (e.g. MDF and ParadisEO), the strategies have been restricted to built-in metaheuristics components in software libraries. In order to perform extensive modification for user-defined strategy, the programmers have to modify software libraries which have been developed in JAVA, C++ or C#. These programming languages are difficult for novice programmer.

Despite the fact that GUI is easier than template, it has restricted program modification. While hybridization techniques could be enabled in HeuristicLab with GUI, the implementation supports only for built-in high-level hybridization. In MDF software framework, the researchers introduce modeling technique for designing new hybridization strategies. The program codes are automatically generated based on user-defined model but the strategies are still bounded with available metaheuristics components in software library. In order to create new functions or components, the developer has to understand the detail of software working structure.

In order to resolve these deficiencies, an alternative solution is by providing scripting language programming environment at front-end software framework. While scripting language is less complicated to be used, it is also applicable for the development of complex functional programs. Therefore, scripting language can support rapid and flexible user-defined low-level hybridization for metaheuristics.

5. The Proposed Software Framework

The proposed software framework is designed with three-tier architecture namely front-end scripting language, intermediate compiler and back-end software libraries as illustrated in Figure 6.

5.1. The Back-End Software Library

The back-end software libraries consist of high performance program codes for different metaheuristics. High performance programs are developed with JAVA. The basic feature of the back-end software architecture is to support generic and extensible environment for implementing different kind of metaheuristics and optimization problems. The class architecture is illustrated in Figure 7.

The back-end programs are bundled with a collection of software libraries that consists of five main elements, one is a collection of controller classes and the rest is a set of interface classes. The set of interface classes comprise of general interface, proprietary interface, adaptive interface and time-varying interface. The interface classes are highly flexible for extensible through inheritance implementation. Therefore, the software frame-work can be used for developing different metaheuristics algorithms. In this paper, the focus is given to Particle Swarm Optimization (PSO) and Genetic Algorithm (GA).

The general interface consists of different classes for general metaheuristics components while proprietary interface provides specific component classes for specific metaheuristics. As shown in Figure 7, specific components for GA are selection, crossover and mutation while specific components for PSO are position and velocity update.

In addition, self-adaptive and time-varying interfaces facilitate dynamic behavior of metaheuristics parameters such as mutation rate for GA, inertia weight and constriction parameters for PSO. Self-adaptive behavior

determines parameters value with regards to metaheuristics search ability namely exploration and exploitation. In metaheuristics, exploration ability promotes high accuracy of solutions while exploitation facilitates fast convergence speed. Therefore, the balance of both abilities is very important to the performances of metaheuristics algorithms. Based on empirical studies, it is found that one of the successful ways to balance the search ability is by providing self-adaptive environment [33]. Nevertheless, besides self-adaptive, time-varying behavior is also contributes to improvement of metaheuristics performance. By providing time-varying behavior, the exploration and exploitation search abilities can be dynamically adjusted according to number of iteration.

The low-level hybrid controller is an important element that consists of low-level hybrid engine for implementing low-level hybridization. It is a JAVA codes generated by scripting compiler at the intermediate software framework.

5.2. The Intermediate Compiler

Scripting compiler is intermediate software between scripting program and software library that translates the scripting language codes for low-level metaheuristics hybridization into JAVA program. The JAVA program will be saved at back-end software to operate as a main program that defines class interactions between software libraries. It might also consist of new instantiations of metaheuristics components.

5.3. The Front-End Scripting Language

The front-end software framework is supported with scripting language to be used by programmers for defining and developing new low-level hybridization of metaheuristics. The steps for basic operations in creating low-level hybridization are given in Figure 8.

The scripting language is not just usable for calling pre-defined operations from software libraries but capable in creating new functions of metaheuristics components. The scripting language is capable to fulfill these requirements since it has the following special characteristics:

• The scripting language tend not to have strong typing rules and not error-prone.

• In particular, scripting language tend to have powerful data structure and operations, which are tightly built-in with the language.

These special characteristics have given additional advantages to developers to use scripting language for many purposes such as to support rapid software development, API manipulation for back-end software libraries and software functions extension. These purposes are essential to the development of flexible user-defined

low-level hybridization. The following parts discuss how scripting language can be used to fulfill these requirements.

5.4. Scripting Language for Rapid Software Development

Scripting languages are simpler than application programming languages like C, C++ and JAVA. Thus, scripting language will considerably increase the efficiency of development. Some of the key enhancing features in scripting languages with regards to efficiency include simplify, expressiveness, and easiness.

Scripting language consists of simplify instructions which reduces the development errors for programming. A single statement of a scripting language can describe many instructions. In other words, scripting languages are normally expressiveness. It can generate roughly 10 to 100 times shorter code compared to application programming languages. For example, one statement in Tcl can represents more than 100 instructions while in C programming language, it means for several (5 to 10) instructions only.

5.5. Scripting Language for API

Scripting language can be used to call and communicate with different program codes from the software libraries [34]. Thus, scripting language can be used to operate as an API between the different programs or applications software.

The API with scripting language could be implemented at front-end software framework while the software libraries at back-end software are written with application programming language such as JAVA or C++. Therefore, scripting language and application programing language are complimentary to each other. Programming with scripting language promises better productivity for integrating different software codes and libraries while application programming language supports high efficiency performance for algorithm implementation.

5.6. Scripting Language for Flexible Software Extension

At the beginning, conventional scripting languages have some limitations, which restrict their efficiency and expressiveness. For instance, they have limited capability for concurrency, data structuring and object-oriented programming. Responding to the deficiencies, language developers have created advanced scripting languages such as Perl, Python and among others. Perl provides compact but very powerful sets of data types and data structures for example list, stack and queue. Python also has a great feature comparable Perl, but it is based on object-oriented programming. In addition, the Tcl is an excellent language for writing system or hardware program without using intermediate language to machine. With the very powerful sets of data types and data structures, scripting languages are not just able to invoke and glue together other programs, but they are also appropriate for writing new complex program as flexible as application programming language.

With the flexibility, software designer interest has been attracted to invent different types of scripting languages for different types of computer applications. As for example, the JACIE scripting language has been invented for developing collaborative and distributed application [10]. In addition, in order to develop grid based application Gaussion script has been introduced [11]. More than that, a group of researcher has created Japlo scripting language useful for rules based programming similar to Prolog language [35]. The Japlo language works on top of JAVA and it has better functionality than the Prolog itself.

In addition, there are also available scripting languages for implementing metaheuristics based application. Table 2 lists the scripting languages for metaheuristics.

Some scripting use XML script which is integrated in metaheuristics software framework such as Open Beagle [36], Distributed Beagle [24] and JCLEC [17]. The XML in JCLEC is used for running different experiments with different configurations in parallel.

A scripting programming language is proven to be useful for facilitating user-defined strategy. The T++ scripting language for example, has been designed to support flexible user-defined strategy [25]. The language is incorporated in OpenTS software framework but it is only usable for high-level hybridization. More interesting, in METASIS software framework [37], the scripting with Sequential Interactive Synthesis System (SIS) could enable user-defined strategy for low-level hybridization. However, SIS is specifically usable for synthesizing and optimizing sequential circuits only. Thus, it has a limit to be employed for different kinds of optimization problem.

6. Conclusions

Rapid programming is significant to the development of metaheuristics based applications. Therefore, the implementation needs software framework in order to reduce development time and difficulty. However, for implementing low-level metaheuristics hybridization with software framework, another complexity has emerged due to its extensive programming. Current approaches in software frameworks have some limitations for supporting easy and flexible programming. As a result, they lack of flexibility in providing user-defined hybridization strategy at front-end software. Besides, the deficiencies would discourage programmers to develop a variety of lowlevel hybridization strategies for metaheuristics algorithms.

In order to enable rapid and flexible front-end programming environment, a scripting language should be developed. The scripting language is not just beneficial for integrating different metaheuristics programs, but it also permits the creation of new functionalities beyond the capability of software libraries. This paper has several contributions to the metaheuristics community as well as to the software engineering. Firstly, formal definition of low-level hybridization provides general views of the implementation. Secondly, it introduces three-tier software architecture that promotes rapid and flexible

programming at front-end software. In addition, this paper also provides operation steps for operating low-level metaheuristics hybridization that can be used for designing structure and details specification of a software framework.

7. Acknowledgements

The authors would like to thank Kementerian Pengajian Tinggi MALAYSIA and Universiti Teknologi MARA for their financial support to this project.

REFERENCES

NOTES

^*Corresponding author.