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

The minimum weight vertex cover problem is an interesting and applicable NP-hard problem that has been investigated from many different aspects. The ant colony optimization metaheuristic is a relatively new technique that was successfully adjusted and applied to many hard combinatorial optimization problems, including the minimum weight vertex cover problem. Some kind of hybridization or exploitation of the knowledge about specific problem often greatly improves the performance of standard evolutionary algorithms. In this article we propose a pheromone correction heuristic strategy that uses information about the best-found solution to exclude suspicious elements from it. Elements are suspicious if they have some undesirable properties that make them unlikely members of the optimal solution. This hybridization improves pure ant colony optimization algorithm by avoiding early trapping in local convergence. We tested our algorithm on numerous test-cases that were used in the previous research of the same problem and our algorithm uniformly performed better, giving slightly better results in significantly shorter time.

One of the classical graph theory problems is the minimum weight vertex cover problem (MWVCP). The problem is defined for an undirected graph G = (V, E) where V is the set of vertexes, E is the set of edges and weights are assigned to each vertex in the graph. A vertex cover of graph G is a set of vertexes V′ ⊆ V that has the property that for every edge e(v1,v2)∈Ee(v1,v2)∈E at least one of vertexes v1v1 or v2v2 is an element of V′. A minimum weight vertex cover is the vertex cover with the minimum sum of weights of the belonging vertexes. It has been shown that this problem is NP-complete even when it is restricted to a unit-weighted planar graph with the maximum vertex degree of three [1]. A large number of real life problems could be converted to this form. An example could be the optimal positioning of garbage disposal facilities. For such NP-hard problems, since the optimal solution is computationally intractable, research is concentrated on heuristic algorithms that can find good suboptimal solutions in a reasonable time. It has been shown that for the restricted version of the MWVCP, the so-called real-WVC, where a total weight is at most k and each weight is ≥1, the solution can be found in time O(1.3954k + kn) where n =| V |, or in O(1.3788k + kn) with modestly exponential memory use [2]. When weights are restricted to positive integers (integer-WVC) the problem can be solved as fast as unweighted vertex cover in O(1.2738k + kn), again with exponential memory use [3] and [4]. A variety of different methods have been utilized for calculating near optimal solutions. The first one is a greedy heuristic approach of collecting the vertex with the smallest ratio between its weight and degree. This approach was first applied for a generalized version of the set cover problem [5], and its variation for the vertex cover problem with a performance guarantee of 2 [6]. The MWVCP has also been investigated by application of the genetic algorithms combined with greedy heuristic [7] and recently by metaheuristic based on gravity [8]. The ant colony optimization (ACO) is another metaheuristic for solving combinatorial problems. It was first used for the traveling salesman problem (TSP) by Dorigo and Gambardella [9] and [10]. The ACO was applied to the MWVCP by Shyu et al. [11] and good results were obtained, better that those acquired by local search methods like tabu search or simulated annealing. Gilmour and Dras further analyzed the ACO for the MWVCP in the direction of finding the optimal values for ACO parameters [12] and improving the effectiveness of ACO by using the parameterized complexity concept and the kernelization as a tool for algorithm design [13]. Several other approaches have been introduced for improving the efficiency of the ACO. One such approach is the use of different types of hybridization, like addition of local searchers [14] and [15]. Although this is a good approach in the majority of cases, it has been shown that it may prevent the ACO from finding the optimal solution [16]. Combining the ACO with genetic algorithms has been applied to large number of problems and gave better results than separate use of these methods: Lee et al. [17] or Zuo and Xiong [18]. Both of these hybridization methods are rather complex due to the need for two algorithms, one for the ACO and another one for the local search or genetic algorithm. A simpler method of improving the performance of the ACO is the use of variations of the basic algorithm like elitist ant colony, rank based ant colony system, min–max ant system (MMAS). We have previously performed a comparative assessment of different variations of the ACO for the MWVCP and shown that the MMAS outperforms other variations of the basic algorithm [19]. All these variations have the problem of becoming trapped in local optima. An interesting approach, named the minimum pheromone threshold strategy (MPTS), to solve the stagnation problem was proposed by Wong and See for the quadratic assignment problems [20]. In this article we propose a new type of hybridization for the ACO and implement it for the MWVCP. We improve the ACO with a hybridization method for leaving local optima i.e. avoiding stagnation in search for the best solution. This method is based on correcting the pheromone trail used in the ACO. We calculate this correction based on the properties of the best-found solution so far. The concept of this correction is to lower the possibility of vertexes with high level of undesirable properties to belong to the optimal solution. We show that our method improves results acquired by the ACO and that it is simple to add the method to the existing algorithms. It also gives better results that some other recent improvements [8]. This paper is organized as follows. In Section 2 we present the implementation of the ACO for the MWVCP. In Section 3 we review the other methods of avoiding the ACO algorithm stagnation. In the next section we explain our hybridization used for escaping search stagnation. In Section 5 we analyze and compare experimental results of using pure ACO and its combination with our method for the MWVCP and show the advantages of using our approach.

In this paper we have introduced a new type of hybridization for the ACO applied to the MWVCP. This hybridization adds a pheromone trail correction method to the pure ACO algorithm and it is activated in the situations when the search algorithm has been trapped in local optima and started to stagnate. The pheromone correction method is based on the analysis of properties of the best-found solution. It adds a new heuristic for determining the desirability of vertices belonging to the solution. In the case of the MVWCP, vertices that are part of the solution and have high weights while the solution set without them covers a large number of edges are considered as undesirable. The calculation time for this heuristic was negligible compared to the other parts of the algorithm. We compared our hybridization to the use of the simple ACO. The positive effect of this hybridization was evident on small, medium and large problems when the solution quality was considered. The main advantage of our method was that it greatly increased the convergence speed of the ACO. For the solutions of the same quality our hybridization enhanced algorithm needed just a quarter of the iterations that simple ACO needed. This type of hybridization has the potential to improve the efficiency of the ACO applications for different problems with appropriate heuristics defined for measuring the desirability or suspicion on parts of the solution. In most cases these heuristic functions are easy to calculate and implement. One of the main advantages of this type of hybridization is that it can easily be added to the existing ACO algorithms, with minimal change to the original source code.