Solving Travelling Salesman Problem Using Artificial Bee Colony Based Approach

Solving Travelling Salesman Problem Using Artificial Bee Colony Based Approach

Sahil Sobti1, Parikshit Singla2

2 Assistant Professor, DIET,Karnal

Abstract

This paper mainly explains about the performance of Artificial Bee Colony (ABC) algorithms in solving the Travelling Salesman Problem (TSP). The main goal of TSP is that a number of cities should be visited by a salesman and return to the starting city along with a number of possible shortest routes. As the domain experts are difficult to find & knowledge extraction from the experts itself is difficult task the data driven modeling assume significance, One has to apply soft computing base methodology to generate rule base form data. Neural networks, genetic algorithm & particle swam optimization are some of the approaches [1]. Basic Artificial Bee Colony algorithm (ABC) has the advantages of strong robustness, fast convergence and high flexibility, fewer setting parameters, but it has the disadvantages premature convergence in the later search period and the accuracy of the optimal value which cannot meet the requirements sometimes [4].

Keywords: -Artificial Bee Colony Algorithm, Fuzzy Membership Function, Sugeno System, Rule Based Generation.

1. INTRODUCTION

   Fuzzy systems are used to model highly complex and highly nonlinear systems and under the circumstances, the rule base extraction problem becomes NP hard problem. When the problem is very complex, application of classical methods turns out to be very expensive computationally. ABC is an example of how a natural process can be modeled to solve optimization problems [3]. The concept of mathematical model is fundamental to system analysis & design which requires representation of systems as functional dependence between interacting input & output variables conventionally, a mathematical model is constructed by analyzing input output from the system.

2. FUZZY SYSTEM

   Fuzzy systems are used to model highly complex and highly nonlinear systems and under the circumstances, the rule base extraction problem becomes NP hard problem. When the problem is very complex, application of classical methods

   turns out to be very expensive computationally. ABC is an example of how a natural process can be modeled to solve optimization problems [3]. The concept of mathematical model is fundamental to system analysis & design which requires representation of systems as functional dependence between interacting input & output variables conventionally, a mathematical model is constructed by analyzing input output from the system. Optimization problems is mainly used for finding nearly optimal solution and are frequently encountered in various applications such as TSP [10], Container Loading problems (CL) [11],

   Scheduling problems [12], engineering design [13, 14] etc. TSP is one of the NP hard optimization problems. In TSP, the salesman travels all the cities at once and returns to the starting city with the possible shortest route within small duration. Many heuristic optimization methods are developed so far for searching nearly optimal solution in solving TSP such as Genetic Algorithm (GA) [1, 2], Particle Swarm

   Optimization (PSO) [3, 5], Ant Colony

   optimization (ACO) [4, 6], Simulated Annealing (SA) [7] and Artificial Bee Colony (ABC)

3. Algorithm

   In the ABC model, the colony consists of three groups of bees: employed bees, onlookers and scouts. It is assumed that there is only one artificial employed bee for each food source. In other words, the number of employed bees in the colony is equal to the number of food sources around the hive. Employed bees go to their food source and come back to hive and dance on this area. The employed bee whose food source has been abandoned becomes a scout and starts to search for finding a new food source. Onlookers watch the dances of employed bees and choose food sources depending on dances.In ABC, a population based algorithm, the position of a food source represents a possible solution to the optimization problem and the nectar amount of a food source corresponds to the quality (fitness) of

   the associated solution.

