MMCE and MathMods Optimisation 2012/13

C learning

Combinatorial Algorithms for graphs

Assignments

The graph of streets of Berga is given in the data file Berga-graph.txt (in UTF8) or Berga-graph-latin1.txt (in Latin1).
The corrected graph (without edges of length 0) is given in the data file Berga-graph-corrected.txt (in UTF8) or Berga-graph-corrected-latin1.txt (in Latin1).
In both assignments, the optimization is for walking. This means that the streets can be walked in both directions and, hence, the graph is undirected.

Genetic Algorithms

Assignments

First exercise (compulsory part)
  1. Use a GA to compute the minimum of the function (x + 0.2 )*x + cos(14.5 * x - 0.3).
  2. 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.
Second exercise (optional part): The knapsack problem
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.
Solve this problem by means of a genetic algorithm which has to be developed "ad-hoc".

Simulated Annealing

Assignment (based on the last previous link)

You are a zookeeper in the reptile house. One of your rare South Pacific Tufted Wizzo lizards (Tufticus wizzocus) has just had EIGHT babies. Your job is to find a place to put each baby lizard in a nursery. However, there is a catch, the baby lizards have very long tongues. A baby lizard can shoot out its tongue and eat any other baby lizard before you have time to save it. As such, you want to make sure that no baby lizard can eat another baby lizard in the nursery (burp).

For each baby lizard, you can place them in one spot on a grid. From there, they can shoot out their tongue up, down, left, right and diagonally as well. Their tongues are very long and can reach to the edge of the nursery from any location. Figure 1 shows in what ways a baby lizard can eat another.

Figure 1 (A) the baby lizard can attack any other lizard in a red square. Thus it can be seen that a baby lizard can eat another lizard to its top, bottom, left right or diagonal. (B) In this setup both lizards can eat each other.

In addition to baby lizards, your nursery has some trees planted in it. Your lizards cannot shoot their tongues through the trees nor can you move a lizard into the same place as a tree. As such, a tree will block any lizard from eating another lizard if it is in the path. Additionally, the tree will block you from moving the lizard to that location. Figure 2 shows some different valid arrangements of lizards

Figure 2 Both nurseries have valid arrangements of baby lizards such that they cannot eat one another. (A) with no trees, no lizard is in a position to eat another lizard. (B) Two trees are introduced such that the lizard in the last column cannot eat the lizard in the second or fourth column.

Write a program in C that will take as input the number (from 0 to 8) and positions of trees in the grid, and returns a valid configuration for the 8 baby lizards computed by using simulated annealing.

Idea of the algorithm: The lizards are initially placed in random rows and columns such that each lizard is in a different row and a different column. During each turn, an attacked lizard is chosen and a random column is picked for that lizard. If moving the lizard to the new column will reduce the number of attacked lizards on the board, the move is taken (so the energy function is the number of attacked lizards). Otherwise, the move is taken only with a certain probability, which decreases over time.

Questions to be addressed in the report

  1. Why is simulated annealing a good algorithm for this problem? (think about complexity and other considerations).
  2. What would be reasonable temperature decrease schedules to use for this problem? Include equations and function graphs for each schedule that you test.
  3. Experiment with the different temperature schedules you found and conduct a comparative analysis, running your algorithm on different problems (that is, different number and positions of trees). Motivate your answer with a table showing some measure of performance on your test problems (for example, steps taken) for your different schedules. Include a conclusion on which schedule seems superior with supporting statistics and illustrations.
  4. In addition to using simulated annealing, could you also have used genetic algorithms to solve this problem? If so, how would you have done it (just explain, you do not have to code), if not, then why?

Ant colony algorithms

Assignments

Solve the traveling salesman problem stated in Genetic Algorithms by using an Ant Colony System. Take edge probabilities of the form stated in page 249 of the [Dorigo, Blum] paper.

Scheduling

Assignments

Identify and solve the problem stated here with Scheduling algorithms. The data for the problem is the following (trying to be realistic):
Np: 25, 26, 27, 28, 29, 30
Nq: 16 (1 lecture per group — per class)
Nx: 16 (different groups)
Nt: 30 (5 days x 6 hours/day)

Neural Networks for Combinatorial Optimization

Assignments

Solve the traveling salesman problem stated in Genetic Algorithms by using a Neural Network.

Evaluation

The list of assignments that will be proposed is the following:
Assignment Status  Deadline  Weight in the final mark
Dijkstra Algorithm Compulsory 2012/11/26 15%
Map routing (A* algorithm) Compulsory 2012/12/10 30%
Genetic Algorithm Compulsory 2013/01/07 30%
Genetic Algorithm (2nd) Optional 2013/01/07 Together increment the final mark up to 20%
Simulated Annealing Optional 2013/01/14
Ant Colony Algorithm Optional 2013/01/21
Neural Networks Optional 2013/02/27
Scheduling Compulsory 2013/02/27 25%