Degree constrained minimum spanning tree problem: a learning automata approach

Degree-constrained minimum spanning tree problem is an NP-hard bicriteria combinatorial optimization problem seeking for the minimum weight spanning tree subject to an additional degree constraint on graph vertices. Due to the NP-hardness of the problem, heuristics are more promising approaches to find a near optimal solution in a reasonable time. This paper proposes a decentralized learning automata-based heuristic called LACT for approximating the DCMST problem. LACT is an iterative algorithm, and at each iteration a degree-constrained spanning tree is randomly constructed. Each vertex selects one of its incident edges and rewards it if its weight is not greater than the minimum weight seen so far and penalizes it otherwise. Therefore, the vertices learn how to locally connect them to the degree-constrained spanning tree through the minimum weight edge subject to the degree constraint. Based on the martingale theorem, the convergence of the proposed algorithm to the optimal solution is proved. Several simulation experiments are performed to examine the performance of the proposed algorithm on well-known Euclidean and non-Euclidean hard-to-solve problem instances. The obtained results are compared with those of best-known algorithms in terms of the solution quality and running time. From the results, it is observed that the proposed algorithm significantly outperforms the existing method.     

The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm

In this paper we consider the quadratic minimum spanning tree problem (QMSTP) which is known to be NP-hard. Given a complete graph, the QMSTP consists of finding a minimum spanning tree (MST) where interaction costs between pairs of edges are prescribed. A Lagrangian relaxation procedure is devised and an efficient local search algorithm with tabu thresholding is developed. Computational experiments are reported on standard test instances, randomly generated test instances and quadratic assignment problem (QAP) instances from the QAPLIB by using a transformation scheme. The local search heuristic yields very good performance and the Lagrangian relaxation procedure gives the tightest lower bounds for all instances when compared to previous lower bounding approaches.     

A swarm intelligence approach to the quadratic minimum spanning tree problem

The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.     

Evolving combinatorial problem instances that are difficult to solve

This paper demonstrates how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. As a result of this technique, the corresponding algorithms used to solve these instances are stress-tested. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. The problem instances acquired through this technique are more difficult than the ones found in popular benchmarks. In this paper, these evolved instances are analysed with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.     

From the Dandelion Code to the Rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality

There are many ways to represent spanning trees in genetic algorithms (GAs). Among them are Cayley codes, which represent each tree on n vertices as a string of (n-2) integers from the set [1,n]. In 2003, Thompson showed that the Dandelion Code, a Cayley code with high locality, offers consistently better performance in a GA than all other known Cayley codes, including the Pru/spl uml/fer Code and the Blob Code. In this paper, we study the Dandelion Code and its properties. We give linear-time implementations of the decoding and encoding algorithms, and prove that the representation has bounded locality and asymptotically optimal locality, unlike all other known Cayley codes. We then modify the Dandelion Code to create bijective spanning tree representations for graph topologies other than the complete graph. Two variations are described: the bipartite Dandelion Code (for encoding the spanning trees of a complete bipartite graph) and the Rainbow Code (for encoding the spanning trees of a complete layered graph). Both variations inherit the Dandelion Code's desirable properties, and have the potential to outperform existing GA representations for computationally hard transportation problems (including the Fixed Charge Transportation Problem) and multistage transportation problems, particularly on large instances.     

Random-tree Diameter and the Diameter-constrained MST

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations such as when distributed mutual-exclusion algorithms are used, or when information retrieval algorithms need to compromise between fast access and small storage. The Diameter-Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph, G , with n nodes and a positive integer, k , find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP-complete, for all values of k ; 4 h k h ( n m 2). In this paper, we investigate the behavior of the diameter of an MST in randomly generated graphs. Then, we present heuristics that produce approximate solutions for the DCMST problem in polynomial time. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs.     

基于最小代价和生成树的算法研究

最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。     

Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem

