Research On Winner Determination Problem With Niche-based Particle Swarm Algorithm

With the rapid development of e-commerce,the number of products available to bidders in the auction market has increased dramatically,and the auction method has also gradually shifted from the traditional auction of a single homogenous item to the combinatorial auction of heterogeneous multi-items.Combinatorial Auction(CA)allows bidders to bid on the combination of multiple items based on the value of the association between items,which can increase the efficiency of the auction and reduce the risk of abortive auction.The Winner Determination Problem(WDP)is the core issue of combinatorial auction,which has been proved to be an NP-hard problem.The performance of the algorithm for solving the WDP problem directly affects the final revenue of the auctioneer.Particle Swarm Optimization(PSO)is a classical swarm intelligence evolutionary algorithm,and it has the advantages of strong interpretability,simple control parameters and easy implementation.It has been widely used to solve the NP-hard problem,so this paper selects the PSO algorithm to solve the WDP problem.In order to solve conflict between convergence and diversity in PSO algorithm,a Niche-Based Reverse-learning and Local-Learning Particle Swarm Algorithm(NRLPSO)is proposed.This paper has mainly done two parts of research work:(1)A niche-based reverse-learning and local-learning(NRLPSO)is proposed.Firstly,in order to improve the diversity of population and reduce probability of falling into local optimum,a reverse-learning mechanism was introduced to the PSO algorithm.When the algorithm is judged of local convergence,a reverse-learning mechanism is started.Secondly,In order to improve the accuracy and the convergence speed,an local-learning was introduced to the PSO algorithm.Different niches are adaptively generated through fuzzy clustering.The reverse-learning mechanism is used between niches to enhance the ability of the overall exploration of the algorithm.The simulated annealing method is used within the niche to enhance the local search ability of the algorithm.Finally,the algorithm performs comparison experiments on different dimensional benchmark functions,and analyzes the optimization performance of the algorithm,such as convergence speed and solution accuracy.The experimental results show that compared with the improved comparison PSO algorithm,the proposed NRLPSO has a better solution accuracy and stability.(2)Using the proposed algorithm to solve the WDP problem.Firstly,in order to reduce the difficulty of solving the WDP problem,the feasible solution space is preprocessed according to the value constraint relationship between bids.Secondly,because the feasible solution space of the WDP problem is discrete space,in order to keep the algorithm efficient and robust when dealing with the discrete optimization problem,mapping the velocity of the particles to 0 or 1 while maintaining the same way to update particles' speed and position with the continuous version of the PSO to solve the WDP problem.Finally,the CATS 2.0 software platform was used to generate test data of different scales based on L3 and L4 distributions.Comparison experiments showed that NRLPSO algorithm has higher accuracy in solving WDP problems.