Path relinking for the fixed spectrum frequency assignment problem

作     者：Lai, Xiangjing Hao, Jin-Kao 

作者机构：Univ Angers LERIA F-49045 Angers 01 France 

出 版 物：《EXPERT SYSTEMS WITH APPLICATIONS》 (专家系统及其应用)

年 卷 期：2015年第42卷第10期

页      面：4755-4767页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：LigeRo project (Region of Pays de la Loire, France) PGMO project (Jacques Hadamard Mathematical Foundation) Region of Pays de la Loire (France) 

主　　题：Path relinking Population algorithm Heuristics Frequency assignment 

摘      要：The fixed spectrum frequency assignment problem (FS-FAP) is a highly relevant application in modern wireless systems. This paper presents the first path relinking (PR) approach for solving FS-FAP. We devise four relinking operators to generate intermediate solutions (or paths) and a tabu search procedure for local optimization. We also adopt a diversity-and-quality technique to maintain population diversity. To show the effectiveness of the proposed approach, we present computational results on the set of 42 benchmark instances commonly used in the literature and compare them with the current best results obtained by any other existing methods. By showing improved best results (new upper bounds) for 19 instances, we demonstrate the effectiveness of the proposed PR approach. We investigate the impact of the relinking operators and the population updating strategy. The ideas of the proposed could be applicable to other frequency assignment problems and search problems. (C) 2015 Elsevier Ltd. All rights reserved.