An Optimization Heuristic Based on Non-Dominated Sorting and Tabu Search for the Fixed Spectrum Frequency Assignment Problem

Abstract

Frequency assignment for minimum interference is a fundamental problem in telecommunications networks. Combinatorial optimization heuristics are among the successful techniques employed to solve this problem. The heuristic proposed in this paper is a hybrid of the non-dominated sorting genetic algorithm-II and tabu search (TS) heuristics. Although several hybrid heuristics exist, in addition to the parameters of the metaheuristics, they also contain problem-specific parameters. The proposed heuristic does not have any problem-specific parameter. In each iteration, we apply TS to each element of the population to replace it with the best solution in its neighborhood. We select the elements for the population of the next generation using the principles of the non-dominated sorting. The non-dominated sorting considers two attributes of a solution: 1) interference (i.e., a measure of the violation of constraints) and 2) entropy (i.e., a measure of the diversity of the solutions in a population). Experimental results show that the proposed heuristic can produce solutions of quality better than four existing known heuristics. The gain of the proposed heuristic over a recently proposed hybrid heuristic is verified using the Wilcoxon statistical test. The convergence time of the proposed heuristic is also comparable with the existing heuristics.

Keywords

• Frequency assignment problem
• genetic algorithm
• tabu search
• heuristics
• non-dominated sorting
• combinatorial optimization