The postgraduate TCS course will this semester be in the form of a seminar on fitness landscapes, i.e. the geometrical, statistical and computational characteristics of the hypersurfaces determined by natural or artificial fitness (cost, potential, energy) functions. Although one might superficially think that not much can be said at this level of generality, the study of fitness landscapes has in fact recently become quite an active area of research, and many interesting phenomena have been uncovered. In this seminar, we shall get acquainted with some fundamental fitness landscape families, their known characteristics, and approaches to analysing them. There are many unresolved issues in this field, and it is our purpose to get up-to-date on the state of the research. Some of the questions we aim to address are: the existence of in some sense "universal" families of fitness landscapes; the characteristics of computationally "easy" vs. "hard" landscapes; threshold/phase transition phenomena in parameterised landscapes; and the use of landscape information in adaptive search and optimisation algorithms.

Current

• Landscape workshop in Turku 30 May. Speakers include e.g. Peter Stadler, Leila Kallel. For more details, see the announcement.

General

• Time, place: Mondays, 4:30 thru 7:30 p.m., seminar room TB353.
• Coordinator: Pekka Orponen, room TB207.
• Registration by TOPI, attending the first meeting, or by contacting the coordinator.
• Prerequisites: Basic knowledge of calculus, linear algebra and probability theory; concepts of graph theory; some familiarity with (combinatorial) optimisation problems and algorithms.
• Assets: Familiarity with transform techniques (Fourier, Laplace), stochastic processes, computational complexity theory, statistical mechanics. (Also evolutionary models, genetic algorithms, random graphs, stochastic optimisation.)
• Credits: Seminar presentation plus archivable slides 2 cr per topic. Seminar paper plus 1 cr. Documented individual research additional 2 cr per topic.

Schedule

• 21 Jan: Opening, overview, handing out assigments (P.O.)
  General main reference: Reidys & Stadler (2002)
• 11 Feb: Landscape families: spin glasses, NK models, optimisation problems (Timo Latvala)
  Key references: Altenberg (1997), Istrail (2000), Wright et al. (2000)
  Presentation: slides (pdf), paper (pdf)
• 18 Feb: Spectral analysis of landscapes (Petteri Kaski)
  Key references: Davies et al. (2001), Grover (1992), Godsil & Royle (2001)
  Presentation: slides (pdf), paper (pdf)
• 25 Feb: Random landscapes (Satu Virtanen)
  Key references: Hordijk & Stadler (1998), Reidys & Stadler (2001), Stadler (2002)
  Presentation: slides (pdf), paper (pdf)
• 4 Mar: Ruggedness and neutrality (Pekka Isto)
  Key references: Ferreira et al. (2001), Garnier & Kallel (2000), Reidys & Stadler (2001), Stadler (1995), Stadler (1996)
  Presentation: slides (pdf), paper (pdf),
• 11 Mar: Cancelled.
• 18 Mar: Dynamics on landscapes (Hannu Rummukainen)
  Key references: Aarts & Lenstra Ch. 4 (1997), Flyvbjerg & Lautrup (1992), Nolte & Schrader (1996), Weinberger (1991)
  Presentation: slides (pdf), paper (pdf)
• 25 Mar: Combinatorial phase transitions and landscape theory (Viljo Petäjä)
  Key references: Achlioptas et al. (2001), Gao & Culberson (2001), Martin et al. (2001)
  Presentation: slides (pdf), paper (pdf)
• 1 Apr: No seminar (Easter Monday)
• 8 Apr: "Small world" landscapes (Satu Virtanen)
  Key references: Albert & Barabasi (2002), Walsh (1999), Watts & Strogatz (1998)
  Presentation: slides (pdf), paper (pdf)
• 15 Apr: No seminar (in lieu of the " Complexity and Probability" course, Gothenburg)
• 22 Apr: "No Free Lunch" theorems vs. landscape theory (Sakari Seitz)
  Key references: Wolpert & Macready (1997)
  Presentation: slides (pdf),
• 29 Apr: Influence of landscape structure on evolutionary algorithms (Timo Latvala)
  Key references: Kallel et al. (2001), Naudts & Kallel (2000), Rosé et al. (1996)
  Presentation: slides (pdf),
• 6 May: Eigenvectors and spectra of Cayley graphs (Petteri Kaski)
  Key references: James & Kerber (1981), Rockmore et al. (2002), Serre (1977)
  Presentation: slides (pdf), paper (pdf)

Further optional topics might include, e.g., protein folding or other biomodel landscapes, and the connections of stochastic optimisation to landscape theory. Additionally, in May there will be an excursion to attend a landscape workshop in Turku. (Speakers include e.g. Peter Stadler, one of the key authors in the area, cf. the references below.)

Arrangements

• Pointers to seminar material will be linked to the schedule above by coordinator. Printed copies of the material will be available for inspection in the course folder at the theory lab office (TB336).
• Electronic copy of presentation slides and/or seminar paper, together with any possible additional literature pointers mailed by presenter to coordinator by the presentation date. These will also be linked to the schedule above. A printed copy of the presentation will eventually be filed in the course folder.
• To enhance the interaction at the seminar meetings, each speaker should, in addition to preparing his/her own talk, study also some of the material of the following speaker and be prepared to discuss this at the next meeting.
• In addition, each speaker should discuss the material he/she intends to cover in his/her presentation with the coordinator ca. two weeks before the talk.

Seminar material

• E. Aarts, J. K. Lenstra (eds.), Local Search in Combinatorial Optimization. J. Wiley & Sons, Chichester, 1997.
• D. Achlioptas, A. Chtcherba, G. Istrate, C. Moore, "The phase transition in 1-in-k SAT and NAE 3-SAT." Proc. ACM Symposium on Discrete Algorithms (SODA-2001), 721-722. ACM Press, New York, NY 2001.
• R. Albert, A. Barabasi, "Statistical mechanics of complex networks." Rev. Mod. Phys. 74 (2002), in press.
• L. Altenberg, "NK fitness landscapes." Handbook of Evolutionary Computation (T. Bäck, D. Fogel, Z. Michalewicz, eds.) Oxford University Press 1997.
• E. B. Davies, G. M. L. Gladwell, J. Leydold, P. F. Stadler, "Discrete nodal domain theorems." Linear Algebra and its Applications 336 (2001), 51-60.
• F. F. Ferreira, J. F. Fontanari, P. F. Stadler, "Landscape statistics of the low autocorrelated binary string problem." J. Phys. A: Math. Gen. 33 (2000), 8635-8647.
• H. Flyvbjerg, B. Lautrup, "Evolution in a rugged fitness landscape," Phys. Rev. A 46 (1992), 6714-6723.
• Y. Gao, J. Culberson, "The phase transition in NK landscapes is easy." Proc. Genetic and Evolutionary Computation Conference (GECCO-2001), 1227-1234. Morgan Kaufmann, San Francisco, CA 2001.
• J. Garnier, L. Kallel, "Efficiency of local search with multiple local optima." SIAM J. Discr. Math. 15 (2000), 122-141.
• C. Godsil, G. Royle, Algebraic Graph Theory. Graduate Texts in Mathematics 207, Springer-Verlag, New York, NY 2001.
• L. Grover, "Local search and the local structure of NP-complete problems." Operations Research Letters 12 (1992), 235-243.
• W. Hordijk, P. F. Stadler, "Amplitude spectra of fitness landscapes." Journal of Complex Systems 1 (1998), 39-66.
• S. Istrail, "Statistical mechanics, three-dimensionality and NP-completeness - I. Universality of intractability for the partition function of the Ising model across non-planar lattices (Extended abstract)." Proceeding of the 31st ACM Annual Symposium on the Theory of Computing (STOC 2000), 87-96. ACM Press, New York, NY 2000.
• G. James, A. Kerber, The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications 16, Addison-Wesley, Reading, MA 1981.
• L. Kallel, B. Naudts, C.R. Reeves, "Properties of fitness functions and search landscapes." Theoretical Aspects of Evolutionary Computing (L. Kallel, B. Naudts, A. Rogers, eds.), pp. 175-206. Springer-Verlag, Berlin Heidelberg 2001.
• O. C. Martin, R. Monasson, R. Zecchina, "Statistical mechanics methods and phase transitions in optimization problems." arXiv preprint cond-mat/0104428v1, 23 April 2001.
• B. Naudts, L. Kallel, "A comparison of predictive measures of problem difficulty in evolutionary algorithms." IEEE Transactions on Evolutionary Computation 4 (2000), 1-15.
• A. Nolte, R. Schrader, "A note on the finite time behaviour of simulated annealing." Operations Research Proceedings, 1996.
• C. M. Reidys, P. F. Stadler, "Combinatorial landscapes." SIAM Review 44 (2002), 3-54.
• C. M. Reidys, P. F. Stadler, "Neutrality in fitness landscapes." Applied Math. and Computation 117 (2001), 321-350.
• D. Rockmore, P. Kostelec, W. Hordijk, P. F. Stadler, "Fast Fourier transform for fitness landscapes." Appl. Comput. Harmon. Anal. 12 (2002), 57-76.
• H. Rosé, W. Ebeling, T. Asselmayer, "The density of states - A measure of difficulty of optimization problems." Proc. 4th Conf. Parallel Problem Solving from Nature, 263-290. Springer-Verlag, Berlin Heidelberg 1996.
• J.-P. Serre. Linear Representations of Finite Groups. Graduate Texts in Mathematics 42, Springer-Verlag, New York, NY 1977.
• P. F. Stadler, "Towards a theory of landscapes." Complex Systems and Binary Networks (R. Lopez-Pena, R. Capovilla, R. Garcia-Pelayo, H. Waelbroeck, F. Zertuche, eds.) Springer-Verlag, Berlin Heidelberg 1996. Pp. 77-163.
• P. F. Stadler, "Landscapes and their correlation functions." J. Math. Chem. 20 (1996), 1-45.
• P. F. Stadler, "Spectral landscape theory." Evolutionary Dynamics - Exploring the Interplay of Selection, Neutrality, Accident, and Function (J. P. Crutchfield, P. Schuster, eds.) Oxford University Press 2002, in press.
• T. Walsh, "Search in a small world." Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Vol 2. Morgan Kaufmann, San Francisco 1999.
• D. J. Watts, S. H. Strogatz, "Collective dynamics of small-world networks." Nature 393 (1998), 440-442.
• E. D. Weinberger, "Local properties of Kauffman's N-k model: A tunably rugged energy landscape." Phys. Rev. A 44 (1991), 6399-6413.
• D. H. Wolpert, W. G. Macready, "No free lunch theorems for optimization." IEEE Transactions on Evolutionary Computation 1 (1997), 67-82.
• A. H. Wright, R. K. Thompson, J. Zhang, "The Computational Complexity of N-K Fitness Functions." IEEE Transactions on Evolutionary Computation 4 (2000), 373-379.