Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem
This addresses NP-hard combinatorial optimization problems like MLST, offering a novel algorithmic approach with potential broader applications, though it appears incremental as an adaptation of evolutionary concepts.
The paper tackles the minimum labeling Steiner tree (MLST) problem by proposing devolutionary genetic algorithms, which start from super-optimal unfeasible solutions and devolve to feasible ones, showing competitive performance compared to state-of-the-art methods in experiments on randomly generated instances.
This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We claim that distinguishing them from the widely used evolutionary algorithms is relevant. The most important distinction lies in the fact that in the former type of processes, the value function decreases over successive generation of solutions, thus providing a natural stopping condition for the computation process. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution among the first generations of feasible solutions. We additionally introduce a novel integer linear programming formulation of the MLST problem and a valid constraint used for speeding up the devolutionary process. Finally, we conduct an experiment comparing the performances of devolutionary algorithms to those of state of the art approaches used for solving randomly generated instances of the MLST problem. Results of this experiment support the use of devolutionary algorithms for the MLST problem and their development for other NP-hard combinatorial optimization problems.