MMCE and MathMods Optimisation 2011/12

• C learning

• Dijkstra Algorithm by Eric Demaine
• Dijkstra Algorithm Notes (Notes of COMP271: Design and Analysis of Algorithms), Mordecai J.GOLIN
  Department of Computer Science & Engineering,
  Hong Kong University of Science & Technology.
• Dijkstra Animated: a simple example and an example with more nodes


• Introduction to A* Algorithms
• Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
  Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
  Pages used: 33 to 46, 48, 49, 64, 65, 73--85. Also the example in pages 52--54 might be relevant.
• A* Algorithm (correct version)

• Dijkstra Algorithm (taken from Russell Martin; University of Liverpool).
• A*: A real Map Routing problem; the data file Berga-graph.txt and the data file in latin1.

• Transparencies of Jacek Dziedzic (full version)
• Essentials of Metaheuristics, A Set of Undergraduate Lecture Notes, Sean Luke,
  Department of Computer Science, George Mason University.

• An Overview of Genetic Algorithms: Part 1, Fundamentals
• An Overview of Genetic Algorithms: Part 2, Research Topics
• An Introduction to Genetic Algorithms, Melanie Mitchell
  1996, MIT Press, Cambridge, Massachusetts.

• Example: Maximization of a (complicate and artificial) function by a genetic algorithm
• Implement the idea described in the page Genetic Programming: Evolution of Mona Lisa to render (and compress images) by using a standard Genetic Algorithm with Elitism or the Steady-State Genetic Algorithm (not just the original version with small size population and no coss-over).
  Compare the results of this implementation with the simple original one and discuss whether these versions of the GA are appropriate.

• Optimization by simulated annealing (post by dcoetzee on March 19, 2009)
• Comprehensive introduction to Simulated Annealing
• Simulated Annealing, weighted simulated annealing and genetic algorithm at work
  François Bergeret and Philippe Besse
• Numerical Recipes in C. The Art of Scientific Computing: Section 10.9

• Simulated Annealing visualization A visualization of a simulated annealing solution to the N-Queens puzzle by Yuval Baror./li>
• Image evolution Online demonstration. This is a debatable implementation of SA, being more like a hill climbing algorithm.
• C++ SA A simple C++ implementation of simulated annealing by Antonio Gulli
• Simulated Annealing A Java applet that allows you to experiment with simulated annealing. Source code included.
• Self-Guided Lesson on Simulated Annealing A Wikiversity project.

Assignments
Make Problem 2 of Self-Guided Lesson on Simulated Annealing (see also Simulated Annealing visualization A visualization of a simulated annealing solution to the N-Queens puzzle by Yuval Baror).

• Ant colony optimization theory: A survey
  by Marco Dorigoa and Christian Blumb,
  Theoretical Computer Science 344 (2005) 243 – 278.
• Ant colony Optimization Algorithms: Introduction and Beyond
  by Anirudh Shekhawat, Pratik Poddar and Dinesh Boswal.
• Numeric example of ACS algorithm.
  Extracted from Ant Colony Optimization Solving the Traveling Salesman Problem by Kiril Matev.

Assignments
Implementation of the Traveling salesman problem using Ant Systems.

• Scheduling Algorithms, Peter Brucker
  Springer-Verlag, 2007, Berlin Heidelberg New York (ISBN 978-3-540-69515-8).
• Deterministic Scheduling Theory (Pages: 1-13), R. Gary Parker
  Chapman Hall, 1996, London (ISBN-13: 978-0412996818 ISBN-10: 0412996812).
• Notation for theoretic scheduling problems
• An adaptative genetic algorithm for multiprocessor task assignment problem with limited memory

Assignments
Two easy exercises.