Master's degree in Modelling for Science and Engineering
Combinatorial Algorithms for graphs
- General definitions and searches on graphs
- Dijkstra Algorithm for optimum paths on graphs
- A* Algorithm: Heuristic search for optimum paths on graphs
- A* Algorithm:
- Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from
For testing the program, you can use the much smaller file catalunya.csv.zip (51.9Mb)
(it has only 3472620 nodes and 201235 ways and it has the same format as the file
Valid nodes ID for start and goal are: 771979683 (in Girona) and 429854583 (in Lleida).
Here you can find my solution of the Barcelona-Sevilla problem for reference
(recall that it depends globally on the distance formula).
in the setting of the memory structure recommended in the assignment.
- Dijkstra Algorithm:
- Solve exercises 12, 13 and 14 of the document Shortest path algorithms by Jeff Erickson, linked above.
Heuristics and problem representation
- 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
Chapter 1; Pages 3-13 and 27-31.
- Hanoi Towers
Overview of optimization algorithms: Deterministic and heuristic
Deterministic optimization for nonlinear problems (constrained and non-constrained)
- Gradient descent ("steepest descent")
- Newton and Quasi-Newton methods
- Conjugate gradient methods
- Levenberg Marquardt
- Karush-Kuhn-Tucker conditions for constrained optimization
- Penalty and Barrier Methods for constrained optimization
Solve the problems proposed here.
Assignment for Research and Innovation
Solve the 8 queens problem by means of a genetic algorithm which has to be developed "ad-hoc".
Compulsory Assignment for Optimisation
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 ones given by the simple original GA and discuss whether these versions of the GA are appropriate.
Optional Assignment for Optimisation
Maximization of a (complicate and artificial) function by a genetic algorithm
(this is a more academic exercise but more standard from the point of view of genetic algorithms in binary).
- Basic bibliography
- Some interesting links from the wikipedia page
We have to load a truck with some goods. The values and the weights of these goods are listed here,
and the truck can carry a maximum weight of 600 Kg. We want to maximize the total value of the taken goods.
Ant colony algorithms
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 an ACO to compute the optimum route according to driving distance
(take edge probabilities of the form stated in page 249 of the [Dorigo, Blum] paper).
Crash mini-course on Machine Learning with Neural Networks
The list of assignments that will be proposed is the following:
||Weight in the final mark
|Map routing (A* algorithm)
|Genetic Algorithm for Optimisation
||Together increment the final mark up to 20%
|Ant Colony Algorithm|
|Genetic Algorithm for R&I
- To comply with the university evaluation rules:
- The compulsory assignment of Map routing (A* algorithm) is to be done in pairs.
- All other assignments (compulsory or optional) are individual.
- The Assignment for Research and Innovation is to be done in pairs.
- The assignments will be delivered in Campus Virtual. Further instructions will be given.
- 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
- The quality of the code of the program will be taken into account for the marks of the assignments and discussed in the interviews.