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 combinatoria...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.展开更多
To reduce the difficulty of implementation and shorten the runtime of the traditional Kim-Fisher model, an entirely discrete Kim-Fisher-like model on lattices is proposed. The discrete model is directly built on the l...To reduce the difficulty of implementation and shorten the runtime of the traditional Kim-Fisher model, an entirely discrete Kim-Fisher-like model on lattices is proposed. The discrete model is directly built on the lattices, and the greedy algorithm is used in the implementation to continually decrease the energy function. First, regarding the gray values in images as discrete-valued random variables makes it possible to make a much simpler estimation of conditional entropy. Secondly, a uniform method within the level set framework for two-phase and multiphase segmentations without extension is presented. Finally, a more accurate approximation to the curve length on lattices with multi-labels is proposed. The experimental results show that, compared with the continuous Kim-Fisher model, the proposed model can obtain comparative results, while the implementation is much simpler and the runtime is dramatically reduced.展开更多
基金This work is supported by the National Natural Science Foundation of China under Grant 61772179the Hunan Provincial Natural Science Foundation of China under Grant 2019JJ40005+3 种基金the Science and Technology Plan Project of Hunan Province under Grant 2016TP1020the Double First-Class University Project of Hunan Province under Grant Xiangjiaotong[2018]469the Open Fund Project of Hunan Provincial Key Laboratory of Intelligent Information Processing and Application for Hengyang Normal University under Grant IIPA19K02the 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.
文摘To reduce the difficulty of implementation and shorten the runtime of the traditional Kim-Fisher model, an entirely discrete Kim-Fisher-like model on lattices is proposed. The discrete model is directly built on the lattices, and the greedy algorithm is used in the implementation to continually decrease the energy function. First, regarding the gray values in images as discrete-valued random variables makes it possible to make a much simpler estimation of conditional entropy. Secondly, a uniform method within the level set framework for two-phase and multiphase segmentations without extension is presented. Finally, a more accurate approximation to the curve length on lattices with multi-labels is proposed. The experimental results show that, compared with the continuous Kim-Fisher model, the proposed model can obtain comparative results, while the implementation is much simpler and the runtime is dramatically reduced.
