Christine Solnon
email: christine.solnon@liris.cnrs.fr

Serge Fenet Liris

A study of ACO capabilities for solving the Maximum Clique Problem

This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal cliques through the repeated addition of vertices into partial cliques, and uses "pheromone trails" as a greedy heuristic to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are laid and exploited, i.e., on edges or on vertices of the graph.

We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures -the re-sampling and the dispersion ratio-for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.

Introduction

The maximum clique problem is a classical combinatorial optimization problem that has important applications in different domains such as coding theory, fault diagnosis, or computer vision. Moreover, many important problems -such as constraint satisfaction, subgraph isomorphism, or vertex covering problemsare easily reducible to this maximum clique problem.

Given a non-directed graph G = (V, E), such that V is a set of vertices, and E ⊆ V × V is a set of edges, a clique is a set of vertices C ⊆ V such that every 1 pair of distinct vertices of C is connected with an edge in G, i.e., the subgraph induced by C is complete. A clique is partial if it is strictly included in another clique; otherwise it is maximal. The goal of the maximum clique problem is to find a clique of maximum cardinality.

The maximum clique problem is very closely related to the maximum independent (or stable) set problem, the goal of which is to find the maximum subset of V such that no two vertices of the subset are pairwise adjacent: a maximum clique of a graph G = (V, E) is a maximum independent set of the complement graph G = (V, V × V -E) of G.

