Optimisation 2018/19

Master's degree in Modelling for Science and Engineering

C learning

Combinatorial Algorithms for graphs

  • General Bibliography

    • Compulsory Assignment

    A* Algorithm:
    Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from here (348.5Mb).
    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 spain.csv.zip). 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.

    Optional Assignment

    Dijkstra Algorithm:
    Solve exercises 12, 13 and 14 of the document Shortest path algorithms by Jeff Erickson, linked above.

    Heuristics and problem representation

    Overview of optimization algorithms: Deterministic and heuristic

    Deterministic optimization for nonlinear problems (constrained and non-constrained)

    Compulsory Assignment

    Solve the problems proposed here.

    Genetic Algorithms

    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).

    Simulated Annealing

    Assignments

    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

    Concrete Examples

    Assignments

    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


    Evaluation

    The list of assignments that will be proposed is the following:
    Assignment Status Deadline Weight in the final mark
    Map routing (A* algorithm) Compulsory 23/12/2018 50%
    Genetic Algorithm for Optimisation Compulsory 03/02/2019 30%
    Deterministic Optimisation Compulsory 10/02/2019 20%
    Dijkstra Algorithm Optional 10/02/2019 Together increment the final mark up to 20%
    Simulated Annealing
    Ant Colony Algorithm
    Genetic Algorithm for R&I 30/11/2018