How to escape local optima in black box optimisation: when non-elitism outperforms elitism. (English) Zbl 1390.68605
Summary: Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The \((1+1)\) EA is a simple and well-studied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the \((1+1)\) EA depends critically on the length of the valley while the runtimes of the non-elitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68W40 | Analysis of algorithms |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
evolutionary algorithms; runtime analysis; population genetics; strong selection weak mutation regime; Metropolis algorithm; simulated annealing; black-box optimisationReferences:
| [1] | Boese, K.D., Kahng, A.B., Muddu, S.: A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. 16(2), 101-113 (1994) · Zbl 0812.90126 · doi:10.1016/0167-6377(94)90065-5 |
| [2] | Corus, D., He, J., Jansen, T., Oliveto, P.S., Sudholt, D., Zarges, C.: On easiest functions for mutation operators in bio-inspired optimisation. Algorithmica 59(3), 343-368 (2016) · Zbl 1366.68257 |
| [3] | Dang, D.-C., Friedrich, T., Kötzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Emergence of diversity and its benefits for crossover in genetic algorithms. In: Proceedings of the 14th Parallel Problem Solving from Nature Conference (PPSN XIV), Volume 9921 of LNCS, pp. 890-900. Springer, Berlin (2016) · Zbl 1211.90200 |
| [4] | Dang, D.-C., Friedrich, T., Kötzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima with diversity mechanisms and crossover. In: Proceedings of the 2016 Genetic and Evolutionary Computation Conference (GECCO ’16), Volume 9921, pp. 645-652. ACM Press, New York (2016) · Zbl 0825.68416 |
| [5] | Dang, D.-C., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75(3), 428-461 (2016) · Zbl 1348.68225 · doi:10.1007/s00453-015-0103-x |
| [6] | Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51-81 (2002) · Zbl 1002.68037 · doi:10.1016/S0304-3975(01)00182-7 |
| [7] | Feller, W.: An Introduction to Probability Theory and its Applications. Wiley, New York (1968) · Zbl 0155.23101 |
| [8] | Gillespie, J.H.: Molecular evolution over the mutational landscape. Evolution 38(5), 1116-1129 (1984) · doi:10.1111/j.1558-5646.1984.tb00380.x |
| [9] | He, J., Chen, T., Yao, X.: On the easiest and hardest fitness functions. IEEE Trans. Evol. Comput. 19(2), 295-305 (2015) · doi:10.1109/TEVC.2014.2318025 |
| [10] | He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127(1), 57-85 (2001) · Zbl 0971.68129 · doi:10.1016/S0004-3702(01)00058-3 |
| [11] | Horn, J., Goldberg, D.E., Deb, K.: Long path problems. In Parallel Problem Solving from Nature (PPSN III), Volume 866 of LNCS, pp. 149-158 (1994) · Zbl 1342.68310 |
| [12] | Jägersküpper, J., Storch, T.: When the plus strategy outperforms the comma strategyand when not. In: 2007 IEEE Symposium on Foundations of Computational Intelligence, pp. 25-32 (2007) |
| [13] | Jansen, T., De Jong, K.A., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evol. Comput. 13, 413-440 (2005) · doi:10.1162/106365605774666921 |
| [14] | Jansen, T., Wegener, I.: The analysis of evolutionary algorithms—a proof that crossover really can help. Algorithmica 34(1), 47-66 (2002) · Zbl 1016.68030 · doi:10.1007/s00453-002-0940-2 |
| [15] | Jansen, T., Wegener, I.: A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation. Theor. Comput. Sci. 386(1-2), 73-93 (2007) · Zbl 1137.68049 · doi:10.1016/j.tcs.2007.06.003 |
| [16] | Jerrum, M., Sorkin, G.B.: The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82(1-3), 155-175 (1998) · Zbl 0932.60079 · doi:10.1016/S0166-218X(97)00133-9 |
| [17] | Kimura, M.: On the probability of fixation of mutant genes in a population. Genetics 47(6), 713-719 (1962) |
| [18] | Lehre, P.K., Witt, C.: General drift analysis with tail bounds. CoRR (2013). arXiv:1307.2559 · Zbl 1512.68443 |
| [19] | Merz, P., Freisleben, B.: Memetic algorithms and the fitness landscape of the graph bi-partitioning problem. In: Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V), pp. 765-774. Springer, Berlin (1998) · Zbl 0604.60067 |
| [20] | Mitra, D., Romeo, F., Sangiovanni-Vincentelli, A.: Convergence and finite-time behavior of simulated annealing. Adv. Appl. Probab. 18(3), 747-771 (1986) · Zbl 0604.60067 · doi:10.2307/1427186 |
| [21] | Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of the 2009 Genetic and Evolutionary Computation Conference (GECCO ’09), pp. 835-842. ACM Press, New York (2009) · Zbl 0932.60079 |
| [22] | Ochoa, G., Veerapen, N.: Deconstructing the big valley search space hypothesis. In: Proceedings of the 16th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2016), pp. 58-73. Springer, Berlin (2016) · Zbl 0604.60067 |
| [23] | Oliveto, P.S., Lehre, P.K., Neumann, F.: Theoretical analysis of rank-based mutation-combining exploration and exploitation. In: Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC ’09), pp. 1455-1462. IEEE Press, New York (2009) · Zbl 1137.68049 |
| [24] | Oliveto, P. S., Paixão, T., Pérez Heredia, J., Sudholt, D., Trubenová, B.: When non-elitism outperforms elitism for crossing fitness valleys. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO ’16, pp. 1163-1170. ACM, New York (2016) · Zbl 1390.68605 |
| [25] | Oliveto, P.S., Witt, C.: On the runtime analysis of the simple genetic algorithm. Theor. Comput. Sci. 545, 2-19 (2014) · Zbl 1342.68310 · doi:10.1016/j.tcs.2013.06.015 |
| [26] | Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theor. Comput. Sci. 605, 21-41 (2015) · Zbl 1330.68120 · doi:10.1016/j.tcs.2015.01.002 |
| [27] | Paixão, T., Badkobeh, G., Barton, N., Corus, D., Dang, D.-C., Friedrich, T., Lehre, P.K., Sudholt, D., Sutton, A.M., Trubenová, B.: Toward a unifying framework for evolutionary processes. J. Theor. Biol. 383, 28-43 (2015) · Zbl 1343.92364 · doi:10.1016/j.jtbi.2015.07.011 |
| [28] | Paixão, T., Pérez Heredia, J., Sudholt, D., Trubenová, B.: Towards a runtime comparison of natural and artificial evolution. Algorithmica 78(2), 681-713 (2017) · Zbl 1366.68270 · doi:10.1007/s00453-016-0212-1 |
| [29] | Pérez Heredia, J., Trubenová, B., Sudholt, D., Paixão, T.: Selection limits to adaptive walks on correlated landscapes. Genetics 205(2), 803-825 (2016) · doi:10.1534/genetics.116.189340 |
| [30] | Reeves, C.: Landscapes, operators and heuristic search. Ann. Oper. Res. 86, 473-490 (1999) · Zbl 0921.90095 · doi:10.1023/A:1018983524911 |
| [31] | Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the \[(1, \lambda\] λ) evolutionary algorithm. Theor. Comput. Sci. 545, 20-38 (2014) · Zbl 1360.68788 · doi:10.1016/j.tcs.2013.09.036 |
| [32] | Rudolph, G.: How mutation and selection solve long-path problems in polynomial expected time. Evol. Comput. 4(2), 195-205 (1997) · doi:10.1162/evco.1996.4.2.195 |
| [33] | Sasaki, G.H., Hajek, B.: The time complexity of maximum matching by simulated annealing. J. ACM 35, 387-403 (1988) · Zbl 0825.68416 · doi:10.1145/42282.46160 |
| [34] | Sudholt, D.: The impact of parametrization in memetic evolutionary algorithms. Theor. Comput. Sci. 410(26), 2511-2528 (2009) · Zbl 1172.68055 · doi:10.1016/j.tcs.2009.03.003 |
| [35] | Sudholt, D.: Hybridizing evolutionary algorithms with variable-depth search to overcome local optima. Algorithmica 59(3), 343-368 (2011) · Zbl 1211.90200 · doi:10.1007/s00453-009-9384-2 |
| [36] | Wegener, I.: Simulated annealing beats metropolis in combinatorial optimization. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP ’05), Volume 3580 of LNCS, pp. 589-601 (2005) · Zbl 1084.68123 |
| [37] | Whitlock, M.C., Phillips, P.C., Moore, F.B.-G., Tonsor, S.J.: Multiple fitness peaks and epistasis. Annu. Rev. Ecol. Syst. 26, 601-629 (1995) · doi:10.1146/annurev.es.26.110195.003125 |
| [38] | Witt, C.: Runtime analysis of the \[(\mu\] μ+1) EA on simple pseudo-Boolean functions. Evol. Comput. 14(1), 65-86 (2006) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
