Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T02:15:11.801Z Has data issue: false hasContentIssue false
  • English
  • Français

The 2-epistasis of fitness functions

Published online by Cambridge University Press:  17 April 2009

M. T. Iglesias ,
V. S. Peñaranda ,
C. Vidal  and
A. Verschoren
M. T. Iglesias
Affiliation:
Universidade da Coruña, A Coruña, Spain
V. S. Peñaranda
Affiliation:
Universidade da Coruña, A Coruña, Spain
C. Vidal
Affiliation:
University of Antwerp, Antwerp, Belgium
A. Verschoren
Affiliation:
University of Antwerp, Antwerp, Belgium
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this note about Genetic Algorithms (GA-), we study the 2-epistasis of a fitness function over a search space. This concept is a natural generalisation of that of epistasis, previously considered by Davidor in 1991 Suys and Verschoren in 1996 and Van Hove and Verschoren in 1994 for example. We completely characterise fitness functions whose 2-epistasis is minimal: these are exactly the second order functions. The validity of 2-epistasis as a measure of hardness with respect to genetic algorithms is checked over some classical laboratory functions. Finally, we obtain an upper bound of the maximal value of the 2-epistasis when we restrict attention to non-negative functions.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 76 , Issue 3 , December 2007 , pp. 397 - 419
Copyright
Copyright © Australian Mathematical Society 2007

References

[1]Davidor, Y., ‘Epistasis and variance: A viewpoint on GA-hardness’, in Foundations of Genetic Algorithms 1, (Rawlins, G.J.E., Editor) (Morgan Kaufmann Publishers, San Mateo, 1991), pp. 23–25.Google Scholar
[2]Forrest, S. and Mitchell, M., ‘Relative building-block fitness and the building-block hypothesis’, in Foundations of Genetic Algorithms 2, (Whitley, L.D., Editor) (Morgan Kaufmann Publishers, San Mateo, 1993), pp. 109–126.Google Scholar
[3]Goldberg, D., Genetic algorithms and Walsh functions: Part I, A gentle introduction, Complex Systems 3, 1989, pp. 129–152.Google Scholar
[4]Iglesias, M.T., Verschoren, A. and Vidal, C., ‘Template functions and their epistasis’,in Proceedings of MS'2000 International Conference on Modelling and Simulation, (Las Palmas de Gran Canaria, 2000), pp. 539–546.Google Scholar
[5]Iglesias, M.T., Verschoren, A. and Vidal, C., ‘Computing epistasis of template functions through Walsh transforms’, Comput. Inform. 24 (2005), 263–279.Google Scholar
[6]Iglesias, M.T., Naudts, B., Verschoren, A. and Vidal, C., Foundations of generic optimization, A Combinatorial approach to epistasis, (Volume 1) (Springer-Verlag, Dordrecht, 2005).Google Scholar
[7]Iglesias, M.T., Peñaranda, V.S. and Verschoren, A., ‘Higher order functions and Walsh coefficients’, Bull. Belg. Math. Soc. Simon Stevin 13 (2006), 633–643.CrossRefGoogle Scholar
[8]Iglesias, M.T., Peñaranda, V.S., Verschoren, A. and Vidal, C., ‘Higher epistasis’, (in preparation).Google Scholar
[9]Naudts, B., Suys, D. and Verschoren, A., ‘Epistasis, deceptivity and Walsh transforms’,in Proceedings of the International ICSC Symposium on Engineering of Intelligent Systems (EIS'98) 1, Fuzzy Logic/Genetic Algorithms (ICSC Academic Press, 1998), pp. 210–216.Google Scholar
[10]Naudts, B., Suys, D. and Verschoren, A., ‘Generalized Royal Road functions and their epistasis’, Comput. Artificial Intelligence 19 (2000), 317–334.Google Scholar
[11]Peñaranda, V.S., Epistasis superior, (Ph.D. Thesis) (Universidade da Coruña, Spain, 2006).Google Scholar
[12]Suys, D. and Verschoren, A., ‘Extreme epistasis’,in International Conference on Intelligent Technologies in Human-Relates Sciencies (ITHURS96) Vol.II(León,1996), pp. 251–258.Google Scholar
[13]Suys, D., A mathematical approach to epistasis, (Ph.D. Thesis) (University of Antwerp, 1999).Google Scholar
[14]Van Hove, H. and Verschoren, A., ‘On epistasis’, Comput. Artificial Intelligence 14 (1994), 271–277.Google Scholar