Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Advances in Computer Science Research

2 Ostrowski K.

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Orienteering Problem

Sortuj według:

Ogranicz wyniki do:

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

Ostrowski K.

Advances in Computer Science Research

2018

Nr 14

143--161

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.

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.

Parameters tuning of evolutionary algorithm for the orienteering problem

Ostrowski K.

Advances in Computer Science Research

2015

Nr 12

53--78

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.

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.