When to use bit-wise neutrality. (English) Zbl 1215.68213
Summary: Representation techniques are important issues when designing successful evolutionary algorithms. Within this field the use of neutrality plays an important role. We examine the use of bit-wise neutrality introduced by R. Poli and E. Galván-López [Lect. Notes Comput. Sci. 4436, 138–164 (2007; Zbl 1196.68235)] from a theoretical point of view and show that this mechanism only enhances mutation-based evolutionary algorithms if not the same number of genotypic bits for each phenotypic bit is used. Using different numbers of genotypic bits for the bits in the phenome we point out by rigorous runtime analyses that it may reduce the optimization time significantly.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Citations:
Zbl 1196.68235References:
| [1] | Collins M (2005) Finding needles in haystacks is harder with neutrality. In: Proceedings of the annual conference on genetic and evolutionary computation (GECCO ’05). ACM Press, pp 1613–1618 |
| [2] | Droste S, Jansen T, Wegener I (1998) A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with boolean inputs. Evol Comput 6(2):185–196 · doi:10.1162/evco.1998.6.2.185 |
| [3] | Droste S, Jansen T, Wegener I (2002) On the analysis of the (1 + 1) evolutionary algorithm. Theor Comput Sci 276:51–81 · Zbl 1002.68037 · doi:10.1016/S0304-3975(01)00182-7 |
| [4] | Garnier J, Kallel L, Schoenauer M (1999) Rigorous hitting times for binary mutations. Evol Comput 7(2):173–203 · doi:10.1162/evco.1999.7.2.173 |
| [5] | Gutjahr WJ, Sebastiani G (2008) Runtime analysis of ant colony optimization with best-so-far reinforcement. Methodol Comput Appl Probab 10(3):409–433 · Zbl 1192.68965 · doi:10.1007/s11009-007-9047-1 |
| [6] | He J, Yao X (2001) Drift analysis and average time complexity of evolutionary algorithms. Artif Intell 127(1):57–85 · Zbl 0971.68129 · doi:10.1016/S0004-3702(01)00058-3 |
| [7] | Huynen MA (1996) Exploring phenotype space through neutral evolution. J Mol Evol 43:165–169 · doi:10.1007/BF02338823 |
| [8] | Huynen MA, Stadler P, Fontana W (1996) Smoothness within ruggedness: the role of neutrality in adaptation. Proc Natl Acad Sci USA 93:397–401 · doi:10.1073/pnas.93.1.397 |
| [9] | Jansen T, Wegener I (2001) Evolutionary algorithms–how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans Evol Comput 5(6):589–599 · doi:10.1109/4235.974841 |
| [10] | Kimura M (1968) Evolutionary rate at the molecular level. Nature 217:624–626 · doi:10.1038/217624a0 |
| [11] | Neumann F, Sudholt D, Witt C (2007) Comparing variants of MMAS ACO algorithms on pseudo-boolean functions. In: Proceedings of engineering stochastic local search algorithms (SLS ’07), LNCS, vol 4638. Springer, pp 61–75 · Zbl 1134.68499 |
| [12] | Poli R, López EG (2007) On the effects of bit-wise neutrality on fitness distance correlation, phenotypic mutation rates and problem hardness. In: Proceedings of foundations of genetic algorithms (FOGA ’07), pp. 138–164 · Zbl 1196.68235 |
| [13] | Rothlauf F (2003) Population sizing for the redundant trivial voting mapping. In: Proceedings of the annual conference on genetic and evolutionary computation (GECCO ’03), LNCS, vol 2724. Springer, pp 618–627 · Zbl 1038.68843 |
| [14] | Schuster P (2002) Molecular insights into evolution of phenotypes. In: Crutchfield JP, Schuster P (eds) Evolutionary dynamics–exploring the interplay of accident, selection, neutrality and function. Santa Fe Institute Series in the Science of Complexity. Oxford University Press, Oxford |
| [15] | Stephens C, Waelbroeck H (1999) Codon bias and mutability in HIV sequences. J Mol Evol 48:390–397 · doi:10.1007/PL00006483 |
| [16] | Toussaint M, Igel C (2003) Neutrality and self-adaptation. Nat Comput 2(2):117–132 · Zbl 1059.68088 · doi:10.1023/A:1024906105255 |
| [17] | Wegener I, Witt C (2005) On the optimization of monotone polynomials by simple randomized search heuristics. Combin Probab Comput 14:225–247 · Zbl 1062.68049 · doi:10.1017/S0963548304006650 |
| [18] | Weicker K, Weicker N (2001) Burden and benefits of redundancy. In: Proceedings of foundations of genetic algorithms (FOGA ’00). Morgan Kaufmann, pp 313–333 · Zbl 1001.68972 |
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.
