Progress properties and fitness bounds for geometric semantic search operators

Tomasz P. Pawlak, Krzysztof Krawiec

Abstract

Metrics are essential for geometric semantic genetic programming. On one hand, they structure the semantic space and govern the behavior of geometric search operators; on the other, they determine how fitness is calculated. The interactions between these two types of metrics are an important aspect that to date was largely neglected. In this paper, we investigate these interactions and analyze their consequences. We provide a systematic theoretical analysis of the properties of abstract geometric semantic search operators under Minkowski metrics of arbitrary order. For nine combinations of popular metrics (city-block, Euclidean, and Chebyshev) used in fitness functions and of search operators, we derive pessimistic bounds on fitness change. We also define three types of progress properties (weak, potential, and strong) and verify them for operators under those metrics. The analysis allows us to determine the combinations of metrics that are most attractive in terms of progress properties and deterioration bounds.

Access full text

Full text is available at SpringerLink (open access).

BibTeX

@Article{Pawlak2015,
author="Pawlak, Tomasz P.
and Krawiec, Krzysztof",
title="Progress properties and fitness bounds for geometric semantic search operators",
journal="Genetic Programming and Evolvable Machines",
year="2015",
volume="17",
number="1",
pages="5--23",
abstract="Metrics are essential for geometric semantic genetic programming. On one hand, they structure the semantic space and govern the behavior of geometric search operators; on the other, they determine how fitness is calculated. The interactions between these two types of metrics are an important aspect that to date was largely neglected. In this paper, we investigate these interactions and analyze their consequences. We provide a systematic theoretical analysis of the properties of abstract geometric semantic search operators under Minkowski metrics of arbitrary order. For nine combinations of popular metrics (city-block, Euclidean, and Chebyshev) used in fitness functions and of search operators, we derive pessimistic bounds on fitness change. We also define three types of progress properties (weak, potential, and strong) and verify them for operators under those metrics. The analysis allows us to determine the combinations of metrics that are most attractive in terms of progress properties and deterioration bounds.",
issn="1573-7632",
doi="10.1007/s10710-015-9252-6",
url="http://dx.doi.org/10.1007/s10710-015-9252-6"
}