Publication: Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem
Issued Date
2018-06-01
Resource Type
ISSN
18686486
18686478
18686478
Other identifier(s)
2-s2.0-85047907384
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Evolving Systems. Vol.9, No.2 (2018), 157-168
Suggested Citation
Nassim Dehouche Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem. Evolving Systems. Vol.9, No.2 (2018), 157-168. doi:10.1007/s12530-017-9182-z Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/45633
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem
Author(s)
Other Contributor(s)
Abstract
© 2017, Springer-Verlag Berlin Heidelberg. 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.