4. Travelling Salesman Problem (TSP)

   The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. TSP has several applications, such as planning, logistics, network communication, transportation, and the manufacture of microchips. TSP states that for one salesman who wants to visit cities and given distances between them, travelling salesman has to visit all of them, but by travelling very less. The Task is to find a sequence of cities to minimize travelled distance [1][16].

   To solve the Travelling salesman problem the researcher has used the Artificial Bee Colony Algorithm. In this, an initial population is chosen by selecting random starting values from the search space, the sequence vector associated with each individual is calculated, sequence vector is a member of the set of x, where x is the total number of cities. After getting the initial population and associating it with initial sequence vector, fitness value of each individual is calculated. This problem can be solved by using ABC approach where the different bees perform different task. In the next step, these individuals are visited by employed bees and onlooker bees of Bee colony. Employed and onlooker bee operator are used for local search to avoid local max problem.

   In employed and onlooker bee phase new vector is generated. Then the cost of this offspring is calculated. Using the sequence and its cost from the cost matrix the fitness value of One problem ran into, though, is that if multiple worker roles begin firing events, every time a solution is found, the system will likely grind to a halt trying to cope with a gazillion messages (not to mention a potentially unpleasantly high bill), whereas every single solution is not taken into consideration. So it is notified about some improvements, not necessarily every single one. Ability tothrottle the flow of events coming from the solver, to receive, the best one in every 60 seconds. The syntax for declaring an event is refreshingly simple, and can be used in a way similar to what would do in C.

   TSP can be modeled as an undirected weighted

   graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's length. A TSP tour becomes a Hamiltonian cycle if and only if every edge has the same distance. Often, the model is a complete graph (i.e., an edge connects each pair of vertices). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

   1. Computational complexity :- The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. The bottleneck travelling salesman problem is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases. Removing the condition of visiting each city

      "only once" does not remove the NP-hardness, since it is easily seen that in the planar case there is an optimal tour that visits each city only once (otherwise, by the triangle inequality, a shortcut that skips repeated visit would not increase the tour length).

      If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 7/6. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance; it is an open question if a constant factor approximation exists.

   2. Experimental Setup: – For every algorithm there are some control parameters which are used for its efficient working. Hence, there are some control parameters for artificial bee colony algorithm. An extensive literature survey has been done and the researcher has carried out experiments for determining the values of these control parameters. From this, the researcher found that the values which have taken in this experiment are standard values and they are also suitable for this experiment. The first control Parameter is Maximum cycle number: Maximum numbers of cycles (MCN) are equal to the maximum number of generation, the results were taken for 1500, 2000 and 2500 MCN value. The next parameter in experiment is maximum number of population and the value taken is 30 and 60. Another control

   parameter is number of runs and the value of it in experiment as 30. It must be noted that each run contains maximum cycle number, which is 1500, 2000, 2500 in this experiment. The fourth control parameter is dimension and it depends upon the number of cities.

5. RESULT

   The Mean Square Error (MSE) for the Travelling Salesman Problem using proposed approach is

   0.030. The Comparison with Some of the existing approaches is as shown in table 1:

   Table 1: Comparison with other approaches

   Approach	Mean Square Error (MSE)
   Genetic Algorithm	0.13
   Wang & Mendel Approach [3]	0.06
   Ant Colony Optimization [30]	0.05
   Proposed Approach (S-ABC)	0.03

   The proposed approach (S-ABC) was compared with the existing approaches and shown below in the graphical manner. The graph showed that means square error for proposed approach was lesser among means square error of other approaches, resulting in the more accuracy of proposed approach. Figure 1 is showing the comparative analysis of all the approaches (GA, Wangs Approach and ACO).

   0.14

   0.12

   0.1

   The classification rates are calculated using following formula:

   . . =

   Total number of data samples Number of misclassifications Total number of data samples

   (1.1)

   The proposed approach was further compared with other approaches (GA, Wangs Approach and ACO) on the basis of classification rate. The proposed approach had the highest classification rate of 98.20% which further confirmed its accuracy. The table 2 is showing the values of classification rate of all the approaches.

   Table 2: Comparison with other approaches

   Approach	Classification Rate (C.R)
   Genetic Algorithm [25]	90.67%
   Wang & Mendel Approach [29]	97.33%
   Ant Colony Optimization [30]	97.87%
   Proposed Approach (S- ABC)	98.20%

   Figure 2 shows the graph representing comparing of ABC approach with all others approaches. Also, it can be seen in the graph that there is very small difference in the classification rate of ACO approach and proposed approach.

   Classification Rate

   Classification Rate

   100.00%

   98.00%

   96.00%

   94.00%

   92.00%

   90.00%

   0.08

   MSE

   MSE

   0.06

   0.04

   0.02

   0

   Series1

   88.00%

   86.00%

   Approach

   Series1

   Figure 2: Comparison with other approaches

   Approaches

   Figure 1: Comparison with other approaches

