Impact of Different Discrete Sampling Strategies on Fitness Landscape Analysis Based on Histograms
Vojtěch Uher, Pavel Krömer · 2023
Complex problems are frequently tackled using techniques from the realm of computational intelligence and metaheuristic algorithms. Selection of a metaheuristic from the wide range of algorithms possessing various properties to address specific problem types efficiently is a difficult and crucial task to avoid unnecessary blind alleys and computational expenses. Approximation of continuous problem landscapes by a limited number of scattered discrete samples is a widespread problem characterization applied in exploratory landscape analysis (ELA). ELA is a set of methods analyzing the objective and solution spaces of a problem to construct features estimated from the random samples. This paper describes a simple method for fitness landscape analysis based on the normalized histograms of sample fitnesses. Generation of a small number of representative discrete samples is crucial for efficient problem characterization, and therefore, amount of sampling strategies including random generators and low-discrepancy sequences was developed to evenly cover the problem landscapes. The main contribution of this paper is a study examining the impact of different sampling strategies on the distribution of fitness values based on the normalized histogram analysis. The results reveal a strong effect.