International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Blog/Latest News Contact Us
10th percentile
Powered by  Scopus
Scopus coverage:
Nov 2018 to May 2020


IJSTR >> Volume 8 - Issue 8, August 2019 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

Travelling Salesman Problem Using Genetic Algorithm And Fuzzy C-Mean Clustering Algorithm

[Full Text]



Ajendra Kumar, Preet Pal Singh, Pawan Joshi



Travelling Salesman Problem (TSP), Genetic Algorithm (GA), Fuzzy C-Mean algorithm (FCM), Fuzzy C-Mean Genetic Algorithm (FCMGA)



This paper presents a new algorithm called Fuzzy C-Mean Genetic Algorithm (FCMGA) to solve TSP which is used to calculate the minimum travelling cost in TSP. FCMGA is a combination of both Fuzzy C-Mean (FCM) and Genetic Algorithm (GA). The role of FCM and GA is different in this algorithm. FCM is used to find the membership values of each chromosome, whereas GA is used to apply mutation on the variables of those chromosomes. The proposed algorithm is very helpful to find nearly optimized solutions of these types of problems, in order to give the best solution of the problem with the reduction of cost. The algorithm (FCMGA) proposed here is tested with some examples and the experiment shows that the algorithm can achieve good results as compared with GA.



[1]. Bezdek, J.C., Ehrlich, R., Full, W., 1984. The Fuzzy C- Mean clustering algorithm. Computer and Geosciences 10, 191-203.
[2]. Cai, W., Chen, S., Zhang, D., 2007. Fast and Robust Fuzzy C-Means Clustering Algorithms Incorporating Local Information for Image Segmentation. Pattern recognition 40, 825-838.
[3]. Chuang, K.S., Tzeng, H.L., Chen, S., Wu, J., Chen, T.J., 2005. Fuzzy C-means clusters with spatial information for image segmentation. Computerized medical imaging and graphics 30, 9-15.
[4]. Dwivedi, V., Chauhan, T., Saxena, S., Agrawal, P., 2012. Traveling Salesman Problem using Genetic Algorithm. International journal of computer applications (IJCA).
[5]. Gambhava, N., Sanghani, G., 2003. Traveling Salesman Problem using Genetic Algorithm.
[6]. Gong, M., Liang, Y., Shi, J., Ma, W., Ma, J., 2013. Fuzzy C-Means Clustering with Local Information and Kernel Metric for Image Segmentation. IEEE Transactions on image processing 22(2), 573-584.
[7]. Grefenstette, J., Gopal, R., Rosmaita, B., Gucht, D.V., 1985. Genetic algorithm for travelling salesman problem. (IEEE conference paper), 160-168.
[8]. Hung, C.C., Kulkarni, S., Kuo, B.C., 2011. A New Weighted Fuzzy C-Means Clustering Algorithm for Remotely Sensed Image Classification. IEEE Journal of selected topics in signal processing 5(3), 543-553.
[9]. Hung, M.C., Yang, D.L., 2001. An Efficient Fuzzy C-Means Clustering Algorithm. IEEE, 225-232.
[10]. Izakian, H., Abraham, A., 2011. Fuzzy C-means and fuzzy swarm for fuzzy clustering problem. Expert systems with applications 38, 1835-1838.
[11]. Larranaga, p., Kuijpers, C.M.H., Murga, R.H., Inza,I., Dizdarevic, S., 1999. Genetic Algorithm for Travelling Salesman Problem: A Review of Representations and Operators. Artificial intelligence 13, 129-170.
[12]. Maulik, u., Bandyopadhyay, S., 2000. Genetic Algorithm-Based Clustering Algorithm. The journal of the pattern recognition 33, 1455-1465.
[13]. Moon, C., Kim, J., Choi, J., Seo, Y., 2002. An Efficient Genetic Algorithm for Travelling Salesman Problem with Precedence Constraints. European journal of operational research 140, 606-617.
[14]. Murthy, C.A., Chowdhury, N., 1996. In search for optimal clusters using genetic algorithm. Pattern recognition letters 17, 825-832.
[15]. Pal, N., Bezdek, J.C., 1997. A mixed c-mean clustering model. IEEE, 11-21.
[16]. Pal, N.R., Pal, K., Keller, J.M., Bezdek, J.C., 2005. A Probabilistic Fuzzy C-Mean clustering algorithm. IEEE Transactions on fuzzy systems 13(4), 517-530.
[17]. Potvin, J.Y., 1996. Genetic algorithm for the travelling salesman problem. Annals of operational research 63, 339-370.
[18]. Rezaee, M.R., Lelieveldt, B.P.F., Reiber, J.H.C., 1998. A new cluster validity index for the fuzzy c-mean. Pattern recognition letters 19, 237-246.
[19]. Snyder, L.V., Daskin, M.S., 2006. A Random Key Genetic Algorithm for the Generalized Travelling Salesman Problem. European journal of operational research 174, 38-53.
[20]. Wu, K.L., Yang, M.S., 2002. Alternative C-Means Clustering Algorithm. Pattern recognition 35, 2267-2278.