Abstract
In this paper, we propose a memetic algorithm for the optimal winner determination problem in combinatorial auctions. First, we investigate a new selection strategy based on both fitness and diversity to choose individuals to participate in the reproduction phase of the memetic algorithm. The resulting algorithm is enhanced by using a stochastic local search (SLS) component combined with a specific crossover operator. This operator is used to identify promising search regions while the stochastic local search performs an intensified search of solutions around these regions. Experiments on various realistic instances of the considered problem are performed to show and compare the effectiveness of our approach.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Andersson A, Tenhunen M, Ygge F (2000) Integer programming for combinatorial auction winner determination. In: Proceedings of 4th international conference on multi-agent systems. IEEE Computer Society Press, New York, pp 39–46
Bean JC (1994) Genetics and random keys for sequencing and optimization. ORSA J Comput 6(2): 154–160
Boughaci D, Drias H (2005) Taboo Search as an Intelligent Agent for Bid Evaluation. Int J Internet Enter Manage (IJIEM) 3(2): 170–186
Boughaci D, Drias H, Benhamou B (2004) Solving Max-SAT problems using a mimetic evolutionary metaheuristic. In: Proceedings of 2004 IEEE CIS 2004, pp 480–484
Burke E, Cowling P, DeCausmaecker Berghe GV (2001) A memetic approach to the nurse rostering problem. Appl Intell 15(3): 199–214
Caponio A, Cascella GL, Neri F, Salvatore N, Sumner M (2007) A fast adaptive memetic algorithm for online and offline control design of pmsm drives. IEEE Trans Syst Man Cybern B 37(1): 28–41
Collins J, Sundareswara R, Gini M, Mobasher B (2000) Bid selection strategies for multi-agent contracting in the presence of scheduling constraints. In: Moukas A, Sierra C, Ygge F (eds) Agent-mediated electronic commerce II. Lecture Notes in AI, vol 1788. Springer, Heidelberg
Dawkins R (1976) The selfish gene. Oxford University Press, Oxford
Franca PM, Mendes A, Moscato P (2001) A memetic algorithm for the total tardiness single machine scheduling problem. Eur J Oper Res 132(1): 224–242
Fujishima Y, Leyton-Brown K, Shoham Y (1999) Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. In: Sixteenth international joint conference on artificial intelligence, pp 48–53
Guo Y, Lim A, Rodrigues B, Zhu Y, (2004) Heuristics for a brokering set packing problem. In: Proceedings of eighth international symposium on artificial intelligence and mathematics, pp 10–14
Guo Y, Lim A, Rodrigues B, Zhu Y (2006) Heuristics for a bidding problem. Comp Oper Res 33(8): 2179–2188
Hart William E, Krasnogor N, Smith JE (eds) (2005) Recent Advances in Memetic Algorithms. In: Series: studies in fuzziness and soft computing, vol 166
Holland A , O’sullivan B (2004) Towards fast vickrey pricing using constraint programming. Artif Intell Rev 21(3–4): 335–352
Hoos HH (2002) An Adaptive Noise Mechanism for WalkSAT. In: Proceedings of the 19 th national conference on artificial intelligence AAAI/IAAI 2002, pp 655–660
Hoos HH, Boutilier C (2000) Solving combinatorial auctions using stochastic local search. In: Proceedings of the 17th national conference on artificial intelligence, pp 22–29
Lau HC, Goh YG (2002) An intelligent brokering system to support multi-agent web-based 4th-party logistics. In: Proceedings of the 14th international conference on tools with artificial intelligence, 2002, pp 54–61
Ishibuchi H, Narukawa K (2004) Some issues on the implementation of local search in evolutionary multi-objective optimization. Proc GECCO 1: 1246–1258
Ishibuchi H, Yoshida T, Murata T (2003) ’Balance between genetic search and local search in memetic algorithms for multi-objective permutation flowshop scheduling. IEEE Trans Evolut Comput 7(2): 204–223
Leyton-Brown K, Pearson M, Shoham Y (2000a) Towards a universal test suite for combinatorial auction algorithms. In: ACM conference on electronic commerce, pp 66–76
Leyton-Brown K, Tennenholtz M, Shoham Y (2000b) An algorithm for multi-unit combinatorial auctions. In: Proceedings of the 17th national conference on artificial intelligence, Austin, Games-2000, Bilbao, and ISMP-2000, Atlanta
McAfee R, McMillan PJ (1987) Auctions and bidding. J Econ Lit 25: 699–738
Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. In: Caltech concurrent computation program, C3P Report 826
Neri F, Toivanen J, Cascella G, Yew-Soon Ong (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE/ACM Trans Comput Biol Bioinf 4(2): 264–278
Nisan N (2000) Bidding and allocation in combinatorial auctions. In: Proceedings of ACM conference on electronic commerce (EC’00). ACM SIGecom, ACM Press, Minneapolis, October, pp 1–12
Ong YS, Lim MH, Zhu N, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern B 36(1): 141–152
Ong YS, Krasnogor N, Ishibuchi H (eds) (2007) Special Issue on Memetic Algorithms. IEEE Trans Syst Man Cybern B 37(1)
Rothkopf MH, Pekee A, Ronald M (1998) Computationally manageable combinatorial auctions. Manag Sci 44(8): 1131–1147
Sandholm T (1999) Algorithms for optimal winner determination in combinatorial auctions. Artif Intell 135(1–2): 1–54
Sandholm T (2006) Optimal winner determination algorithms. In: Cramton P et al (ed) Combinatorial auctions. MIT Press, Cambridge
Sandholm T, Suri S, (2000) Improved optimal algorithm for combinatorial auctions and generalizations. In: Proceedings of the 17th national conference on artificial intelligence, pp 90–97
Sandholm T, Suri S, Gilpin A, Levine D (2001) CABoB: a fast optimal algorithm for combinatorial auctions. In: Proceedings of the international joint conferences on artificial intelligence, pp 1102–1108
Tang M, Yao X (2007) A memetic algorithm for VLSI floorplanning. IEEE Trans Syst Man Cybern B 37(1): 62–69
Tang J, Lim MH, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11(9): 873–888
Vries de S, Vohra R (2003) Combinatorial auctions a survey. INFORMS J Comput 15: 284–309
Zhou Z, Ong YS, Lim MH, Lee BS (2007) Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Comput 11(10): 957–971
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boughaci, D., Benhamou, B. & Drias, H. A memetic algorithm for the optimal winner determination problem. Soft Comput 13, 905–917 (2009). https://doi.org/10.1007/s00500-008-0355-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-008-0355-3