M-Race: A Racing Algorithm for the Tuning of Meta-Heuristics Based on Multiple Performance Objectives
Source abstract
Abstract
The performance of meta-heuristic algorithms on optimisation problems depend on the values of control parameters. These parameters greatly influence the behaviour of algorithms and affect the quality of the solutions. In order to optimise an algorithm for a specific problem set, a structured approach is followed to carefully select the appropriate control parameters. This approach is called control parameter tuning. Most existing tuning approaches focus on tuning an algorithm based on only one performance objective, such as accuracy or convergence speed. However, these objectives often work against each other, and improving the algorithm based on one objective can worsen the performance based on another objective. For example, obtaining a more accurate solution generally requires the algorithm to run for a longer time. The goal of this research is to develop a tuning approach that takes multiple performance objectives into account when tuning the control parameters of a meta-heuristic. The result of the tuning algorithm presents the experimenter with multiple values for control parameters, each representing different trade-offs between the various objectives. Experimental results demonstrate that M-race successfully discovered between 9 and 15 non-dominated parameter configurations across benchmark functions for both particle swarm optimisation (PSO) and differential evolution (DE) algorithms. These non-dominated parameter configurations represent balances among the tuning objectives used.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Artificial Intelligence in Games · Educational Games and Gamification · Robotic Path Planning Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Computer Science Division, Stellenbosch University, Stellenbosch 7600, South Africa
Department of Industrial Engineering, Stellenbosch University, Stellenbosch 7600, South Africa
GUST Engineering and Applied Innovation Research Center, Gulf University for Science and Technology, Mubarak Al-Abdullah 32093, Kuwait
References (30)
Show source-provided references
1. Tuning Optimization Algorithms Under Multiple Objective Function Evaluation Budgets10.1109/TEVC.2014.2322883 ↗
2. Ugolotti, R., and Cagnoni, S. (2014, January 12–16). Analysis of evolutionary algorithms using multi-objective parameter tuning. Proceedings of the Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.10.1145/2576768.2598226 ↗
3. Zhang, T., Georgiopoulos, M., and Anagnostopoulos, G. (2013, January 6–10). S-Race: A multi-objective racing algorithm. Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, Amsterdam, The Netherlands.10.1145/2463372.2463561 ↗
4. Ridge, E. (2007). Design of Experiments for the Tuning of Optimisation Algorithms, University of York.
5. Montgomery, D. (2020). Design and Analysis of Experiments, John Wiley & Sons.
6. Birattari, M., Yuan, Z., Balaprakash, P., and Stützle, T. (2010). F-Race and Iterated F-Race: An Overview. Experimental Methods for the Analysis of Optimization Algorithms, Springer.10.1007/978-3-642-02538-9_13 ↗
7. Conover, W. (1999). Practical Nonparametric Statistics, John Wiley & Sons.
8. Klazar, R., and Engelbrecht, A. (2014, January 6–11). Parameter optimization by means of statistical quality guides in F-Race. Proceedings of the IEEE Congress on Evolutionary Computation, Beijing, China.10.1109/CEC.2014.6900446 ↗
9. Bartz-Beielstein, T., Lasarczyk, C., and Preuß, M. (2005, January 2–5). Sequential parameter optimization. Proceedings of the IEEE Congress on Evolutionary Computation, Edinburgh, UK.
10. Nannen, V., and Eiben, A. (2007, January 25–28). Efficient relevance estimation and value calibration of evolutionary algorithm parameters. Proceedings of the IEEE Congress on Evolutionary Computation, Singapore.10.1109/CEC.2007.4424460 ↗
11. Mockus, J. (1989). The Bayesian Approach to Local Optimization. Bayesian Approach to Global Optimization: Theory and Applications, Springer.10.1007/978-94-009-0909-0 ↗
12. Brochu, E., Cora, V.M., and de Freitas, N. (2009). A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning. Technical Report UBC TR-2009-023, Department of Computer Science, University of British Columbia.
13. Roman, I., Ceberio, J., Mendiburu, A., and Lozano, J. (2016, January 24–29). Bayesian optimization for parameter tuning in evolutionary algorithms. Proceedings of the IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada.10.1109/CEC.2016.7744410 ↗
14. Algorithms for hyper-parameter optimization
15. Hyperband: A novel bandit-based approach to hyperparameter optimization
16. A Simple Sequentially Rejective Multiple Test Procedure
17. Zhang, T., Georgiopoulos, M., and Anagnostopoulos, G.C. (2015, January 11–15). SPRINT Multi-Objective Model Racing. Proceedings of the Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain.10.1145/2739480.2754791 ↗
18. Wald, A. (2004). Sequential Analysis, Courier Corporation.
19. Eberhart, R., and Kennedy, J. (1995, January 4–6). A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan.
20. Shi, Y., and Eberhart, R. (1998, January 4–9). A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation, Anchorage, AK, USA.
21. Mean and Variance of the Sampling Distribution of Particle Swarm Optimizers During Stagnation10.1109/TEVC.2008.2011744 ↗
22. Hoffmeister, F., and Bäck, Y. (1991). Genetic Algorithms and evolution strategies: Similarities and differences. Parallel Problem Solving from Nature, Springer.10.1007/BFb0029787 ↗
23. Ackley, D. (1987). A Connectionist Machine for Genetic Hillclimbing, Kluwer Academic Publishers.10.1007/978-1-4613-1997-9 ↗
24. Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T. (2000). A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. Parallel Problem Solving from Nature PPSN VI, Springer.10.1007/3-540-45356-3_83 ↗
25. On the distribution of points in a cube and the approximate evaluation of integrals10.1016/0041-5553(67)90144-9 ↗
26. Differential Evolution—A Simple and Efficient Heuristic for global Optimization over Continuous Spaces10.1023/A:1008202821328 ↗
27. Vanaret, C., Gotteland, J., Durand, N., and Alliot, J. (2020). Certified Global Minima for a Benchmark of Difficult Optimization Problems. arXiv.
28. Schwefel, H. (1981). Numerical Optimization of Computer Models, John Wiley & Sons, Inc.
29. On using the hypervolume indicator to compare Pareto fronts: Applications to multi-criteria optimal experimental design10.1016/j.jspi.2014.12.004 ↗
30. Mezura-Montes, E., Velázquez-Reyes, J., and Coello Coello, C. (2006, January 8–12). A Comparative Study of Differential Evolution Variants for Global Optimization. Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, WA, USA.10.1145/1143997.1144086 ↗