The clique problem -that consists in finding a clique of size k in a graphis one of the first problems shown to be NP-complete in [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. More generally, the problem of finding a maximum clique is NP-hard, and does not admit polynomial-time approximation algorithms (unless P=NP) [START_REF] Bomze | The maximum clique problem[END_REF]. Hence, exact approaches -usually based on branch-and-bound-become intractable when the number of vertices increases, and much effort has recently been directed on heuristic approaches.

Heuristic approaches for the maximum clique problem

Heuristic approaches leave out exhaustivity and use heuristics to guide the search towards promising areas of the search space. They run in polynomial time and quickly find "rather good" solutions, that may be optimal, but optimality is not guaranteed.

Many heuristic approaches are based on sequential greedy heuristics [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF][START_REF] Feo | A greedy randomized adaptive search procedure for maximum independent set[END_REF][START_REF] Abello | On maximum clique problems in very large graphs[END_REF][START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF][START_REF] Jagota | Adaptive, restart, randomized greedy heuristics for maximum clique[END_REF][START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF]. The idea is to build maximal cliques, starting from an empty clique, and iterating through the repeated addition of vertices. To decide which vertex is added, one uses a greedy heuristic such as, e.g., choosing the vertex that has the highest degree among candidate vertices. To avoid usual greedy traps, greedy heuristics can be improved by injecting a mild amount of randomization combined with multiple restarts. Also, weights used by the greedy heuristic may be adapted from restart to restart as proposed, e.g., in [START_REF] Jagota | Adaptive, restart, randomized greedy heuristics for maximum clique[END_REF][START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF].

To improve the quality of a constructed clique, local search can be used to explore its neighborhood, i.e., the set of cliques that can be obtained by removing and/or adding a given number of vertices: local search iteratively moves in the search space composed of all cliques, from a clique to one of its (best) neighbors. To avoid being trapped in local optima, where all neighbors are cliques of smaller sizes, local search may be combined with some advanced meta-heuristics. For example in [START_REF] Aarts | Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing[END_REF][START_REF] Homer | Experiments with polynomial-time clique approximation algorithms on very large graphs[END_REF], Simulated Annealing is used to jump out of local optima by allowing moves towards smaller cliques with a probability proportional to a decreasing temperature parameter. In [START_REF] Friden | STABULUS: A technique for finding stable sets in large graphs with tabu search[END_REF][START_REF] Glover | Tabu search[END_REF][START_REF] Gendreau | Solving the maximum clique problem using a tabu search approach[END_REF], Tabu Search is used to prevent local search from cycling through a small set of good but suboptimal cliques by keeping track, in a tabu list, of forbidden moves between cliques. In [START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF], Reactive Search enhances Tabu Search by reactively adapting the size of the tabu list with respect to the need of diversification. In [START_REF] Marchiori | Genetic, iterated and multistart local search for the maximum clique problem[END_REF], local search is combined with a Genetic Algorithm that allows one to escape from local maxima by applying crossover and mutation operators to a population of maximal cliques.

The Ant Colony Optimization meta-heuristic

In this paper, we investigate the capabilities of another meta-heuristic -Ant Colony Optimization (ACO) [START_REF] Dorigo | The Ant Colony Optimization meta-heuristic[END_REF][START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF]-for solving the maximum clique problem. The basic idea of ACO is to model the problem to solve as the search for a minimum cost path in a graph, and to use artificial ants to search for best paths.

The behavior of artificial ants is inspired from real ants: artificial ants lay pheromone trails on components of the graph and choose their path with respect to probabilities that depend on pheromone trails that have been previously laid; these pheromone trails progressively decrease by evaporation. Intuitively, this indirect stigmergic communication means aims at giving information about the quality of path components in order to attract ants, in the following iterations, towards the corresponding areas of the search space. Indeed, for many combinatorial problems, a study of the search space landscape shows a correlation between solution quality and the distance to optimal solutions [START_REF] Jones | Fitness distance correlation as a measure of problem difficulty for genetic algorithms[END_REF][START_REF] Merz | Fitness landscapes and memetic algorithm design[END_REF][START_REF] Stützle | MAX -MIN Ant System[END_REF].

The first ant algorithm to be applied to a discrete optimization problem has been proposed by Dorigo in [START_REF] Dorigo | Optimization, Learning and Natural Algorithms[END_REF]. The problem chosen for the first experiments was the Traveling Salesman Problem and, since then, this problem has been widely used to investigate the solving capabilities of ants [START_REF] Dorigo | Ant System: Optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | Ant colony system: A cooperative learning approach to the traveling salesman problem[END_REF]. The ACO meta-heuristic, described in [START_REF] Dorigo | The Ant Colony Optimization meta-heuristic[END_REF][START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF], is a generalization of these first ant based algorithms, and it has been successfully applied to different hard combinatorial optimization problems such as quadratic assignment problems [START_REF] Gambardella | Ant colonies for the quadratic assignment problem[END_REF][START_REF] Maniezzo | The Ant System applied to the quadratic assignment problem[END_REF], vehicle routing problems [START_REF] Bullnheimer | An improved ant system algorithm for the vehicle routing problem[END_REF][START_REF] Gambardella | MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows[END_REF], and constraint satisfaction problems [START_REF] Solnon | Solving permutation constraint satisfaction problems with artificial ants[END_REF][START_REF] Solnon | Ants can solve constraint satisfaction problems[END_REF].

We have proposed in [START_REF] Fenet | Searching for maximum cliques with ant colony optimization[END_REF] a first ACO algorithm for the maximum clique problem. The contribution of this paper with respect to this preliminary work mainly concerns (i) the definition of a variant of this first ACO algorithm, that differs in the way pheromone is laid and exploited; (ii) an experimental comparison of these two different ways of managing pheromone; (iii) the use of diversity measures in order to provide an insight into the performance at runtime; (iv) an investigation of the benefit of combining ACO with local search for this problem; and (v) an experimental comparison with three state-of-the-art heuristic approaches.

Another Ant algorithm for the maximum clique problem has been recently proposed in [START_REF] Bui | Finding maximum cliques with distributed ants[END_REF]. This algorithm is rather different as ants are distributed, i.e., each ant only has local knowledge of the graph, so that the algorithm can be implemented in a distributed system. As a counterpart, performance of this algorithm by means of solutions' quality are rather far from performance of the ACO algorithm proposed in [START_REF] Fenet | Searching for maximum cliques with ant colony optimization[END_REF] and other non distributed algorithms.

Overview of the paper

Section 2 describes the generic ACO algorithm for the maximum clique problem -called Ant-Clique-and its two different instantiations -called Vertex-AC and Edge-AC. Basically, Ant-Clique uses pheromone trails as a greedy heuristic for choosing, at each step, the next vertex to enter the clique. However, in Vertex-AC, pheromone trails are laid on vertices, and the choice of vertices directly depends on the quantity of pheromone laying on them, whereas in Edge-AC, pheromone trails are laid on edges, and the choice of vertices depends on pheromone trails laying on edges connecting candidate vertices with the vertices of the clique under construction.

In Section 3, we illustrate and compare the behavior of Vertex-AC and Edge-AC on a representative benchmark instance. We consider two measures in order to provide a deeper insight into their behavior at run-time: the resampling ratio is used to measure how often the search space is re-sampled, whereas the dispersion ratio is used to quantify the differences between the cliques successively computed during the solution process.

In Section 4, we show how local search can be combined with Ant-Clique, and we study on a representative benchmark instance the influence of local search on the solution process.

Section 5 experimentally compares the four different ACO instantiations (Vertex-AC and Edge-AC, with and without local search) on a set of benchmark graphs. We show that Edge-AC usually finds better solutions than Vertex-AC, but is more time consuming. We also show that the integration of local search improves solutions' quality on a majority of instances.

Finally, Section 6 compares our approach with other heuristic approaches. We have more particularly chosen for this comparison three recent and representative algorithms within different classes of heuristic approaches: RLS [START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF], which uses reactive local search and obtains the best known results on most benchmark instances, DAGS [START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF], which combines an adaptive greedy approach with swap local moves and obtains the best known results on some other instances, and GLS [START_REF] Marchiori | Genetic, iterated and multistart local search for the maximum clique problem[END_REF], which combines a genetic approach with local search.

ACO for the maximum clique problem

In ACO algorithms, ants lay pheromone trails on components of the best constructed solutions in order to attract other ants towards the corresponding area of the search space. To solve a new problem with ACO, one mainly has to define the pheromone laying procedure -i.e., decide on which components of constructed solutions ants should lay pheromone trails-and define the solution construction procedure -i.e., decide how to exploit these pheromone trails when constructing new solutions.

Hence, to solve the maximum clique problem with ACO, the key point is to decide which components of the constructed cliques should be rewarded, and how to exploit these rewards when constructing new cliques. Indeed, given a maximal clique C i , one can lay pheromone trails either on the vertices of C i , or on the edges connecting every pair of different vertices of C i :

• when laying pheromone on the vertices of C i , the idea is to increase the Search of an approximate maximum clique in a graph G = (V, E): desirability of each vertex of C i so that, when constructing a new clique, these vertices will be more likely to be selected;

• when laying pheromone on the edges of C i , the idea is to increase the desirability of choosing together two vertices of C i so that, when constructing a new clique C k , the vertices of C i will be more likely to be selected if C k already contains some vertices of C i . More precisely, the more C k will contain vertices of C i , the more the other vertices of C i will be attractive.

A goal of this paper is to compare these two different ways of using pheromone. Therefore, we introduce a generic ACO algorithm called Ant-Clique, and two different instantiations of it: Vertex-AC, where pheromone is laid on vertices, and Edge-AC, where pheromone is laid on edges.

In this section, we first describe the generic algorithmic scheme that is common to the two instantiations. Then, we describe the three points on which they differ, i.e., the definition of pheromonal components, the exploitation of pheromone trails when constructing cliques, and the pheromone updating process. Finally, we compare their time complexities.

Generic algorithmic scheme of Ant-Clique

Figure 1 displays the generic ACO algorithmic scheme for solving the maximum clique problem. At each cycle of this algorithm, every ant constructs a maximal clique. It first randomly chooses an initial vertex to enter the clique, and then iteratively adds vertices that are chosen within a set Candidates that contains all the vertices that are connected to every vertex of the partial clique under construction. This choice is performed randomly with respect to probabilities that are defined in Section 2.3. Once each ant has constructed a clique, pheromone trails are updated, as described in Section 2.4. The algorithm stops either when an ant has found a maximum clique (when the optimal bound is known), or when a maximum number of cycles has been performed. This algorithm more particularly borrows features from the MAX -MIN Ant System [START_REF] Stützle | MAX -MIN Ant System[END_REF]: it explicitly imposes lower and upper bounds τ min and τ max on pheromone trails (with 0 < τ min < τ max ), and pheromone trails are set to τ max at the beginning of the search.

Definition of pheromonal components

Pheromone trails are laid by ants on components of the graph G = (V, E) in which they are looking for a maximum clique.

• In Vertex-AC, ants lay pheromone trails on the vertices V of the graph.

The quantity of pheromone on a vertex v i ∈ V is denoted τ i . Intuitively, this quantity represents the learned desirability to select v i when constructing a clique.

• In Edge-AC, ants lay pheromone trails on the edges E of the graph. The quantity of pheromone on an edge (v i , v j ) ∈ E is denoted τ ij . Intuitively, this quantity represents the learned desirability to select v i when constructing a clique that already contains v j . Notice that since the graph is not directed, τ ij = τ ji .

Exploitation of pheromone trails

Pheromone trails are used to choose vertices when constructing cliques: at each step, a vertex v i is randomly chosen within the set Candidates with respect to a probability p(v i ). This probability is defined proportionally to pheromone factors, i.e.,

p(v i ) = [τ fact (v i )] α vj ∈Candidates [τ fact (v j )
] α where α is a parameter which weights pheromone factors, and τ fact (v i ) is the pheromone factor of vertex v i . This pheromone factor depends on the quantity of pheromone laying on pheromonal components of the graph:

• in Vertex-AC, it depends on the quantity of pheromone laid on the candidate vertex, i.e., τ fact

(v i ) = τ i
• in Edge-AC, it depends on the quantity of pheromone laid on edges connecting the vertices that already are in the partial clique and the candidate vertex: let C k be the partial clique under construction, the pheromone factor of a candidate vertex v i is

τ fact (v i ) = vj ∈C k τ ij
Note that this pheromone factor can be computed in an incremental way: once the first vertex v i has been randomly chosen, for each candidate vertex v j that is adjacent to v i , the pheromone factor τ fact (v j ) is initialized to τ ij ; then, each time a new vertex v k is added to the clique, for each candidate vertex v j that is adjacent to v k , the pheromone factor τ fact (v j ) is incremented by τ kj .

One should remark that, for both Vertex-AC and Edge-AC, the probability of choosing a vertex v i only depends on a pheromone factor and not on some other heuristic factor that locally evaluates the quality of the candidate vertex, as usually in ACO algorithms. Actually, we have experimented different heuristics, and more particularly the greedy heuristic proposed, e.g., in [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF][START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF][START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF]. The idea is to favor vertices with largest degrees in the "residual graph", i.e., the subgraph induced by the set of candidate vertices that can extend the partial clique under construction. The underlying motivation is that a larger degree implies a larger number of candidates once the vertex has been added to the current clique. When using no pheromone, or at the beginning of the search process when all pheromone trails have the same value, this heuristic actually allows ants to construct larger cliques with respect to a random choice. However, when combining it with pheromone learning, we have noticed that after a hundred or so cycles we obtain larger cliques without using the heuristic than when using it.

To explain this rather counter-intuitive result, we have compared re-sampling ratio (i.e., the percentage of solutions that are re-computed several times [START_REF] Van Hemert | Measuring the searched space to guide efficiency: The principle and evidence on constraint satisfaction[END_REF]) at run-time. We have noticed that when integrating the greedy heuristic to the probability p(v i ), this re-sampling ratio is significantly increased. This shows that the search is trapped around a set of locally optimal cliques, and is not diversified enough to be able to find larger cliques.

Updating pheromone trails

Once each ant has constructed a clique, the amount of pheromone laying on pheromonal components is updated according to the ACO meta-heuristic. First, all amounts are decreased in order to simulate evaporation. This is done by multiplying the quantity of pheromone laying on each pheromonal component by a pheromone persistence rate ρ such that 0 ≤ ρ ≤ 1. Then, the best ant of the cycle deposits pheromone. More precisely, let C k ∈ {C 1 , . . . , C nbAnts } be the largest clique built during the cycle (if there are several largest cliques, ties are randomly broken), and C best be the largest clique built since the beginning of the run (including the current cycle). The quantity of pheromone laid by ant k is inversely proportional to the gap of size between C k and C best , i.e., it is equal

to 1/(1+ | C best | -| C k |).
This quantity of pheromone is deposited on the pheromonal components of C k , i.e.,

• in Vertex-AC, it is deposited on each vertex of C k ,

• in Edge-AC, it is deposited on each edge connecting two different vertices of C k .

Time complexity of Vertex-AC and Edge-AC

Let nbMaxCycles and nbAnts respectively be the maximum number of cycles and the number of ants. In the worst case (if an optimal solution is not found), both Vertex-AC and Edge-AC will have to construct nbMaxCycles • nbAnts maximal cliques, and to perform nbMaxCycles pheromone updating steps.

To construct a maximal clique, Vertex-AC and Edge-AC nearly perform the same number of operations. Indeed, to construct a clique C, both instantiations perform | C | -1 times the "while" loop of the algorithm of Figure 1. At each iteration of this loop, they both have to: (i) compute probabilities for all candidates, (ii) choose a vertex with respect to these probabilities, and (iii) update the list of candidates. These three steps take a linear time with respect to the number of candidate vertices1 . At the first iteration, the number of candidate vertices is equal to the degree of the initial vertex, and it decreases at each iteration. Hence, in the worst case, the complexity of the construction of a clique in a graph G, for both Vertex-AC and Edge-AC,

is in O(ω(G) • max d • (G))
, where ω(G) is the size of the maximum clique of G, and max d • (G) is the maximum vertex degree in G. Note that both ω(G) and max d • (G) are bounded by the number of vertices of G.

To update pheromone trails laying on pheromonal components of a graph G = (V, E), Vertex-AC and Edge-AC perform a different number of operations: Hence, the overall time complexity of Vertex-AC is in

• In Vertex-AC,
O(nbMaxCycles (nbAnts • ω(G) • max d • (G)+ | V |))
whereas the overall time complexity of Edge-AC is in

O(nbMaxCycles (nbAnts • ω(G) • max d • (G)+ | E |))
3

Diversification versus intensification of search

When solving a combinatorial optimization problem with a heuristic approach such as evolutionary computation or ACO, one usually has to find a compromise between two dual goals. On the one hand, one has to intensify the search around the most "promising" areas, that are usually close to the best solutions found so far [START_REF] Jones | Fitness distance correlation as a measure of problem difficulty for genetic algorithms[END_REF][START_REF] Merz | Fitness landscapes and memetic algorithm design[END_REF][START_REF] Stützle | MAX -MIN Ant System[END_REF]. On the other hand, one has to diversify the search and favor exploration in order to discover new, and hopefully more successful, areas of the search space. The behavior of ants with respect to this intensification/diversification duality can be influenced by modifying parameter values [START_REF] Colorni | An investigation of some properties of an ant algorithm[END_REF].

In this section, we first briefly discuss the settings of τ min , τ max , and nbAnts. Then, we study the influence of α and ρ on the solution process on a representative benchmark instance. Finally, we provide an insight into the influence of α and ρ on the intensification/diversification duality by means of two diversity measures.

Bounding pheromone trails within [τ min , τ max ]

As pointed out in [START_REF] Stützle | MAX -MIN Ant System[END_REF], the goal of bounding pheromone trails within an interval [τ min , τ max ] is to avoid premature stagnation of search, i.e., a situation where all ants construct the same solution over and over again so that no better solutions can be found anymore. Indeed, by imposing explicit limits τ min and τ max on the minimum and maximum pheromone trails, one ensures that relative differences between pheromone trails cannot become too extreme. Therefore, the probability of choosing a vertex cannot become too small and stagnation situations are avoided. Furthermore, by initializing pheromone trails to τ max at the beginning of the search, one ensures that during the first cycles the relative difference between pheromone trails is rather small (after i cycles, it is bounded by a ratio of ρ i ). Hence, exploration is emphasized at the beginning of the search.

The effectiveness of bounding pheromone trails, and initializing them to the upper bound, is demonstrated in [START_REF] Stützle | MAX -MIN Ant System[END_REF] on the traveling salesman problem and the quadratic assignment problem. Also, it has been shown to be effective on constraint satisfaction problems [START_REF] Solnon | Boosting ACO with a preprocessing step[END_REF].

To set appropriately τ min and τ max , we ran Ant-Clique on a "representative" subset of instances with different settings with τ max ∈ [4, 10] and τ min ∈ [0.001, 0.05]. On average, the best results have been obtained with τ min = 0.01 and τ max = 6. Note that this setting is consistent with [START_REF] Stützle | MAX -MIN Ant System[END_REF], in which it is shown that τ max should be set to an estimate of the asymptotically maximum pheromone trail value, which is defined by δ avg /(1ρ) where δ avg is the average quantity of pheromone that is laid on pheromonal components at each cycle. Indeed, in Ant-Clique, the quantity of pheromone laid at each cycle is equal to

1/(1+ | C best | -| C k |)
, where C k is the largest clique built during the cycle, and C best the largest clique built since the beginning of the run: this quantity is equal to 1 if C k is the best clique found so far, and it is lower than 1 otherwise. This quantity varies from one cycle to another (depending on the size of the cliques computed during the cycle), but also from an instance to another. On the set of DIMACS benchmark instances, the average gap of size beween C k and C best is close to 13, so that τ max should be set to a value around 1/((1 + 13) • (1ρ)) which is equal to 7.1 when ρ = 0.99.

Varying the number of ants

To emphasize diversification and avoid premature stagnation, one can also increase the number of ants so that more states are explored at each cycle. This parameter has been set experimentally, by running Ant-Clique with different values beween 10 and 50. On average, the best results have been obtained with nbAnts = 30. With lower values, solution quality is often decreased as the best clique constructed at each cycle usually is significantly smaller. With greater values, running time often increases while solution quality is not significantly improved as the best clique constructed at each cycle is not significantly better than with 30 ants. Experimental results and a deeper analysis about the influence of the number of ants on the solution process of Edge-AC can be found in [START_REF] Fenet | Searching for maximum cliques with ant colony optimization[END_REF].

Influence of α and ρ on the solution process

The two pheromonal parameters α and ρ have a great influence on the solution process. Indeed, diversification can be emphasized either by decreasing the value of the pheromone factor weight α -so that ants become less sensitive to pheromone trails-or by increasing the value of the pheromone persistence rate ρ -so that pheromone evaporates more slowly. When increasing the exploratory ability of ants in this way, one usually finds better solutions, but as a counterpart it takes longer time to find them. This is illustrated in Figure 2 on the C500.9 instance of the DIMACS benchmark. Note that this instance, which has 500 vertices and 112332 edges, is a rather difficult one, for which Ant-Clique has difficulties in finding the maximum clique -which contains 57 vertices.

On this figure, one can first note that when α = 0 and ρ = 1, the best constructed cliques are much smaller: in this case, pheromone is totally ignored and the resulting search process performs as a random one so that after 500 or so cycles, the size of the best clique nearly stops increasing, and hardly reaches 48 vertices. This shows that pheromone actually improves the solution process with respect to a pure random algorithm.

For both Edge-AC and Vertex-AC, we remark that α and ρ influence the solution process in a very similar way: when α increases or ρ decreases, ants are able to find better solutions quicker. However, after a thousand or so cycles, both versions find better solutions when α is set to 1 and ρ to 0.99 or 0.995 than when α is set to 2 or ρ to 0.98. Hence, the setting of α and ρ let us balance between two main tendencies. On the one hand, when limiting the influence of pheromone with a low pheromone factor weight and a high pheromone persistence rate, the quality of the final solution is better, but the time needed to converge on this value is also higher. On the other hand, when increasing the influence Figure 2: Influence of pheromone on the solution process of Edge-AC (upper curves) and Vertex-AC (lower curves) for the C500.9 graph: each curve plots the evolution of the size of the best constructed clique (average over 50 runs), when the number of cycles increases, for a given setting of α and ρ. The other parameters have been set to nbAnts = 30, τ min = 0.01, and τ max = 6. of pheromone with a higher pheromone factor weight and a lower pheromone persistence rate, ants find better solutions during the first cycles, but after 500 or so cycles, they are no longer able to find better solutions.

When comparing Edge-AC (upper curves) with Vertex-AC (lower curves), one can note that after 2500 cycles, the best cliques found by Edge-AC are slightly larger than the best ones found by Vertex-AC. For example, when setting α to 1 and ρ to 0.99, the average size of the best constructed cliques is equal to 55.6 for Edge-AC and to 55.2 for Vertex-AC. Moreover, three runs of Edge-AC (over the fifty performed runs) have been able to find a clique of 57 vertices, whereas Vertex-AC only found cliques of 56 or less vertices.

However, if Edge-AC is able to find better cliques, it needs more cycles to converge towards them. For example, when setting α to 1 and ρ to 0.99, the average number of cycles needed to find the best clique is respectively equal to 923 for Edge-AC and 722 for Vertex-AC. Moreover, as discussed in Section 2.5, each cycle of Edge-AC takes a longer time to perform than Vertex-AC: on this instance, in one second of CPU time, Edge-AC and Vertex-AC respectively perform 104 and 188 cycles. Hence, to find their best cliques, Edge-AC and Vertex-AC respectively need 8.9 and 3.8 seconds on average.

As a conclusion, on instance C500.9, the two algorithms behave in a rather similar way at run time with respect to pheromone parameters, and a good compromise between solution quality and CPU time is reached when α is set to 1 and ρ to 0.99. With such a parameter setting, Vertex-AC is more than twice as fast as Edge-AC to find its best clique, but the best clique found by Edge-AC is slightly better, on average, than the one found by Vertex-AC, and Edge-AC has been able to find the best known solution for 6% of its runs, whereas Vertex-AC never reached it.

This study on instance C500.9 allows us to determine a "good" parameter setting to solve this particular instance. However, one can hardly assert that the best parameters for C500.9 are also the best ones for other instances. In particular, we have shown in [START_REF] Fenet | Searching for maximum cliques with ant colony optimization[END_REF] that the best parameters for another instance (gen 400 P0.9 75) were different: indeed this instance is "easier" than C500.9 so that one has better choose parameters that favor a quick convergence such as α = 3 and ρ = 0.985. In the rest of this paper, we have chosen to set parameters to the same values for all instances. Another possibility would have been to use an adaptive method, such as, e.g., the one described in [START_REF] Birattari | A racing algorithm for configuring metaheuristics[END_REF]. This method aims at defining an automatic procedure for finding good parameters through statistically guided experimental evaluations. A racing method uses a pool of initial parameters and, as computation proceeds, gather evidences allowing to remove inferior candidates from the pool.

Measuring the diversity at run time

To provide an insight into Ant-Clique's performance and to explicit the influence of pheromone on the capability of ants to explore the search space, we now propose to measure the diversity of the computed solutions at run time. Many diversity measures have been introduced for evolutionary approaches. Indeed, Table 1: Evolution of the re-sampling ratio of Edge-AC and Vertex-AC for graph C500.9. Each row successively displays the setting of α and ρ, and the re-sampling ratio after 500, 1000, 1500, 2000, and 2500 cycles (average over 50 runs). The other parameters have been set to nbAnts = 30, τ min = 0.01, τ max = 6.

Re-sampling ratio for Edge-AC Number of cycles: 500 1000 1500 2000 2500 α = 1, ρ = 0.995 0.00 0.00 0.00 0.00 0.00 α = 1, ρ = 0.99 0.00 0.00 0.00 0.00 0.00 α = 2, ρ = 0.99 0.00 0.04 0.06 0.07 0.07 α = 2, ρ = 0.98 0.06 0.10 0.12 0.13 0.13

Re-sampling ratio for Vertex-AC Number of cycles: 500 1000 1500 2000 2500 α = 1, ρ = 0.995 0.00 0.00 0.02 0.13 0.25 α = 1, ρ = 0.99 0.00 0.07 0.26 0.39 0.48 α = 2, ρ = 0.99 0.38 0.68 0.78 0.84 0.87 α = 2, ρ = 0.98 0.58 0.78 0.85 0.88 0.91 maintaining population diversity is a key point to prevent from premature convergence and stagnation. Most commonly used diversity measures include the number of different fitness values, the number of different structural individuals, and distances between individuals [START_REF] Burke | A survey and analysis of diversity measures in genetic programming[END_REF].

To measure the diversification effort of Ant-Clique at run time, we propose in this paper to compute the re-sampling and the diversification ratio.

Re-sampling ratio

This measure is used, e.g., in [START_REF] Van Hemert | Measuring the searched space to guide efficiency: The principle and evidence on constraint satisfaction[END_REF][START_REF] Van Hemert | A study into ant colony optimization, evolutionary computation and constraint programming on binary constraint satisfaction problems[END_REF], in order to get insight into how "effective" algorithms are in sampling the search space: if we define nbDiff as the number of unique candidate solutions generated by an algorithm over a whole run and nbTot as the total number of generated candidate solutions, then the re-sampling ratio is defined as (nbTot -nbDiff)/nbTot. Values close to 0 correspond to an "effective" search, i.e., not many duplicate candidate solutions are generated, whereas values close to 1 indicate a stagnation of the search process around a small set of solutions.

Table 1 provides an insight into Ant-Clique's performance by means of this re-sampling ratio. This table shows that Vertex-AC is less "effective" than Edge-AC in sampling the search space as it often generates cliques that have already been previously generated. For example, when setting α to 1 and ρ to 0.99, 7% of the cliques computed by Vertex-AC during the first thousand of cycles had already been computed. This re-sampling ratio increases very quickly and reaches 48% at cycle 2500, i.e., nearly half of the cliques computed during each run already had been computed before. As a comparison, with the same parameter setting, Edge-AC nearly never computes twice a same clique during a same run, so that it actually explores twice more states in the search space.

The re-sampling ratio allows one to quantify the size of the searched space, and shows that Edge-AC has a higher search capability than Vertex-AC (for the considered C500.9 instance). However, the re-sampling ratio gives no information about the distribution of the computed cliques within the whole search space. Actually, a pure random search (nearly) never re-samples twice a same solution but, as it does not intensify the search around promising solutions, it usually is not able to find good solutions. Hence, to provide a complementary insight into Ant-Clique's performance, we propose to compute a similarity ratio which indicates how much the computed cliques are similar, i.e., how much the search is intensified.

Similarity ratio

The similarity ratio corresponds to the pair-wise population diversity measure, introduced for genetic approaches, e.g., in [START_REF] Sidaner | Measuring the spatial dispersion of evolutionist search processes: application to walksat[END_REF][START_REF] Morrison | Measurement of population diversity[END_REF]. More precisely, we define the similarity ratio of a set of cliques S by the average number of vertices that are shared by any pair of cliques in S, divided by the average size of the cliques of S. Hence, this ratio is equal to one if all the cliques of S are identical, whereas it is equal to zero if the intersection of every pair of cliques of S is empty. Note that this ratio can be computed very quickly by maintaining an array freq such that, for every vertex v i ∈ V , freq[i] is equal to the number of cliques of S which have selected vertex v i . In this case, the similarity ratio of S is equal to

vi∈V (freq[i] • (freq[i] -1)) (| S | -1) • C k ∈S | C k |
and it can be easily computed in an incremental way while constructing cliques (see [START_REF] Morrison | Measurement of population diversity[END_REF] for more details). Figure 3 plots the evolution of the similarity ratio of the cliques computed every 50 cycles, for graph C500.9, thus giving an information about the distribution of the set of cliques computed during these 50 cycles. For example, let us consider the curve plotting the evolution of the similarity ratio for Edge-AC when α is set to 1 and ρ to 0.99. The similarity increases from less than 10% at the beginning of the solution process to 45% after a thousand or so cycles. This shows that ants progressively focus on a sub-region of the search space, so that two cliques constructed after cycle 1000 share nearly half of their vertices on average. When considering this together with the fact that the re-sampling ratio is null, one can conclude that in this case Edge-AC reaches a good compromise between diversification -as it never re-computes twice a same solution-and intensification -as the similarity of the computed solutions is increased.

Figure 3 also shows that, when α increases or ρ decreases, the similarity ratio both increases sooner and rises more steeply. However, both for Edge-AC and Vertex-AC, the similarity ratio of all runs converges towards a same value, Vertex-AC (lower curves) for graph C500.9: each curve plots the similarity ratio of the set of cliques constructed every 50 cycles (average over 50 runs), for a given setting of α and ρ. The other parameters have been set to nbAnts = 30, τ min = 0.01, τ max = 6. whatever the setting of α and ρ: after two thousand or so cycles, the cliques computed by Edge-AC during every cycle share around 45% of their vertices whereas those computed by Vertex-AC share around 90% of their vertices.

The difference of diversification between Edge-AC and Vertex-AC may be explained by the choice made about their pheromonal components. Indeed, the considered C500.9 instance has 500 vertices, so that in Vertex-AC ants may lay pheromone on 500 components, whereas in Edge-AC they may lay pheromone on 500 • 499/2 = 124750 components. Let us now consider the two cliques that are rewarded at the end of the first two cycles of a run. For both Vertex-AC and Edge-AC, these two cliques contain 44 vertices on average (see Fig. 2), and their similarity ratio is lower than 10% (see Fig. 3) so that they share 4 vertices on average. Under this hypothesis, after the first two cycles of Vertex-AC, 4 vertices -corresponding to 1% of the pheromonal components-have been rewarded twice, and 80 vertices -corresponding to 16% of the pheromonal components-have been rewarded once. As a comparison, under the same hypothesis, after the first two cycles of Edge-AC, 6 edges -corresponding to less than 0.005% of the pheromonal components-have been rewarded twice, and 940 edges -corresponding to less than 0.8% of the pheromonal componentshave been rewarded once. This explains why the search of Edge-AC is much more diversified than the one of Vertex-AC, and therefore why Edge-AC needs more time to converge, but as a counterpart it often finds better solutions with respect to Vertex-AC.

Enhancing ACO with local search

Basically, local search searches for a locally optimal solution in the neighborhood of a given constructed solution. Local search may be combined with the ACO meta-heuristic in a very straightforward way: ants construct solutions exploiting pheromone trails, and local search improves their quality by iteratively performing local moves. Actually, the best-performing ACO algorithms for many combinatorial optimization problems are hybrid algorithms that combine probabilistic solution construction by a colony of ants with local search [START_REF] Dorigo | Ant colony system: A cooperative learning approach to the traveling salesman problem[END_REF][START_REF] Stützle | MAX -MIN Ant System[END_REF][START_REF] Solnon | Ants can solve constraint satisfaction problems[END_REF].

In this section, we study the benefit of integrating local search within Ant-Clique. The hybrid algorithm is derived from the algorithm of Figure 1 as follows: once each ant has constructed a clique, and before updating pheromone trails, we apply a local search procedure on the largest clique of the cycle until it becomes locally optimal2 . Pheromone trails are then updated with respect to this locally optimal clique.

Various local search procedures may be used to improve cliques, e.g., [START_REF] Abello | On maximum clique problems in very large graphs[END_REF][START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF][START_REF] Marchiori | Genetic, iterated and multistart local search for the maximum clique problem[END_REF]. However, as pointed out in [START_REF] Lourenço | Iterated local search[END_REF], when choosing the local search procedure to use in a meta-heuristic such as evolutionary algorithms, iterated local search or ACO, one has to find a trade-off between computation time and solution quality. In other words, one has to choose between a fast but not-so-good local search procedure or a slower but more drastic one.

For all experiments reported in this paper, we have considered the (2,1)exchange procedure used in GRASP [START_REF] Abello | On maximum clique problems in very large graphs[END_REF]. Given a clique C, this local search procedure looks for three vertices v i , v j and v k such that: -v i belongs to C, -v j and v k do not belong to C, -v j and v k are linked by an edge, and -v j and v k are adjacent to every vertex of C -{v i }. Then, it replaces the vertex v i by the two vertices v j and v k , thus increasing the clique size by one. This local search procedure is iterated until it reaches a locally optimal state that cannot be improved by such a (2,1)-exchange.

Figure 4 shows that this local search procedure actually enhances the performance of Ant-Clique when solving instance C500.9. In particular, when α is set to 0 and ρ to 1, i.e., when pheromone is not used, the local search procedure roughly increases the size of the constructed cliques by four, and this improvement in quality is constant during the whole run. When α is set to 1 and ρ to 0.99, so that pheromone actually influences the solution process, local search also improves the quality of the cliques constructed by Ant-Clique, but the improvement in quality is not constant during the run. At the beginning of the run, local search increases cliques by four vertices. However, after a thousand or so cycles, the improvement in quality is much smaller. Finally, at the end of the run the best clique found when combining Ant-Clique with local search is slightly larger than when local search is not used. Note that local search enhances the performances of the two variants of Ant-Clique in a very similar way: for Edge-AC (resp. Vertex-AC) the integration of local search increases the average quality of the best clique after 2500 cycles from 55.6 to 55.9 (resp. 55.2 to 55.4)

Experimental comparison of the four instantiations of Ant-Clique

In this section, we experimentally evaluate and compare the four proposed instantiations of Ant-Clique, i.e., Edge-AC, Vertex-AC, Edge-AC combined with local search (referred to as Edge-AC+LS) and Vertex-AC combined with local search (referred to as Vertex-AC+LS).

Experimental setup. All algorithms have been implemented in the C language and ran on a 1.9 GHz Pentium 4 processor, under Linux operating system. In all experiments, we have set the number of ants to 30, τ min to 0.01, τ max to 6, α to 1, and ρ to 0.99, thus achieving a good compromise between solution quality and CPU time as discussed in Section 3.

The maximum number of cycles has been set to 5000. Indeed, for many Figure 4: Evolution of the size of the best clique (average over 50 runs) for graph C500.9 with local search (*-AC + LS) or without local search (*-AC), and with pheromone (alpha=1, rho=0.99) or without pheromone (alpha=0, rho=1.00), for graph C500.9. The other parameters have been set to nbAnts = 30, τ min = 0.01, and τ max = 6. Upper curves display results for Edge-AC and lower curves for Vertex-AC.

benchmark instances, all algorithms have converged to the best solutions within the first three thousands of cycles. However, on larger instances -that have more than one thousand of vertices-Edge-AC may need more cycles to converge so that we have fixed the maximum number of cycles to 5000 for all instances.

Test suite. We consider 36 benchmark graphs provided by the DIMACS challenge on clique coloring and satisfiability3 .

• Cn.p and DSJCn.p graphs are randomly generated graphs with n vertices and a density of 0.p, i.e., an edge is created between any pair of vertices with probability 0.p.

• MANN a27 and MANN a45 graphs are clique formulations of set covering formulations of Steiner Triple Problems and respectively have 378 and 1035 vertices, and a density of 0.99.

• brockn m graphs have n vertices and a density between 0.496 and 0.74. These graphs contain large cliques hidden among a connected population of significantly smaller cliques.

• genn p0.p m graphs have n vertices, a density of 0.p, and hidden cliques of known size m.

• hammingn m graphs associate a vertex with each different n-bits word, so that hamming8-4 and hamming10-4 respectively have 256 and 1024 vertices. In these graphs, an edge exists between two vertices if and only if their words are at least distant of a Hamming distance m, so that the density respectively is 0.639 and 0.829.

• Keller graphs are based on a representation of Keller's conjecture on the tiling of space using hypercubes. keller 4, 5 and 6 graphs respectively have 171, 776 and 3361 vertices, and a density of 0.649, 0.751, and 0.818.

• p hatn m are random graphs having n vertices, and a density between 0.244 and 0.506. These graphs are tuned to have a wider vertex degree spectrum.

We do not report results for the MANN a81 instance, which has 3321 vertices and a maximum clique of 1098 vertices: for this instance, Vertex-AC and Edge-AC respectively spend 8800 and 11600 seconds of CPU time to perform 5000 cycles. Note that this prohibitive time is mainly due to the size of the computed cliques. Indeed, the keller6 graph, that has 3361 vertices but a maximum clique of 59 vertices, is processed in a few minutes by both Vertex-AC and Edge-AC.

Table 2: Comparison of ACO algorithms by means of solutions' quality. Each row successively displays the instance name, the size of its maximum clique, and the results obtained by Vertex-AC, Edge-AC, Vertex-AC+LS, and Edge-AC+LS (best and average solution found over 50 runs; standard deviation in brackets). This table also shows that local search improves the solution process of both algorithms for many instances. For Vertex-AC, the integration of local search improves average results for 22 instances, whereas it deteriorates them for 1 instance, and for Edge-AC, the integration of local search improves average results for 16 instances, whereas it deteriorates them for 2 instances. Note that the benefit of integrating local search within Ant-Clique varies with respect to the considered classes of instances. In particular, local search does not improve solutions' quality for MANN instances, whereas it significantly improves it on hard random C*.* instances, so that Edge-AC+LS has been able to find the best known solutions for all C*.* instances.

Hence, Edge-AC+LS is the best performing of the four proposed ACO instantiations, for a majority of instances, and it has been able to find the best known solution for 31 instances, over the 36 considered instances. However, for 2 instances (brock400 2 and keller6), Edge-AC has found the best known solution whereas Edge-AC+LS did not.

Finally, this comparison on a large set of instances has shown us that solutions' quality depends on the considered classes of instances. In particular, the four considered ACO instantiations obtained very good average results on gen* p* * and p hat* * instances, being able to find the best known solution for nearly all the runs on most of these instances. On the other side, average results are rather far from optimality on brock* * instances. Actually, as pointed out in [START_REF] Brockington | Camouflaging independent sets in quasi-random graphs[END_REF], brock* * graphs were created using trap mechanisms destined to fool greedy algorithms and guide them towards deceptively easy solutions while bigger cliques remain hidden. As a consequence, if some runs have been able to find these hidden cliques, most runs have been trapped in smaller cliques.

Comparison of CPU time. Table 3 compares the four proposed ACO instantiations by means of CPU time. This table first shows that, for each considered ACO instantiation, the number of cycles -and therefore the CPU timeneeded to find the best solution mainly depends on the number of vertices and the connectivity of the graph. For example, Edge-AC respectively performs, on average, 473, 923, 2359, and 3278 cycles to solve instances C250.9, C500.9, C1000.9, and C2000.9 that respectively have 250, 500, 1000 and 2000 vertices and a connectivity close to 0.9, whereas it performs 1062 cycles to solve instance C2000.5 that has 2000 vertices and a connectivity of 0.5.

Table 3 also shows that Vertex-AC nearly always performs less cycles than Edge-AC and, on average for all instances, it needs 1.8 times less cycles to converge towards its best solution. When considering CPU times, the difference becomes more important as Edge-AC needs more time to perform one cycle than Vertex-AC. Hence, Vertex-AC is from 1.5 to 26 times as fast as Edge-AC, and it is 5.7 times as fast on average for all instances.

Finally, one can remark that the integration of local search always decreases the number of cycles: on average, both Vertex-AC+LS and Edge-AC+LS perform 1.8 times less cycles than Vertex-AC and Edge-AC respectively. However, as local search is time consuming, CPU times are rather comparable.

Discussion. This comparison on 36 benchmark graphs showed us that integrating local search within Ant-Clique nearly always improves solutions' quality without increasing CPU times, so that one clearly has better use Vertex-AC+LS or Edge-AC+LS instead of Vertex-AC or Edge-AC.

However, to choose between Vertex-AC+LS and Edge-AC+LS, one has to consider the CPU time available for the solution process. Indeed, Edge-AC+LS usually finds better solutions than Vertex-AC+LS at the end of its solution process, but it is also more time consuming. As a consequence, if one has to find a solution within a short time limit, one has better use Vertex-AC+LS, whereas for larger time limits, or when there is no time limit, one has better use Edge-AC+LS. This is illustrated in Figure 5 on graph C500.9: for time limits smaller than 8 seconds, Vertex-AC+LS finds larger cliques than Edge-AC+LS, whereas for larger time limits Edge-AC+LS finds larger cliques than Vertex-AC+LS.

Figure 5 also compares Vertex-AC+LS and Edge-AC+LS with a multi-start local search procedure called multi-start LS. This multi-start local search procedure iterates on the two following steps:

1. randomly build a maximal clique, 2. apply the local search procedure described in Section 4 on this maximal clique Hence, multi-start LS corresponds to Ant-Clique+LS when pheromone is not used and the number of ants is set to 1 (so that local search is applied to every constructed clique). Figure 5 shows us that during the first second of CPU time multi-start LS finds better solutions than Ant-Clique+LS. Indeed, Ant-Clique+LS spends time to manage pheromone whereas this pheromone starts influencing ants only after a few hundreds or so cycles. Hence, Vertex-AC+LS (resp.Edge-AC+LS) finds better solutions than multi-start LS only after one second (resp. five seconds) of CPU time.

Experimental comparison with other heuristic approaches

We now compare Edge-AC+LS, which is our best performing ACO algorithm by means of solution quality on a majority of instances, with three recent and representative algorithms, i.e., RLS, DAGS, and GLS.

RLS (Reactive Local Search) [START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF] is based on a tabu local search heuristic.

Starting from an empty clique, RLS iteratively moves in the search space composed of all cliques by adding/removing one vertex to/from the current clique.

A tabu list is used to memorize the T last moves and, at each step, RLS greedily selects a move that is not prohibited by the tabu list. The key point is that the length T of the tabu list is dynamically updated with respect to the need for diversification. RLS appears to be the best heuristic algorithm for the maximum clique problem we are aware of, for a majority of DIMACS benchmark instances. Table 4 displays results reported in [START_REF] Battiti | Reactive local search for the maximum clique problem[END_REF] for the "basic" version of RLS which obtained the best results. CPU times have been multiplied by 0.027, corresponding to the ratio of computers' speed with respect to the Spec benchmark on floating point units.

DAGS [START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF] is a two-phase procedure: in a first phase, a greedy procedure combined with "swap" local moves is applied, starting from each node of the graph; in a second phase, nodes are scored with respect to the number of times they have been selected during the first phase, and an adaptive greedy algorithm is repeatedly started to build cliques around the nodes with the least scores, in order to diversify the search towards less explored areas.

Experiments reported in [START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF] show that the first phase is able to find best known solutions for many instances. For harder instances, the second phase improves solutions' quality in many cases. This improvement in quality is dramatic on the set of brock instances, that are known to be very difficult for greedy approaches. For these instances, DAGS outperforms RLS performance.

Table 4 displays results reported in [START_REF] Grosso | Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem[END_REF]. Note that the second phase of DAGS has been performed only for the harder instances, that have not been solved during the first phase. Hence, we specify in Table 4 if these results have been obtained after the first or the second phase. We multiplied CPU times by 0.84, corresponding to the ratio of computers' speed with respect to the Spec benchmark on floating point units. Note also that CPU times reported for DAGS correspond to the total time spent for the whole solving process, and not the time spent to find the best solution like for the three other considered algorithms.

GLS [START_REF] Marchiori | Genetic, iterated and multistart local search for the maximum clique problem[END_REF] combines a genetic algorithm with local search. We consider it for comparison, though it does not outperform RLS nor DAGS, because it presents some similarities with ACO: both approaches use a bio-inspired metaphor to intensify the search towards the most "promising" areas with respect to previously computed solutions. GLS generates successive populations of maximal cliques from an initial one by repeatedly selecting two parent cliques from the current population, recombining them to generate two children cliques, applying local search on children to obtain maximal cliques, and adding to the new population the best two cliques of parents and children. GLS can be instantiated to different algorithms by modifying its parameters. In particular, [START_REF] Marchiori | Genetic, iterated and multistart local search for the maximum clique problem[END_REF] compares results obtained by the three following instantiations of GLS: GENE performs genetic local search; ITER performs iterated local search, starting from one random point; and MULT performs multi-start local search, starting from a new random point at each time.

Table 4 displays, for each considered instance, the results obtained by the GLS algorithm (over GENE, ITER, and MULT) that obtained the best average results. We multiplied CPU times by 0.037, corresponding to the ratio of computers' speed with respect to the Spec benchmark on floating point units.

By means of solutions' quality, the results of table 4 are summarized in table 5. When considering the best found results, Edge-AC+LS is competitive with both RLS and DAGS, being able to find better solutions than RLS on two brock instances, and better solutions than DAGS on two C*.9 instances. However, when considering average results RLS outperforms Edge-AC+LS on 16 instances. The comparison with DAGS on average results depends on the considered instances. In particular, DAGS outperforms Edge-AC+LS on brock instances, whereas Edge-AC+LS outperforms DAGS on gen instances.

This table also shows that Edge-AC+LS outperforms GLS both with respect to best and average results. Hence, for this problem ACO is better suited than evolutionary computation for guiding the search towards promising areas.

When considering CPU times reported in Table 4, one can note that Edge-Table 4: Comparison of Edge-AC+LS with other heuristic approaches. Each row successively displays the results obtained by Edge-AC+LS, RLS, DAGS (followed by ( 1) or (2) if they have been obtained after the first or the second phase), and GLS (followed by (G), (I), or (M) if they have been obtained by GENE, ITER, or MULT). For each approach, the table reports the best and average solution found (over 50 runs for Edge-AC+LS, 100 runs for RLS, 20 runs DAGS, and 10 runs for GLS), and the estimated CPU time w.r.t. the Spec floating points benchmark. AC+LS is an order slower than RLS, which itself is an order slower than GLS. However, Edge-AC+LS is rather comparable with DAGS: it is quicker than DAGS for 24 instances, and it is slower for 8 instances.

Conclusion

We have described a generic ACO algorithm for searching for maximum cliques, and two different instantiations for it. These two instantiations differ in the choice of their pheromonal components. A main motivation was to answer the following question: should we lay pheromone on the vertices or on the edges of the graph? Experiments have shown us that both algorithms are able to find optimal solutions on many benchmark instances, showing that ACO is actually able to guide the search towards promising areas. However, when comparing the diversification capability of the two algorithms by means of re-sampling and similarity ratio, we have noticed that the search is more diversified when pheromone is laid on edges so that better solutions are found on a wide majority of benchmark instances, but as a counterpart, more time is needed to converge. Also, experiments have shown us that the integration of local search techniques improves the solution process and makes ACO competitive with state-of-the-art heuristic approaches, though it is more time consuming.

We believe that this comparison of two ACO models for the maximum clique problem could be useful to solve other similar problems. Indeed, for many combinatorial optimization problems such as multi-dimensional knapsack problems or generalized assignment problems, the goal is to find, given an initial set of objects, the best subset with respect to some objective function. To solve this kind of problems with ACO, one has to choose between laying pheromone on the objects to choose, or on edges linking the objects to choose. In the first case, one will increase the desirability of choosing each rewarded object independently from the others, whereas in the second case, one will increase the desirability of choosing together two objects. Hence, further work will concern a generalization of this comparative study.

Figure 1 :

 1 Figure 1: Generic algorithmic scheme of Ant-Clique

  the evaporation step requires O(| V |) operations and the reward of a clique C requires O(| C |) operations. As | C |≤| V |, the whole pheromone updating step requires O(| V |) operations. • In Edge-AC, the evaporation step requires O(| E |) operations and the reward of a clique C requires adding pheromone on each edge of C. As the number of edges of a clique is smaller or equal to | E |, the whole pheromone updating step requires O(| E |) operations.

  largest clique (average on 50 runs) Number of cycles performed by Edge-AC alpha=1 rho=.995 alpha=1 rho=.990 alpha=2 rho=.990 alpha=2 rho=.980 alpha=0 rho=1clique (average on 50 runs) Number of cycles performed by Vertex-AC alpha=1 rho=.995 alpha=1 rho=.990 alpha=2 rho=.990 alpha=2 rho=.980 alpha=0 rho=1.00

  of common vertices in the cliques constructed every 50 cycles) Number of cycles performed by Edgeof common vertices in the cliques constructed every 50 cycles) Number of cycles performed by Vertex-AC alpha=1 rho=.995 alpha=1 rho=.990 alpha=2 rho=.990 alpha=2 rho=.980

