Parallel algorithm portfolios with adaptive resource allocation strategy. (English) Zbl 07822726
Summary: Algorithm portfolios are multi-algorithmic schemes that combine a number of solvers into a joint framework for solving global optimization problems. A crucial part of such schemes is the resource allocation process that is responsible for assigning computational resources to the constituent algorithms. We propose a resource allocation process based on adaptive decision-making procedures. The proposed approach is incorporated in algorithm portfolios composed of three essential types of numerical optimization algorithms, namely gradient-based, direct search, and swarm intelligence algorithms. The designed algorithm portfolios are experimentally demonstrated on a challenging optimization problem for different dimensions and experimental settings. The accompanying statistical analysis offers interesting conclusions and insights on the performance of the algorithm portfolio compared to its constituent algorithms, as well as on the effect of its parameters.
MSC:
| 68Qxx | Theory of computing |
Keywords:
algorithm portfolios; adaptive pursuit; resource allocation; global optimization; metaheuristicsReferences:
| [1] | Almakhlafi, A., Knowles, J.: Systematic construction of algorithm portfolios for a maintenance scheduling problem. In: IEEE Congress On Evolutionary Computation, pp. 245-252. Cancun, Mexico (2013) |
| [2] | Battiti, R.; Mascia, F.; Stützle, T.; Birattari, M.; Hoos, HH, An algorithm portfolio for the sub-graph isomorphism problem, Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, International Workshop, SLS, 106-120, 2007, New York: Springer, New York · Zbl 1134.68494 |
| [3] | Calderín, JF; Masegosa, AD; Pelta, DA, An algorithm portfolio for the dynamic maximal covering location problem, Memet. Comput., 9, 141-151, 2016 · doi:10.1007/s12293-016-0210-5 |
| [4] | Clerc, M.; Kennedy, J., The particle swarm-explosion, stability, and convergence in a multidimensional complex space, IEEE Trans. Evol. Comput., 6, 1, 58-73, 2002 · doi:10.1109/4235.985692 |
| [5] | Goldberg, DE, Probability matching, the magnitude of reinforcement, and classifier system bidding, Mach. Learn., 5, 407-425, 1990 · doi:10.1007/BF00116878 |
| [6] | Huberman, BA; Lukose, RM; Hogg, T., An economics approach to hard computational problems, Science, 27, 51-53, 1997 · doi:10.1126/science.275.5296.51 |
| [7] | Loreggia, A., Malitsky, Y., Samulowitz, H., Saraswat, V.: Deep learning for algorithm portfolios. In: Thirtieth AAAI Conference on Artificial Intelligence, pp. 1280-1286. Phoenix, Arizona(2016) |
| [8] | Müller, CL; Sbalzarini, IF, Energy landscapes of atomic clusters as black box optimization benchmarks, Evol. Comput., 20, 4, 543-573, 2012 · doi:10.1162/EVCO_a_00086 |
| [9] | Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 4, 308-313, 1965 · Zbl 0229.65053 · doi:10.1093/comjnl/7.4.308 |
| [10] | Nocedal, J.; Wright, SJ, Numerical Optimization, 2006, New York: Springer, New York · Zbl 1104.65059 |
| [11] | Pardalos, PM; Shalloway, D.; Xue, G., Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding, DIMACS-Series in Discrete Mathematics and Theoretical Computer Science, 1996, Providence: AMS, Providence · Zbl 0831.00024 |
| [12] | Parsopoulos, KE; Vrahatis, MN, Particle Swarm Optimization and Intelligence: Advances and Applications, 2010, New York: Information Science Publishing (IGI Global), New York · doi:10.4018/978-1-61520-666-7 |
| [13] | Peng, F.; Tang, K.; Chen, G.; Yao, X., Population-based algorithm portfolios for numerical optimization, IEEE Trans. Evol. Comput., 14, 5, 782-800, 2010 · doi:10.1109/TEVC.2010.2040183 |
| [14] | Rice, JR, The algorithm selection problem, Adv. Comput., 15, 65-118, 1976 · doi:10.1016/S0065-2458(08)60520-3 |
| [15] | Shukla, N., Dashora, Y., Tiwari, M., Chan, F., Wong, T.: Introducing algorithm portfolios to a class of vehicle routing and scheduling problem. In: Operations and Supply Chain Management (OSCM 2007), pp. 1015-1026. Bangkok, Thailand (2007) |
| [16] | Souravlias, D.; Parsopoulos, KE; Alba, E.; Lübbecke, M., Parallel algorithm portfolio with market trading-based time allocation, Operations Research Proceedings 2014, 567-574, 2016, New York: Springer, New York · Zbl 1341.90153 · doi:10.1007/978-3-319-28697-6_79 |
| [17] | Souravlias, D.; Parsopoulos, KE; Kotsireas, IS, Circulant weighing matrices: a demanding challenge for parallel optimization metaheuristics, Optim. Lett., 10, 6, 1303-1314, 2016 · Zbl 1353.90132 · doi:10.1007/s11590-015-0927-y |
| [18] | Souravlias, D.; Parsopoulos, KE; Meletiou, GC, Designing bijective S-boxes using algorithm portfolios with limited time budgets, Appl. Soft Comput., 59, 475-486, 2017 · doi:10.1016/j.asoc.2017.05.052 |
| [19] | Souravlias, D.; Parsopoulos, KE; Kotsireas, IS; Pardalos, PM, Algorithm Portfolios: Advances, Applications, and Challenges. Springer Briefs in Optimization, 2021, New York: Springer, New York · Zbl 07312877 · doi:10.1007/978-3-030-68514-0 |
| [20] | Tang, K.; Peng, F.; Chen, G.; Yao, X., Population-based algorithm portfolios with automated constituent algorithms selection, Inf. Sci., 279, 94-104, 2014 · doi:10.1016/j.ins.2014.03.105 |
| [21] | Thathachar, MAL; Sastry, PS, A class of rapidly converging algorithms for learning automata, IEEE Trans. Syst. Man Cybern., 15, 168-175, 1985 · Zbl 0572.68046 · doi:10.1109/TSMC.1985.6313407 |
| [22] | Thierens, D.: An adaptive pursuit strategy for allocating operator probabilities. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO’05), pp. 1539-1546. ACM (2005) |
| [23] | Wawrzyniak, J.; Drozdowski, M.; Sanlaville, É., Selecting algorithms for large berth allocation problems, Eur. J. Oper. Res., 283, 3, 844-862, 2020 · Zbl 1441.90069 · doi:10.1016/j.ejor.2019.11.055 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
