Hybridization of population-based ant colony optimization via data mining

Abstract

We propose a hybrid application of Population Based Ant Colony Optimization that uses a data mining procedure to wisely initialize the pheromone entries. Hybridization of metaheuristics with data mining techniques has been studied by several researchers in recent years. In this line of research, frequent patterns in a number of initial high-quality solutions are extracted to guide the subsequent iterations of an algorithm, which results in an improvement in solution quality and computational time. Our proposal possesses certain differences from and contributions to existing literature. Instead of one single run that incorporates both the main metaheuristic and the data mining module inside, we propose to carry out independent runs and collect elite sets over these trials. Another contribution is the way we use the knowledge gained from the application of the data mining module. The extracted knowledge is used to initialize the memory model in the algorithm rather than to construct new initial solutions. One additional contribution is the use of a path mining algorithm (a specific sequence mining algorithm) rather than Apriori-like association mining algorithms. Computational experiments, conducted both on symmetric Travelling Salesman Problem and symmetric/asymmetric Quadratic Assignment Problem instances, showed that our proposal produces significantly better results, and is more robust than pure applications of population-based ant colony optimization.

Keywords

Data Mining population-based ant colony optimization hybrid metaheuristics travelling salesman problem quadratic assignment problem sequence mining

1. Introduction

Metaheuristics have found a broad application area in achieving fast and acceptable solutions of combinatorial optimization problems over the past decades. Ant Colony Optimization (ACO) [6, 7] is one of the most popular and largely applied technique that is inspired by food searching behavior of real ants. A colony of artificial ants work independently, but share their knowledge of good quality solution characteristics to achieve high quality solutions in an iterative manner. In every iteration, each of several ants stochastically constructs a feasible solution based on pheromone (trail ants left behind) information and problem specific heuristic information. This solution construction process is generally same among ACO variants. Different ACO applications vary in the way they update the pheromone matrix at the end of an iteration or throughout an iteration. Reader is referred to Dorigo and Stutzle [8] for a broad review of different pheromone update approaches in ACO applications.

Population-based ACO (PACO) [11] carries out pheromone update only if an update occurs in a so-called solution archive which is a population of solutions kept in fixed size while the algorithm runs. Whenever a new solution is appended to the archive, one of the present solutions is chosen to leave the archive according to the update strategy used. The newly added solution adds pheromone, and the leaving solution evaporates the formerly added pheromone of its own. This pheromone update procedure makes the algorithm run much faster than the traditional ACO algorithms. PACO is successfully applied to various optimization problems [3, 4, 13, 23]. Its pure [11] and hybrid [22] Travelling Salesman Problem (TSP) applications also shown to be promising. Furthermore, the algorithm parameters were analyzed in detail when applied to TSP and Quadratic Assignment Problem (QAP) [14, 13] since PACO parameter settings and algorithm behavior are strongly problem dependent.

Metaheuristic applications have been shown to perform much better when they are hybridized with some other heuristics or techniques [2]. Applying local search to PACO results, for example, is a common convention, which combines the strength of PACO in exploiting promising areas in the search space with the strength of local search in exploring a certain promising area. There are innumerable hybrid applications in the literature in every type of combinatorial optimization problem, that make use of two or more metaheuristics (or metaheuristics-heuristics) in conjunction with each other with the hope to create a balance between intensification and diversification aspects of a search process. Hybridization of metaheuristics with data mining (DM), however, is a more recent, and less studied approach in searching for quick and acceptable solutions to combinatorial optimization problems. In this line of research, the main aim is to analyze a set of good quality solutions -collected while the metaheuristic algorithm runs- in order to extract valuable knowledge about the characteristics of high quality areas in solution space and use this knowledge to guide the search algorithm through the promising regions of the solution space. This approach is used to hybridize several metaheuristics and applied to a number of research problems with favorable results in terms of solution quality and computational time.

In this study, we propose a hybrid version of PACO that incorporates a DM module to guide the search process. A number of initial independent PACO trials were carried out, during which an elite set of good quality solutions have been collected. Using DM techniques, frequent patterns in these solutions have been extracted to guide a number of following independent trials. We show that the proposal here produces significantly better results, on average, than pure PACO trials when applied both to several symmetric TSP instances from TSPLIB and to symmetric/asymmetric QAP instances from QAPLIB.

1.1 Related work

Ribeiro et al. [17, 16] were the first to propose a hybrid application of GRASP with data mining (DM-GRASP), where, after a certain number of GRASP iterations, they extract patterns from an elite set of solutions to guide the succeeding GRASP iterations. They worked on a Set Packing Problem (SPP) as a case study. A feasible solution to a SPP is represented as a set of items to be included in a packing. A set that have a maximum total cost of items without violating any given restrictions (constraints that define which items cannot appear together in a packing) defines an optimal solution. GRASP iteratively constructs a solution (construction phase) using a greedy function, and applies local search to this initial solution to find a local optimum. Many GRASP iterations are carried out to find a good sub-optimal solution. They used Apriori-like algorithms to mine frequent itemsets (patterns or subset of items) that appear in a significant number of good-quality GRASP-solutions. They carried out more GRASP iterations, later again, where they used these frequent patterns as part of the construction phase of each GRASP iteration. This way, they forced the solutions produced by the construction phase to include some pattern among the frequent patterns. DM-GRASP is later applied to Maximum Diversity Problem [20], Server Replication for Reliable Multicast Problem [19], and the $p$ -Median problem [15] with successful results. Barbalho et al. [1] incorporated a path relinking (PR) strategy to DM-GRASP to solve the 2-path network design problem. They collected the elite set over GRASP-PR iterations rather than the general GRASP. That is, they used GRASP-PR as the main metaheuristic, while the incorporation of the DM approach is the same as the previous research.

Other than GRASP, some other metaheuristics were also hybridized with Martins et al. [12] applied DM procedure to a state-of-the-art hybrid heuristic-which combines ideas from multi-start local search, path relinking and tour merging – for the classical $p$ -median problem, and managed to reach better quality solutions, in average, within much lower (28%) computational time. The underlying mechanism of the DM-hybrid approach in their study was again similar. They let the mined frequent patterns to appear in newly constructed solutions upon which they applied local search, and other parts of the hybrid heuristic proceeded. Santos et al. [18], on the other hand, applied the same approach to a genetic algorithm (GA) to solve a single-vehicle routing problem. They apply the DM routine to a set of best solutions they collect while the algorithm proceeds. This DM routine has been called multiple times as long as the elite set changes significantly, controlled by a parameter. Through DM implementation, they try to find frequent contiguous sequences which they later use in construction of new individuals by the crossover operation, aiming to accelerate the occurrence of good-quality solutions in GA population. The crossover operator they use, incorporates both edge frequencies in parent solutions and heuristic criterion. However, when they call the DM routine, they refer to DM output, instead of any parent solutions, for the frequency element in the crossover. Although the solution of a single vehicle routing problem is an ordered set of cities, Santos et al. [18] preferred to apply an Apriori-like algorithm which would rather detect the frequent itemsets where the order of items would not be taken into account though. They justified their implementation of this type of algorithm stating that the database they deal with is fairly smaller than the common DM databases and that they focus only on contiguous sequences rather than solution items ordered apart from each other as in sequence pattern mining problems. This implies that they referred to the elite set and applied a post-processing on the DM output to find the frequent contiguous sequences.

