Keywords

1 Introduction

Optimization problems can be found in several real application domains such as engineering, medicine, mathematics, mechanics, physics, mining, games, design, and biology, among others. There exist several techniques to the efficient solving of these problems. On one hand, we found the exact methods, which aim at providing the global optimum of the given problem by exploring the complete search space of potential solutions. A main problem of these techniques is that for several optimization problems, the search space cannot be completely explored in a reasonable amount of time. The approximate methods tackle this concern, which on the contrary, explore only promising regions of the search space in order to provide a good enough local optimum in a limited amount of time. However, they are unable to always guarantee the global optimum.

Metaheuristics are one of the most famous and widely used approximate methods for solving optimization problems [1, 10]. Most of them are known for being inspired on interesting behaviors that can be found on the nature, such as the way in which ants, bees and fishes found food, or the way in which fireflies and bats move on the environment. However, solving optimization problems via metaheuristics is not always a simple trip, mainly because metaheuristics are not black boxes ready to be used to solve any optimization problem and there are different topics that must be handled before designing and implementing a metaheuristic: iterations, exploration, exploitation, move operators, and representation of solutions, among others. They must be smartly adapted to the nature of the problem and most of them must be efficiently tuned to reach good results in a reasonable amount of time. This commonly demands specific and advanced knowledge from the user. In this paper, we analyze and discuss a method in order to reduce the effort for designing and implementing metaheuristics.

2 Discussion

In general, when trying to solve optimization problems, we consider different solution techniques. The metaheuristics are one of these techniques, but succeed in correctly using them depends on the maturity of certain implementation and design knowledge. The task is not trivial, as each metaheuristic has its own behavior and characteristics, so you cannot consider it as a black box. Firstly, we need to select among single solution or population-based metaheuristics. Secondly, the representation of the solution must be established. After that, we need to identify the move operators that allow to find or to generate potential solutions. Then, the treatment of unfeasible must be handled, from which we can use three classic methods: penalization, discarding, or repairing. Finally, it will be useful to design a sampling process for the initial configuration of the metaheuristic. Details about those instructions are given in the following.

  • The selection of the metaheuristic is the first step to determine which algorithm will attempt to solve the optimization problem. As mentioned earlier, there is a strong link between the implementation of the metaheuristic and the problem.

  • The representation of the solutions is a key process to design and implement a metaheuristic. This process is responsible for defining the data structure to model the solution. This structure is independent from the problem domain, but is bounded by the dimension of the problem.

  • The variable domains of the problem are the set of values that can take a solution and it is defined by the mathematical model of the optimization problem. This is strongly linked to the representation of the solution.

  • The move operators generate a new solution, generally from an existing one. They are usually mathematical functions that define the behavior of the metaheuristic.

  • The unfeasible solutions must be treated in different ways. When move operators generate solutions that are not in the problem domain, you must consider three classic alternatives: discard the solution, penalize, or repair it. These three alternatives are commonly part of the metaheuristic implementations.

  • The sampling process is an important part of the process. Each metaheuristic has its own configuration so it is necessary to develop an a priori sampling and to define values for each parameter. This process is iterative and depends on the robustness of the implementation of the metaheuristic.

  • The sampling process aims at defining proper values for each metaheuristic parameter. This process may be useful for the robustness of the metaheuristic.

  • At the end, it is crucial to evaluate the performance of the implemented metaheuristic. To this end, the trial and error process is key in demonstrating the robustness of the metaheuristic.

This method can be seen as a knowledge discovery process that solves optimization problems using metaheuristics as solving technique. This method has been repeatedly applied by computer science students from the Pontificia Universidad Católica de Valparaíso, Chile. This method has been conducted over a period of five months, corresponding to one semester of study. Students must solve the set covering problem applying metaheuristics and compare their results with 65 reported instances. In Table 1 we illustrate the progress of three iterations of the metaheuristic implementation. In the first iteration, is hard to achieve optimal values, however several values can be close to the optimal one. At the second, and third iteration the number of optimal values improve. Finally, incorporating tuning and efficient repairing, several optimal values can be found. Indeed, several articles have been published based on the student results reached by using this method [2–9].

Table 1. A performance example of three students.
Full size table

3 Conclusion

In this paper, we have illustrated a method for designing and implementing metaheuristics for solving optimization problems. This method depends on the maturity of certain basic concepts for all metaheuristic. The aim is to identify and define each of these step according to the given problem and metaheuristic. This method can be seen as a process of knowledge discovery, which has phases that must be resolved for success in the design and implementation of metaheuristic. To date, this method has been used by computer science students with very promising results. We expect to continue improving this method, detailing each of the stages.