TCS /
Studies /
T-79.300 /
Spring 2002
T-79.300 Postgraduate Course in Theoretical Computer Science
Spring 2002 (2-10 cr)
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.
- Landscape workshop in Turku 30 May. Speakers include e.g.
Peter Stadler, Leila Kallel. For more details, see the
announcement.
- 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.
- 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.)
- 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.
- 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.
Latest update: Aug 21, 2002
by orponen@tcs.hut.fi