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

In this paper, we present a new method, called the parallelized genetic ant colony system (PGACS), for solving the traveling salesman problem. It consists of the genetic algorithm, including the new crossover operations and the hybrid mutation operations, and the ant colony systems with communication strategies. We also make an experiment with three classical data sets got from the TSP library to test the performance of the proposed method. The experiment results show that the performance of the proposed method is better than Chu et al.’s method (2004).

The traveling salesman problem (TSP) (Lawler, Lenstra, & Shmoys, 1985) is a NP-complete problem. It tries to find a complete route with a minimal cost. Because the traveling salesman problem is a good background for testing the performance of optimization methods, some methods (Adachi and Yoshida, 1995, Baraglia et al., 2001, Chien and Chen, 2009, Ellabib et al., 2007, Fiechter, 1994, Freisleben and Merz, 1996, Hopfield and Tank, 1985, Kirkpatrick et al., 1983, Liu and Zeng, 2009, Martin and Otto, 1996, Naimi and Taherinejad, 2009, Saadatmand-Tarzjan et al., 2007, Xie and Liu, 2009 and Yi et al., 2008) have been developed for solving the traveling salesman problem. Kirkpatrick et al. (1983) presented a simulated annealing method to solve the traveling salesman problem by simulating the annealing action in metallurgy. Hopfield and Tank (1985) presented a method based on neural networks to make routing decisions for solving the traveling salesman problem by mimicking the properties of biological neurons. Fiechter (1994) presented a tabu searching method with a parallelized mechanism to solve the traveling salesman problem. Adachi and Yoshida (1995) presented the parallelized techniques and the idea of protected chromosomes to reduce the searching space to speed up the processing time of genetic algorithm (GA) for solving the traveling salesman problem. Freisleben and Merz (1996) presented a hybrid method combining the GA and local search heuristics to find a near-optimum solution for solving the traveling salesman problem. Martin and Otto (1996) presented a method combining the simulated annealing (SA) with the local heuristics to solve the traveling salesman problem. Baraglia et al. (2001) presented a hybrid heuristic genetic algorithm for solving the traveling salesman problem. Ellabib et al. (2007) presented a method with exchange strategies for multiple ant colony systems to solve the traveling salesman problem. Saadatmand-Tarzjan et al. (2007) presented a novel constructive-optimizer neural network for solving the traveling salesman problem. Yi et al. (2008) presented a fast elastic net method for solving the traveling salesman problem. Naimi and Taherinejad (2009) presented an ant colony algorithm using a local updating process to solve the traveling salesman problem. Chien and Chen (2009) presented a method based on parallelized genetic ant colony systems to solve the traveling salesman problem. Liu and Zeng (2009) presented a method using genetic algorithms with reinforcement learning to solve the traveling salesman problem. Xie and Liu (2009) presented a method using multiagent optimization systems for solving the traveling salesman problem. Swarm intelligence is an important research topic for solving optimization problems. It is inspired by the social behaviors of real insects or animals. Ant colony optimization (ACO) is the most popular one in this research topic. The original algorithm of ACO is known as the ant system (Dorigo, 1992) which was proposed by Dorigo to solve the traveling salesman problem. Since then, some algorithms based on the ACO are presented, such as the ant colony system (ACS) (Dorigo and Gambardella, 1997a and Dorigo and Gambardella, 1997b), the MMAS (Stützle and Hoos, 1996 and Stützle and Hoos, 2000), the rank-based AS (Bullnheimer, Hartl, & Strauss, 1997) and KCC-Ants (Naimi & Taherinejad, 2009). These algorithms are all based on the idea of updating the pheromone information to search the shortest route. ACO algorithms are also used to solve other combinational optimization problems, such as the quadratic assignment (Stützle & Hoos, 2000) and the job scheduling (Merkle et al., 2002 and Merkle and Middendorf, 2003). Genetic algorithms (GA) are important techniques in the research area of evolutionary computing. Because GA can search the domain space globally, it has been widely used to solve large-scale combinational optimization problems. As long as the fitness function is determined, we can obtain a good result by means of GA. Adachi and Yoshida (1995) presented protected chromosomes techniques to implement GA to solve the traveling salesman problem. In this paper, we propose a new method, called the parallelized genetic ant colony system (PGACS) to solve the traveling salesman problem. First, we use the ant colony system to obtain the initial solutions. Then, we use the initial solutions as the initial population of GA to obtain better solutions. If GA searches a better solution, we use the global update of ACS to feedback the learning experience to ACS. After a certain number of cycles, we use the communication strategies (Chu, Roddick, & Pan, 2004) to exchange the learning experience between groups to speed up the convergence process. The performance of the proposed method is better than Chu et al.’s method (2004). The rest of this paper is organized as follows. In Section 2, we briefly review the concepts of ant system (AS) and the ant colony optimization (ACO). In Section 3, we briefly review the concepts of genetic algorithms. In Section 4, we present a new method to solve the traveling salesman problem by parallelized genetic ant colony systems. In Section 5, we show the experiment results of the proposed method based on three classical TSP data sets. The conclusions are discussed in Section 6.

In this paper, we have presented a new method called the parallelized genetic ant colony systems (PGACS) for solving the traveling salesman problem. We also make an experiment with tree data sets get from the TSP library to test the performance of the proposed method. From Table 2, Table 3 and Table 4, we can see that the performance of the proposed method is better than Chu et al.’s method (2004). It provides us with a useful way to solve the traveling salesman problem