Description of the system

[Rob174]

In this issue we will use BI for best improvement method classical approach as described in First vs. best improvement: An empirical study and FI for first improvement classical approach of the same paper

Role of the algorithm: analysis tool of an algorithm. Determine the best approach for a problem

Details input points mostly in R^2

[Rob174]

Question : why adding the cluster assigned ? In a real life situation we want to know which method (FI or BI) will give the best clustering results ?

Proposed pipeline:

[Rob174]

Ideas

How to deal with multiscale clusters

[Rob174]

2 initial solutions that outputs different results ([1])

" If the initial solution is chosen at random, the first improvement is better and faster than the best improvement. However, if the initial solution is found by some constructive heuristic, i.e., if the initial solution is not too bad, then the best improvement is slightly better and even faster in average than the first improvement. Indeed, it is shown below that when applying the 2-opt heuristic [2,3], to both the Euclidean and random distance TSP, using first improvement instead of best improvement gives on average local optima with a smaller value, but only if initial solution is chosen at random. "

[1]P. Hansen et N. Mladenović, « First vs. best improvement: An empirical study », Discrete Applied Mathematics, vol. 154, nᵒ 5, p. 802‑817, avr. 2006, doi: 10.1016/j.dam.2005.05.020.

[Rob174]

After meeting 07/02/2022 revision: