Hybrid metaheuristics : an automated approach

Abstract

Hybrid metaheuristics have proven to be effective at solving complex real-world problems. However, designing hybrid metaheuristics is extremely time consuming and requires expert knowledge of the different metaheuristics that are hybridized. In previous work, the effectiveness of automating the design of relay hybrid metaheuristics has been established. A genetic algorithm was used to determine the sequence of hybridized metaheuristics and the parameters of the metaheuristics in the hybrid. This study extends this idea by automating the design of each metaheuristic involved in the hybridization in addition to automating the design of the hybridization. A template is specified for each metaheuristic, defining the metaheuristic in terms of components. Manual design of metaheuristics usually involves determining the components of the metaheuristic. In this study, a genetic algorithm is employed to determine the components and parameters for each metaheuristic as well as the sequence of hybridized metaheuristics. The proposed genetic algorithm approach was evaluated by using it to automatically design hybrid metaheuristics for two problem domains, namely, the aircraft landing problem and the two-dimensional bin packing problem. The automatically designed hybrid metaheuristics were found to perform competitively to state-of-the-art hybridized metaheuristics for both problems. Future research will extend these ideas by looking at automating the derivation of metaheuristic algorithms without predefined structures specified by the templates.