Finding Mount Everest and Handling Voids

Abstract

Evolutionary algorithms (EAs) are randomized search heuristics that solve problems successfully in many cases. Their behavior is often described in terms of strategies to find a high location on Earth’s surface. Unfortunately, many digital elevation models describing it contain void elements. These are elements not assigned an elevation. Therefore, we design and analyze simple EAs with different strategies to handle such partially defined functions. They are experimentally investigated on a dataset describing the elevation of Earth’s surface. The largest value found by an EA within a certain runtime is measured, and the median over a few runs is computed and compared for the different EAs. For the dataset, the distribution of void elements seems to be neither random nor adversarial. They are so-called semirandomly distributed. To deepen our understanding on the behavior of the different EAs, they are theoretically considered on well-known pseudo-Boolean functions transferred to partially defined ones. These modifications are also performed in a semirandom way. The typical runtime until an optimum is found by an EA is analyzed, namely bounded from above and below, and compared for the different EAs. We figure out that for the random model it is a good strategy to assume that a void element has a worse function value than all previous elements. Whereas for the adversary model it is a good strategy to assume that a void element has the best function value of all previous elements.