A Hybrid Steady-State Genetic Algorithm for the Minimum Conflict Spanning Tree Problem

This paper studies a hybrid approach for the minimum conflict spanning tree (MCST) problem, where the MCST problem deals with finding a spanning tree (T) with the minimum number of conflicting edge-pairs. The problem finds some important real-world applications. In this hybrid approach (hSSGA), a steady-state genetic algorithm generates a child solution with the help of crossover operator and mutation operator which are applied in a mutually exclusive way, and the generated child solution is further improved through a local search based on reduction of conflicting edge-pairs. The proposed crossover operator is problem-specific operator that attempt to create a fitter child solution. All components of SSGA and local search effectively coordinate in finding a conflict-free solution or a solution with a minimal number of conflicting edge-pairs. Experimental results, particularly, on available 12 instances of type 1 benchmark instances whose conflict solutions are not known show that the proposed hybrid approach hSSGA is able to find better solution quality in comparison to state-of-the-art approaches. Also, hSSGA discovers new values on 8 instances out of 12 instances of type 1.