© 2020 Elsevier B.V.Stochastic Fractal Search (SFS) is a new and original meta-heuristic search (MHS) algorithm with strong foundations. As with many other MHS methods, there are problems in effectively balancing the exploitation-exploration in the SFS algorithm. In order to achieve this balance, it is necessary to improve its diversity capability. This article presents the studies that were carried out to strengthen the diversity and balanced search capabilities of the SFS algorithm. For this purpose, the diversity operator of the SFS algorithm was designed with a novel method called Fitness-Distance Balance (FDB), which more effectively mimics the way fractals occur in nature. Thus, the FDBSFS algorithm, which has a much stronger search performance, was developed. Comprehensive experimental studies were conducted to test and validate the developed FDB-based SFS algorithm (FDBSFS). Thirty-nine novel and powerful MHS algorithms, eighty-nine unconstrained test functions and five constrained engineering problems were used. Two nonparametric tests, the Wilcoxon signed rank test and the Friedman test, were used to analyze the results obtained from the experimental studies. The results of the analysis showed that the problem of premature convergence had been largely eliminated by the application of the FDB method and that the exploitation-exploration balance was also effectively provided. Moreover, the proposed FDBSFS algorithm ranked first among the thirty-nine competing algorithms.