Hyper heuristics is a relatively new optimisation algorithm. Numerous studies have reported that hyper heuristics are well applied in combinatorial optimisation problems. As a classic combinatorial optimisation problem, the row layout problem has not been publicly reported on applying hyper heuristics to its various sub-problems. To fill this gap, this study proposes a parallel hyper-heuristic approach based on reinforcement learning for corridor allocation problems and parallel row ordering problems. For the proposed algorithm, an outer layer parallel computing framework was constructed based on the encoding of the problem. The simulated annealing, tabu search, and variable neighbourhood algorithms were used in the algorithm as low-level heuristic operations, and Q-learning in reinforcement learning was used as a high-level strategy. A state space containing sequences and fitness values was designed. The algorithm performance was then evaluated for benchmark instances of the corridor allocation problem (37 groups) and parallel row ordering problem (80 groups). The results showed that, in most cases, the proposed algorithm provided a better solution than the best-known solutions in the literature. Finally, the meta-heuristic algorithm applied to three low-level heuristic operations is taken as three independent algorithms and compared with the proposed hyper-heuristic algorithm on four groups of parallel row ordering problem instances. The effectiveness of Q-learning in selection is illustrated by analysing the comparison results of the four algorithms and the number of calls of the three low-level heuristic operations in the proposed method.     

Solving an algebraic path problem and some related graph problemson a hyper-bus broadcast network

The parallel computation model upon which the proposed algorithms are based is the hyper-bus broadcast network. The hyper-bus broadcast network consists of processors which are connected by global buses only. Based on such an improved architecture, we first design two O(1) time basic operations for finding the maximum and minimum of N numbers each of size O(log N)-bit and computing the matrix multiplication operation of two N×N matrices, respectively. Then, based on these two basic operations, three of the most important instances in the algebraic path problem, the connectivity problem, and several related problems are all solved in O(log N) time. These include the all-pair shortest paths, the minimum-weight spanning tree, the transitive closure, the connected component, the biconnected component, the articulation point, and the bridge problems, either in an undirected or a directed graph, respectively     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

Broadcasting Spanning Forests on a Multiple-Access Channel

The problem of finding a spanning forest of a graph in a distributed-processing environment is studied. If an input graph is weighted, then the goal is to find a minimum-weight spanning forest. The processors communicate by broadcasting. The output consists of the edges that make a spanning forest and have been broadcast on the network. Input edges are distributed among the processors, with each edge held by one processor. The underlying broadcast network is implemented as a multiple-access channel. If exactly one processor attempts to perform a broadcast, then the broadcast is successful. A message broadcast successfully is delivered to all the processors in one step. If more than one processors broadcast simultaneously, then the messages interfere with each other and no processor can receive any of them. Optimality of algorithmic solutions is investigated, by way of comparing deterministic with randomized algorithms, and adaptive with oblivious ones. Lower bounds are proved that either justify the optimality of specific algorithms or show that the optimal performance depends on a class of algorithms.     

Rough‐fuzzy quadratic minimum spanning tree problem

A quadratic minimum spanning tree problem determines a minimum spanning tree of a network whose edges are associated with linear and quadratic weights. Linear weights represent the edge costs whereas the quadratic weights are the interaction costs between a pair of edges of the graph. In this study, a bi‐objective rough‐fuzzy quadratic minimum spanning tree problem has been proposed for a connected graph, where the linear and the quadratic weights are represented as rough‐fuzzy variables. The proposed model is formulated by using rough‐fuzzy chance‐constrained programming technique. Subsequently, three related theorems are also proposed for the crisp transformation of the proposed model. The crisp equivalent models are solved with a classical multi‐objective solution technique, the epsilon‐constraint method and two multi‐objective evolutionary algorithms: (a) nondominated sorting genetic algorithm II (NSGA‐II) and (b) multi‐objective cross‐generational elitist selection, heterogeneous recombination, and cataclysmic mutation (MOCHC) algorithm. A numerical example is provided to illustrate the proposed model when solved with different methodologies. A sensitivity analysis of the example is also performed at different confidence levels. The performance of NSGA‐II and MOCHC are analysed on five randomly generated instances of the proposed model. Finally, a numerical illustration of an application of the proposed model is also presented in this study.     

Finding the k most vital edges with respect to minimum spanning tree

For a connected, undirected and weighted graph G = (V,E), the problem of finding the k most vital edges of G with respect to minimum spanning tree is to find k edges in G whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitraryk. In this paper, we first describe a simple exact algorithm for this problem, based on t he approach of edge replacement in the minimum spanning tree of G. Next we present polynomial-time randomized algorithms that produce optimal and approximate solutions to this problem. For and , our algorithm producing optimal solution has a time complexity of O(mn) with probability of success at least , which is 0.90 for and asymptotically 1 when k goes to infinity. The algorithm producing approximate solution runs in time with probability of success at least , which is 0.998 for , and produces solution within factor 2 to the optimal one. Finally we show that both of our randomized algorithms can be easily parallelized. On a CREW PRAM, the first algorithm runs in O(n) time using processors, and the second algorithm runs in time using mn/logn processors and hence is RNC. Received 30 October 1995 / 5 November 1998     

并行机间歇过程生产调度的遗传局部搜索算法

研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

Energy-aware topology control for wireless sensor networks using memetic algorithms

Cost-effective topology control is critical in wireless sensor networks. While much research has been carried out in this aspect using various methods, no attention has been made on utilizing modern heuristics for this purpose. This paper proposes a memetic algorithm-based solution for energy-aware topology control for wireless sensor networks. This algorithm (called ToCMA), using a combination of problem-specific light-weighted local search and genetic algorithms, is able to solve the minimum energy network connectivity (MENC) this NP-hard problem in an approximated manner that performs better than the classical minimum spanning tree (MST) solution. The outcomes of ToCMA can also be utilized for various network optimization and fault-tolerant purposes.     

Randomized local search,evolutionary algorithms,and the minimum spanning tree problem

Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.     

A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem

Given a graph with its vertex set partitioned into a set of groups, nonnegative costs associated to its edges, and nonnegative prizes associated to its vertices, the prize‐collecting generalized minimum spanning tree problem consists in finding a subtree of this graph that spans exactly one vertex of each group and minimizes the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP‐hard generalized minimum spanning tree optimization problem. We propose a GRASP (greedy randomized adaptive search procedure) heuristic for its approximate solution, incorporating path‐relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path‐relinking and restarts heuristic with a data mining strategy that is applied along with the GRASP iterations, after the elite set is modified and becomes stable, contributes to making the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.     

Ant Colony Optimization and the minimum spanning tree problem

Ant Colony Optimization (ACO) is a kind of metaheuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. In contrast to many successful applications, the theoretical foundation of this kind of metaheuristic is rather weak. Theoretical investigations with respect to the runtime behavior of ACO algorithms have been started only recently for the optimization of pseudo-Boolean functions.We present the first comprehensive rigorous analysis of a simple ACO algorithm for a combinatorial optimization problem. In our investigations, we consider the minimum spanning tree (MST) problem and examine the effect of two construction graphs with respect to the runtime behavior. The choice of the construction graph in an ACO algorithm seems to be crucial for the success of such an algorithm. First, we take the input graph itself as the construction graph and analyze the use of a construction procedure that is similar to Broder’s algorithm for choosing a spanning tree uniformly at random. After that, a more incremental construction procedure is analyzed. It turns out that this procedure is superior to the Broder-based algorithm and produces additionally in a constant number of iterations an MST, if the influence of the heuristic information is large enough.     

The multi-criteria minimum spanning tree problem based genetic algorithm

Minimum spanning tree (MST) problem is of high importance in network optimization and can be solved efficiently. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problems in the real world, but it is difficult for traditional optimization technique to deal with. In this paper, a non-generational genetic algorithm (GA) for mc-MST is proposed. To keep the population diversity, this paper designs an efficient crossover operator by using dislocation a crossover technique and builds a niche evolution procedure, where a better offspring does not replace the whole or most individuals but replaces the worse ones of the current population. To evaluate the non-generational GA, the solution sets generated by it are compared with solution sets from an improved algorithm for enumerating all Pareto optimal spanning trees. The improved enumeration algorithm is proved to find all Pareto optimal solutions and experimental results show that the non-generational GA is efficient.