Different Approaches to Infeasible Solutions in Evolutionary Algorithms for The Orienteering Problem

• Autorzy: Ostrowski K.

Identyfikatory

DOI

10.24427/acsr-2018-vol14-0009

Warianty tytułu

PL

Różne metody traktowania rozwiązań niedopuszczalnych w algorytmach ewolucyjnych rozwiązujących Orienteering Problem

• Języki publikacji: PL

Abstrakty

PL

Orienteering Problem (OP) należy do problemów optymalizacji kombinatorycznej i jest zdefiniowany na grafach ważonych. Celem OP jest znalezienie ścieżki o ograniczonej długości i maksymalnym łącznym proficie (zbieranym w wierzchołkach). Artykuł prezentuje porównanie różnych metod radzenia z rozwiązaniami niedopuszczalnymi (zbyt długimi ścieżkami) w algorytmach ewolucyjnych rozwiązujących OP. Grupa algorytmów ewolucyjnych (różniących się operatorami selekcji i krzyżowania) została przetestowana w dwóch konfiguracjach: z osobnikami dopuszczalnymi w populacji oraz bez nich. Wartości parametrów algorytmów zostały ustawione za pomocą automatycznej procedury kalibracji (ParamILS). Wyniki wskazują, że obecność zbyt długich ścieżek w populacji może poprawić jakość rozwiązań. Prezentowana meta-heurystyka uzyskiwała rozwiązania optymalne lub bliskie optymalnym dla sieci testowych.

EN

The Orienteering Problem (OP) is a combinatorial optimization problem defined on weighted graphs. The purpose of the OP is to find a path of limited length which maximizes total profit (collected in vertices). This paper presents comparison of different approaches to infeasible solutions (too long paths) in evolutionary algorithms solving the OP. A group of evolutionary algorithms (varying in crossover and selection operators) was tested in different configurations: with and without infeasible solutions in populations. Parameters for all algorithm configurations were obtained from automatic tuning procedure (ParamILS). Results show that presence of too long paths in a population can improve quality of resulting solutions. The presented metaheuristic generated optimal or close to optimal solutions for the tested benchmark networks.

Słowa kluczowe

PL

rozwiązania niedopuszczalne; algorytmy ewolucyjne; Orienteering Problem

EN

infeasible solutions; evolutionary algorithms; Orienteering Problem

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Advances in Computer Science Research
• Rocznik: 2018
• Tom: Nr 14
• Strony: 143--161
• Opis fizyczny: Bibliogr. 25 poz., rys., tab., wykr.

Twórcy

autor

Ostrowski K.

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

Bibliografia

• [1] 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.
• [2] Caserta, M., Voss, S.: A hybrid algorithm for the DNA sequencing problem. Discrete Applied Mathematics, vol. 163(1), 87-99, 2014.
• [3] Golden, B., Levy, L., Vohra, R.: The orienteering problem. Naval Research Logistics, vol. 34, 307-318, 1987.
• [4] Ostrowski, K.: Parameters tuning of evolutionary algorithm for the Orienteering Problem. Advances in Computer Science Research, vol. 12, 53-78, 2015.
• [5] Tsiligirides, T.: Heuristic methods applied to orienteering. Journal of the Operational Research Society, vol. 35 (9), 797-809, 1984.
• [6] Fischetti, M., Salazar, J., Toth, P.: Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, vol. 10, 133-148, 1998.
• [7] 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.
• [8] 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.
• [9] 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.
• [10] 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.
• [11] 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.
• [12] Schilde, M., Doerner, K., Hartl, R., Kiechle, G.: Metaheuristics for the biobjective orienteering problem. Swarm Intelligence, vol. 3, 179-201, 2009.
• [13] 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.
• [14] 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.
• [15] Koszelew. J., Ostrowski. K.: A Genetic Algorithm with Multiple Mutation which Solves Orienteering Problem in Large Networks. Computational Collective Intelligence. Technologies and Applications, vol. 8083, 356-366, 2013.
• [16] 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, vol. 9012, 31-40, 2015.
• [17] Ostrowski, K., Karbowska-Chilinska, J., Koszelew, J., Zabielski, P.: Evolutioninspired local improvement algorithm solving orienteering problem. Annals of Operations Research, vol. 253(1), 519-543, 2017.
• [18] 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.
• [19] Ostrowski, K.: Evolutionary Algorithm for the Time-Dependent Orienteering Problem. Proceedings from the Computer Information Systems and Industrial Management : 16th IFIP TC8 International Conference : CISIM 2017 (eds. Khalid Saeed, Wladyslaw Homenda, Rituparna Chaki). Lecture Notes in Computer Science, vol. 10244, 50-62, 2017.
• [20] Ostrowski, K.: An Effective Metaheuristic for Tourist Trip Planning in Public Transport Networks. Applied Computer Science, vol. 14(2), 2018.
• [21] Sokolov, A., Whitley, D.: Unbiased tournament selection. Proceedings of Genetic and Evolutionary Computation Conference. ACM Press, 1131-1138, 2005.
• [22] 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.
• [23] 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.
• [24] 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.
• [25] Network of 908 cities in Poland. http://p.wi.pb.edu.pl/sites/default/files/krzysztof-ostrowski/files/polska908.txt. Accessed 1 November 2018.

Uwagi

The author gratefully acknowledges support from the Polish Ministry of Science and Higher Education at the Bialystok University of Technology (grant S/WI/1/2014).

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).