Figure 3 :

 3 Figure3: Evolution of the similarity ratio for Edge-AC (upper curves) and Vertex-AC (lower curves) for graph C500.9: each curve plots the similarity ratio of the set of cliques constructed every 50 cycles (average over 50 runs), for a given setting of α and ρ. The other parameters have been set to nbAnts = 30, τ min = 0.01, τ max = 6.

  largest clique (average over 50 runs) CPU time in seconds (logscale) vertex-AC+LS edge-AC+LS multi-start LS

Figure 5 :

 5 Figure 5: Comparison of Edge-AC+LS, Vertex-AC+LS, and multi-start local search on graph C500.9. Parameters have been set to α = 1, ρ = 0.99, nbAnts = 30, τ min = 0.01, and τ max = 6 for Edge-AC+LS and Vertex-AC+LS.

  Initialize pheromone trails to τmax repeat the following cycle:for each ant k in 1..nbAnts , construct a maximal clique C k as follows:Randomly choose a first vertex vi ∈ V C E} end while end for Update pheromone trails w.r.t. {C1, . . . , C nbAnts } if a pheromone trail is lower than τmin then set it to τmin if a pheromone trail is greater than τmax then set it to τmax until maximum number of cycles reached or optimal solution found return the largest constructed clique since the beginning

