A Dynamic Hyper Heuristic Approach for Solving the Static Frequency Assignment Problem

This study proposes a novel approach to solve the minimum-order frequency assignment problem. This problem involves assigning a frequency to each request while satisfying a set of constraints and minimizing the number of used frequencies. This approach solves the static problem by modeling it as a dynamic problem through dividing this static problem into smaller sub-problems, which are then solved in turn in a dynamic process. The proposed approach can be thought of as an algorithm that combines multiple heuristics to solve hard combinatorial optimization problems. Such heuristics are called low level heuristics and are managed by hyper heuristic algorithm. Different mechanisms for selecting the low level heuristics are investigated. Several techniques are also used to make this approach in this study more efficient. One of these is using a lower bound on the number of frequencies that are required for a feasible solution to exist in each sub-problem, based on the underlying graph coloring model. These lower bounds ensure that the search focuses on parts of the solution space that are likely to contain feasible solutions. Overall, this approach showed competitive performance compared with other algorithms in the literature.