×

zbMATH — the first resource for mathematics

Automatically improving the anytime behaviour of optimisation algorithms. (English) Zbl 1401.90274
Summary: Optimisation algorithms with good anytime behaviour try to return as high-quality solutions as possible independently of the computation time allowed. Designing algorithms with good anytime behaviour is a difficult task, because performance is often evaluated subjectively, by plotting the trade-off curve between computation time and solution quality. Yet, the trade-off curve may be modelled also as a set of mutually nondominated, bi-objective points. Using this model, we propose to combine an automatic configuration tool and the hypervolume measure, which assigns a single quality measure to a nondominated set. This allows us to improve the anytime behaviour of optimisation algorithms by means of automatically finding algorithmic configurations that produce the best nondominated sets. Moreover, the recently proposed weighted hypervolume measure is used here to incorporate the decision-maker’s preferences into the automatic tuning procedure. We report on the improvements reached when applying the proposed method to two relevant scenarios: (i) the design of parameter variation strategies for MAX-MIN Ant System and (ii) the tuning of the anytime behaviour of SCIP, an open-source mixed integer programming solver with more than 200 parameters.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
68W01 General topics in the theory of algorithms
68W40 Analysis of algorithms
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 10, 1, 0 1-41, (2009) · Zbl 1171.90476
[2] Adenso-Díaz, B.; Laguna, M., Fine-tuning of algorithms using fractional experimental design and local search, Operations Research, 540, 1, 0 99-114, (2006) · Zbl 1167.90654
[3] Aine, S.; Kumar, R.; Chakrabarti, P. P., Adaptive parameter control of evolutionary algorithms to improve quality-time trade-off, Applied Soft Computing, 90, 2, 0 527-540, (2009)
[4] Ansótegui, C.; Sellmann, M.; Tierney, K., A gender-based genetic algorithm for the automatic configuration of algorithms, (Gent, I. P., Principles and practice of constraint programming, CP 2009, LNCS, Vol. 5732, (2009), Springer), 142-157
[5] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences, (Rothlauf, F., Proceedings of GECCO 2009, (2009), ACM Press), 563-570
[6] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Hypervolume-based multiobjective optimization: theoretical foundations and practical implications, Theoretical Computer Science, 425, 0 75-103, (2012) · Zbl 1242.90205
[7] Auger, A.; Hansen, N., A restart CMA evolution strategy with increasing population size, (Proceedings of CEC 2005, (2005), IEEE Press), 1769-1776
[8] Balaprakash, P.; Birattari, M.; Stützle, T., Improvement strategies for the F-race algorithm: sampling design and iterative refinement, (Bartz-Beielstein, T.; etal., Hybrid metaheuristics, LNCS, Vol. 4771, (2007), Springer), 108-122
[9] Bartz-Beielstein, T., Experimental research in evolutionary computation: the new experimentalism, (2006), Springer · Zbl 1106.68037
[10] Bartz-Beielstein, T.; Lasarczyk, C.; Preuss, M., The sequential parameter optimization toolbox, (Bartz-Beielstein, T.; etal., Experimental methods for the analysis of optimization algorithms, (2010), Springer), 337-360 · Zbl 1208.90166
[11] Birattari, M., Tuning metaheuristics: A machine learning perspective, Studies in computational intelligence, Vol. 197, (2009), Springer · Zbl 1183.68464
[12] Birattari, M.; Stützle, T.; Paquete, L.; Varrentrapp, K., A racing algorithm for configuring metaheuristics 2002, (Langdon, W. B.; etal., Proceedings of GECCO, (2002), Morgan Kaufmann Publishers San Francisco, CA), 11-18
[13] Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated F-race: an overview, (Bartz-Beielstein, T.; etal., Experimental methods for the analysis of optimization algorithms, (2010), Springer), 311-336 · Zbl 1204.68280
[14] Branke, J.; Elomari, J., Simultaneous tuning of metaheuristic parameters for various computing budgets, (Krasnogor, N.; Lanzi, P. L., Proceedings of GECCO 2011, (2011), ACM Press), 263-264
[15] Chiarandini, M. (2005). Stochastic local search methods for highly constrained combinatorial optimisation problems. PhD thesis, FG Intellektik, FB Informatik, TU Darmstadt, Germany.
[16] Conover, W. J., Practical nonparametric statistics, (1999), John Wiley & Sons
[17] Coy, S. P.; Golden, B. L.; Runger, G. C.; Wasil, E. A., Using experimental design to find effective parameter settings for heuristics, Journal of Heuristics, 70, 1, 77-97, (2001) · Zbl 0967.90018
[18] Dean, T.; Boddy, M. S., An analysis of time-dependent planning, (Proceedings of the 7th national conference on artificial intelligence, AAAI-88, (1988), AAAI Press), 49-54
[19] den Besten, M. (2004). Simple metaheuristics for scheduling. PhD thesis, FB Informatik, TU Darmstadt, Germany.
[20] Dorigo, M.; Gambardella, L. M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 10, 1, 0 53-66, (1997)
[21] Dorigo, M.; Stützle, T., Ant colony optimization, (2004), MIT Press Cambridge, MA · Zbl 1092.90066
[22] Dréo, J., Using performance fronts for parameter setting of stochastic metaheuristics, (Rothlauf, F., GECCO (companion), (2009), ACM Press), 2197-2200
[23] Dubois-Lacoste, J.; López-Ibáñez, M.; Stützle, T., Automatic configuration of state-of-the-art multi-objective optimizers using the TP+PLS framework, (Krasnogor, N.; Lanzi, P. L., Proceedings of GECCO 2011, (2011), ACM Press), 2019-2026
[24] Eiben, A. E.; Michalewicz, Z.; Schoenauer, M.; Smith, J. E., Parameter control in evolutionary algorithms, (Lobo, F.; etal., Parameter setting in evolutionary algorithms, (2007), Springer), 19-46
[25] Eiben, A. E.; Smit, S. K., Parameter tuning for configuring and analyzing evolutionary algorithms, Swarm and Evolutionary Computation, 10, 1, 19-31, (2011)
[26] Fonseca, C. M.; Paquete, L.; López-Ibáñez, M., An improved dimension-sweep algorithm for the hypervolume indicator, (Proceedings of the 2006 congress on evolutionary computation (CEC 2006), (2006), IEEE Press Piscataway, NJ), 1157-1163
[27] Gagliolo, M.; Legrand, C., Algorithm survival analysis, (Bartz-Beielstein, T.; etal., Experimental methods for the analysis of optimization algorithms, (2010), Springer), 161-184 · Zbl 1214.68480
[28] Grunert da Fonseca, V.; Fonseca, C. M., The attainment-function approach to stochastic multiobjective optimizer assessment and comparison, (Bartz-Beielstein, T.; etal., Experimental methods for the analysis of optimization algorithms, (2010), Springer), 103-130 · Zbl 1206.90107
[29] Hoos, H. H., Programming by optimization, Communications of the ACM, 550, 2, 0 70-80, (2012)
[30] Hoos, H. H.; Stützle, T., Stochastic local search—foundations and applications, (2005), Morgan Kaufman Publishers San Francisco, CA · Zbl 1126.68032
[31] Hutter, F.; Hoos, H. H.; Leyton-Brown, K., Sequential model-based optimization for general algorithm configuration, (Learning and intelligent optimization, 5th international conference, LION 5, LNCS, (2011), Springer)
[32] Hutter, F.; Hoos, H. H.; Leyton-Brown, K.; Stützle, T., Paramils: an automatic algorithm configuration framework, Journal of Artificial Intelligence Research, 36, 267-306, (2009) · Zbl 1192.68831
[33] Johnson, D. S., McGeoch, L. A., Rego, C., & Glover, F. (2001). 8th DIMACS implementation challenge. http://www.research.att.com/dsj/chtsp/.
[34] KhudaBukhsh, A. R.; Xu, L.; Hoos, H. H.; Leyton-Brown, K., Satenstein: automatically building local search SAT solvers from components, (Boutilier, C., Proceedings of the twenty-first international joint conference on artificial intelligence (IJCAI-09), (2009), AAAI Press Menlo Park, CA), 517-524
[35] Knowles, J. D. (2005). A summary-attainment-surface palotting method for visualizing the performance of stochastic multiobjective optimizers. In Proceedings of the 5th international conference on intelligent systems design and applications (pp. 552-557).
[36] Knowles, J. D., Thiele, L., & Zitzler, E. (2006). A tutorial on the performance assessment of stochastive multiobjective optimizers. TIK-Report 214, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zürich, Switzerland, February 2006. Revised version.
[37] Leyton-Brown, K.; Pearson, M.; Shoham, Y., Towards a universal test suite for combinatorial auction algorithms, (Jhingran, A.; etal., ACM conference on electronic commerce (EC-00), (2000), ACM Press New York, NY), 66-76
[38] López-Ibáñez, M. & Stützle, T. (2012a). Automatically improving the anytime behaviour of optimisation algorithms. Technical Report TR/IRIDIA/2012-012, IRIDIA, Université Libre de Bruxelles, Belgium. · Zbl 1401.90274
[39] López-Ibáñez, M. & Stützle, T. (2012b). Automatically improving the anytime behaviour of optimisation algorithms: Supplementary material. http://iridia.ulb.ac.be/supp/IridiaSupp2012-011/.
[40] López-Ibáñez, M., Dubois-Lacoste, J., Stützle, T., & Birattari M. (2011). The irace package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium.
[41] López-Ibáñez, M.; Liao, T.; Stützle, T., On the anytime behavior of IPOP-CMA-ES, (Coello Coello, C. A.; etal., PPSN 2012, Part I, LNCS, Vol. 7491, (2012), Springer), 357-366
[42] López-Ibáñez, M.; Paquete, L.; Stützle, T., Exploratory analysis of stochastic local search algorithms in biobjective optimization, (Bartz-Beielstein, T.; etal., Experimental methods for the analysis of optimization algorithms, (2010), Springer), 209-222 · Zbl 1208.90154
[43] López-Ibáñez, M.; Stützle, T., Automatic configuration of multi-objective ACO algorithms, (Dorigo, M.; etal., Swarm intelligence, 7th international conference, ANTS 2010, LNCS, Vol. 6234, (2010), Springer), 95-106
[44] López-Ibáñez, M.; Stützle, T., The automatic design of multi-objective ant colony optimization algorithms, IEEE Transactions on Evolutionary Computation, 160, 6, 0 861-875, (2012)
[45] Loudni, S.; Boizumault, P., Combining VNS with constraint programming for solving anytime optimization problems, European Journal of Operational Research, 191, 705-735, (2008) · Zbl 1160.90661
[46] Maron, O.; Moore, A. W., The racing algorithm: model selection for lazy learners, Artificial Intelligence Research, 110, 1-5, 193-225, (1997)
[47] Maur, M.; López-Ibáñez, M.; Stützle, T., Pre-scheduled and adaptive parameter variation in MAX-MIN ant system, (Ishibuchi, H.; etal., Proceedings of the 2010 congress on evolutionary computation (CEC 2010), (2010), IEEE Press), 3823-3830
[48] Montes de Oca, M. A.; Stützle, T.; Birattari, M.; Dorigo, M., Frankenstein’s PSO: A composite particle swarm optimization algorithm, IEEE Transactions on Evolutionary Computation, 130, 5, 1120-1132, (2009)
[49] Nannen, V.; Eiben, A. E., A method for parameter calibration and relevance estimation in evolutionary algorithms, (Cattolico, M.; etal., Proceedings of GECCO 2006, (2006), ACM Press), 183-190
[50] Radulescu, A.; López-Ibáñez, M.; Stützle, T., Automatically improving the anytime behaviour of multiobjective evolutionary algorithms, (Purshouse, R. C.; etal., EMO 2013, LNCS, Vol. 7811, (2013), Springer), 825-840
[51] Stützle, T. (1997). MAX-MIN Ant System for the quadratic assignment problem. Technical Report AIDA-97-4, FG Intellektik, FB Informatik, TU Darmstadt, Germany, July 1997.
[52] Stützle T. (2002). ACOTSP: A software package of various ant colony optimization algorithms applied to the symmetric traveling salesman problem. http://www.aco-metaheuristic.org/aco-code/.
[53] Stützle, T.; Hoos, H. H., MAX-MIN ant system, Future Generation Computer Systems, 160, 8, 889-914, (2000)
[54] Stützle, T.; López-Ibáñez, M.; Pellegrini, P.; Maur, M.; Montes de Oca, M. A.; Birattari, M., Parameter adaptation in ant colony optimization, (Hamadi, Y.; Monfroy, E.; Saubion, F., Autonomous search, (2012), Springer Berlin, Germany), 191-215
[55] Wah, B. W.; Chen, Y. X., Optimal anytime constrained simulated annealing for constrained global optimization, (Dechter, R., Principles and practice of constraint programming, CP 2000, LNCS, Vol. 1894, (2000), Springer), 425-440 · Zbl 1044.68807
[56] Wessing, S.; Beume, N.; Rudolph, G.; Naujoks, B., Parameter tuning boosts performance of variation operators in multiobjective optimization, (Schaefer, R.; etal., Parallel problem solving from nature XI, LNCS, Vol. 6238, (2010), Springer), 728-737
[57] Woodruff, D. L.; Ritzinger, U.; Oppen, J., Research note: the point of diminishing returns in heuristic search, International Journal of Metaheuristics, 10, 3, 0 222-231, (2011) · Zbl 1306.90187
[58] Zilberstein, S., Using anytime algorithms in intelligent systems, AI Magazine, 170, 3, 0 73-83, (1996)
[59] Zitzler, E.; Brockhoff, D.; Thiele, L., The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration, (Obayashi, S.; etal., EMO 2007, LNCS, Vol. 4403, (2007), Springer), 862-876
[60] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto evolutionary algorithm, IEEE Transactions on Evolutionary Computation, 30, 4, 0 257-271, (1999)
[61] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation, 70, 2, 0 117-132, (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.