Master-apprentice Evolutionary Algorithm For Maximum Weighted Set K-covering Problem

Among the variants of set cover problems,the maximum set k-covering problem(MKCP)has gained special research attentions in recent years.However,in real life,each variable of MKCP always needs to be labelled a corresponding numerical weight to describe the impact of being covered.Thus,the maximum weighted set k-covering problem(MWKCP)is proposed,which is NP-hard to be solved.So far,related researches mostly focus on MKCP.How to solve MWKCP efficiently can bring significant theoretical and practical values.This paper firstly formulates MWKCP and then introduces MWKCP in detail.After that,the master-apprentice algorithm(MAE)is applied to solve this problem.Specially,we design the recombination operator of MAE based on the path relinking method.The recombination operator can guide current solution search to the leading one to produce high-quality offspring.In addition,on the designing of local search,a new local search based on the bare bone firework is adopted in the algorithm.To effectively search the neighborhood of offspring,the new local search can transform its neighborhood structures by adaptively changing the explosion radius.Experiments on 150 instances show that the proposed algorithm outperforms CPLEX,RNKC,ABPSO and HBABC.Besides,the validation of strategies is investigated.Experimental results validate the efficiency of the path relinking method and the local search operator.