k ← {vi} Candidates ← {vj ∈ V | (vi, vj ) ∈ E} while Candidates = ∅ do

Choose a vertex vi ∈ Candidates with probability p(vi)

C k ← C k ∪ {vi} Candidates ← Candidates ∩ {vj | (vi, vj ) ∈

Table 3 :

 3 Comparison of ACO algorithms by means of CPU time. Each row successively displays the number of cycles (average over 50 runs) and the CPU time (average and standard deviation over 50 runs) for Vertex-AC, Edge-AC, Vertex-AC+LS, and Edge-AC+LS.Comparison of solutions' quality. Table2compares the four proposed ACO instantiations by means of solutions' quality. On this table, one can first note that Edge-AC outperforms Vertex-AC: when considering average results over the 50 runs, Edge-AC has found larger cliques than Vertex-AC for 21 instances, whereas it has found smaller cliques for 2 instances only. Moreover, Edge-AC has been able to find the best known solution for 29 instances, whereas Vertex-AC has found it for 24 instances.

			Number of cycles and time to find the best clique
		Vertex-AC	Edge-AC	Vertex-AC+LS	Edge-AC+LS
	Graph	Cycles Time(Stdv) Cycles Time(Stdv) Cycles Time(Stdv) Cycles Time(Stdv)
	C125.9	60	0.1 (0.0)	126	0.2 (0.1)	14	0.0 (0.0)	23	0.0 (0.0)
	C250.9	359	0.8 (0.7)	473	1.7 (0.3)	172	0.5 (0.1)	239	1.0 (0.3)
	C500.9	722	3.8 (1.9)	923	8.9 (4.0)	477	4.6 (2.7)	671	8.6 (4.7)
	C1000.9	1219	13.2 (5.8) 2359	55.0 (21.9)	832	23.4 (8.5) 1242	49.8 (26.6)
	C2000.9	1770 41.3 (11.0) 3278 214.4 (49.8) 1427 112.4 (16.8) 2067 238.7 (98.3)
	DSJC500.5	588	0.5 (0.2)	832	2.6 (1.8)	249	0.7 (0.5)	285	1.4 (1.3)
	DSJC1000.5	820	1.4 (1.0) 1017	9.6 (6.4)	561	3.8 (4.0)	567	7.8 (8.8)
	C2000.5	957	3.3 (3.0) 1062	30.4 (16.8)	312	5.9 (5.7)	957	40.6 (56.0)
	C4000.5	927	6.0 (5.1) 1116 108.3 (73.8)	445	22.4 (33.1) 1915 257.6 (190.2)
	MANN a27	616	11.5 (3.5) 2274	61.7 (25.3)	574	11.1 (4.9) 1824	44.8 (19.3)
	MANN a45	1771 271.3 (77.0) 4360 877.4 (69.1) 1498 239.2 (56.9) 3639 749.4 (132.5)
	brock200 2	115	0.0 (0.0)	127	0.1 (0.1)	104	0.1 (0.1)	115	0.1 (0.1)
	brock200 4	156	0.1 (0.0) 1627	1.3 (1.2)	69	0.1 (0.0) 1356	1.7 (1.9)
	brock400 2	650	1.0 (0.6) 1004	3.5 (1.9)	424	1.4 (0.6)	720	3.8 (3.5)
	brock400 4	498	0.8 (0.2)	977	3.4 (3.3)	254	0.8 (0.4) 1141	5.7 (6.3)
	brock800 2	1145	2.6 (1.1) 1238	9.1 (6.1)	881	6.3 (3.6)	959	11.6 (10.5)
	brock800 4	1173	2.7 (1.0) 1288	9.8 (7.1)	858	6.1 (2.5)	906	11.1 (10.7)
	gen200 p0.9 44	297	0.6 (0.2)	338	0.9 (0.2)	136	0.3 (0.1)	165	0.5 (0.1)
	gen200 p0.9 55	102	0.2 (0.0)	130	0.3 (0.1)	57	0.2 (0.0)	100	0.3 (0.1)
	gen400 p0.9 55	475	2.0 (1.2) 1634	11.5 (6.4)	270	1.8 (0.6)	760	6.7 (3.7)
	gen400 p0.9 65	337	1.4 (0.2)	391	2.7 (0.3)	206	1.5 (0.1)	255	2.3 (0.3)
	gen400 p0.9 75	251	1.0 (0.1)	293	2.1 (0.2)	153	1.2 (0.1)	198	2.1 (0.2)
	hamming8 4	34	0.0 (0.0)	42	0.1 (0.0)	49	0.1 (0.1)	42	0.1 (0.1)
	hamming10 4	2308	13.7 (1.9) 1474	28.0 (10.5) 1204	26.2 (17.3)	865	29.3 (16.3)
	keller4	2	0.0 (0.0)	2	0.0 (0.0)	0	0.0 (0.0)	0	0.0 (0.0)
	keller5	1652	4.9 (1.2) 1136	10.8 (7.9)	979	9.4 (6.0)	830	12.3 (9.7)
	keller6	2514 55.3 (15.2) 3034 308.8 (111.8) 1657 206.8 (145.3) 2617 549.2 (250.6)
	p hat300 1	40	0.0 (0.0)	46	0.0 (0.0)	18	0.0 (0.0)	20	0.0 (0.0)
	p hat300 2	113	0.1 (0.0)	206	0.3 (0.1)	26	0.1 (0.0)	54	0.2 (0.1)
	p hat300 3	281	0.5 (0.5)	457	1.3 (0.3)	110	0.3 (0.1)	176	0.7 (0.2)
	p hat700 1	379	0.2 (0.1)	624	2.6 (1.6)	253	0.7 (0.3)	391	2.4 (2.0)
	p hat700 2	297	0.7 (0.1)	445	3.2 (0.6)	128	2.0 (0.6)	227	4.5 (1.0)
	p hat700 3	575	3.0 (2.2)	878	9.8 (3.2)	220	3.8 (1.0)	333	7.8 (1.4)
	p hat1500 1	391	0.4 (0.3)	662	10.5 (8.5)	318	3.0 (4.4)	438	9.7 (17.0)
	p hat1500 2	499	3.3 (1.0)	801	20.1 (4.9)	238	17.3 (2.7)	379	35.2 (3.9)
	p hat1500 3	581	8.6 (6.5) 2199	74.3 (41.6)	551	37.0 (34.4)	528	54.9 (8.8)

Table 5 :

 5 Number of times Edge-AC+LS has found larger (+), equal (=), and smaller (-) cliques than RLS, DAGS and GLS.

	Comparison of Edge-AC+LS with
	RLS	DAGS	GLS
	+ = -+ = -+ =	-
	Best clique 2 30 4 2 29 1 11 23	2
	Average size 0 20 16 6 15 11 28 7	1

Remember that, as pointed out in

2.3, pheromone factors in Edge-AC are computed in an incremental way, i.e., each time a new vertex is added to the clique, the pheromone factor of each candidate vertex is updated by a simple addition.

Local search could be applied to every computed clique (instead of applying it only to the best clique of the cycle). However, experiments showed us that this does not significantly improve solutions' quality, whereas it is much more time consuming.

This benchmark is available at http://dimacs.rutgers.edu/.


Yuan-Shao Huang

Kun-Ming Yu
email: yu@chu.edu.tw

Li-Wei Zhou

Ching-Hsien Hsu

Sheng-Hui Liu

Accelerating Parallel Frequent Itemset Mining on Graphics Processors with Sorting

Keywords: Parallel Data Mining, Apriori, Graphic Processing Unit (GPU). Acknowledgment

Frequent Itemset Mining (FIM) is one of the most investigated fields of data mining. The goal of Frequent Itemset Mining (FIM) is to find the most frequently-occurring subsets from the transactions within a database. Many methods have been proposed to solve this problem, and the Apriori algorithm is one of the best known methods for frequent Itemset mining (FIM) in a transactional database. In this paper, a parallel Frequent Itemset Mining Algorithm, called Accelerating Parallel Frequent Itemset Mining on Graphic Processors with Sorting (APFMS), is presented. This algorithm utilizes newgeneration graphic processing units (GPUs) to accelerate the mining process. In it, massive processing units of GPU were used to speed up the frequent item verification procedure on the OpenCL platform. The experimental results demonstrated that the proposed algorithm had dramatically reduced computation time compared with previous methods.

Introduction

With the development of information technology, all sectors of society have to handle massive explosions in their digital databases. The size of datasets has been increased exponentially in recent years in all fields as speed ups in processing and communication have greatly improved the capability for data generation and collection. Therefore the extraction of interesting and meaningful information has become a highly popular field of study. Data mining, known as Knowledge Discovery in Databases (KDD), is the process of automatically extracting useful hidden information from very large databases.

Frequent Itemset Mining (FIM) is one of the main tasks in data mining field which aims at finding interesting patterns from databases. The data in the database contains a set of items that are called transactions, each of which is labeled by a unique ID. The goal of FIM algorithms is to generate all possible itemsets and find the most frequently-occurring subsets that are bought together in not less than a given, userspecified threshold. The number of itemsets occurrences is called support, and the threshold is minimum support.

In recent years, parallel data mining algorithms has been attracted more and more attention. Modern Graphics Processing Units (GPU) have evolved into powerful processors that not only support typical computer graphics tasks but are also flexible enough to perform general purpose computations [6] [7] [10] [START_REF] Silvestri | gpuDCI: Exploiting GPUs in Frequent Itemset Mining[END_REF]. Recently, there has been a trend to accelerate computational data mining algorithm on a GPU + CPU heterogeneous system which the GPU acts as the computation accelerator. Nowadays, high level languages have emerged to support easy programming on GPUs. OpenCL [START_REF]OpenCL[END_REF] seems to be emerging as an open and cross-vendor standard for exploiting computational power of both CPUs and GPUs. However, many classical algorithms have been proposed for single CPU architectures [START_REF] Ferencbodon | A trie-based APRIORI implementation for mining frequent item sequences[END_REF] [START_REF] Borgelt | Frequent Item Set Mining[END_REF]. If CPU-GPU hybrid architectures are used to speed up the mining purpose, it will improve performance.

In order to best utilize the power computing resources offered by GPUs and extend traditional, CPU-based data mining algorithms for mapping to CPU-GPU hybrid architecture, scalable GPU-based parallel evaluation model for speeding up the computing process was implemented in this study. A solution is proposed that would have all frequent itemsets sorted after constructing the TID table which will then greatly reduce the candidate itemsets when using CPU architecture. Suitable GPU threads were allocated after sorting the itemset in decreasing order. Therefore, the times of the checking process were reduced, and support counting was time efficient. The compared results showed that efficiency had been significantly improved.

The remainder of this paper is organized as follows. Section 2 provides an overview of data mining, describes the Apriori algorithm [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] [START_REF] Park | An effective hash-based algorithm for mining association rules[END_REF], the Multi-core Apriori Transaction Identifiers algorithm (MATI) [START_REF] Kun | An Efficient Load Balancing Multi-core Frequent Patterns Mining Algorithm[END_REF] and the Candidate Slicing Frequent Pattern Mining (CSFPM) [START_REF] Lin | An OpenCL Candidate Slicing Frequent Pattern Mining algorithm on graphic processing units[END_REF] algorithm. The proposed algorithm Accelerating Parallel Frequent Itemset Mining on Graphics Processors with Sorting (APFMS) is introduced in Section 3. Section 4 presents the experimental results. In section 5, the conclusion of the paper is given.

Related Works

Data mining is a technology used to determine special relationships hidden in large amounts of data, and efficiency is especially crucial for an algorithm finding frequent item sets from a large database. Many methods have been proposed to solve this problem. Among them, parallel computing has become a popular trend, such as grid, cloud, multi-core or GPU computing platforms.

In this section, the most relevant studies, including Apriori algorithms, the Multicore Apriori Transaction Identifiers (MATI) algorithm and the Candidate Slicing Frequent Pattern Mining (CSFPM) algorithm, are briefly reviewed.

Apriori algorithm

The Apriori Algorithm was proposed by R. Agrawal and R. Srikant in 1994 [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]. It's a classic algorithm for frequent itemset mining and association rule learning over transactional databases. It uses a level-wise behavior, which involves a number of dataset scans equal to the size of the largest frequent itemset. Apriori iteratively generates K+1 frequent itemsets by joining frequent K-itemsets. This step is candidate generation. First, the set of frequent 1-item sets is found by scanning the database to assess the count for each item, and then collecting the items that satisfy minimum support, denoted L 1 . L 1 is used to find L 2 , and L 2 to find L 3 , and this continues, until all frequent itemsets are found. After generating each new set of candidates, the algorithm scans the database to count the number of occurrences of each itemsets. This step is called support counting. The Apriori Algorithm stops when all the frequent item sets have been generated. However, the algorithm scans datasets many times and may generate redundant candidate itemsets. When there are many frequent 1-item sets and the frequent patterns are very long, the number of generated candidate itemsets increases significantly. Therefore, the efficiency of the algorithm deteriorates significantly.

Multi-core Apriori Transaction Identifiers

Lately, novel algorithms on frequent pattern mining have been proposed. Yu et al. propose the MATI algorithm [START_REF] Kun | An Efficient Load Balancing Multi-core Frequent Patterns Mining Algorithm[END_REF] to speed up the computation time of data mining by enhancing the efficiency of Apriori on multi-core architecture. The algorithm utilizes the AprioriTID algorithm [START_REF] Agawal | Mining Association Rules between Sets of Items in Large Database[END_REF] [8] at the first pass to shorten the database scanning process by creating the Transaction Identification (TID) tables. In MATI algorithm, two strategies are proposed, Item set Block and Task Dispatches. In the process of generating candidate in MATI, frequent itemsets are divided into multiple blocks, all frequent itemsets with the same prefix are put into the same block, and candidates are generated in the same block only. The frequent itemsets in the same itemset block will be generated on the same core avoiding data distributed on different cores.

Candidate Slicing Frequent Pattern Mining

Candidate Slicing Frequent Pattern Mining (CSFPM) [START_REF] Lin | An OpenCL Candidate Slicing Frequent Pattern Mining algorithm on graphic processing units[END_REF] is proposed by Lin et al. This algorithm uses the Transaction Identification (TID) table to store the itemsets which shorten the database scanning process, as shown in Table 1. Corresponding to the TID table, two elements, the TID value table and the TID index table are created with GPU-FPM [START_REF] Zhou | Parallel frequent patterns mining algorithm on GPU[END_REF]. In Fig. 1, TID value table stores the itemsets associated with their transaction numbers in GPU threads, TID index table stores the location numbers in GPU threads corresponded to its itemset. As numbers in the table starts from 0, the first itemset A contains 1, 2 in the TID value table, then in the TID index table the number is 0 to 1, and the itemset B contains 1, 2, 3, so the index number range 2 to 4, this process continues until all the itemsets have been dispatched.

The CSFPM algorithm divides candidate into smaller units with parallel computing on each GPU thread. Each GPU thread is only responsible checking for its own one candidate itemset in the TID value table. The GPU thread only checks and compares the numbers whether are equal or not. If the values are equal, then returns result 1, else result 0 is returned instead. The checking process is shown in Fig. 2. Item A and Item B has the common transaction value 1 and 2, then the output returns double 1. After the first computation finished, the result was returned with an array of 1110100, and then the number of 1 was calculated; all the numbers of 1 were summed to compare with the minimum support checking whether the candidate itemset was frequent or not, as shown in Fig. 2 and Table 2.

The CSFPM algorithm is an implementation on CPU-GPU architecture based on the Apriori algorithm, and reducing the counting time of the GPU support to speed up the total computing time. In order to achieve better load balancing performance, the algorithm parallelizes the candidate itemsets and divides them into the GPU threads, assign one thread only checking to its own one transaction in a candidate item. This strategy can reduce the processor waiting time since the load between processing units is more balanced.

Table 1. TID table

Items TID Value

Proposed Algorithm

Since the information in a data stream is large, the implementing of an efficient algorithm based on the Apriori algorithms has been the focus of many researchers. Due to the great advantages of GPUs, they have evolved become highly parallel, multithreaded with tremendous computational horsepower and very high memory bandwidth. In this paper, an Accelerating Parallel Frequent Itemset Mining on Graphics Processors with Sorting (APFMS) algorithm is presented. It is based on the advantages of CSFPM and MATI utilizing the sorting of the 1-frequent item sets from the dataset after constructing the TID table in order to cut down on computing time for better performance.

The APFMS algorithm was optimized by using the dividing method of CSFPM and the merging method of MATI. The MATI algorithm uses the follow technique. Unlike the original Apriori algorithm, the (k+1)-itemset is generated only by the kitemset with the same k-1 prefix itemset. Fig. 3 illustrates the procedure for MATI, in the example, k=2 and itemset AB and AC are the 2-itemsets which were frequent, when the 3-itemset was be generated, the 2-itemset merged with each other to satisfy the (2-1=1) prefix, as AB and AC had the same prefix. A, thus AB and AC merged with each other to generate candidate 3-itemset, ABC. However, the AC and BC did not merge with each other as they did not have the same prefix. Therefore, it was not necessary to generate all possible itemsets as in the original Apriori algorithm; the MATI algorithm filtered the redundant itemsets which were not frequent and only merge the useful frequent itemsets.

Fig. 3. Generating itemsets in MATI

GPU threads were allocated by the number of TID values in the Candidate Slicing Frequent Pattern Mining (CSFPM) algorithm. Therefore, the higher the TID value, the more GPU threads were allocated. Fig. 4 shows the processing of CSFMP in comparing the TID value. Owing to the varying TID values, the GPU threads did not compute efficiently. As a result, the APFMS algorithm proposed a strategy sorting all 1-frequent itemsets after constructing the TID table with the support of 1-frequent itemset each and in the decreasing order, and then the GPU threads were allocated according the new TID value after sorting. Therefore, the time complexity was reduced when the GPU checked the itemsets; whether they had the same prefix in order to merge so that the next rank candidate itemsets could be generated. The processing of the APFMS algorithm when comparing the TID values is presented in fig. 5.

Fig. 4. CSFMP method

Fig. 5. APFMS method

As in fig. 5, when compared with the CSFMP algorithm in fig. 4, the APFMS algorithm sorted all frequent itemsets in descending order after constructing the TID table in CPU cores, and the results were transferred to the TID value tables in the GPU threads in the same order; Then, the larger itemsets were mapped in the front in the TID value tables. Due to this, the numbers of checking process support counting steps were reduced. Therefore, the support counting time will reduce as well. Following, are several basic steps for applying the APFMS algorithm.

Procedure

1. First, Scan the database, transform the transaction items to a TID table and build the corresponded TID value table and TID index table. 2. Calculate the Tidset and count the support number of each 1-candidate itemset, prune the non-valid itemsets and generate the 1-frequent itemset. 3. Sort the 1-frequent itemset in decreasing order. 4. Use the MATI merge function in CPU cores, that all K+1 itemsets are generated from K itemsets with the same K-1 prefix 5. Let the GPU cores calculate the support counting step, all datasets are transfer from CPU cores to GPU cores, dynamic GPU threads are allocated to calculate the item in the TID value table and its corresponding TID index table. 6. Return the 0-1 arrays from GPU cores to CPU cores, use CPU cores to calculate the number of 1 and compare with the threshold. 7. Generate the next rank candidate itemsets, repeat the step above until all the frequent itemsets are found.

The pseudo code of APFMS is shown in fig. 6.

CPU: Main Function ( C++ )

Database is D, merge round is N, candidate itemsets in N round is Cn, Frequent pattern is Fn. Cnis candidate patterns and more than 1.

Fn is frequent pattern and more than 1.

Experimental Results

In this section, the experiments are conducted to verify the performance of the APFMS method and the comparison with CSFPM on GPU are presented. In the experiments, the same hardware and software configurations were used and the Input data was from the IBM data generator [START_REF] Agrawal | Quest Synthetic Data Generator[END_REF] shown in Table 3. In the experiment, the computation time shown in Fig. 7 indicates that with the dataset (T10I4D100KN100K) and the threshold 0.1%, the APFMS algorithm needed less time than the CSFPM algorithm, and hence resulted in higher efficiency with 300% speedup when the GPU was set at 65536 threads. This experiment compared the computation time of APFMS with that of CSFPM with the same threshold of 0.1%, but with different methods, number of transactions and number of threads (153837). As in Fig. 8, APFMS performed better than CSFPM on the same platform.

Fig. 9 shows the execution time of CSFPM and APFMS with different GPU threads when the dataset was T10I4D1000KN100K, and the threshold 0.1%. In this experiment, with the transaction numbers increasing, the execution time of the APFMS increased as well. However, with the number of GPU threads getting higher than 153837, the checking times and the time complex of CSFPM were increasing. The CSFPM did not even finish computing when the number of GPU threads was set as more than 153837.

Using the same dataset as the CSFPM algorithm, the APFMS algorithm had a better speedup performance. Further, with the number of GPU threads increasing, the computing time increased as well, causing the CPU cores having to finish computation with more space and bandwidth. However, when the computing time delay exceeded the GPU thread limit time, the CSFPM algorithm stopped and jumped out of the GPU computing. By contrast, the APFMS went on go accelerating computation until finished. Therefore, the APFMS was proven to be more suitable with better performance.

Conclusions

Recently, with GPU providing extremely high parallelism and high bandwidth in memory transfer, its hybrid architectures are starting to be used for data mining. However, it is not easy to parallelize existing algorithms to achieve good performance on these hybrid architectures. Therefore, it is necessary to examine to what extent traditionally CPU-based data mining problems can be mapped to the GPU architecture.

In this paper, the Accelerating Parallel Frequent Itemset Mining on Graphics Processors with Sorting (APFMS) algorithm is proposed in order to improve the performance of a CSFPM.APFMS algorithm based on the advantages of CSFPM and MATI. The sorting of the 1-frequent item sets from the dataset after constructing the TID table is used in order to cut down computing time and the time complexity of GPU computing. The experiment results indicated that when the dataset was T10I4D100KN100K, with a threshold of 0.1%, the implementation had a 300% speed up compared the CSFPM, and a better load balancing performance was achieved with the increase of transaction numbers.

Future work on the research includes utilizing different types of GPU for better performance. As a result, in order to achieve heterogeneity in the GPU architecture, the different performance allocation will be considered with different candidate itemsets with different types of GPU.

Fig. 1 .Fig. 2 .

 12 Fig. 1. TID value and TID index tables

Fig. 7 .Fig. 8 .Fig. 9 .

 789 Fig. 7. Runtime with different number of GPU threads

Table 2 .

 2 Computing the candidate number of repetitions per item

	Item	Time
	AB	2
	AC	1
	BC	1

Table 3 .

 3 Hardware and software configurations

	Items	Description
	CPU	Intel Core i7-3960X 3.3GHz
	Memory	16G DDR3 memory
	GPU	NVidia GTX 580 1536MB GDDR5
	OS	Microsoft Windows 7
	Compiler	Microsoft Visual C++ 2010
	SDK	OpenCL 1.1

This paper is partial supported by the National Science Council of Taiwan, under grant number NSC 100-2632-E-216-001-MY3.