Steps toward the design of hybrid metaheuristics for the multi-objective frequency assignment problem in broadcasting

This paper presents steps toward the design of hybrid metaheuristics for solving multiobjective frequency assignment problem in broadcasting. At each step we compare the performances of our algorithm with the performance of operating frequency assignment in the field of TV broadcasting used nowadays in France and its neighbors. We use real-world benchmarks provided by TDF¹ as part of a research partnership. We start with Tabu Search (TS) then present Probabilistic Tabu Search (PTS), a variant of TS, which uses a probabilistic aspiration criterion. As it is interesting to get more than one solution, we use the genetic based NSGA-II method which offers this possibility. We design an original hybrid NSGA-II-PTS metaheuristic for solving this problem: Probabilistic Tabu Search (PTS) is used as a non-destructive mutation operator in the modified version (combinatorial version) of NSGA-II. We perform a similar study with Simulated Annealing (SA) and present an original hybrid metaheuristic NSGA-II-SA.