A hybrid binary harmony search algorithm for solving the winner determination problem. (28th June 2019)

• Record Type: Journal Article
• Authors: Lin, Geng; Li, Zuoyong
• Is Part Of: International journal of innovative computing and applications. Volume 10:Number 1(2019)
• Page Start: 59
• Page End: 68
• Publication Date: 2019-06-28
• Subjects: harmony search algorithm -- local search -- winner determination problem -- combinatorial optimisation; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

Abstract

The winner determination problem (WDP) in combinatorial auctions is to determine an allocation of items to bidders such that each item is allocated to at most one bidder, and the auctioneer's revenue is maximised. This paper proposes a hybrid binary harmony search algorithm for the WDP. Firstly, to enhance the global search ability of the proposed algorithm, a modified harmony improvisation mechanism is developed with a modified memory consideration rule and an adaptive pitch adjustment scheme. Next, a repair operator is employed to guarantee the feasibility of the new candidate harmonies. Finally, a tabu search procedure is presented to improve the local search ability. These strategies make a good balance between intensification and diversification. In the experiments, the performance of the proposed algorithm is validated on five groups of 500 instances. Experimental results and comparisons show that the proposed algorithm is very efficient, and the tabu search procedure significantly improves the performance of the proposed algorithm.