A decomposition-based memetic algorithm using helper objectives for shortwave radio broadcast resource allocation problem in China

Abstract Shortwave radio broadcast resource allocation (SRBRA) is an NP-hard combinatorial optimization problem with practical significance in many countries. The aim of SRBRA is to allocate radio programs to transmission devices so as to broadcast all radio programs felicitously with a maximized objective of total qualified monitoring sites. To solve such an issue presented by the State Administration of Press, Publication, Radio, Film and Television (SAPPRFT) in China, the authors propose a parallel multi-objective memetic algorithm based on helper objective assistance and decomposition technique, called pMMA-HD. Specifically, a multi-objective evolutionary optimization framework is used to maintain the diversity in a single objective problem, where the authors add a helper objective function on the diversity metric. Then, the decomposition method is performed to settle this transformational multi-objective problem effectively, and a diversity matrix is preserved in order to provide sufficient candidates for a decision maker to select from. To approach the pareto front, an efficient local search with a guided perturbation is integrated after the evolutionary process. Considering the natural characteristics of evolutionary algorithms (EAs), a thread-based parallel version of MMA-HD is carefully designed to improve the computational efficiency. Experiments are performed on real-world benchmarks to compare pMMA-HD with three categories of algorithms: one exact solver clasp, two canonical multi-objective algorithms and three local search methods. Afterwards, the experiments on parameters tuning are conducted based on the Taguchi method of design-of-experiment. Besides, the validation of strategies are investigated and the robustness of solutions is further analyzed. The experimental results on the real-world dataset validate the efficiency of pMMA-HD by updating 33 best-known solutions.