6. CONCLUSION

   This paper proposed an ABC based algorithm to enumerate rule base for a sugeno type fuzzy logic based system. The length of the path set represents the system output i.e. WI*Ci / Wi.

   The difference between computed output and actual output as given in the training data gives the error. TSP the colony size is taken as 40. The number of cities is taken as 50 and the number of iteration is 50.

7. REFERENCES

1. Singh D.,Solving Real Optimization Problem using Genetic Algorithm with Employed Bee International Journal of Computer Applications (0975 8887) Volume 42 No.11, March 2012.

2. MohdAfiziMohdShukran, Artificial Bee Colony based Data Mining Algorithms for Classification Tasks 2011.

3. Mustafa M. Noaman,Solving Shortest Common Super sequence Problem Using Artificial Bee Colony Algorithm The Research Bulletin of Jordan ACM, ISSN, Volume II (III) PP-80.

4. Gupta M., An Efficient Modified Artificial Bee Colony Algorithm for Job Scheduling Problem International Journal of Soft Computing and Engineering (IJSCE) ISSN: 2231-2307, Volume-1, Issue-6, January 2012

5. Inova B., Artificial bee colony algorithm for the capacitated vehicle routing problem Proceedings of the European Computing Conference 2010.

6. Chang Jianghui, Zhao Yongsheng, Wen Chongzhu, Research on Optimization of Fuzzy Membership function based on Ant Colony Algorithm, Proc of the 25th Chinese Control Conference, Harbin, Aug, 2006.

7. Ashita S. Bhagade, Artificial Bee Colony (ABC) Algorithm for Vehicle Routing Optimization Problem International Journal of Soft Computing and Engineering (IJSCE ISSN: 2231-2307, Volume-2, Issue-2, May 2012

8. MalekAlzaqebah, Artificial bee colony search algorithm for examination timetabling Problems International Journal of the Physical Sciences Vol. 6(17), pp. 4264-4272, September, 2011

9. AdilBaykasoglu,Artificial Bee Colony Algorithm and Its Application to Generalized Assignment Problem International Conference on Computational Intelligence for Modeling, Control and Automation, Las Vegas.

10. Marco Dorigo and Thomas Stuzzle, Ant Colony Optimization, Eastern Economy Edition, PHI, 2005.

11. ArunKhosla, Shakti Kumar, KK Aggarwal, JagatpreetSingh,Particle Swarm Optimizer for fuzzy models IEEE Proc. on Fuzzy Systems, 2007

12. Marco Dorigo and Thomas Stuzzle, Ant Colony Optimization, Eastern Economy Edition, PHI, 2005.

13. M. Galea and Q. Shen, Fuzzy Rules from ant-inspired computation, Proc. IEEE Intl Conf. Fuzzy Systems, pp. 1691-1696, 2004.

14. Bhalla P., Fuzzy Rule base generation from Numerical Data using Ant colony optimization, MAIMT-Journal of IT & Management. Vol. 1, No. 1 May-Oct, 2007, pp. 33-47.

15. Chia-Feng J, H.J. Huang and C.M. Lu, Fuzzy Controller Design by ant colony optimization, IEEE Proc. on Fuzzy Systems, 2007.

16. Kumar S. Introduction to Fuzzy Logic Based Systems, Workshop on Intelligent System Engineering (WISE-2010), 2010.

17. Shakti Kumar, P.Bhalla and Amarpartap Singh, Soft Computing Approaches to Fuzzy System identification: A Survey, IISN-2009,pp. 402-411, 2009.

18. M.S. Abadeh, J. Habibi and E. Soroush, Induction of Fuzzy classification systems using evolutionary ABC-based algorithms, Proc. of the First Asia Intl Conf. on Modeling and Simulation (AMS07), 2007

19. Shakti K, P. Bhalla and S.Sharma, Automatic Fuzzy Rule base Generation for Intersystem Handover using Ant Colony Optimization Algorithm, International Conference on Intelligent Systems and Networks (IISN-2007), Feb 23-25, 2007, MAIMT, Jagadhri Haryana, India, pp. 764- 773.

20. Shakti Kumar, Rule base generation using ant colony optimization, Proc. Of the one week workshop on applied soft computing (SOCO-2006), Haryana Engineering Colleg, Jagadhri, July 2006.