research-article

S-Race: a multi-objective racing algorithm

Authors:

Tiantian Zhang,

Michael Georgiopoulos,

Georgios C. AnagnostopoulosAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 1565 - 1572

https://doi.org/10.1145/2463372.2463561

Published: 06 July 2013 Publication History

Abstract

This paper presents a multi-objective racing algorithm, S-Race, which efficiently addresses multi-objective model selection problems in the sense of Pareto optimality. As a racing algorithm, S-Race attempts to eliminate candidate models as soon as there is sufficient statistical evidence of their inferiority relative to other models with respect to all objectives. This approach is followed in the interest of controlling the computational effort. S-Race adopts a non-parametric sign test to identify pair-wise domination relationship between models. Meanwhile, Holm's Step-Down method is employed to control the overall family-wise error rate of simultaneous hypotheses testing during the race. Experimental results involving the selection of superior Support Vector Machine classifiers according to 2 and 3 performance criteria indicate that S-Race is an efficient and effective algorithm for automatic model selection, when compared to a brute-force, multi-objective selection approach.

References

[1]

B. Adenso-Díaz and M. Laguna. Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research, 54:99--114, 2006.

Digital Library

[2]

S. Becker, J. Gottlieb, and T. Stützle. Applications of racing algorithms: An industrial perspective. In Lecture Notes in Computer Science, volume 3871, chapter Artificial Evolution, pages 271--283. Springer, 2005.

Digital Library

[3]

M. Birattari, T. Stützle, L. Paquete, and K. Varrentrapp. A racing algorithm for configuring metaheuristics. In GECCO'02 Proceedings of the Genetic and Evolutionary Computation Conference, pages 11--18, 2002.

Digital Library

[4]

M. Birattari, Z. Yuan, P. Balaprakash, and T. Stützle. F-race and iterated f-race: An overview. Technical report, IRIDIA, 2011.

[5]

C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:1--27, 2011.

Digital Library

[6]

M. Chiarandini, M. Birattari, K. Socha, and O. Rossi-doria. An effective hybrid algorithm for university course timetabling. J Sched, 9:403--432, 2006.

Digital Library

[7]

C. Cortes and V. N. Vapnik. Support-vector networks. Machine Learning, 20:273--297, 1995.

[8]

K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, 2009.

Digital Library

[9]

M. Duarte and Y. H. Hu. Vehicle classification in distributed sensor networks. Journal of Parallel and Distributed Computing, 64:826--838, 2004.

Digital Library

[10]

V. Heidrich-Meisner and C. Igel. Hoeffding and bernstein races for selecting policies in evolutionary direct policy search. In ICML '09 Proceedings of the 26th Annual International Conference on Machine Learning, pages 401--408, 2009.

Digital Library

[11]

Y. Hochberg and A. Tamhane. Multiple Comparison Procedures. New York: Wiley, 1987.

Digital Library

[12]

S. Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 2:65--70, 1979.

[13]

M. Horn and C. W. Dunnett. Power and sample size comparisons of stepwise fwe and fdr controlling test procedures in the normal many-one case. Recent Developments in Multiple Comparison Procedures, 47:48--64, 2004.

[14]

E. J. Hughes. Evolutionary multi-objective ranking with uncertainty and noise. Evolutionary Multi-criterion Optimization, 1999:329--343, 2001.

Digital Library

[15]

Y. Jin. Pareto-based multiobjective machine learning: An overview and case studies. IEEE Transactions on Systems, Man and Cybernetics, Part C: APplications and Reviews, 38:397--415, 2008.

Digital Library

[16]

H. Leather, M. O. Boyle, and B. Worton. Raced profiles: Efficient selection of competing compiler optimizations. In roceedings of the 2009 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 50--59, 2009.

Digital Library

[17]

S. Lessmann, R. Stahlbock, and S. Crone. Genetic algorithms for support vector machine model selection. In IJCNN '06. International Joint Conference on Neural Networks, pages 3063--3069, 2006.

[18]

M. Lopez-Ibanez and T. Stützle. Automatic configuration of multi-objective aco algorithms. In Proceedings of 7th International Conference, ANTS 2010, Brussels, Belgium, September 8--10, 2010., pages 95--106, 2010.

Digital Library

[19]

M. Lopez-Ibanez and T. Stützle. Automatically improving the anytime behaviour of optimisation algorithms. Technical report, IRIDIA, 2012.

[20]

O. Maron and A. Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. Advances in Neural Information Processing Systems, 6:59--66, 1994.

[21]

W. Mendenhall, D. D. Wackerly, and R. L. Scheaffer. Mathematical Statistics with Applications, chapter Nonparametric statistics, pages 674--679. PWS-Kent, 1989.

[22]

V. Mnih and C. Szepesvari. Empirical bernstein stopping. In Proceedings of the 25th International Conference on Machine Learning, 2008.

Digital Library

[23]

A. W. Moore. Efficient algorithms for minimizing cross validation error. In Proceedings of the Eleventh International Conference on Machine Learning, pages 190--198, 1994.

Digital Library

[24]

D. J. Newman, S. Hettich, C. L. Blake, and C. J. Merz. UCI repository of machine learning databases, 1998.

[25]

J. C. Platt. Advances in Kernel Methods - Support Vector Learning, chapter Fast training of support vector machines using sequential minimal optimization. MIT Press, 1998.

Digital Library

[26]

A. C. Tamhane. Multiple comparisons. In E. S. Ghosh and C. R. Rao, editors, Handbook of Statistics, pages 587--630. Elsevier Science, 1996.

[27]

J. Teich. Pareto-front exploration with uncertain objectives. Evolutionary Multi-criterion Optimization, 1999:314--328, 2001.

Digital Library

[28]

J.-Y. Wang. Application of support vector machines in bioinformatics. Master's thesis, National Taiwan University, 2002.

[29]

B. Yuan and M. Gallagher. Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In Parallel Problem Solving from Nature - PPSN VIII, 8th International Conference, pages 172--181, 2004.

Cited By

Karl FPielok TMoosbauer JPfisterer FCoors SBinder MSchneider LThomas JRichter JLang MGarrido-Merchán EBranke JBischl B(2023)Multi-Objective Hyperparameter Optimization in Machine Learning—An OverviewACM Transactions on Evolutionary Learning and Optimization10.1145/36105363:4(1-50)Online publication date: 5-Sep-2023
https://dl.acm.org/doi/10.1145/3610536
Eryoldaş YDurmuşoglu A(2022)A Literature Survey on Offline Automatic Algorithm ConfigurationApplied Sciences10.3390/app1213631612:13(6316)Online publication date: 21-Jun-2022
https://doi.org/10.3390/app12136316
Brownlee AEpitropakis MMulder JPaelinck MBurke E(2022)A systematic approach to parameter optimization and its application to flight schedule simulation softwareJournal of Heuristics10.1007/s10732-022-09501-828:4(509-538)Online publication date: 5-Jul-2022
https://doi.org/10.1007/s10732-022-09501-8
Show More Cited By

Index Terms

S-Race: a multi-objective racing algorithm
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms
      1. Statistical graphics

Recommendations

SPRINT Multi-Objective Model Racing
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Multi-objective model selection, which is an important aspect of Machine Learning, refers to the problem of identifying a set of Pareto optimal models from a given ensemble of models. This paper proposes SPRINT-Race, a multi-objective racing algorithm ...
Multi-Label Classification Based on Multi-Objective Optimization
Special Issue on Linking Social Granularity and Functions

Multi-label classification refers to the task of predicting potentially multiple labels for a given instance. Conventional multi-label classification approaches focus on single objective setting, where the learning algorithm optimizes over a single ...
Inverted PBI in MOEA/D and its impact on the search performance on multi and many-objective optimization
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

MOEA/D decomposes a multi-objective optimization problem into a number of single objective optimization problems. Each single objective optimization problem is defined by a scalarizing function using a weight vector. In MOEA/D, there are several ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 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: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
161
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Karl FPielok TMoosbauer JPfisterer FCoors SBinder MSchneider LThomas JRichter JLang MGarrido-Merchán EBranke JBischl B(2023)Multi-Objective Hyperparameter Optimization in Machine Learning—An OverviewACM Transactions on Evolutionary Learning and Optimization10.1145/36105363:4(1-50)Online publication date: 5-Sep-2023
https://dl.acm.org/doi/10.1145/3610536
Eryoldaş YDurmuşoglu A(2022)A Literature Survey on Offline Automatic Algorithm ConfigurationApplied Sciences10.3390/app1213631612:13(6316)Online publication date: 21-Jun-2022
https://doi.org/10.3390/app12136316
Brownlee AEpitropakis MMulder JPaelinck MBurke E(2022)A systematic approach to parameter optimization and its application to flight schedule simulation softwareJournal of Heuristics10.1007/s10732-022-09501-828:4(509-538)Online publication date: 5-Jul-2022
https://doi.org/10.1007/s10732-022-09501-8
Huang CLi YYao X(2020)A Survey of Automatic Parameter Tuning Methods for MetaheuristicsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.292159824:2(201-216)Online publication date: Apr-2020
https://doi.org/10.1109/TEVC.2019.2921598
Branke JZhang W(2019)Identifying efficient solutions via simulation: myopic multi-objective budget allocation for the bi-objective caseOR Spectrum10.1007/s00291-019-00561-0Online publication date: 23-Aug-2019
https://doi.org/10.1007/s00291-019-00561-0
Bezerra LLópez-Ibáñez MStützle T(2019)Automatic Configuration of Multi-objective Optimizers and Multi-objective ConfigurationHigh-Performance Simulation-Based Optimization10.1007/978-3-030-18764-4_4(69-92)Online publication date: 2-Jun-2019
https://doi.org/10.1007/978-3-030-18764-4_4
Branke JZhang WTao YHuschka TChick S(2016)Multiobjective ranking and selection based on hypervolumeProceedings of the 2016 Winter Simulation Conference10.5555/3042094.3042212(859-870)Online publication date: 11-Dec-2016
https://dl.acm.org/doi/10.5555/3042094.3042212
Branke JZhang WYang Tao (2016)Multio-bjective ranking and selection based on hypervolume2016 Winter Simulation Conference (WSC)10.1109/WSC.2016.7822148(859-870)Online publication date: Dec-2016
https://doi.org/10.1109/WSC.2016.7822148
Zhang TGeorgiopoulos MAnagnostopoulos G(2016)Multi-Objective Model Selection via RacingIEEE Transactions on Cybernetics10.1109/TCYB.2015.245618746:8(1863-1876)Online publication date: Aug-2016
https://doi.org/10.1109/TCYB.2015.2456187
Blot AHoos HJourdan LKessaci-Marmion MTrautmann H(2016)MO-ParamILS: A Multi-objective Automatic Algorithm Configuration FrameworkLearning and Intelligent Optimization10.1007/978-3-319-50349-3_3(32-47)Online publication date: 1-Dec-2016
https://doi.org/10.1007/978-3-319-50349-3_3
Show More Cited By

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