Guerine et al. [9] studied one-commodity pickup-and-delivery TSP, and enabled a direct implementation of Frequent Itemset Mining (FIM) algorithms to mine solutions which are defined as sequence of elements where the order of elements is important. Since FIM algorithms are not suitable for mining solutions defined as ordered items, they use a solution representation where each successive item pair is defined as a new single item, thus re-representing the same solution as a set of unordered items. They also proposed [10] later a multi-DM scheme for the same problem case, where they called DM routine multiple times throughout the running process of the GRASP/VND algorithm.

All the above-mentioned research incorporate DM procedure into the search process mainly as follows. The main algorithm, either GRASP, GA or some other, starts to process and carries out some number of iterations, visiting many different areas in the solution space. During this first running phase of the algorithm, an elite set of relatively good quality solutions are collected. This elite set is analyzed using DM techniques to extract knowledge about the characteristics of superior solutions. These characteristics are in form of patterns that are sets of items representing an incomplete solution. New complete solutions, then, are constructed using both these patterns and the same construction procedure as the main algorithm uses. These new complete solutions act either as initial solutions – in GRASP – or new individuals – in GA – from which the main algorithm continues to process. This way the search process is facilitated and guided through promising regions in the search space.

Our study possesses some differences from the existing research about hybridization of metaheuristics using DM techniques. First, the knowledge gained from applying DM is used to initialize the memory model (pheromone matrix) in PACO rather than to construct new solutions. Reflecting the knowledge on hand into a memory model enables the DM hybridization approach to be applied to a range of other similar metaheuristic techniques. Second, instead of one single run that incorporates both the main metaheuristic and the DM module inside, we propose to carry out independent trials and collect elite sets over these trials. Independent trials of PACO enable the search process to scan a wide range of areas in the solution space, and a subsequent knowledge extraction by DM uncovers the characteristics of the promising regions over those previously visited areas. Lastly, the solution sequences are mined directly using a path mining algorithm, ASIPATH [5], rather than Apriori-like association mining algorithms used up to date in all existing research in this topic.

Another contribution of this work is the idea of knowledge-based pheromone initialization prior to performing a PACO trial. Pheromone initialization in PACO studied only – to our knowledge – by Shi et al. [21]. In their probability initialization approach, as they call it, they initialize the pheromone values based both on how many of the archive solutions include the transition from city $i$ to city $j$ , and on problem-specific knowledge. We propose a fundamentally different approach here by initializing pheromone trails using the knowledge extracted from an elite set of solutions.

1.2 Organization of the paper

The rest of the paper is organized as follows. We describe PACO algorithm in Section 1.1. Our proposal of hybridizing PACO with DM is introduced and detailed in Section 2.2. Section 3.1 includes a representation and discussion of our computational experiments. Concluding remarks are given in Section 4.

PACO()

Initialization $\tau\leftarrow\frac{1}{n-1}$ $\eta_{ij}=\frac{1}{d_{ij}}\hskip 19.916929pt(i\neq j)$ $P\leftarrow\emptyset$ $n\leftarrow\textit{number of cities}$ time limit not exceeded $f(\textit{sol}^{*})\leftarrow\infty$ Tour Construction $i\leftarrow 1$ untilnumber of ants $\textit{sol}\leftarrow\textit{Tour\_Construction}()$ Iteration-Best Solution $f(\textit{sol})<f(\textit{sol}^{*})$ $\textit{sol}^{*}\leftarrow\textit{sol}$ Pheromone Update&Archieve Update $\textit{iter}<K+1$ $P\leftarrow P\cup{\textit{sol}^{*}}$ $\tau_{ij}\leftarrow\tau_{ij}+\Delta\cdot\frac{1-w_{e}}{K-1}\hskip 14.226378pt(% i,j)\in\textit{sol}^{*}(y,y+1)|\forall y\in(1,2,\ldots,n)$ $\textit{iter}=K$ $\textit{elitist\_sol}\leftarrow\arg\min{f(P_{i})|i\in(1,2,\ldots,K)}$ $\tau_{ij}\leftarrow\tau_{ij}-\Delta\cdot\frac{1-w_{e}}{K-1}+w_{e}\cdot\tau_{% \textit{max}}\hskip 14.226378pt(i,j)\in\textit{elitist\_sol}(y,y+1)|\forall y% \in(1,2,\ldots,n)$ $f(\textit{sol}^{*})<f(\textit{elitist\_sol})$ $\tau_{ij}\leftarrow\tau_{ij}-w_{e}\cdot\tau_{\textit{max}}\hskip 14.226378pt(i% ,j)\in\textit{elitist\_sol}(y,y+1)|\forall y\in(1,2,\ldots,n)$ $\tau_{ij}\leftarrow\tau_{ij}+w_{e}\cdot\tau_{\textit{max}}\hskip 14.226378pt(i% ,j)\in\textit{sol}^{*}(y,y+1)|\forall y\in(1,2,\ldots,n)$ $P\leftarrow\textit{P-elitist\_sol}$ $P\leftarrow P\cup{\textit{sol}^{*}}$ $\textit{elitist\_sol}\leftarrow\textit{sol}^{*}$ $\tau_{ij}\leftarrow\tau_{ij}-\Delta\cdot\frac{1-w_{e}}{K-1}\hskip 14.226378pt(% i,j)\in P_{\textit{oldest}}(y,y+1)|\forall y\in(1,2,\ldots,n)$ $\tau_{ij}\leftarrow\tau_{ij}+\Delta\cdot\frac{1-w_{e}}{K-1}\hskip 14.226378pt(% i,j)\in\textit{sol}^{*}(y,y+1)|\forall y\in(1,2,\ldots,n)$ $P\leftarrow P-P_{\textit{oldest}}$ $P\leftarrow P\cup{\textit{sol}^{*}}$ elitist_sol PACO for TSP

2. Population based ant colony optimization

