Adaptive Knowledge Transfer in Multifactorial Evolutionary Algorithm for the Clustered Minimum Routing Cost Problem

Ta Bao Thang

doi:10.1016/j.asoc.2021.107253

2021-07-01

PRE

Ta Bao Thang

Nguyen Binh Long

Huỳnh Thị Thanh Bình *

DOI：10.1016/j.asoc.2021.107253

原文链接

原文求助

摘要

En 中文

Having tremendous promising impact on society, the Internet of Things refers to the connection of millions of worldwide devices to communicate and exchange data, which requires to aggregate similar devices into clusters for maximizing the network efficiency. Minimum Routing Cost Clustered Tree Problem (CluMRCT) is a lately investigated topic that has significant application towards enhancing the interconnectivity among various devices. Belonging to NP-Hard class, the CluMRCT problem can be solved effectively by a meta-heuristic approach such as Multifactorial Evolutionary Algorithm (MFEA), which can facilitate to find better solutions for multiple problems simultaneously. Recently, an improved framework (called MFEA-II) has been introduced to overcome the weakness of algorithm performance governed by the degree of underlying inter-task synergies in the previous version. Therefore, this paper proposes to apply MFEA-II for solving multiple CluMRCT problems concurrently with the population representation under a probabilistic distribution model adept at online learning. In the proposed algorithm, evolutionary operators are applied in two levels: the first level is to construct a spanning tree in each cluster, while the second one builds a spanning tree for connecting all clusters. To reduce consuming resources, this paper also introduces a new method to calculate the cost of CluMRCT solution in linear time complexity. Numerous types of test instances are implemented to demonstrate the effectiveness of the proposed algorithm when its performance surpassed other state-of-the-art algorithms in most of the datasets. (C) 2021 Elsevier B.V. All rights reserved.

Keyword:

Multifactorial Evolutionary Algorithm

Minimum Routing Cost

Clustered Tree Problem

Adaptive Knowledge Transfer