Subscribe Now Subscribe Today
Science Alert
 
Blue
   
Curve Top
Journal of Applied Sciences
  Year: 2010 | Volume: 10 | Issue: 4 | Page No.: 291-297
DOI: 10.3923/jas.2010.291.297
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Discrete Quantum-Behaved Particle Swarm Optimization for the Multi-Unit Combinatorial Auction Winner Determination Problem

Saeed Farzi

Abstract:
Combinatorial auctions are efficient mechanisms for allocating resource in complex marketplace. Winner determination, which is NP-complete, is the core problem in combinatorial auctions. In this study we introduce a discrete quantum-behaved particle swarm optimization algorithm with a penalty function for solving the winner determination problem. Particle swarm optimization is a population-based swarm intelligence algorithm. A quantum-behaved particle swarm optimization is also proposed by combining the classical particle swarm optimization philosophy and quantum mechanics to improve performance of particle swarm optimization. Since, potential solutions are presented in binary space, we use a discrete version of quantum-behaved particle swarm optimization that introduced to discrete binary search space. And the penalty function has been applied to overcome constraints. We evaluated our approach in two steps. First we showed that the discrete quantum-behaved particle swarm optimization is applicable to the problem. Second we compared our approach with CASS (Combinatorial Auction Structured Search), Casanova, Genetic algorithm and OMAGA (Orthogonal Multi-Agent Genetic Algorithm) on eight standard test tests used by other researchers. The results showed that the discrete quantum-behaved particle swarm optimization in comparison to other algorithms is better on five test sets worse on one test set and same on two test sets. Therefore, we could conclude that our approach for solving the multi-unit combinatorial auction winner determination problem is suitable and could find the best solutions.
PDF Fulltext XML References Citation Report Citation
 RELATED ARTICLES:
  •    A Novel Quantum-inspired Binary Gravitational Search Algorithm in Obtaining Optimal Power Quality Monitor Placement
How to cite this article:

Saeed Farzi , 2010. Discrete Quantum-Behaved Particle Swarm Optimization for the Multi-Unit Combinatorial Auction Winner Determination Problem. Journal of Applied Sciences, 10: 291-297.

DOI: 10.3923/jas.2010.291.297

URL: https://scialert.net/abstract/?doi=jas.2010.291.297

COMMENT ON THIS PAPER
 
 
 

 

 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 

Curve Bottom