New genetic algorithm approach for the min-degree constrained minimum spanning tree
| Autor: | Rui Pedro Salgueiro, Ana de Almeida, Orlando Oliveira |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
Combinatorial optimization Lower bound Information Systems and Management General Computer Science Crossover 0211 other engineering and technologies Heuristic 02 engineering and technology Management Science and Operations Research Minimum spanning tree Industrial and Manufacturing Engineering Distributed minimum spanning tree Chromosome (genetic algorithm) Degree-constrained spanning tree Genetic algorithm 0202 electrical engineering electronic engineering information engineering Mathematics 021103 operations research Ciências Sociais::Economia e Gestão [Domínio/Área Científica] Modeling and Simulation Reverse-delete algorithm 020201 artificial intelligence & image processing |
| Zdroj: | Repositório Científico de Acesso Aberto de Portugal Repositório Científico de Acesso Aberto de Portugal (RCAAP) instacron:RCAAP |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2016.11.007 |
| Popis: | A novel approach is proposed for the NP-hard min-degree constrained minimum spanning tree (md-MST). The NP-hardness of the md-MST demands that heuristic approximations are used to tackle its intractability and thus an original genetic algorithm strategy is described using an improvement of the Martins-Souza heuristic to obtain a md-MST feasible solution, which is also presented. The genetic approach combines the latter improvement with three new approximations based on different chromosome representations for trees that employ diverse crossover operators. The genetic versions compare very favourably with the best known results in terms of both the run time and obtaining better quality solutions. In particular, new lower bounds are established for instances with higher dimensions. info:eu-repo/semantics/submittedVersion |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect