دانلود مقاله ISI انگلیسی شماره 7779
عنوان فارسی مقاله

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

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
7779 2012 6 صفحه PDF سفارش دهید 4430 کلمه
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A hybrid algorithm based on tabu search and ant colony optimization for k-minimum spanning tree problems
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Expert Systems with Applications, Volume 39, Issue 5, April 2012, Pages 5681–5686

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

چکیده انگلیسی

This paper considers an efficient approximate algorithm for solving k-minimum spanning tree problems which is one of the combinatorial optimization in networks. A new hybrid algorithm based on tabu search and ant colony optimization is provided. Results of numerical experiments show that the proposed method updates some of the best known values with very short time and that the proposed method provides a better performance with solution accuracy over existing algorithms.

مقدمه انگلیسی

A k-minimum spanning tree (k-MST) problem is one of combinatorial optimization problems formulated in networks, and the objective of the problem is to find a subtree with exactly k edges such that the sum of the weights attached to edges is minimal, called k-minimum spanning tree. The k-MST problem is a generalized version of minimum spanning tree (MST) problems; when k = ∣V∣ − 1 where ∣V∣ is a cardinality of vertices in a graph, the k-MST problem corresponds to the MST problem. The wide varieties of decision making problems in the real world can be formulated as k-MST problems, e.g. telecommunications (Garg & Hochbaum, 1997), facility layout (Foulds, Hamacher, & Wilson, 1998), open pit mining (Philpott & Wormald, 1997), oil-field leasing (Hamacher, Jörnsten, & Maffioli, 1991), matrix decomposition ( Börndorfer et al., 1997 and Börndorfer et al., 1998) and quorum-cast routing (Cheung & Kumar, 1994). The k-MST problem was firstly introduced by Hamacher et al. (1991). Since the k-MST problem is NP-hard ( Fischetti et al., 1994 and Marathe et al., 1996), it is difficult to solve large-scale problems within a practically acceptable time. Therefore, it is very important to construct approximate solution methods which quickly find a near optimal solution ( Jörnsten and Løkketangen, 1997 and Katagiri et al., 2010). Blum and Blesa (2005) proposed several approximate solution methods including metaheuristics such as evolutionary computation, ant colony optimization (ACO) and tabu search (TS). They compared their performances through benchmark instances (KCTLIB, 2003) and showed that an ACO approach is the best for relatively small ks, whereas a TS-based approach has an advantage for large ks with respect to solution accuracy. Recently, it is shown that both ACO and TS are promising approaches to solving not only k-MST problems but also other combinatorial optimization problems ( Abdallah et al., 2009, Aladag et al., 2009, Li et al., 2010, Öncan et al., 2008 and Tseng et al., 2008). Moreover, in order to construct more efficient solution method by combining some effective approximate ones, hybrid algorithms ( Chen et al., 2008, Chen and Chien, 2011, Liu and Zeng, 2009 and Naimi and Taherinejad, 2009) have been highly attracted attention to many researchers. In this paper, we propose a new hybrid approximate solution algorithm based on TS and ACO. In order to demonstrate efficiency of the proposed solution method, we compare the performances of the proposed method with those of existing algorithms using the well-known benchmark instances (KCTLIB, 2003) that are easily accessible through the internet. The numerical experimental results show that the proposed method updates some of the best known solutions and values with very short computational times, and that the proposed method provides a better performance with solution accuracy over existing algorithms. 2. Problem formulation and existing solution methods Given that a graph G = (V, E) where V is a set of vertices and E is a set of edges, a subtree with exactly k edges, called k-subtree Tk, is defined as View the MathML sourceTk∈G,k⩽|V|-1. View the MathML sourceminimize∑e∈E(Tk)w(e)subject toTk∈Tk, where TkTk is the set of all possible k-subtrees Tk in G, E(Tk) denotes the edges of Tk and w(e) is a weight attached to an edge e. The above problem is to seek a k-subtree with the minimum sum of weights. If the problem size is small, the problem can be easily solved by finding an optimal solution after enumerating all possible k-subtrees in a given graph. If the size of problem is not so large, it can be solved by some exact solution algorithm such as a branch and bound method (Cheung & Kumar, 1994) and a branch and cut algorithm (Freitag, 1993). However, it has been shown that the k-MST problem is NP-hard even if the edge weight is in {1, 2, 3} for all edges, or if a graph is fully connected. The problem is also NP-hard for planar graphs and for points in the plane (Marathe et al., 1996). Therefore, it is important to construct not only exact solution methods but also efficient approximate solution methods

نتیجه گیری انگلیسی

In this paper, we have proposed a new hybrid approximate solution algorithm for k-MST problems by combining tabu search and ant colony optimization. Through numerical experiments for several benchmark instances, we have shown that the performances of the proposed method are better than those of existing methods. Furthermore, it has been shown that the proposed method updates some of the best known values. In the near future, we will construct some other benchmark instances to clarify the efficiency of the proposed algorithm as well as its advantages and disadvantages over the existing algorithms.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.