A Novel Binary Firefly Algorithm for the Minimum Labeling Spanning Tree Problem.

Mugang Lin; Fangju Liu; Huihuang Zhao; Jianzhen Chen

Given a connected undirected graph G whose edges are labeled, the minimumlabeling spanning tree (MLST) problemis to find a spanning tree of G with the smallest number of different labels. TheMLST is anNP-hard combinatorial optimization problem, which is widely applied in communication networks, multimodal transportation networks, and data compression. Some approximation algorithms and heuristics algorithms have been proposed for the problem. Firefly algorithm is a new meta-heuristic algorithm. Because of its simplicity and easy implementation, it has been successfully applied in various fields. However, the basic firefly algorithm is not suitable for discrete problems. To this end, a novel discrete firefly algorithm for the MLST problem is proposed in this paper. A binary operation method to update firefly positions and a local feasible handling method are introduced, which correct unfeasible solutions, eliminate redundant labels, and make the algorithm more suitable for discrete problems. Computational results show that the algorithm has good performance. The algorithm can be extended to solve other discrete optimization problems.

ALGORITHMS; SPANNING trees; CONTAINERIZATION; LABELS; UNDIRECTED graphs; DATA compression; BINARY operations; GRAPH labelings

Computer Modeling in Engineering & Sciences (CMES), 2020, Vol 125, Issue 1, p197

1526-1492

Academic Journal

10.32604/cmes.2020.09502