  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.
