More Web Proxy on the site http://driver.im/

short-paper

Using messy genetic algorithms for solving the winner determination problem

Authors:

Madalina Raschip,

Henri LuchianAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

Pages 1825 - 1832

https://doi.org/10.1145/1830761.1830810

Published: 07 July 2010 Publication History

Abstract

The paper presents a study on the application of messy genetic algorithms for the winner determination problem in the combinatorial auction realm. Messy genetic algorithms operate explicitly on building blocks in order to obtain good solutions. Since the winner determination is a constrained problem, the Ordering Messy Genetic Algorithm is used in order to preserve the validity of chromosomes. Experiments on instances generated with the CATS system are presented to illustrate and compare the effectiveness of the approach. The approach is compared against a simple genetic algorithm, which is a random-key genetic algorithm. Other well-known algorithms from literature are used in experiments. Conclusions are drawn on the advantages of using a messy genetic algorithm for this problem.

References

[1]

A. Andersson, M. Tenhunen, and F. Ygge. Integer programming for combinatorial auction winner determination. In 4th Internationl Conference on Multiagent Systems, pages 39--46, 2000.

Digital Library

[2]

J. Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154--160, 1994.

[3]

M. Berkelaar. lp_solve - version 5.5. Technical report, Eindhoven University of Technology. http://sourceforge.net/projects/lpsolve/.

[4]

D. Boughaci, B. Benhamou, and H. Drias. A memetic algorithm for the optimal winner determination problem. Soft Computing, 13(8-9):905--917, 2009.

Digital Library

[5]

P. Fenton and P. Walsh. A comparison of messy ga and permutation based ga for job shop scheduling. In Conference on Genetic and Evolutionary Computation, pages 1593--1594, 2005.

Digital Library

[6]

Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. In 16th International Joint Conference on Artificial Intelligence, pages 48--53, 1999.

Digital Library

[7]

D. Goldberg, K. Deb, H. Kargupta, and G. Harik. Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In 5h International Conference on Genetic Algorithms, pages 56--64, 1993.

Digital Library

[8]

D. Goldberg, B. Korb, and K. Deb. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems, 3(5):493--530, 1989.

[9]

J. Gottlieb. Permutation-based evolutionary algorithms for multidimensional knapsack problems. ACM symposium on Applied computing, 1:408--414, 2000.

Digital Library

[10]

Y. Guo, A. Lim, B. Rodrigues, and Y. Zhu. Heuristics for a bidding problem. Computers and Operations Research, 33(8):2179--2188, 2006.

Digital Library

[11]

H. Hoos and C. Boutilier. Solving combinatorial auctions using stochastic local search. In 17th National Conference on Artificial Intelligence, pages 22--29, 2000.

Digital Library

[12]

H. Kargupta. SEARCH, polynomial complexity, and the fast messy genetic algorithm. Technical Report 95008, University of Illinois at Urbana-Champaign, Urbana, IL, 1995.

[13]

D. Knjazew and D. E. Goldberg. Omega - ordering messy ga: Solving permutation problems with the fast genetic algorithm and random keys. In Genetic and Evolutionary Computation Conference (GECCO-2000), pages 181--188, 2000.

[14]

J. Ledyard, M. Olson, D. Porter, J. Swanson, and D. Torma. The first use of a combined-value auction for transportation services. Interfaces, 34:4--12, 2002.

Digital Library

[15]

K. Leyton-Brown, M. Pearson, and Y. Shoham. Towards a universal test suite for combinatorial auction algorithms. In 2nd ACM conference on Electronic Commerce, pages 66--76, 2000.

Digital Library

[16]

Z. Michalewicz. A survey of constraint handling techniques in evolutionary computation methods. In 4th Anual Conference on Evolutionary Programming, pages 135--155, 1995.

[17]

N. Nisan. Bidding and allocation in combinatorial auctions. In ACM Conference on Electronic Commerce, pages 1--12, 2000.

Digital Library

[18]

J. Pfeiffer and F. Rothlauf. Analysis of greedy heuristics and weight-coded eas for multidimensional knapsack problems and multi-unit combinatorial auctions. In 9th annual Conference on Genetic and Evolutionary Computation, pages 1529--1529, 2007.

Digital Library

[19]

M. Rothkopf, A. Pekec, and R. Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8):1131--1147, 1998.

Digital Library

[20]

T. Sandholm, S. Suri, A. Gilpin, and D. Levine. Cabob: a fast optimal algorithm for combinatorial auctions. In International Joint Conferences on Artificial Intelligence, pages 1102--1108, 2001.

Digital Library

[21]

R. Vohra and S. de Vries. Combinatorial auctions: A survey. INFORMS Journals of Computing, 15(3):284--309, 2003.

Digital Library

[22]

W. Walsh, M. Wellman, and F. Ygge. Combinatorial auctions for supply chain formation. In ACM Conference on Electronic Commerce, pages 260--269, 2000.

Digital Library

[23]

E. Zurel and N. Nisan. An efficient approximate allocation algorithm for combinatorial auctions. In 3rd ACM conference on Electronic Commerce, pages 125--136, 2001.

Digital Library

Cited By

Taghaddos MMohamed YAbouRizk STaghaddos HHermann U(2021)Enhanced resource scheduling framework for industrial construction projectsProceedings of the Winter Simulation Conference10.5555/3522802.3522993(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522993
Taghaddos MMohamed YAbouRizk STaghaddos HHermann U(2021)Enhanced Resource Scheduling Framework For Industrial Construction Projects2021 Winter Simulation Conference (WSC)10.1109/WSC52266.2021.9715359(1-12)Online publication date: 12-Dec-2021
https://doi.org/10.1109/WSC52266.2021.9715359

Index Terms

Using messy genetic algorithms for solving the winner determination problem
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Genetic algorithms for task scheduling problem

The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several genetic algorithms have been developed to solve this ...
Neural network crossover in genetic algorithms using genetic programming
Abstract
The use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...
An approach to solve winner determination in combinatorial reverse auctions using genetic algorithms
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

Nowadays, winner determination problem is one of the main challenges in the domain of real-time applications such as combinatorial reverse auctions. To determine the winner(s) in combinatorial reverse auctions, in our previous work, we have proposed a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

July 2010

1496 pages

ISBN:9781450300735

DOI:10.1145/1830761

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
182
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Taghaddos MMohamed YAbouRizk STaghaddos HHermann U(2021)Enhanced resource scheduling framework for industrial construction projectsProceedings of the Winter Simulation Conference10.5555/3522802.3522993(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522993
Taghaddos MMohamed YAbouRizk STaghaddos HHermann U(2021)Enhanced Resource Scheduling Framework For Industrial Construction Projects2021 Winter Simulation Conference (WSC)10.1109/WSC52266.2021.9715359(1-12)Online publication date: 12-Dec-2021
https://doi.org/10.1109/WSC52266.2021.9715359

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents