This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices...This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices to the respective closest one of two prescribed vertices in the modified network is upper bounded by a given value.l1 norm and l∞norm are used to measure the total modification cost. These two problems have a strong practical application background and important theoretical research value. It is shown that such problems can be transformed into a series of sum-type and bottleneck-type continuous knapsack problems respectively.Based on the property of the optimal solution two O n2 algorithms for solving the two problems are proposed where n is the number of vertices on the tree.展开更多
As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a nume...As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.展开更多
Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a f...Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.展开更多
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.展开更多
Conservation of ancient and large trees in domestic and overseas cities was compared, ancient and large trees were regarded as important cultural relics playing an important role in optimizing urban natural environmen...Conservation of ancient and large trees in domestic and overseas cities was compared, ancient and large trees were regarded as important cultural relics playing an important role in optimizing urban natural environment and enriching urban humanistic and natural landscapes, and they were also important contents of urban garden works symbolizing urban parks. A case study was carried out Yunqizhujing Park to study conservation of ancient and large trees in park green spaces of Hangzhou City, solutions to current problems were proposed, and constructive suggestions were given for the conservation of ancient and large trees in urban park green spaces.展开更多
As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality ...As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.展开更多
Multi-objective optimal evolutionary algorithms (MOEAs) are a kind of new effective algorithms to solve Multi-objective optimal problem (MOP). Because ranking, a method which is used by most MOEAs to solve MOP, has so...Multi-objective optimal evolutionary algorithms (MOEAs) are a kind of new effective algorithms to solve Multi-objective optimal problem (MOP). Because ranking, a method which is used by most MOEAs to solve MOP, has some shortcoming s, in this paper, we proposed a new method using tree structure to express the relationship of solutions. Experiments prove that the method can reach the Pare-to front, retain the diversity of the population, and use less time.展开更多
The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is int...The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is introduced. Compared with other evolutionary algorithms on MST problem, it is more advanced: firstly, very simple and easy to realize; then, efficient and accurate; finally general on other combination optimization problems.展开更多
Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding co...Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.展开更多
k-ary trees are one of the most basic data structures in Computer Science. A new method is presented to determine how many there are with n nodes. This method gives additional insight into their structure and provides...k-ary trees are one of the most basic data structures in Computer Science. A new method is presented to determine how many there are with n nodes. This method gives additional insight into their structure and provides a new algo-rithm to efficiently generate such a tree randomly.展开更多
基金The National Natural Science Foundation of China(No.10801031)
文摘This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices to the respective closest one of two prescribed vertices in the modified network is upper bounded by a given value.l1 norm and l∞norm are used to measure the total modification cost. These two problems have a strong practical application background and important theoretical research value. It is shown that such problems can be transformed into a series of sum-type and bottleneck-type continuous knapsack problems respectively.Based on the property of the optimal solution two O n2 algorithms for solving the two problems are proposed where n is the number of vertices on the tree.
文摘As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.
文摘Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.
基金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.
基金Supported by Lin’an Scientific and Technological Program of Zhejiang Province(200933)Hangzhou Social Development Scientific Research Program of Zhejiang Province(20100933B34)
文摘Conservation of ancient and large trees in domestic and overseas cities was compared, ancient and large trees were regarded as important cultural relics playing an important role in optimizing urban natural environment and enriching urban humanistic and natural landscapes, and they were also important contents of urban garden works symbolizing urban parks. A case study was carried out Yunqizhujing Park to study conservation of ancient and large trees in park green spaces of Hangzhou City, solutions to current problems were proposed, and constructive suggestions were given for the conservation of ancient and large trees in urban park green spaces.
基金the National Natural Science Foundation of China (No. 79870030).
文摘As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.
基金Supported by the National Natural Science Foundation of China(60073043,70071042,60133010)
文摘Multi-objective optimal evolutionary algorithms (MOEAs) are a kind of new effective algorithms to solve Multi-objective optimal problem (MOP). Because ranking, a method which is used by most MOEAs to solve MOP, has some shortcoming s, in this paper, we proposed a new method using tree structure to express the relationship of solutions. Experiments prove that the method can reach the Pare-to front, retain the diversity of the population, and use less time.
文摘The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is introduced. Compared with other evolutionary algorithms on MST problem, it is more advanced: firstly, very simple and easy to realize; then, efficient and accurate; finally general on other combination optimization problems.
文摘Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.
文摘k-ary trees are one of the most basic data structures in Computer Science. A new method is presented to determine how many there are with n nodes. This method gives additional insight into their structure and provides a new algo-rithm to efficiently generate such a tree randomly.
