الگوریتم مصنوعی کلونی زنبور عسل برای حداقل برگ محدود پوشا درمسئله درخت

Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks on this graph a spanning tree of minimum weight among all the spanning trees of the graph that have at least ℓℓ leaves. In this paper, we have proposed an artificial bee colony (ABC) algorithm for the LCMST problem. The ABC algorithm is a new metaheuristic approach inspired by intelligent foraging behavior of honeybee swarm. We have compared the performance of our ABC approach against the best approaches reported in the literature. Computational results demonstrate the superiority of the new ABC approach over all the other approaches. The new approach obtained better quality solutions in shorter time.

Given an undirected, connected, weighted graph with n nodes and a positive integer ℓ(2≤ℓ<n−1)ℓ(2≤ℓ<n−1), the leaf-constrained minimum spanning tree (LCMST) problem seeks on this graph a spanning tree that contains at least ℓℓ leaves and has minimum total weight among all such spanning trees. Formally, let G = (V, E) be an undirected, connected graph, where V denotes the set of nodes and E denotes the set of edges. Given a non-negative weight function w:E→ℝ+w:E→ℝ+ associated with its edges and a positive integer ℓ(2≤ℓ<n−1)ℓ(2≤ℓ<n−1), the LCMST problem seeks a spanning tree T ⊆ E that has at least ℓℓ leaves and that minimizes: View the MathML sourceW(T)=∑e∈Tw(e) In general, this problem is NP-Hard [1]. If the leaf constraint ℓℓ is less than the number of leaves in an unconstrained minimum spanning tree (MST), then this MST is also a LCMST. Therefore, the LCMST problem can be solved in polynomial time in this case. However, if ℓℓ is larger than the number of leaves in any MST, then the LCMST problem is NP-Hard. Usually, the difficulty of the problem increases with increase in ℓℓ. The LCMST problem has several practical applications. It finds applications in facilities location, circuit and network designs [2]. This problem can be considered as an extension of the p-median problem, where medians are also connected among themselves [3]. Several heuristics for the LCMST problem work by first computing a MST and then transforming this MST into a leaf-constrained spanning tree (LCST), i.e., a spanning tree with at least ℓℓ leaves. Deo and Micikevicius [1] presented one such heuristic. It iteratively tries to transform a MST into a LCST. During each iteration, it interchanges a tree edge with a non-tree edge so that the number of leaves in the tree increases with minimum increase in tree’s weight. This process is repeated until either the number of leaves in the tree reaches ℓℓ or no edge interchange is possible that increases the number of leaves. Therefore, this heuristic some times fails to find a LCST. Its time complexity is O(n4). Julstrom [4] proposed another heuristic called ML that also begins by computing a MST. Then it iteratively transforms this MST into a LCST. During each iteration, it selects an interior node (a node that is not a leaf) from the set of current interior nodes and converts it into a leaf. The interior node is selected according to the following criterion. It tries each interior node as leaf one by one. During each trial it finds a MST on the graph induced by the remaining interior nodes and then connects all leaves including the new one to the nearest interior node. The interior node for which the resulting spanning tree is of minimum weight is chosen for conversion to leaf. This process is repeated until the number of leaves in the spanning tree reaches ℓℓ. If the underlying graph is complete then ML always finds a LCST. The complexity of ML is also O(n4). Julstrom [4] observed that for ℓ=0.6nℓ=0.6n, ML finds lower-weight LCSTs than the heuristic of Deo and Micikevicius [1] does and for ℓ=0.9nℓ=0.9n the latter heuristic always fails to find a LCST. Edelson and Gargano [5] developed a permutation-coded genetic algorithm for the LCMST problem that encodes a LCST using 3n−ℓ−23n−ℓ−2 symbols. A two-level decoder converts this encoding first into Prüfer code [6] and then this Prüfer code into equivalent LCST. This scheme represents only the feasible solutions. However, chromosome length is considerably large with this scheme. Julstrom [2] presented two generational genetic algorithms. One of these two genetic algorithms uses the Blob code [7], whereas the other uses the subset coding. The subset coding represents a LCST by the set of its interior nodes only. A two-step procedure converts this coding into its equivalent LCST. The first step constructs a MST on the graph induced by the set of interior nodes, whereas the latter step connects each leaf to its nearest interior node. Like the encoding of Edelson and Gargano [5], both of these encodings also represent feasible solutions only. At the same time their chromosome lengths are much smaller. The chromosome length with Blob code is n – 2, whereas that with subset coding is n−ℓn−ℓ. The genetic operators for these two genetic algorithms are designed in such a way that they generate feasible solutions only. Computational results on the test instances considered in [2] showed that subset-coded genetic algorithm always finds the LCST of lowest weight followed by ML heuristic. The Blob-coded genetic algorithm performed even worse than ML heuristic. Hereafter, the subset-coded genetic algorithm will be referred to as SCGA. Singh and Baghel [8] presented two metaheuristic approaches, one based on ant-colony optimization (ACO) and the other based on tabu search, for the LCMST problem and compared their approaches with the subset-coded genetic algorithm and ML heuristic [2]. Both of these methods use the subset coding [2] to represent a LCST and construct the equivalent LCST according to the two-step procedure described above. The ACO approach constructs a LCST by first identifying its (n−ℓ)(n−ℓ) interior nodes through ant and then constructs the complete LCST by the two-step procedure. Starting from a random initial solution, the tabu search iteratively moves from one solution to another by exchanging an interior node with a leaf node until the stopping criterion is satisfied. During each iteration, among all valid exchange moves, the move which results in a LCST of least cost is selected (even if its cost is more than the current solution). Once a move has been performed its exactly reverse move is forbidden for the duration determined by tabu tenure. This tabu search also has an in-built cycle detection mechanism. Computational results demonstrated the superiority of these approaches over subset-coded genetic algorithm and ML heuristic. The tabu search and ACO performed quite similar in terms of solution quality, but tabu search was much faster than the ACO approach. Hereafter, these tabu search and ACO approaches will be, respectively referred to as TS-LCMST and ACO-LCMST. In this paper, we have proposed an artificial bee colony (ABC) algorithm for the LCMST problem. The artificial bee colony algorithm is a new metaheuristic approach, proposed by Karaboga [9]. It is inspired by the intelligent foraging behavior of honeybee swarm. We have compared our ABC approach against the ACO-LCMST and TS-LCMST approaches proposed in [8] and SCGA proposed in [2]. Computational results demonstrate the effectiveness of our approach in comparison to these approaches. The rest of this paper is organized as follows: Section 2 provides an introduction to the artificial bee colony algorithm. Section 3 describes our ABC algorithm for the LCMST problem. Computational results are presented in Section 4, whereas Section 5 outlines some conclusions.

In this paper we have designed and implemented an artificial bee colony algorithm ABC-LCMST for the LCMST problem. We have compared our approach against three other metaheuristic approaches—a genetic algorithm, an ant-colony optimization approach and a tabu search approach. Our approach outperformed all the other approaches. Best as well as average solution qualities of ABC-LCMST are always as good as or better than those obtained with other approaches except in one case, where average solution quality of tabu search is better. Computational times for ABC-LCMST are also quite small. In particular, ABC-LCMST completely outperforms ACO-LCMST both in terms of solution quality as well as running time. This is especially important as both approaches are based on swarm intelligence. To our knowledge this is the first application of artificial bee colony algorithm for a discrete optimization problem. This paper demonstrates the capability of artificial bee colony algorithm in solving a discrete optimization problem. Ideas presented in this paper can be applied to many other problems also. The concept of collisions introduced here keeps a check on the number of duplicate solutions in the population. Like other population-based approaches, the presence of duplicate solutions can impair the performance of ABC algorithm also. The procedure that we have developed for determining the neighboring solutions can be adapted to other subset selection problems such as 0/1 knapsack problem, quadratic knapsack problem, minimum k-cardinality tree problem, minimum vertex cover problem, etc.