# Optimisation 2018/19

## 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

• 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

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

• Newton and Quasi-Newton methods
• Levenberg Marquardt
• Karush-Kuhn-Tucker conditions for constrained optimization
• Penalty and Barrier Methods for constrained optimization

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

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

## Evaluation

 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

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