A hybrid binary particle swarm optimization with tabu search for the set-union knapsack problem. (30th November 2019)

• Record Type: Journal Article
• Authors: Lin, Geng; Guan, Jian; Li, Zuoyong; Feng, Huibin
• Is Part Of: Expert systems with applications. Volume 135(2019)
• Page Start: 201
• Page End: 211
• Publication Date: 2019-11-30
• Subjects: Set-union knapsack problem -- Particle swarm optimization -- Local search -- Heuristic -- Binary programming; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.06.007
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A hybrid binary particle swarm optimization is proposed. Applying an adaptive penalty function as fitness function. Using a tabu search procedure to improve solution quality. Presenting a tabu based mutation procedure to achieve diversification. We find new best solutions for 28 out of 30 instances. Abstract: The set-union knapsack problem (SUKP) is a generalization of the standard 0–1 knapsack problem. It is NP-hard, and has several industrial applications. Several approximation and heuristic approaches have been previously presented for solving the SUKP. However, the solution quality still needs to be enhanced. This work develops a hybrid binary particle swarm optimization with tabu search (HBPSO/TS) to solve the SUKP. First, an adaptive penalty function is utilized to evaluate the quality of solutions during the search. This method endeavours to explore the boundary of the feasible solution space. Next, based on the characteristics of the SUKP, a novel position updating procedure is designed. The newly generated solutions obtain the good structures of previously found solutions. Then, a tabu based mutation procedure is introduced to lead the search to enter into new hopeful regions. Finally, we design a tabu search procedure to improve the exploitation ability. Furthermore, a gain updating strategy is employed to reduce the solution time. The HBPSO/TS is tested on three sets of 30 benchmark instances, and comparisons with current state-of-the-art algorithms are performed. Experimental results show that HBPSO/TS performs much better than the other algorithms in terms of solution quality. Moreover, HBPSO/TS improves new best results at 28 out of the 30 instances. The impact of the main parts of the HBPSO/TS is also experimentally investigated.