Parameters tuning of evolutionary algorithm for the orienteering problem

• Autorzy: Ostrowski K.

Warianty tytułu

PL

Kalibracja parametrów algorytmu ewolucyjnego rozwiązującego Orienteering Problem

• Języki publikacji: EN

Abstrakty

EN

Various classes of algorithms solving optimization problems have some set of parameters. Setting them to appropriate values can be as important to results quality as choosing right algorithm components. Parameter calibration can be a complex optimization problem itself and many meta-algorithms were proposed to deal with it in a more automatic way. This paper presents automatic parameter tuning of an evolutionary algorithm solving the Orienteering Problem. ParamsILS method was chosen as a tuner. Obtained results show the importance of appropriate parameter setting in evolutionary algorithms: tuned algorithm achieved very high-quality solutions on known Orienteering Problem benchmarks.

PL

Różne klasy algorytmów rozwiązujących problemy optymalizacyjne posiadają zestawy parametrów. Ustawienie odpowiednich wartości parametrów może być równie ważne, co dobór odpowiednich komponentów algorytmu. Kalibracja parametrów sama w sobie może być skomplikowanym problemem optymalizacyjnym i wiele meta-algorytmów zostało zaproponowanych by przeprowadzać ten proces automatycznie. Artykuł prezentuje automatyczną kalibrację parametrów algorytmu ewolucyjnego rozwiązującego Orienteering Problem. W tym celu wybrano metodę ParamsILS. Otrzymane rezultaty ukazują jak ważny jest odpowiedni dobór parametrów: algorytm po kalibracji uzyskał bardzo wysokiej jakości rozwiązania dla znanych sieci testowych.

Słowa kluczowe

EN

parameter tuning; evolutionary algorithms; Orienteering Problem

PL

kalibracja parametrów; algorytmy ewolucyjne; Orienteering Problem

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Advances in Computer Science Research
• Rocznik: 2015
• Tom: Nr 12
• Strony: 53--78
• Opis fizyczny: Bibliogr. 39 poz., rys., tab.

Twórcy

autor

Ostrowski K.

• Faculty of Computer Science, Bialystok University of Technology, Białystok, Poland

Bibliografia

