Abstract: The study deals with the efficiency of the parallel computation of the Travelling Salesman Problem (TSP) using the genetic algorithms and an unsupervised fuzzy clustering. First, the cities are classified by a clustering algorithms. Second, each class of cities is considered as a sub-tour TSP problem. A parallel genetic algorithms is used for solving the sub tour TSP problem. The main aim by creating the parallel algorithm is to accelerate the execution time of solving TSP. A connection method is proposed to connect the sub-tours into a global tour of whole cities. Furthermore, this global tour is resolved by genetic algorithms for cluster centers and a heuristic scheme. Experimental results, on Master Slave architecture with different TSP problemes show the efficacy of the proposed algorithm in parallelism exploitation.

INTRODUCTION

TSP is a NP hard problem (Greco, 2008) where the computation cost will increase with it size. Lets V₁, V₂, V₃, ..., V_n, n cities and a distance matrix D = [d_ij] where d_ij is the distance between V_i and V_j , TSP requires to find the order in which the salesman visit each city just once and return to the first city as to minimize the total distance traveled (Gutin and Punnen, 2002; Laporte and Palekar, 2002; Reinelt, 1994). More formally the aim is to find a permutation π of the cities that minimizes the sum of the distances:

(1)

For finding solution to TSP, several approximation techniques have been proposed in the literature. The researchers find local search algorithms (Johnson, 1990), simulated annealing (Van Laarhoven and Aarts, 1988), tabu search (Fiechter, 1994) elastic nets (Durbin et al., 1989), neural network (Burke and Ignizio, 1992), genetic algorithms (Back, 1996; Bryant, 2000; Fogel, 1988; Larranaga et al., 1999; Wang et al., 2006) ant colonies (Dorigo and Gambardella, 1997) and particle swarm (Greco, 2008). In addition, other approaches have been obtained by combination of local search and simulated annealing, (Martin and Otto, 1996) by combination of local search and genetic algorithms (Freisleben and Merz, 1996; Katayama and Narihisa, 1999; Lin and Kernighan, 1973; Merz and Freisleben, 1997), genetic algorithms and ant colony systems (Chen and Chien, 2010).

In this study a novel Parallel Genetic Algorithm (PGA) (Alba, 2005) based on a Unsupervised Fuzzy Clustering algorithm is proposed for TSP called Parallel Hybrid Genetic Algorithm (PHGA). PHGA consists of two phases. First, the cities are classified by a clustering algorithm. Clustering of the cities makes the calculations much reduced. If there are N cities, the search space is N! then, the computational time will be higher (Reinelt, 1994). In order to reduce the mathematical complexity, N value should be reduced and this is achieved by clustering. In the second phase, each group of cities are considered as a sub tour TSP problem and this sub tour TSP problem is solved by a parallel genetic algorithm witch get an optimal sub-tour.

For the parallelization, the well known Master Slave (Nedjah et al., 2006) method was used. In this way, each C (C: Number of clusters given by unsupervised fuzzy clustering) slaves is associated to a sub tour TSP and performs it while the master connects these sub-tours into a feasible tour of whole cities. This feasible tour is improved by genetic algorithm and heuristic search scheme. PHGA algorithm is the same as the sequential one but the time consuming is reduced. Also the researchers have used C slaves to speed up the execution of a sequential algorithm.

CLUSTERING ALGORITHMS

In the absence of information about the distribution of cities, the fuzzy clustering offers a better possibility of modeling and management of overlapping clusters. So, the researchers have opted for a fuzzy classification. Thus, the approach is to introduce a fuzzy clustering based on three phases. The first one is the Unsupervised Fuzzy Learning (UFL) (Bouroumi et al., 2000) phase that starts by generating the first class which is around the first city encountered. Then, a new cluster created when the current city presents a small similarity, less than a prefixed threshold S_min, to the entire already existing cluster centers. The second phase is the Fuzzy C-Means algorithms (FCM) (Bezdek, 1981), its purpose is to ameliorate the learned partition generated during the previous phase. This clustering is sensitive of the choice of the data similarity so, criterion validity is used in the third phase. More formally, the proposed clustering algorithm UFL_FCM_VAL() is described as follows:

Pseudo code of UFL-FCM-VAL:

(2)

Pseudo code of UFL:

(3)

(4)

(5)

GENETIC ALGORITHMS

After the researchers have got a number of clusters by the cluster algorithm the researchers then, try to find optimal sub-tour for cities of each cluster by GA.

In order to conceive a genetic (Back, 1996; Goldberg, 1989) solution to TSP, the researchers have to determine the Encoding method. Then, the fitness function in Eq. 1 is used for assessing and comparing the shortest traveling tour. Hence, starting from an initial population of randomly generated individuals (tour), the researchers evolved this population toward better solutions according to the rules of the selection strategy, crossover and mutation.

Encoding method (Kargupta et al., 1992; Wang et al., 2006): The ordinal encoding scheme was used in the PHGA. Under this scheme, for a cluster, the set of vertices of cluster tour is denoted as T_i. If cardinal (card) of Ti is s, card (T_i) = s, these vertices are denoted as 1, 2, ..., s, respectively for representing each cluster cities. Then, chromosomes which represent the traveling paths are permutation j₁, j₂, ... , j_s of 1, 2, ... , s.