PACO is shown to perform better than the numerous ACO algorithms [11, 21, 23]. In contrast to the other ACO algorithms, it stores a population of solutions. Pheromone update is based on an update in this population. Here, we will describe PACO procedure specifically for the TSP and QAP. An overall representation of PACO algorithm for the TSP is given in Algorithm 1.2. Since for the QAP the main PACO engine is the same as in TSP, with slight differences in definitions as we detail in the following, we do not include a separate algorithmic representation of the algorithms for the QAP.

2.1 Solution construction

2.1.1 TSP

In each iteration, each of a predefined number of ants constructs a complete TSP tour, a feasible solution, as given in “Tour Construction” part in Algorithm 1.2. An example of a TSP tour for a $5-city$ problem is $1-4-5-2-3-1$ . From a current city $i$ an ant stochastically determines the next city $j$ , among the unvisited cities, based on pheromone information $\tau_{ij}$ and heuristic information $\eta_{ij}$ . It uses the quality function $F_{ij}$ in (1) to decide on the next city.

$\displaystyle F_{ij}=\tau_{ij}^{\alpha}\eta_{ij}^{\beta}$ (1)

where $\alpha,\beta>0$ are parameters. All entries of the pheromone matrix $\tau$ is initialized as in Eq. (2).

$\displaystyle\tau_{0}=\frac{1}{n-1}$ (2)

where $n$ is the number of cities. Pheromone matrix is a memory model that imitates the trails the ants left behind to mark short distances to food sources. It represents how it is favorable to traverse the edge between cities $i$ and $j$ , based on the previous good quality solutions. The heuristic information is a constant throughout the trial and taken as in Eq. (3).

$\displaystyle\eta_{ij}=\frac{1}{d_{ij}}\hskip 28.452756pti\neq j$ (3)

where $d_{ij}$ is the distance between city $i$ and city $j$ . The initialization of the pheromone matrix and the heuristic information can be observed in “Initialization” part in Algorithm 1.2. In a probabilistic manner, the ant either selects the next city $j$ that maximizes the quality function or according to the probability distribution in Eq. (4).

$\displaystyle P(c_{k+1}=j\mid c_{k}=i)=\frac{F_{ij}}{\sum_{y\in U}{F_{iy}}}$ (4)

where $c_{k}$ is the current city where the ant stands on, and $U$ is the set of unvisited cities.

2.1.2 QAP

The main solution construction mechanism is the same as in TSP, however a feasible solution is a permutation of locations in QAP. One can choose to represent a QAP solution as a permutation of facilities as well. Based on our permutation of locations representation, for a $5-facility$ ( $5-location$ ) QAP, a sample solution would be $3-1-2-5-4$ , and it represents that facility 1 is assigned to location 3, facility 2 to location 1, facility 3 to location 2, and so on. While an ant constructs a solution, it randomly chooses a facility $i$ from the remaining facilities, and stochastically assigns it to a location $j$ , among the remaining locations, using again the quality function given in Eq. (1). However, pheromone trails, $\tau_{ij}$ , are defined as the desirability of assigning facility $i$ to location $j$ , and they are initialized as in Eq. (5)

$\displaystyle\tau_{0}=\frac{1}{n}$ (5)

We refer to Stützle and Dorigo [24] for the heuristic information which is based on flow and distance potentials of facilities and locations, respectively. The heuristic desirability of assigning facility $i$ to location $j$ is given by Eq. (6).

$\displaystyle\eta_{ij}=\frac{1}{e_{ij}}$ (6)

where $e_{ij}=f_{i}\cdot d_{j}$ . $f_{i}$ is the flow potential of facility $i$ and is the sum of the flows from facility $i$ to all other facilities, and $d_{j}$ is the distance potential of location $j$ and is the sum of the distances from location $j$ to all other locations. The heuristic information remains static within a trial and across different trials. In a probabilistic manner, the ant assigns the facility $i$ either to location $j$ which maximizes the quality function in Eq. (1) or according to the probability distribution in Eq. (7).

$\displaystyle p_{ij}=\frac{F_{ij}}{\sum_{y\in U}{F_{iy}}}$ (7)

where $U$ is the set of unassigned locations.

2.2 Solution archive

A predefined number $K$ of solutions are stored in PACO, named as solution archive $P$ , which are referred to while carrying out an update in pheromone matrix. The archive is empty at the beginning. The best solution of all ants, the iteration-best solution – as given in “Iteration-best solution” part in Algorithm 1.2, is appended to the archive at the end of each iteration, where, after $K$ number of iterations the archive contains $K$ number of solutions. The archive is kept at fixed size. Thus, for the iterations $K+1$ and on, a solution should leave the archive for a new one to be added.

There are three strategies to update the solution archive. Age-based strategy makes the oldest solution exit the archive. Quality-based strategy accepts the iteration-best solution only if it is better than the worst-quality solution of the archive. Elitist-based strategy is similar to age-based strategy except that it always keeps the global best solution, the best solution found up to that time during the whole trial, in the archive. New solution replaces the globally best solution if it has a higher quality. Otherwise, new solution is appended to the archive and the oldest solution of the archive leaves.

2.3 Pheromone update

Pheromone update in pheromone matrix is carried out in PACO based on the solutions that leave or enter the archive. Here, we will give the pheromone update procedure only for the elitist-based strategy since it is the one that concerns in this study. Whenever a solution replaces the globally best solution, an elitist-update is carried out. Accordingly, new elitist solution adds $w_{e}\times\tau_{max}$ amount of pheromone to entry $(i,j)$ of the pheromone matrix if it includes the coupling ${ij}$ (the edge from city $i$ to city $j$ in TSP or the assignment of facility $i$ to location $j$ in QAP) as part of its solution. The pheromone previously deposited by the former elitist solution is evaporated as in Eq. (8).

$\displaystyle\tau_{kl}=\tau_{kl}-w_{e}\times\tau_{\textit{max}}\ \ (k,l)\in% \arg\min{f(P_{i})|i\in(1,2,\ldots,K)}$ (8)

where $w_{e}$ and $\tau_{\textit{max}}$ are parameters. When the new solution is not of better quality than the globally best solution, then it replaces the oldest solution and adds $\Delta\times\frac{1-w_{e}}{K-1}$ amount of pheromone. And the leaving oldest solution evaporates same amount of pheromone, as given in Eq. (9).

$\displaystyle\tau_{pr}=\tau_{pr}-\Delta\times\frac{1-w_{e}}{K-1}(p,r)\in P_{% \textit{oldest}}(y,y+1)|\forall y\in(1,2,\ldots,n)\text{in TSP}\text{if % facility }p\ \text{is assigned to location }r\text{ in }P_{\textit{oldest}}% \text{in QAP}$ (9)

where $\Delta={(\tau_{\textit{max}}-\tau_{0})}/{K}$ . The pheromone and archive update procedures detailed above are given in “Pheromone update and Archive update” part of Algorithm 1.2.

3. Hybrid PACO-DM-PACO approach

In this section, we describe in detail our hybrid PACO-DM-PACO proposal. An overall representation of PACO-DM-PACO approach for the TSP problem is given in Algorithm 2. For the QAP, the algorithmic skeleton of the PACO-DM-PACO is the same, however there is a significant difference in how we extract knowledge of frequent couples, which we detail in the following subsection.

PACO-DM-PACO procedure consists of two main phases. In the first phase, we propose to run $N$ number of independent PACO trials. While the algorithm explores different regions of the solution space in these trials, we collect eSize number of elite solutions in each trial. At the end of $N$ runs, we have a resulting elite set of size $N\times\textit{eSize}$ . This elite set is mined for frequent consecutive city patterns in TSP or assignment patterns in QAP. The pheromone matrix is initialized using this knowledge extracted from the elite set of solutions. A following $M$ number of independent PACO trials are carried out. The average solution quality of this second PACO-trials phase is compared with $N+M$ amount of independent pure PACO trials.

In other words, instead of carrying out $N+M$ independent PACO trials, we propose to perform $N$ independent PACO trials and to call DM routine to initialize the pheromone matrix for a second subsequent $M$ number of runs. Performing independent trials let the algorithm explore different regions in the solution space. A subsequent DM algorithm extracts knowledge about the characteristics of favorable regions and initialize the pheromone matrix to guide the algorithm to exploit that promising places in the following $M$ -runs phase.

3.1 Data mining procedure-ASIPATH

The elite set of solutions obtained from the first phase is analyzed using ASIPATH path mining algorithm [5]. ASIPATH is a special case of SPADE algorithm introduced in [26]. The main advantage of SPADE algorithm and its variants is to prune frequent itemset search space by discarding infrequent ones efficiently in a parallel search manner. In contrast to frequent itemset mining algorithms, ASIPATH can be used directly to mine solutions that are represented as sequences, where the order of items in the solution is important.

Suppose tour is a permutation representation of a given feasible tour for a TSP instance with $n$ cities. Let $\textit{tour}_{k}$ represent the $k^{th}$ city in the tour. If $i=\textit{tour}_{k}$ and $j=\textit{tour}_{k+1}$ , then we say $(i,j)$ is a consecutive city pattern in the solution. We refer to these 2-city patterns as city pairs. Similarly, if $i=\textit{tour}_{k}$ , $j=\textit{tour}_{k+1}$ and $h=\textit{tour}_{k+2}$ , then $(i,j,h)$ is a 3-city pattern. ASIPATH is able to mine a set of sequences and report frequencies of patterns composed of up to 10 consecutive cities. A support parameter (abbreviated as sup) is supplied to the algorithm, which defines the ratio of sequences in the set that should include a certain pattern for the pattern to be regarded as frequent.

Consider, for example, a TSP instance with 4 cities. All possible TSP tours -that visits each city once and returns to the starting point- are given in permutation representation in Table 1. We started each representation from city 1 arbitrarily. Suppose we collect an elite set consisting of 4 solutions. Then, we choose the first four tours in Table 1, since their costs are the lowest. Suppose, also, we have a sup parameter of 0.50, which means that at least 2 of the tours in the elite set should include a city pair for it to be considered as frequent. When we apply ASIPATH to the elite set of this 4-city sample problem, we obtain $3-2$ , $2-4$ , $4-1$ , $4-3$ , and $1-2$ as frequent city pairs, each having a frequency of 2. In this study, we consider only 2-city patterns (city pairs) without utilization of longer subsequences.

Table 1
Permutation representation of tours for a 4-city TSP

Cost (tour length)	Tours
15	1	3	2	4	1
17	1	2	4	3	1
20	1	4	3	2	1
21	1	2	3	4	1
23	1	3	4	2	1
28	1	4	2	3	1

Table 2

Permutation of locations representation for a 5-facility QAP

Facility $i$	1	2	3	4	5
Assignment 1	3	4	2	1	5
Assignment 2	1	4	2	5	3
Assignment 3	2	1	4	5	3
Assignment 4	5	4	2	1	3
Assignment 5	1	4	2	3	5
Assignment 6	1	5	3	4	2

For the QAP, supppose $\psi$ is a permutation of locations that represents a feasible QAP assignment. Let $\psi(i)$ represents the location where facility $i$ is assigned to. Thus, a given sample solution of $3-4-2-1-5$ for a 5-facility QAP shows that $\psi(1)=$ 3, $\psi(2)=$ 4, $\psi(3)=$ 2, $\psi(4)=$ 1 and $\psi(5)=$ 5. If $\psi(i)=j$ and $\psi(i+1)=k$ for a certain $i$ over a set of solutions, then we say $[\psi(i)=j;\psi(i+1)=k]$ is an assignment pair. Consider the set of solutions given in Table 2 as an example of an elite set of solutions to apply the DM routine to find the frequent assignment pairs. We can observe that the assignment pair $[\psi(2)=4;\psi(3)=2]$ has a frequency of 4. Notice that we do not take into account the $4-2$ pair in Assignment 6 since it represents a different assignment pair, $[\psi(4)=4;\psi(5)=2]$ . We should note that ASIPATH does not differentiate between the pairs $[\psi(2)=4;\psi(3)=2]$ and $[\psi(4)=4;\psi(5)=2]$ , and continues to add up the frequencies as long as $4-2$ appears as part of a solution. Thus, we applied matrix indexing to find the assignment frequencies properly.

PACO-DM-PACO() $\textit{elite\_set}\leftarrow\emptyset$ $i=1$ until $N$ $\textit{iterEliteSet}\leftarrow\emptyset$ PACO(){

Initialization() Tour_Construction() Update_IterEliteSet(eSize) Iteration-Best_solution() Pheromone_update&Archieve_update() }

$\textit{eliteSet}\leftarrow\textit{eliteSet}\cup\textit{iterEliteSet}$ $\textit{frequent\_couples}\leftarrow\textit{DM(sup,eliteSet)}$ $\textit{elitistSolns}\leftarrow\emptyset$ $i=1$ until $M$ $\textit{elitist\_sol}\leftarrow\emptyset$ PACO(){

Initialization $\tau_{ij}\leftarrow\frac{1}{n-1}$ $\tau_{ij}\leftarrow\tau_{ij}+\Delta\cdot\frac{1-w_{e}}{K-1}\cdot\frac{fr_{ij}}% {fr_{min}}\hskip 14.226378pt(i,j)\in\textit{frequent\_couples}$ $\eta_{ij}\leftarrow\frac{1}{d_{ij}}\hskip 14.226378pt(i\neq j)$ $P\leftarrow\emptyset$ $n\leftarrow\textit{number of cities}$ Tour_Construction() Iteration-Best_solution() $\textit{elitist\_sol}\leftarrow\textit{Pheromone\_update\&Archieve\_update()}$ }

