A decomposition-based memetic algorithm using helper objectives for shortwave radio broadcast resource allocation problem in China
A decomposition-based memetic algorithm using helper objectives for shortwave radio broadcast resource allocation problem in China
复制标题
DOI：
10.1016/j.asoc.2020.106251
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Yupeng Zhou;Mingjie Fan;Feifei Ma;Xin Xu;Minghao Yin
中科院分区：
文献类型：
--
作者：
Yupeng Zhou;Mingjie Fan;Feifei Ma;Xin Xu;Minghao Yin
短波广播资源分配问题(SRBRA)是一个在许多国家都具有实际意义的NP-Hard组合优化问题。SRBRA的目标是将无线电节目分配给传输设备，以便以最大限度地增加合格监测点的总数为目标，适当地广播所有无线电节目。针对国家新闻出版广电总局在《中国》中提出的这一问题，提出了一种基于辅助目标辅助和分解技术的并行多目标表情包算法PMMA-HD。具体地说，使用多目标进化优化框架来保持单目标问题的多样性，其中作者在多样性度量上增加了辅助目标函数。然后，采用分解方法有效地解决了这一转换多目标问题，并保留了一个多样性矩阵，以便为决策者提供足够的候选者进行选择。为了逼近Pareto前沿，在进化过程之后集成了一种带有引导扰动的高效局部搜索。针对进化算法本身的特点，设计了一种基于线程的MMA-HD并行化算法，以提高计算效率。在真实的基准测试上对PMMA-HD算法与三种算法进行了比较：一种精确的SolverCLASP算法，两种典型的多目标算法和三种局部搜索方法。然后，基于田口实验设计方法进行了参数整定实验。此外，还研究了策略的有效性，并进一步分析了解的稳健性。在真实数据集上的实验结果验证了PMMA-HD的有效性，更新了33个最知名的解。
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 solverclasp, 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.