Complete version of lecture notes

I have added a section covering the material for the next lecture to the notes, which means that we now have a first complete version. Based on your input, I have also corrected and extended sections 6.1-6.3 on makespan scheduling. Further suggestions are welcome.

Best regards,

Carsten

Lecture notes updated and next mandatory exercise

Regarding the next mandatory exercise, I was asked what n/i-approximation means. Please see page 20 in the updated lecture notes and put r=n/i there.

Best regards,

Carsten

Remarks on Mandatory Exercise (update)

For your solution of the mandatory exercise it might be convenient to assume that the weights are sorted as w_1 >= w_2 >= … >= w_n. This does not lose generality since the (1+1) EA does not care (more precisely, it has the same stochastic behavior) when you rename the bits.

Note that the exercise considers a class of functions, which includes, amongst others, OneMax and BinVal. So you cannot assume that all weights are different. As a matter of fact, you are not allowed to change the algorithm depending on the function.

Finally, make sure to prove that your partition is fitness-based (in particular verify condition 4 from the definition) and prove that for every search point from a level there is a way to improve to a higher level. Most likely you need an argument like: If the search point is in level L_i (which might be defined according to the fitness only), then I still know that the search point has this-and-that kind of structure, and therefore there is a mutation that results in a search point from a higher level.

Best regards,

Carsten

Fitness-based partition for BinVal

In today’s lecture, it was asked whether the fitness-based partition for BinVal presented on page 19 of the slides

(L_i:=\{x\mid 2^{n-1} + 2^{n-2} + \dots + 2^{n-i} \le \textsc{BinVal}(x)
< 2^{n-1} + 2^{n-2} + \dots +  2^{n-i}+ 2^{n-i-1}\})

is correct or whether the last -1 should be a +1. I think the definition is correct since the powers of 2 are listed in decreasing order.

Best regards,

Carsten

Office hours Carsten

My office hours (until further notice) take place on Thursdays from 12-13 in my office (322/124).

Best regards,

Carsten

Lecture 2010-04-19: additional literature

Following the discussions during the lecture and exercises, you might be interested in the following papers.

1. Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer (1993): Data Structures for Traveling Salesmen. SODA 1993, ACM Press, 145-154
2. J. Reichel, M. Skutella (2009): On the Size of Weights in Randomized Search Heuristics. FOGA 2009, ACM Press, 21-28

The first paper deals with efficient implementations of k-opt moves for the TSP, while the second one is concerned with the limitations of the proof method “expected multiplicative distance decrease”.

As said above, these two papers are for the interested only and not part of the curriculum.

Carsten

Office hours Carsten (22.04.10)

This week my office hours are on Thursday, 22.04.10, from 14-15.

Carsten

Office hours Carsten

I am going to offer an office hour Thursday this week (15.04.) from 13.00-14.00. If you have questions concerning the exercises or the course in general, please feel welcome to come by my office: bldg. 322, room 122.

Carsten