$\textit{elitistSolns}\leftarrow\textit{elitistSolns}\cup\textit{elitist\_sol}$ elitistSolns PACO-DM-PACO Proposal for TSP

When $n$ is very small, one can easily evaluate all the permutations for the optimal cost. Notice that there will be too many permutations for even a moderate size TSP or QAP to be evaluated for the optimality search. Our approach aims to find promising solution fragments via finding the frequent city or assignment pairs.

3.2 Pheromone initialization

Once ASIPATH outputs the frequencies of the city or assignment pairs that meet sup criterion, these frequencies are used to initialize the pheromone matrix for following trials, as shown in “Initialization” part in Algorithm 2. Pheromone is added to entries of the pheromone matrix corresponding to frequent city or assignment pairs. Higher amount of pheromone is added to pairs with higher frequency, as shown in Eq. (10).

$\displaystyle\tau_{ij}=\tau_{ij}+\Delta\cdot\frac{1-w_{e}}{K-1}\cdot\frac{fr_{% ij}}{fr_{min}}\ \ (i,j)\in A$ (10)

where $A$ is the set of frequent pairs, $fr_{ij}$ is the frequency of the pair $(i,j)$ , and $fr_{\textit{min}}$ is the minimum frequency of the pair that meet the sup criterion.

4. Computational experiments

In this section, we represent the computational study to compare performances of PACO and PACO-DM-PACO trials. We used 33 symmetric TSP and 33 symmetric/asymmetric QAP instances from the well-known TSP and QAP repositories available at https://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ and at http://anjos.mgi.polymtl.ca/qaplib//inst.html, respectively. The selected 24 small, 6 medium and 3 large TSP instances are shown respectively in yellow, orange and red colors in Table 3. For the QAP, we have selected 8 instances from each of 4 instance classes [27] and 1 more instance from the fourth class. The instances are shown in Table 4 in yellow, green, blue and red for the classes 1 to 4, respectively. QAP instance classes have been defined broadly as follows: Class I includes unstructured and randomly generated instances, Class II instances have their distance matrix based on the Manhattan distance on a grid, Class III is composed of real-life instances, and lastly Class IV includes randomly generated real-life like instances. A detailed explanation of the QAPLIB instance classifications can be found in [27] and a thorough structural and search space analysis of these instance classes in [25].

PACO-specific parameters have been analyzed in detail for the TSP and the QAP in the literature [11, 14, 13, 22]. Thus, we did not find it necessary to repeat a detailed parameter analysis here, hence we referred to several studies to determine the constant parameters of PACO. It is common to use $\textit{number of ants}=$ 10 and $\alpha=$ 1 since it results in satisfactory performance. $\beta$ is 5 for the TSP [11], and 2 for the QAP [13]. We refer to [11] for the values of $w_{e}$ and $q_{0}$ (the probability parameter used in tour construction). Specifically the values are $w_{e}=$ 0.5 both for TSP and QAP, while $q_{0}$ takes the values 0.2, 0.5, and 0.9 for small, medium and large instances of TSP and 0.9 for all QAP instances. The archive size, $K$ , is 8 for TSP [22] and 5 for QAP [13]. $\tau_{\textit{max}}$ is 3 for TSP and 100 for QAP [13]. We used the elitist-based strategy in archive and pheromone updates both for TSP and QAP [13]. All these PACO-specific parameters are the same as for both PACO and PACO-DM-PACO trials.

In the first PACO phase of our PACO-DM-PACO proposal, we run 10 independent purely PACO trials. We run each trial of the small, medium and large TSP instances respectively for 100, 1000 and 2000 seconds, while for QAP we stop after 1000 seconds in any instance. We collected an elite set of size 100 in each of these trials, making a total of 1000 elite solutions collected in this first phase. sup parameter in DM module is taken for TSP as low as 0.10 wherever memory restrictions allow. Otherwise, it is taken as 0.20 or 0.25. For QAP, sup is a constant over all instances and has the value 0.05. A high sup parameter would result in low number of frequent city or assignment pairs, particularly in large instances. However, here we would prefer to leave a trace in the memory even if the specific pair occurs in even 100 or 50 of 1000 elite solutions. That way, the algorithm will favor to traverse that edge or make that assignment rather than one that does not appear even in an elite set with such a low sup parameter. During pheromone initialization, we used all pairs that meet the sup parameter. We run 10 independent

Table 3
Comparison of PACO and PACO-DM-PACO trials for TSP

Instance	Optimum	PACO					PACO-DM-PACO
		Best cost	Percentage deviation best	Average cost	Percentage deviation average	Percentage deviation std. dev.	Best cost	Percentage deviation best	Average cost	Percentage deviation average	Percentage deviation std. dev.