• [1] Croes, G. A.: A method for solving traveling salesman problems, Operations Research, vol. 6, 791-812, 1958.
• [2] Christofides, N., Mingozzi, A., Toth, P.: The Vehicle Routing Problem. Combinatorial Optimization, 315-338, 1979.
• [3] Tsiligirides, T.: Heuristic methods applied to orienteering. Journal of the Operational Research Society, vol. 35 (9), 797-809, 1984.
• [4] Golden, B., Levy, L., Vohra, R.: The orienteering problem. Naval Research Logistics, vol. 34, 307-318, 1987.
• [5] Baker, J.E.: Reducing Bias and Inefficiency in the Selection Algorithm. Proceedings of the Second International Conference on Genetic Algorithms and their Application, Hillsdale, New Jersey: L. Erlbaum Associates, 14-21, 1987.
• [6] Reinelt, G.: TSPLIB - A Travelling Salesman Problem Library. ORSA Journal of Computing, vol. 3, 155-165, 1991.
• [7] Ramesh, R., Brown, K.: An efficient four-phase heuristic for the generalized orienteering problem. Computers and Operations Research. vol 18, 151-165, 1991.
• [8] Ramesh, R., Yoon, Y., Karwan, M.: An optimal algorithm for the orienteering tour problem. ORSA Journal on Computing, vol. 4, 155-165, 1992.
• [9] Mahfoud, S.W.: Crowding and preselection revisited. Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN II), Brussels, Belgium, 1992. Elsevier, Amsterdam, The Netherlands, 27-36, 1992.
• [10] Taguchi, G., Yokoyama, T.: Taguchi Methods: Design of Experiments, ASI Press, 1993.
• [11] Chao, I., Golden, B., Wasil, E.: Theory and methodology - a fast and effective heuristic for the orienteering problem. European Journal of Operational Research, vol. 88, 475-489, 1996.
• [12] Gendreau, M., Laporte, G., Semet, F.: A branch-and-cut algorithm for the undirected selective traveling salesman problem, Networks, vol. 32(4), 263-273, 1998.
• [13] Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, vol. 106, 539-545, 1998.
• [14] Fischetti, M., Salazar, J., Toth, P.: Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, vol. 10, 133-148, 1998.
• [15] Feillet, D., Dejax, P., Gendreau, M.: Traveling Salesman Problems With Profits, An Overview. Transportation Science, vol. 38, 188-205, 2001.
• [16] Tasgetiren, M.: A genetic algorithm with an adaptive penalty function for the orienteering problem. Journal of Economic and Social Research, vol. 4 (2), 1- 26. 2001.
• [17] Myers, R., Hancock, E.A.: Empirical modelling of genetic algorithms, Evolutionary Computation, vol. 9, 461-493, 2001.
• [18] 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, vol. 7, 77-97, 2001.
• [19] Bartz-Beielstein, T., Parsopoulos, K., Vrahatis, M.: Analysis of Particle Swarm Optimization Using Computational Statistics, in Chalkis (Ed.), Proceedings of the International Conference of Numerical Analysis and Applied Mathematics (ICNAAM 2004), Wiley, pp. 34-37, 2004.
• [20] Ramos, I., Goldbarg, R., Goldbarg, E., Neto, A.: Logistic regression for parameter tuning on an evolutionary algorithm, in: Proceedings of the 2005 IEEE Congress on Evolutionary Computation IEEE Congress on Evolutionary Computation, IEEE Press, Edinburgh, UK, vol. 2, 1061-1068, 2005.
• [21] Birattari, M.: Tuning Metaheuristics, Springer, 2005.
• [22] Sokolov, A., Whitley, D.: Unbiased tournament selection, Proceedings of Genetic and Evolutionary Computation Conference. ACM Press, 1131-1138, 2005.
• [23] Adenso-Diaz, B., Laguna, M.: Fine-tuning of algorithms using fractional experimental designs and local search, Oper. Res. , vol. 54, 99-114, 2006.
• [24] Balaprakash, P., Birattari, M., Stutzle, T.: Improvement strategies for the FRace algorithm: Sampling design and iterative refinementace algorithm: Sampling design and iterative refinement, in: T. Bartz-Beielstein, M. Blesa Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, M. Sampels (Eds.), Hybrid Metaheuristics, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, vol. 4771, 108-122, 2007.
• [25] Nannen, V., Eiben, A. E.: Relevance Estimation and Value Calibration of Evolutionary Algorithm Parameters, in: M. M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, 1034?1039, 2007.
• [26] Jozefowiez, N., Glover, F., Laguna, M.: Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits. Journal of Mathematical Modelling and Algorithms, vol. 7, 177-195, 2008.
• [27] Wang Q.,Sun X., Golden B. L. and Jia J.,: Using artificial neural networks to solve the orienteering problem, emph Annals of Operations Research, vol.61, 111-120, 2008.
• [28] Schilde, M., Doerner, K., Hartl, R., Kiechle, G.: Metaheuristics for the biobjective orienteering problem. Swarm Intelligence, vol. 3, 179-201, 2009.
• [29] Vansteenwegen, P., Souffriau, W., Vanden Berghe, G. and Oudheusden, D.V.: A guided local search metaheuristic for the team orienteering problem. European Journal of the Operational Research, vol. 196(1), 118-127, 2009.
• [30] Hutter, F., Hoos, H.H., Leyton-Brown, K., Stutzle, T.: ParamILS: an automatic algorithm configuration framework, Journal of Artificial Intelligence Research, vol. 36, 267-306, 2009.
• [31] Souffriau, W., Vansteenwegen, P., Vanden Berghe, G. and Oudheusden, D.V.: A path relinking approach for the team orienteering problem, Computers and Operations Research, vol. 37, 1853-1859, 2010.
• [32] Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: The City Trip Planner: An expert system for tourists, Expert Systems with Applications, vol. 38(6), 6540-6546, 2011.
• [33] Ostrowski, K, Koszelew, J.: The comparison of genetic algorithm which solve orienteering problem using complete and incomplete graph, Zeszyty Naukowe, Politechnika Bialostocka. Informatyka, vol. 8 61-77, 2011.
• [34] Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K., Zabielski, P.: Genetic algorithm solving orienteering problem in large networks, Frontiers in Artificial Intelligence and Applications, vol. 243, 28-38, 2012.
• [35] Campos, V., Marti, R.,Sanchez-Oro, J., Duarte, A.: Grasp with Path Relinking for the Orienteering Problem. Journal of the Operational Research Society, vol. 156, 1-14, 2013.
• [36] Koszelew. J., Ostrowski. K.: A Genetic Algorithm with Multiple Mutation which Solves Orienteering Problem in Large Networks. Computational Collective Intelligence. Technologies and Applications, LNCS 8083, 356-366, 2013.
• [37] Karbowska-Chilinska, J., Zabielski, P.: Genetic Algorithm with Path Relinking for the Orienteering Problem with Time Windows, Fundamenta Informaticae, vol. 135, 419-431, 2014.
• [38] Ostrowski, K.: Comparison of Different Graph Weights Representations Used to Solve the Time-Dependent Orienteering Problem, Trends in Contemporary Computer Science, Podlasie 2014, Bialystok University of Technology Publishing Office, 144-154, 2014.
• [39] Zabielski. P., Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K.: A Genetic Algorithm with Grouping Selection and Searching Operators for the Orienteering Problem, Lecture Notes in Artificial Intelligence, LNCS 9012, 31-40, 2015.