TY  - GEN
A1  - Kötzing, Timo
A1  - Lagodzinski, Gregor J. A.
A1  - Lengler, Johannes
A1  - Melnichenko, Anna
T1  - Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming
T2  - Parallel Problem Solving from Nature – PPSN XV
N2  - For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted Concatenation Crossover GP. For this purpose three variants of the wellstudied Majority test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control.
Y1  - 2018
SN  - 978-3-319-99259-4
SN  - 978-3-319-99258-7
U6  - https://doi.org/10.1007/978-3-319-99259-4_4
SN  - 0302-9743
SN  - 1611-3349
VL  - 11102
SP  - 42
EP  - 54
PB  - Springer
CY  - Cham
ER  - 
TY  - GEN
A1  - Blaesius, Thomas
A1  - Eube, Jan
A1  - Feldtkeller, Thomas
A1  - Friedrich, Tobias
A1  - Krejca, Martin Stefan
A1  - Lagodzinski, Gregor J. A.
A1  - Rothenberger, Ralf
A1  - Severin, Julius
A1  - Sommer, Fabian
A1  - Trautmann, Justin
T1  - Memory-restricted Routing With Tiled Map Data
T2  - 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)
N2  - Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
Y1  - 2018
SN  - 978-1-5386-6650-0
U6  - https://doi.org/10.1109/SMC.2018.00567
SN  - 1062-922X
SP  - 3347
EP  - 3354
PB  - IEEE
CY  - New York
ER  -