Title: A hybrid binary harmony search algorithm for solving the winner determination problem

Authors: Geng Lin; Zuoyong Li

Addresses: Collaborative Innovation Center of IoT Industrialization and Intelligent Production, Minjiang University, Fuzhou, China; College of Mathematics and Data Science, Minjiang University, Fuzhou, China ' Fujian Provincial Key Laboratory of Information Processing and Intelligent Control, Minjiang University, Fuzhou, China

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.

Keywords: harmony search algorithm; local search; winner determination problem; combinatorial optimisation.

DOI: 10.1504/IJICA.2019.100547

International Journal of Innovative Computing and Applications, 2019 Vol.10 No.1, pp.59 - 68

Received: 14 Aug 2018
Accepted: 19 Mar 2019
Published online: 29 Jun 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article