A tunable model for multi-objective, epistatic, rugged, and neutral fitness landscapes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A tunable model for multi-objective, epistatic, rugged, and neutral fitness landscapes

Full text

Pdf (509 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 10th annual conference on Genetic and evolutionary computation table of contents

Atlanta, GA, USA

SESSION: Formal theory papers table of contents

Pages 795-802

Year of Publication: 2008

ISBN:978-1-60558-130-9

Authors

Thomas Weise	University of Kassel, Kassel, Germany
Stefan Niemczyk	University of Kassel, Kassel, Germany
Hendrik Skubch	University of Kassel, Kassel, Germany
Roland Reichle	University of Kassel, Kassel, Germany
Kurt Geihs	University of Kassel, Kassel, Germany

Sponsors

ACM: Association for Computing Machinery
SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 43, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1389095.1389252 What is a DOI?

ABSTRACT

The fitness landscape of a problem is the relation between the solution candidates and their reproduction probability. In order to understand optimization problems, it is essential to also understand the features of fitness landscapes and their interaction. In this paper we introduce a model problem that allows us to investigate many characteristics of fitness landscapes. Specifically noise, affinity for overfitting, neutrality, epistasis, multi-objectivity, and ruggedness can be independently added, removed, and fine-tuned. With this model, we contribute a useful tool for assessing optimization algorithms and parameter settings.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. Altenberg. Nk fitness landscapes. In Handbook of Evolutionary Computation, chapter B2.7.2. Oxford University Press, 1996.
	2	W. Bateson. Mendel's Principles of Heredity. Cambridge University Press, 1909.
	3	C. A. Ceollo Coello. An updated survey of evolutionary multiobjective optimization techniques: State of the art and future trends. In Congress on Evolutionary Computation (CEC), pages 3--13. IEEE Press, 1999.
	4	Y. Davidor. Epistasis variance: A viewpoint on GA-hardness. pages 23--35. In {31}.
	5	R. Dawkins. Climbing Mount Improbable. Penguin Books, 1996.
	6	Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
	7	M. Defoin Platel, M. Clergue, and P. Collard. Maximum homologous crossover for linear genetic programming. In Genetic Programming: 6th European Conf., volume 2610 of LNCS, pages 29--48. Springer, 2003.
	8	M. Defoin Platel, S. Vérel, M. Clergue, and P. Collard. From royal road to epistatic road for variable length evolution algorithm. In Evolution Artificielle, 6th Int. Conf., volume 2936 of LNCS, pages 3--14. Springer, 2003.
	9	Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
	10	C. M. Fonseca and P. J. Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms - part i: A unified formulation. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 28(1):26--37, 1998.
	11	W. Fontana, P. F. Stadler, E. G. Bornberg-Bauer, T. Griesmacher, I. L. Hofacker, M. Tacker, P. Tarazona, E. D. Weinberger, and P. Schuster. Rna folding and combinatory landscapes. Physical Review E, 47(3):2083--2099, 1993.
	12	S. Forrest and M. Mitchell. Relative building-block fitness and the building-block hypothesis. In Whitley, editor, Foundations of Genetic Algorithms 2, pages 109--126. Morgan Kaufmann, 1992.
	13	S. Gavrilets. Fitness Landscapes and the Origin of Species. Number MPB-41 in Monographs in Population Biology. Princeton University Press, 2004.
	14	R. W. Hamming. Error-detecting and error-correcting codes. Bell System Technical Journal, 29(2):147--169, 1950.
	15	John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
	16	Terry Jones, A description of holland's royal road function, Evolutionary Computation, v.2 n.4, p.409-415, Winter 1994 [doi>10.1162/evco.1994.2.4.409]
	17	S. A. Kauffman. Adaptation on rugged fitness landscapes. In Lectures in the Sciences of Complexity: Complex Systems Summer School, volume I of Santa Fe Institute Studies in the Sciences of Complexity, pages 527--618. Addison Wesley, 1988.
	18	S. A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, 1993.
	19	S. A. Kauffman and S. Levin. Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 128(1):11--45, 1987.
	20	S. A. Kauffman and E. D. Weinberger. The nk model of rugged fitness landscapes and its application to maturation of the immune response. Journal of Theoretical Biology, 141:211--245, 1989.
	21	Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
	22	J. L. Lush. Progeny test and individual performance as indicators of an animal's breeding value. Journal of Dairy Science, 18(1):1--19, 1935.
	23	Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA, 1998
	24	M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In Varela and Bourgine, editors, Towards a Practice of Autonomous Systems: 1st European Conf. on Artificial Life, pages 245--254. The MIT Press, 1992.
	25	David J. Montana, Strongly typed genetic programming, Evolutionary Computation, v.3 n.2, p.199-230, Summer 1995 [doi>10.1162/evco.1995.3.2.199]
	26	B. Naudts, D. Suys, and A. Verschoren. Generalized royal road functions and their epistasis. Computers and Artificial Intelligence, 19(4), 2000.
	27	B. Naudts and A. Verschoren. Epistasis on finite and infinite spaces. In 8th Int. Conf. on Systems Research, Informatics and Cybernetics, pages 19--23, 1996.
	28	Charles Campbell Palmer, An approach to a problem in network design using genetic algorithms, Polytechnic University, Brooklyn, NY, 1994
	29	C. C. Palmer and A. Kershenbaum. Representing trees in genetic algorithms. In 1st IEEE Conf. on Evolutionary Computation (CEC), volume 1, pages 379--384. IEEE Press, 1994.
	30	Bill Punch , Doug Zongker , Erik Goodman, The royal tree problem, a benchmark for single and multiple population genetic programming, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
	31	Rawlins, editor. 1st Workshop on Foundations of Genetic Algorithms (FOGA). Morgan Kaufmann, 1990.
	32	I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, 1973.
	33	Justinian P. Rosca , Dana H. Ballard, Causality in Genetic Programming, Proceedings of the 6th International Conference on Genetic Algorithms, p.256-263, July 15-19, 1995
	34	Franz Rothlauf , David E. Goldberg, Representations for Genetic and Evolutionary Algorithms, Physica-Verlag, 2002
	35	Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	36	M. Shackleton, R. Shipman, and M. Ebner. An investigation of redundant genotype-phenotype mappings and their role in evolutionary search. In Congress on Evolutionary Computation (CEC), pages 493--500. IEEE Press, 2000.
	37	R. Shipman. Genetic redundancy: Desirable or problematic for evolutionary adaptation? In 4th Int. Conf. on Artificial Neural Nets and Genetic Algorithms, pages 1--11. Springer, 1999.
	38	M. Toussaint , C. Igel, Neutrality: a necessity for self-adaptation, Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, p.1354-1359, May 12-17, 2002
	39	A. Wagner. Robustness and Evolvability in Living Systems. Princeton Studies in Complexity. Princeton University Press, 2005.
	40	A. Wagner. Robustness, evolvability, and neutrality. FEBS Lett, 579(8):1772--1778, 2005.
	41	E. D. Weinberger. Local properties of kauffman's nk model, a tuneably rugged energy landscape. Physical Review A, 44:6399--6413, 1991.
	42	T. Weise and K. Geihs. Dgpf - an adaptable framework for distributed multi-objective search algorithms applied to the genetic programming of sensor networks. In Filipic and Silc, editors, 2nd Int. Conf. on Bioinspired Optimization Methods and their Application, pages 157--166. Jozef Stefan Institute, 2006.
	43	T. Weise, M. Zapf, and K. Geihs. Rule-based genetic programming. In 2nd Int. Conf. on Bio-Inspired Models of Network, Information, and Computing Systems. IEEE Press, 2007.
	44	S. Wright. The roles of mutation, inbreeding, crossbreeding and selection in evolution. In 6th Annual Congress of Genetics, volume 1, pages 356--366, 1932.