Optimisation (2013/14)

C learning

Combinatorial Algorithms for graphs

• General definitions and searches on graphs
• Graph Theory: Introduction
• Glossary of Graph Theory
• Search in Graphs: Depth-first: Wikipedia (the three orderings for binary trees) Lecture by Rashid Bin Muhammad.
• Search in Graphs: Breadth-first: Wikipedia Lecture by Rashid Bin Muhammad.
• Greedy algorithm
• Dijkstra Algorithm for optimum paths on graphs
• Dijkstra Algorithm by Eric Demaine (printable booklet version)
• 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
• A* Algorithm: Heuristic search for optimum paths on graphs
• 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)

Assignments

Dijkstra Algorithm:

Solve the project proposed here.

A* Algorithm:

Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from here (348.5Mb).

Genetic Algorithms

• Basic bibliography
• Transparencies of Jacek Dziedzic (full version)
• Essentials of Metaheuristics, A Set of Undergraduate Lecture Notes, Sean Luke,
  Department of Computer Science, George Mason University.
• Additional bibliography
• 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.
• An example: Genetic Clustering Algorithms for Detecting Money-Laundering
• Comparison of genetic sequencing operators (useful for the Traveling Salesman Problem)
• A Comparison of Genetic Sequencing Operators
• A list of genetic operations (crossover and mutation)
• Genetic algorithms for shop scheduling problems: a survey, Frank Werner.

Assignments

First exercise (compulsory part): The traveling salesman problem

A traveling salesman must visit all cities appearing in the table of distances between European cities starting and ending in Barcelona. He travels by car. Use a GA to compute the optimum route according to driving distance. Se also the "ad-hoc" crossover operations above.

Second exercise (optional part): Maximizing a function

Maximization of a (complicate and artificial) function by a genetic algorithm

Simulated Annealing

• Basic bibliography
• 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
  and an implementation of the algorithm.
• A simple implementation of the SA algorithm for a complicate function in one variable
• Numerical Recipes in C. The Art of Scientific Computing: Section 10.9
• Some interesting links from the wikipedia page
• Simulated Annealing visualization A visualization of a simulated annealing solution to the N-Queens puzzle by Yuval Baror.
• 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

Ant colony algorithms

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

Assignments

Neural Networks for Combinatorial Optimization

• Artificial Neural Networks for Combinatorial Optimization, Jean-Yves Potvin, Kate A. Smith.
• Combinatorial Optimization by Neural Networks, Ugur HALICI (presentation).
• Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research ,Kate Smith 1999.
• Neural Techniques for Combinatorial Optimization with Applications, Kate Smith, Marimuthu Palaniswami and Mohan Krishnamoorthy.

Assignments

Evaluation

• For each assignment a report must be written including:
  • introduction stating the problem and the algorithm to solve it,
  • the code of the program,
  • the results of running the program and
  • conclusions.
• The quality of the code of the program will be taken into account for the marks of the assignments and discussed in the interviews.