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.展开更多
Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-t...Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree 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.展开更多
Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of p...Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.展开更多
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.展开更多
This study uses a simulation-based approach to investigate the impact of delivery delays due to constraints on transport capacity, transit speed, and routing efficiencies on an economy with various levels of interdepe...This study uses a simulation-based approach to investigate the impact of delivery delays due to constraints on transport capacity, transit speed, and routing efficiencies on an economy with various levels of interdependency among firms. The simulation uses object-oriented programming to create specialized production, consumption, and transportation classes. A set of objects from each class is distributed randomly on a 2D plane. A road network is then established between fixed objects using Prim’s MST (Minimum Spanning Tree) algorithm, followed by construction of an all-pair shortest path matrix using the Floyd Warshall algorithm. A genetic algorithm-based vehicle routing problem solver employs the all-pair shortest path matrix to best plan multiple pickup and delivery orders. Production units utilize economic order quantities (EOQ) and reorder points (ROP) to manage inventory levels. Hicksian and Marshallian demand functions are utilized by consumption units to maximize personal utility. The transport capacity, transit speed, routing efficiency, and level of interdependence serve as 4 factors in the simulation, each assigned 3 distinct levels. Federov’s exchange algorithm is used to generate an orthogonal array to reduce the number of combination replays from 3<sup>4</sup> to just 9. The simulation results of a 9-run orthogonal array on an economy with 6 mining facilities, 12 industries, 8 market centers, and 8 transport hubs show that the level of firm interdependence, followed by transit speed, has the most significant impact on economic productivity. The principal component analysis (PCA) indicates that interdependence and transit speed can explain 90.27% of the variance in the data. According to the findings of this research, a dependable and efficient regional transportation network among various types of industries is critical for regional economic development.展开更多
文摘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 National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree 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.
文摘Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.
文摘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.
文摘This study uses a simulation-based approach to investigate the impact of delivery delays due to constraints on transport capacity, transit speed, and routing efficiencies on an economy with various levels of interdependency among firms. The simulation uses object-oriented programming to create specialized production, consumption, and transportation classes. A set of objects from each class is distributed randomly on a 2D plane. A road network is then established between fixed objects using Prim’s MST (Minimum Spanning Tree) algorithm, followed by construction of an all-pair shortest path matrix using the Floyd Warshall algorithm. A genetic algorithm-based vehicle routing problem solver employs the all-pair shortest path matrix to best plan multiple pickup and delivery orders. Production units utilize economic order quantities (EOQ) and reorder points (ROP) to manage inventory levels. Hicksian and Marshallian demand functions are utilized by consumption units to maximize personal utility. The transport capacity, transit speed, routing efficiency, and level of interdependence serve as 4 factors in the simulation, each assigned 3 distinct levels. Federov’s exchange algorithm is used to generate an orthogonal array to reduce the number of combination replays from 3<sup>4</sup> to just 9. The simulation results of a 9-run orthogonal array on an economy with 6 mining facilities, 12 industries, 8 market centers, and 8 transport hubs show that the level of firm interdependence, followed by transit speed, has the most significant impact on economic productivity. The principal component analysis (PCA) indicates that interdependence and transit speed can explain 90.27% of the variance in the data. According to the findings of this research, a dependable and efficient regional transportation network among various types of industries is critical for regional economic development.
