You may complete the assignment on your own or as a group of two. The assignment is due on April 25.
- Implement ITGO (Iterative TGO), see TGO. As local technique, use Unirandi. You may also complement ITGO by performing some steps of Unirandi for each point (also the old ones) before applying the clustering part.
Try to write efficient code, i.e., compute only what is needed. For instance when in computing the distance matrix by accumulating the squared distance (xi1-xj1)2+...+ (xin-xjn)2 from a point i to a point j, this sum exceeds some threshold value dm, the accumulation could be quitted and the distance recorded as maxr_real, meaning that the point j is not a potential neighbor to i. A finally accumulated distance could be checked accordingly. The threshold value could be given as input or somehow automatically computed based on the size of A. This means that especially for k near n or small dm some points may have less than k neighbors.
Pay attention also to the user interface, i.e., the way the input (convenience) and output (lay out) is handled. For each iteration, print a line with best function value, accumulated number of function evaluations, number of graph minima and IDs of graph mimima ordered from best to worst. (The ID of a point is its order of generation 1,2,... among the global points generated).
Use ITGO on the essentially unconstrained problems GOLDPR, S5, H6, G10. Try also on the constrained problem HE. The test problems are taken from Törn & Zilinskas and can be found in the course folder.
The stopping condition is not easy to determine. In an actual application you would of course use the computing time that you can afford to solve the problem. Use 10 iterations with N=100 in one run for the unconstrained problems and whatever you think is necessary for HE. A suitable value to use for k is about 8 for 100 points.
The documentation should be in the form of a research report, which means that you may experiment with different design decisions (like values for k and dm) and ideas of your own and report on your findings. Report your results for the unconstrained problems based on 10 runs. The results should include the best minimum (x, f(x)), % runs finding this minimum, average number of function evaluations made in one run, average computing time for one run measured in seconds and in standard time, i.e., time divided by the time for 1000 evaluations of the function S5.