Author Archives: cawidtu

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

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

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