Parameter-free and cooperative local search algorithms for graph colouring

Parameter-free algorithms are of an increasing interest in applications that require out-of-the-box solving techniques. For instance, scheduling in volatile environments or control parameters optimisation often requires flexible solving approaches without the need to tune or retune the parameters. In addition, parameter-free algorithms are usually beneficial in solving previously unexplored real-world problem instances. In this paper, we propose a parameter-free local search strategy to solve graph colouring, which is the underlying problem for a number of scheduling applications. Two variants of parameter-free local search are computationally investigated: PFLS-A and PFLS-B. Both of these algorithms are based on accepting strictly improving moves and operating as a random walk if no strictly improving move is found. PFLS-A and PFLS-B differ in randomised versus systematic exploration of the neighbourhood of the current solution. Their cooperative variant CPFLS is also proposed. We compare the results of these three algorithms to the results obtained by 13 other local search methods from the literature. CPFLS provides better or equal results as the other local search algorithms in 67.25 % of per-instance comparisons. This is without employing any explicit or implicit parameters that are usually used in metaheuristics. This hints the promising nature of parameter-free metaheuristics not only for this problem but also metaheuristics in general.