Initialization: The initialization of the population of chromosomes is generated by a random process. Each chromosome is represented as permutation j₁, j₂, ... , j_s of 1, 2, ... ,s. The process does not yield any illegal chromosome.

Crossover operator: The researchers have used the Partially-Matched Operator (Larranaga et al., 1999). For Two parents P_{1 ,} P₂:

Mutation operator: The researchers have used the Swap Mutation (Fogel, 1993):

Selection operator: The researchers have used a modified tournament selection which guards in each iteration the best individual. The following pseudo code summarizes the selection method.

Tournament selection modified:

Genetic algorithm for one cluster: The Clustering algorithms give for example, U clusters for TSP. In the following the GA for cities in one cluster is given.

GA for a cluster:

CONNECTION OF CLUSTERS

After an optimal sub-tour for each cluster obtained by algorithm, it is necessary to connect these sub-tours to form an optimal tour for the whole cities. Suppose that clustering algorithms generated U clusters which C₁, ... ,C_u are the cluster centers.

In this study, the researchers consider the two Dimensional (2D) Euclidean TSP in which the cities lie in R² so, the coordinates of their centers can be calculated by Eq. 4 and are denoted by: (x₁,y₁),..... (x_u ,y_u).

The objective of using GA is to form an entire tour that is as short as possible based on the tours generated in the previous section. In each generation, the aim is to evolve candidate solutions which are permutations of the tour formed by the cluster centers C₁, ..., C_U. The details for GA are as follows.

Encoding method: The ordinal encoding scheme has been used in the PHGA.

Initialization: The initialization of the population of chromosomes has been generated randomly.

Mutation operator: The researchers have used the inversion mutation. The inversion mutation (Fogel, 1993) randomly selects a sub tour, removes it from the tour and inserts it in a randomly selected position. However, the sub tour is inserted in a reversed order.

Selection operator: The researchers have used a modified tournament selection.

Genetic algorithm for cluster centers: The GA is similar to that of GA for cluster with modifications at the initialization and mutation operator.

GA for cluster centers:

Connection scheme:

PARALLEL HYBRID GENETIC ALGORITHMS

Based on previous sections, a PHGA can be given as follows (Fig. 1):

Fig. 1:	Master slave architecture for PHGA

Pseudo code of PHGA:

EXPERIMENTAL RESULTS

In this study the researchers present the experimental results of the proposed algorithm. The PHGA presented above is computer coded in C++. The researchers have considered clusters of Pentium 4, 3.6 GHz and 1 GB DDR RAM running GNU/Linux Debian 5.0 as Operating System they are connected through a via Fast Ethernet switch (100 Mbps) and the software environments was Parallel Virtual Machine (PVM) is based on the PVM3 (Geist et al., 1994). PHGA is tested with a benchmark problem set:

These problems are available from (http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/).

The researchers have adopted the following parameter values: population size (N = 500, 1000, 2000). Crossover and mutation probabilities are p_c = 0.8 and p_m = 0.02, respectively.

The researchers have compared the results found by PHGA and those found by a standard GAs (SGAs). SGAs have used the following parameters:

Crossover operator: The researchers have used the partially-matched crossover.

Table 1:	The Relative error in percentage for PHGA and SGA

Table 2:	Speedup for PHGA

Mutation pperator: The researchers have used the inversion mutation.

Selection operator: The researchers have used a Tournament Selection with different tournament size (Back, 1996; Bezdek, 1981; Chen and Chien, 2010).

Initialization: The initialization of the population of chromosomes is generated by a random process.

Table 1 shows the sample results related to an aspect of this study. It is the aspect of quality assessment of the optimum provided by the SGA and PHGA. To measure this quality, the researchers used the Relative Error in Percentage (REP):

(6)

Where:

The cities number varies from 100-7397 i.e., medium and large cities numbers. The results demonstrate clearly the efficiency of the algorithm. In the first two tests, the optimum was found in 20 generations. Note also that the running time of the algorithm was reasonable.

In Table 1, the column labeled by Number of Clusters was especially for PHGA not for SGA.

Table 2 shows sample results related to another aspect of this study. It is the aspect of the speedup. This study considers the conventional de_nition of the parallel speedup of an algorithm as the ration of the execution time of the best serial algorithms Ts and the execution time of the parallel program, T_p:

(7)

By analysing this Table 2 the researchers can see clearly that the proposed method performs better than the standard genetic algorithms.

CONCLUSION

In this study, the reseachers have dealt with TSP problem with large and medium number of cities. The basic idea is to classify cities with a Fuzzy unsupervised learning algorithm and FCM, into several partitions in order to reduce the mathematical complexity. After the clustering phase, the reseachers applied the GA for each cluster of cities in parallel architecure. To make the connection between the different clusters of cities, first the reseachers have applied again the GA for the cluster centers and secondly, the reseachers have used a heuristic algorithm to join the edges of clusters whose cluster centers are the optimal tour given by PGA.

The PHGA has the ability of finding optimal solutions with small amount of computation. The simulation results demonstrate the effectiveness of the proposed algorithm. The PHGA shows superior performance compared to the standard genetic algorithms. For medium size problems, the reseachers have obtained optimal solutions. On a larger size problem, PHGA generated best solutions and the execution time is shorter than SGAs. Thus,the reseachers may conclude that the PHGA is an efficient methodology for the TSP with large number of cities.

In future research, the reseachers will consider implementing PHGA in an another parallel architecture, to investigate and compare the efficiency of the parallel computation.