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

作　　者：Mugang Lin Fangju Liu Huihuang Zhao Jianzhen Chen 

机构地区：[1]College of Computer Science and Technology,Hengyang Normal University,Hengyang,421002,China [2]Hunan Provincial Key Laboratory of Intelligent Information Processing and Application,Hengyang,421002,China [3]School of Computer Science,University of South China,Hengyang,421001,China

出　　处：《Computer Modeling in Engineering & Sciences》2020年第10期197-214,共18页工程与科学中的计算机建模（英文）

基　　金：This work is supported by the National Natural Science Foundation of China under Grant 61772179;the Hunan Provincial Natural Science Foundation of China under Grant 2019JJ40005;the Science and Technology Plan Project of Hunan Province under Grant 2016TP1020;the Double First-Class University Project of Hunan Province under Grant Xiangjiaotong[2018]469;the Open Fund Project of Hunan Provincial Key Laboratory of Intelligent Information Processing and Application for Hengyang Normal University under Grant IIPA19K02;the Science Foundation of Hengyang Normal University under Grant 19QD13.

摘　　要：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.

关 键 词：Minimum labeling spanning tree problem binary firefly algorithm META-HEURISTICS discrete optimization 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]