kroA100	21282	21451	0.7941	21744	2.1716	1.2587	21330	0.2255	21446	0.7692	0.8498
kroC100	20749	20749	0.0000	20906	0.7545	1.0033	20749	0	20749	0.0000	0.0000
kroD100	21294	21410	0.5448	21642	1.6357	0.9125	21330	0.1691	21496	0.9491	1.1040
eil101	629	635	0.9539	652.1	3.6725	1.6513	642	2.0668	652.7	3.7679	1.8128
gr120	6942	7001	0.8499	7248.4	4.4144	1.9337	6997	0.7923	7168.8	3.2671	1.6890
bier127	118282	119325	0.8818	121200	2.4629	1.3552	119386	0.9334	120070	1.5090	0.7781
ch130	6110	6146	0.5892	6278.9	2.7651	1.2049	6204	1.5385	6261.7	2.4828	0.7483
gr137	69853	70588	1.0522	72211	3.3757	2.1881	70339	0.6957	70895	1.4911	0.8090
ch150	6528	6576	0.7353	6642.3	1.7502	0.6464	6547	0.2911	6607.9	1.2240	0.7915
kroB150	26130	26443	1.1979	27026	3.4307	2.0915	26300	0.6506	26753	2.3842	1.9384
si175	21407	21952	2.5459	22197	3.6887	0.8914	21666	1.2099	21780	1.7438	0.4118
d198	15780	16446	4.2205	16863	6.8606	1.8183	16258	3.0292	16619	5.3162	1.4647
kroA200	29368	29635	0.9092	30208	2.8599	0.9975	29557	0.6436	29940	1.9477	1.0488
gr202	40160	41682	3.7898	42907	6.8394	1.9682	41285	2.8013	42174	5.0152	2.6472
pr226	80369	81234	1.0763	83691	4.1333	1.8376	81050	0.8473	81667	1.6153	0.4776
gr229	134602	136153	1.1523	140160	4.1311	1.8798	135607	0.7466	138565	2.9442	1.4155
gil262	2378	2441	2.6493	2504.9	5.3364	1.6307	2415	1.5559	2457.8	3.3558	1.3471
pr264	49135	50349	2.4707	52865	7.5905	2.2157	50503	2.7842	52129	6.0924	1.5868
a280	2579	2665	3.3346	2732.9	5.9694	2.0904	2604	0.9694	2678.5	3.8581	2.3213
lin318	42029	44053	4.8157	44938	6.9207	2.1678	43390	3.2382	44294	5.3882	1.5749
fl417	11861	12494	5.3368	12768	7.6456	1.6721	12211	2.9508	12359	4.1986	0.5601
gr431	171414	186688	8.9106	192650	12.3897	2.4310	184632	7.7112	188750	10.1115	1.8523
pcb442	50778	55125	8.5608	57415	13.0712	2.6688	54136	6.6131	55444	9.1896	1.6043
d493	35002	39260	12.1650	40582	15.9419	2.1798	39041	11.5393	39875	13.9223	1.2329
ali535	202339	216985	7.2383	223880	10.6484	2.2338	212877	5.2081	220810	9.1299	2.2954
rat575	6773	7250	7.0427	7521.7	11.0542	2.5044	7252	7.0722	7428.8	9.6826	1.8123
p654	34643	36801	6.2293	37771	9.0290	1.5242	37061	6.9798	37343	7.7941	0.6864
d657	48912	53338	9.0489	56186	14.8717	2.5361	53594	9.5723	54801	12.0390	1.9112
gr666	294358	321922	9.3641	333040	13.1408	2.1006	317701	7.9301	326930	11.0646	2.0287
u724	41910	46081	9.9523	47727	13.8793	1.9718	45158	7.7499	45944	9.6249	1.4650
pr1002	259045	289499	11.7563	297507	14.8476	1.5398	287861	11.1239	293800	13.4179	1.5717
u1817	57201	65768	14.9770	66947	17.0387	1.8867	63823	11.5767	64751	13.1998	1.6200
pr2392	378032	446269	18.0506	456800	20.8375	1.7084	440228	16.4526	447211	18.2998	1.3966

Bold shows the better result. Bold red shows that the difference is statistically significant (Wilcoxon Rank Sum Test, $\alpha=$ 0.05).

Table 4

Comparison of PACO and PACO-DM-PACO trials for QAP

Instance	Optimum or BKS	Best cost	Percentage deviation best	Average cost	Percentage deviation average	Percentage deviation std. dev.	Best cost	Percentage deviation best	Average cost	Percentage deviation average	Percentage deviation std. dev.
		PACO					PACO-DM-PACO
rou20	725,522	739,010	1.86	754,128.50	3.94	1.40	733,040	1.04	749,385.00	3.29	1.20
tai20a	703,482	705,622	0.30	737,651.70	4.86	1.82	705,622	0.30	727,893.80	3.47	1.45
tai25a	1,167,256	1,196,556	2.51	1,222,050.00	4.69	1.20	1,200,246	2.83	1,225,322.60	4.97	1.14
tai30a	1,818,146	1,874,590	3.10	1,898,840.80	4.44	0.62	1,882,856	3.56	1,898,637.60	4.43	0.73
tai35a	2,422,002	2,509,332	3.61	2,536,587.00	4.73	0.64	2,520,982	4.09	2,541,495.40	4.93	0.64
tai40a	3,139,370	3,250,284	3.53	3,292,980.70	4.89	0.58	3,268,448	4.11	3,315,524.40	5.61	1.06
tai60a	7,205,962	7,599,978	5.47	7,638,017.20	6.00	0.40	7,633,880	5.94	7,656,940.20	6.26	0.20
tai80a	13,499,184	14,358,328	6.36	14,440,917.90	6.98	0.34	14,542,846	7.73	14,603,391.80	8.18	0.27
nug30	6,124	6,268	2.35	6,438.50	5.14	1.72	6,208	1.37	6,357.80	3.82	1.77
tho30	149,936	153,058	2.08	156,652.40	4.48	1.37	154,334	2.93	158,340.40	5.61	2.07
tho40	240,516	246,340	2.42	255,527.00	6.24	1.48	248,866	3.47	254,107.40	5.65	1.26
sko42	15,812	16,380	3.59	16,603.90	5.01	0.71	16,192	2.40	16,425.60	3.88	1.01
sko49	23,386	24,428	4.46	24,746.40	5.82	0.78	24,510	4.81	24,713.80	5.68	0.65
sko56	34,458	36,364	5.53	36,826.60	6.87	0.74	36,516	5.97	36,743.80	6.63	0.56
sko64	48,498	50,656	4.45	51,181.30	5.53	0.57	50,492	4.11	51,073.80	5.31	0.57
sko72	66,256	69,322	4.63	70,040.10	5.71	0.65	69,886	5.48	70,316.80	6.13	0.54
els19	17,212,548	17,351,492	0.81	20,439,299.30	18.75	14.12	17,436,428	1.30	21,568,013.20	25.30	13.45
chr25a	3,796	4,872	28.35	5,599.50	47.51	10.49	4,282	12.80	5,077.80	33.77	8.49
bur26a	5,426,670	5,431,640	0.09	5,440,181.30	0.25	0.13	5,431,255	0.08	5,435,440.50	0.16	0.06
bur26g	10,117,172	10,118,362	0.01	10,138,462.95	0.21	0.24	10,118,598	0.01	10,118,821.50	0.02	0.00
kra30a	88,900	93,290	4.94	95,445.50	7.36	1.44	92,940	4.54	94,603.00	6.42	1.27
kra30b	91,420	92,890	1.61	95,979.00	4.99	2.18	93,300	2.06	95,460.00	4.42	1.65
ste36a	9,526	10,296	8.08	10,914.70	14.58	4.09	10,180	6.87	10,660.40	11.91	2.85
ste36b	15,852	18,958	19.59	21,320.80	34.50	9.12	17,430	9.95	17,876.80	12.77	2.30
tai20b	122,455,319	123,009,513	0.45	133,011,047.25	8.62	10.54	123,002,461	0.45	123,744,626.00	1.05	0.52
tai25b	344,355,646	347,395,912	0.88	385,170,708.50	11.85	8.85	344,355,646	0.00	347,321,872.90	0.86	0.60
tai30b	637,117,113	639,982,634	0.45	719,309,973.80	12.90	6.57	640,822,124	0.58	687,886,827.20	7.97	5.34
tai35b	283,315,445	288,571,889	1.86	306,776,733.15	8.28	3.07	292,368,533	3.20	308,971,044.50	9.06	4.45
tai40b	637,250,948	641,063,258	0.60	681,429,684.00	6.93	3.36	642,012,072	0.75	687,732,643.60	7.92	3.21
tai50b	458,821,517	469,781,592	2.39	487,381,016.00	6.22	2.50	469,212,687	2.26	483,943,156.20	5.48	2.11
tai60b	608,215,054	620,014,921	1.94	658,219,087.05	8.22	3.33	620,108,135	1.96	638,829,041.40	5.03	2.46
tai80b	818,415,043	871,448,466	6.48	888,558,547.45	8.57	1.09	857,115,208	4.73	878,431,914.90	7.33	1.42
tai100b	1,185,996,137	1,270,462,119	7.12	1,295,019,992.65	9.19	1.31	1,331,957,849	12.31	1,358,886,486.40	14.58	2.02

Bold shows the better result. Bold red shows that the difference is statistically significant (Wilcoxon Rank Sum Test, $\alpha=$ 0.05).

PACO trials again, in the second phase, using the initialized pheromone matrix. The statistics for the last 10-trial phase is compared with 20 purely PACO trials where no DM module is applied.

The algorithms were implemented in MATLAB 9.3. All the runs were carried out in a computer with Intel Core i5, 2.40 GHz and 8 GB RAM, running under Windows 10 operating system.

The statistics for PACO and PACO-DM-PACO trials for TSP and QAP are given respectively in Tables 3 and 4. Best Cost is the best objective function value (tour length in TSP and total assignment cost in QAP) obtained over all trials. Percentage deviation – Best is the percentage deviation of the Best Cost solution from the optimum or Best Known Solution (BKS) value. Average Cost is the average of costs of all solutions over all trials. Percentage deviation – Average is the average of percentage deviations of all solutions from the optimum or BKS value. Percentage deviation – standard deviation is the standard deviation of the percentage deviations. The better result is shown in bold in the table. Bold red shows that the difference is statistically significant. Statistical significance of the results is explained in detail in the following subsection.

For the TSP, PACO-DM-PACO approach produces solutions with higher quality, in average, than PACO in 23 of 24 small instances, and in 100% of medium and large instances. The difference is statistically significant in 70% of the small instances, in 4 of the total 6 medium instances and in all 3 of the large instances with a 95% confidence (refer to next subsection). We can see from the table that the superiority of the average solution quality increases as instances get larger. This can be observed more clearly in Fig. 1 which is a plot of average cost values obtained in PACO and PACO-DM-PACO trials for each instance. Table 3 indicates, additionally, that the best tour length found in PACO-DM-PACO trials is lower (better) than that of PACO in 76% of all instances.

For the QAP, the performance of our proposal over pure PACO trials is showing a different behaviour among the four instance classes. We can observe that the performance is clearly worse in Class I instances. This is due to the search landscape of that specific class. These instances may not structurally resemble the optimum solution as they get closer to the optimum objective value [25]. In other words, a solution with a lower objective value may not have more locations of items in common with the optimum solution. This search space feature is in contrast with the main idea of our proposal, where we assume the better the solution quality the more similar the solution with the optimum. Classes II and IV, however, have the exact opposite characteristic of the search landscape [25], resulting in an improved solution quality with our PACO-DM-PACO proposal. Our approach produces higher quality results, in average, in 75% of Class II instances and 62.5% of Class IV instances, respectively. The statistical significance of the superiority of our proposal is higher in Class IV instances. PACO-DM-PACO has the highest performance in Class III instances. It produced better results, in average, in all these instances except one, and the difference is statistically significant in 5 of these 7 instances.

A lower standard deviation of the percentage deviations of the trials from the optimal solution indicates that an algorithm is more robust, it produces similar quality results in different trials. Robustness gives an idea about how predictable would the error be, and how much we can rely on the algorithm in a single trial. Tables 3 and 4 demonstrate that in 76% of both TSP and QAP instances the PACO algorithm with DM module produces more robust solutions. Also, we can observe that generally the proposed algorithm gets more robust as the problem size increases.

4.1 Statistical significance of the results

We use tests of statistical significance to determine whether the superiority of PACO-DM-PACO is statistically significant. We apply Non-parametric Wilcoxon Rank Sum Test to costs of each of 33 instances (a sample table for a TSP instance is given in Table 5) both in TSP and QAP experiments to determine whether the differences between the outputs of the two algorithms are statistically significant.

Figure 1.

Plot of average cost values in PACO and DM-PACO trials for each TSP instance.

Wilcoxon Rank Sum Test is used when one wants to determine whether two samples -not necessarily in equal size- come from the same population. This way, it is possible to understand whether the difference between the samples is statistically significant or it is due to random reasons.

The null and alternative hypothesis are constructed as follows:

$H_{0}$ : The two populations are equal (the results of two algorithms come from the same population) versus $H_{1}$ : The two populations are not equal

We used a 95% confidence level ( $\alpha=$ 0.05). For each of the instances given in Tables 3 and Table 4, the statistically significant results are shown in bold red.

Another statistical test we use is the non-parametric Wilcoxon Signed Rank test to determine whether PACO-DM-PACO produces better solutions than PACO. It is a test on paired samples that tests population median of the differences of results.

Then, the null hypothesis versus the alternative are as:

$H_{0}$ : The median difference is zero versus $H_{1}$ : The median difference is not zero

Comparing overall Average Cost results given in Table 3 using Wilcoxon Signed Rank test, we obtain a $p$ -value of 5.9124 $\times$ (10) ${}^{-7}$ . That is, if $H_{0}$ were true (the two samples are coming from the same population, and hence PACO-DM-PACO and PACO produces same quality results), then we would have such a low probability, as the $p$ -value indicates, to have such different Average Cost samples for the two algorithms. Thus, we strongly reject the null hypothesis and statistically conclude that PACO-DM-PACO produces better solutions than PACO for TSP. The corresponding $p$ -value for the QAP is 0.0736, which is higher than that of TSP experiment. However, with a 92% confidence, we can again reject the null hypothesis and reach the same conclusion.

Table 5

A representation of samples used in Wilcoxon Rank Sum test

Instance pcb442	PACO	PACO-DM-PACO
Trial 1	55125	54136
Trial 2	55581	54379
$\ldots$	$\ldots$	$\ldots$
Trial 10	57262	56908
$\ldots$	$\ldots$	$\ldots$
Trial 20	60201

5. Conclusion

Implementing DM techniques to extract frequent patterns from a set of good quality solutions and using these patterns to guide the search process is an emergent topic in hybridization of metaheuristics in recent years. In the present paper, we implemented a DM module after several independent PACO trials to predict the promising regions of the solution space and used this knowledge in subsequent PACO trials to further exploit these regions. The knowledge from DM module is used to initialize the pheromone entries instead of constructing new initial solutions. One more novelty in our proposal is the use of a path-mining algorithm (a special type of sequence mining algorithm) instead of frequent itemset mining algorithms in the DM process. Several symmetric TSP and symmetric/asymmetric QAP instances are used to compare PACO-DM-PACO trials with pure PACO trials. It is shown that the proposed approach leads to significantly better solution quality, in average. Additionally, the results obtained through integration of a DM module are shown to be more robust.

In the PACO side, the results here can be further improved, as a future study, by applying a local search procedure to solutions ants find in each iteration. A parallel implementation of the algorithm can be carried out as well.

In the DM side, DM module can be applied several times during the trials instead of the single application. Additionally, our approach can be incorporated into many other metaheuristics that use a memory model, and the resulting behavior can be analyzed.

References

Barbalho

Rosseti

Martins

S.L.

and Plastino

, A hybrid data mining grasp with path-relinking, Computers & Operations Research 40(12) (2013), 3159–3173.

Blum

and Roli

, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys (CSUR) 35(3) (2003), 268–308.

Cheng

Y.C.

Hartmann

Tsai

P.Y.

and Middendorf

, Population based ant colony optimization for reconstructing ecg signals, Evolutionary Intelligence 9(3) (2016), 55–66.

Clauß

Lotzmann

and Middendorf

, A population based aco algorithm for the combined tours tsp problem, In In Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS), 128–135. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), May 2016.

Demiriz

, Asipath: A simple path mining algorithm, In In Proceedings of the 16th International Conference on Parallel and Distributed Computing and Systems (PDCS 2004), (2004), 9.

Dorigo

, Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Electronica, Politecnico di Milano, (1992).

Dorigo

Maniezzo

and Colorni

, The ant system: Optimization by a colony of cooperating agents, IEEE Trans Systems, Man, and Cybernetics-Part B 26 (1996), 29–41.

Dorigo

and Stutzle

, Ant Colony Optimization, MIT Press, Cambridge, MA, (2004).

Guerine

Rosseti

and Plastino

, Extending the hybridization of metaheuristics with data mining to a broader domain, In In ICEIS, volume 1, April (2014), 395–406.

10.

Guerine

Rosseti

and Plastino

, Extending the hybridization of metaheuristics with data mining: Dealing with sequences, Intelligent Data Analysis 20(5) (2016), 1133–1156.

11.

Guntsch

and Middendorf

, A population based approach for aco, In S.C. et al., editor, EvoWorkshops 2002, volume 2279 of LNCS, Heidelberg, April (2002). Springer, 71–80.

12.

Martins

Vianna

G.M.

Rosseti

Martins

S.L.

and Plastino

, Making a state-of-the-art heuristic faster with data mining, Annals of Operations Research 263(1-2) (2018), 141–162.

13.

Oliveira

S.M.

Hussin

M.S.

Roli

Dorigo

and Stützle

, Analysis of the population-based ant colony optimization algorithm for the tsp and the qap, In In Evolutionary Computation (CEC), IEEE, June (2017), 1734–1741.

14.

Oliveira

S.M.

Hussin

M.S.

Stützle

Roli

and Dorigo

, A detailed analysis of the population-based ant colony optimization algorithm for the tsp and the qap, In In Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation, July (2011), 13–14.

15.

Plastino

Fonseca

E.R.

Fuchshuber

Martins

S.L.

Freitas

A.A.

and Luis

, A hybrid data mining metaheuristic for the p-median problem, In Proceedings of the SIAM International Conference on Data Mining, 2009, pp. 305–316.

16.

Ribeiro

M.H.

Plastino

and Martins

, Hybridization of grasp metaheuristic with data mining techniques, Journal of Mathematical Modelling Algorithms 5 (2006), 23–41.

17.

Ribeiro

M.H.

Trindade

V.F.

Plastino

and Martins

S.L.

, Hybridization of grasp metaheuristic with data mining techniques, In Workshop on Hybrid Metaheuristics in conjunction with the 16th European Conference on Artificial Intelligence, (2004), 6–78.

18.

Santos

H.G.

Ochi

L.S.

Marinho

E.H.

and Drummond

L.M.D.A.

, Combining an evolutionary algorithm with data mining to solve a single-vehicle routing problem, Neurocomputing 70(1-3) (2006), 70–77.

19.

Santos

L.F.

Albuquerque

C.V.

Martins

S.L.

and Plastino

, A hybrid grasp with data mining for efficient server replication for reliable multicast, In Proceedings of the IEEE GLOBECOM Conference, (2006).

20.

Santos

L.F.

Ribeiro

M.H.F.

Plastino

and Martins

S.L.

, A hybrid grasp with data mining for the maximum diversity problem, In Proceedings of the 2nd International Workshop on Hybrid Metaheuristics, LNCS 3636, (2005), 116–127.

21.

Shi

Weise

Chiong

and Çatay

, Hybrid paco with enhanced pheromone initialization for solving the vehicle routing problem with time windows, In In SSCI, December (2015), 1735–1742.

22.

Skinderowich

, Implementing population-based aco, In International Conference on Computational Collective Intelligence, Springer, Cham, (September 2014), 603–612.

23.

Skinderowicz

, Population-based ant colony optimization for sequential ordering problem, In In Computational Collective Intelligence, Springer, Cham, (2015), 99–109.

24.

Stützle

and Dorigo

, Aco algorithms for the quadratic assignment problem, In New Ideas in Optimization, McGraw-Hill Ltd., UK, (1999), 33–50.

25.

Stützle

, Iterated local search for the quadratic assignment problem, European Journal of Operational Research 174(3) (2006), 1519–1539.

26.

Zaki

M.J.

, SPADE: An efficient algorithm for mining frequent sequences, Machine Learning Journal 42(1/2) (Jan/Feb 2001), 31–60. Special issue on Unsupervised Learning (D. Fisher, editor.).

27.

Taillard

Éric D.

, Comparison of iterative searches for the quadratic assignment problem, Location Science 3(2) (1995), 87–105.

Hybridization of population-based ant colony optimization via data mining

Abstract

Keywords

1. Introduction

1.1 Related work

1.2 Organization of the paper

2. Population based ant colony optimization

2.1 Solution construction

2.1.1 TSP

2.3 Pheromone update

3.1 Data mining procedure-ASIPATH

Table 1 Permutation representation of tours for a 4-city TSP

Table 3 Comparison of PACO and PACO-DM-PACO trials for TSP

References

Table 1
Permutation representation of tours for a 4-city TSP

Table 3
Comparison of PACO and PACO-DM-PACO trials for TSP