A Hybrid Framework Combining Genetic Algorithm with Iterated Local Search for the Dominating Tree Problem

Shuli Hu, Huan Liu, Xiaoli Wu, Ruizhi Li, Junping Zhou and Jianan Wang
Additional contact information
Shuli Hu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Huan Liu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Xiaoli Wu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Ruizhi Li: School of Management Science and Information Engineering, Jilin University of Finance and Economics, Changchun 130117, China
Junping Zhou: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Jianan Wang: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China

Mathematics, 2019, vol. 7, issue 4, 1-14

Abstract: Given an undirected, connected and edge-weighted graph, the dominating tree problem consists of finding a tree with minimum total edge weight such that for each vertex is either in the tree or adjacent to a vertex in the tree. In this paper, we propose a hybrid framework combining genetic algorithm with iterated local search (GAITLS) for solving the dominating tree problem. The main components of our framework are as follows: (1) the score functions D s c o r e and W s c o r e applied in the initialization and local search phase; (2) the initialization procedure with restricted candidate list (RCL) by controlling the parameter to balance the greediness and randomness; (3) the iterated local search with three phases, which is used to intensify the individuals; (4) the mutation with high diversity proposed to perturb the population. The experimental results on the classical instances show that our method performs much better than the-state-of-art algorithms.

Keywords: dominating tree; genetic algorithm; iterated local search; score functions (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/4/359/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/4/359/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:4:p:359-:d:224458

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().