Automated design of specialized variation operators using a generation hyper heuristic for the multi objective quadratic assignment problem

Abstract

The development of specialized, domain-specific operators has significantly enhanced the performance of evolutionary algorithms for solving optimization problems. However, creating such operators often requires substantial effort from human experts, making the process slow, resource-intensive, and heavily reliant on domain knowledge. To overcome these limitations, generation hyper-heuristics provide a framework for automating the design of variation operators by evolving combinations of heuristic components without direct expert input. In this work, a generation hyper-heuristic method based on grammatical evolution using the hypervolume indicator (HV) as part of its selection mechanism to automatically design variation operators (crossover and mutation) tailored to the multi-objective quadratic assignment problem (mQAP)—a challenging combinatorial optimization problem with many real-world applications—is proposed. The proposed method was used to generate variation operators following a grammar-defined search space. This generation was guided by six mQAP instances featuring 10, 20, and 30 variables with two and three objectives, leveraging MOEA/D as its multi-objective optimizer. During the generation process, the hyper-heuristic exhibited consistent improvements in the HV of the population throughout the evolutionary process, demonstrating its ability to evolve increasingly effective operators over time. To validate the hyper-heuristic output, the generated operators were evaluated on sixteen unseen and diverse mQAPinstances. From experimental results, the evolved operators consistently outperformed standard ones regarding median HV in all test instances. Statistical tests further indicate that these evolved operators possess strong exploration and exploitation capabilities for problems with permutation-based solution representations and behave distinctly from conventional operators. Pairwise comparisons confirmed their superiority over human-designed recombination operators such as PMX and CX in HV performance. These results highlight the potential of automated operator design in effectively solving complex combinatorial optimization problems, such as the mQAP. Beyond this specific case, the proposed framework contributes to the field of automated operator design by introducing a new methodology applicable to multi-objective combinatorial optimization scenarios.