A LEARNER PERFORMANCE-BASED BEHAVIOR ALGORITHM FOR SOLVING TRAVELLING SALESMAN PROBLEM

SHAHAD A.  SALIH; TARIK A.  RASHID

doi:10.26682/sjuod.2023.26.1.29

SHAHAD A. SALIH Dept. of Computer Science, University of Duhok, Kurdistan Region–Iraq
TARIK A. RASHID Dept. of Computer Science and Engineering, University of Kurdistan Hewler, Erbil, Kurdistan Region–Iraq

DOI: https://doi.org/10.26682/sjuod.2023.26.1.29

Keywords: Traveling salesman problem, Learner performance-based behavior, Optimization algorithms, Metaheuristics, Genetic algorithm, Particle swarm algorithm

Abstract

The traveling salesman problem (TSP), is one of the complex optimization problems. TSP is considered as a non-deterministic polynomial-time hardness (NP) hard problem, since its solution cannot be found in certain polynomial time. In this work, a new metaheuristic optimization algorithm called learner performance-based behavior (LPB) was applied to find a feasible solution for TSP. The LPB algorithm's operators are based on those of genetic algorithms (crossover and mutation). In addition, the genetic algorithm and particle swarm optimization algorithm were applied to TSP to compare the efficiency of the LPB algorithm with them to solve this problem. The LPB outperformed the generic algorithm and the particle swarm algorithm. For instance, when the number of nodes is 30, the population size is 100, and the number of iterations is 500 within a loop of 30 iterations, the minimum averages were: the LPB (655.1900067), the GA (723.084896), and the PSO (692.6886233).

Downloads

Download data is not yet available.

References

Gunantara, N. and Nurweda Putra, I., 2019. The characteristics of metaheuristic method in selection of path pairs on multicriteria ad hoc networks. Journal of Computer Networks and Communications, 2019.
Rahman, C. M., & Rashid, T. A. (2021). A new evolutionary algorithm: Learner performance-based behavior algorithm. Egyptian Informatics Journal, 22(2), 213-223.
Reinelt, G. (2003). The traveling salesman: computational solutions for TSP applications (Vol. 840). Springer.
Fogel, D. B. (1988). An evolutionary approach to the traveling salesman problem. Biological Cybernetics, 60(2), 139-144.
Cheng, C. B., & Mao, C. P. (2007). A modified ant colony system for solving the travelling salesman problem with time windows. Mathematical and Computer Modelling, 46(9-10), 1225-1235.
Hassanat, A.B., Prasath, V.S., Abbadi, M.A., Abu-Qdari, S.A. and Faris, H., 2018. An improved genetic algorithm with a new initialization mechanism based on regression techniques. Information, 9(7), p.167.
Fu, C., Zhang, L., Wang, X., & Qiao, L. (2018, May). Solving TSP problem with improved genetic algorithm. In AIP Conference Proceedings (Vol. 1967, No. 1, p. 040057). AIP Publishing LLC.
Kaabi, J. and Harrath, Y., 2019. Permutation rules and genetic algorithm to solve the traveling salesman problem. Arab journal of basic and applied sciences, 26(1), pp.283-291.
Hariyadi, P.M., Nguyen, P.T., Iswanto, I. and Sudrajat, D., 2020. Traveling salesman problem solution using genetic algorithm. Journal of Critical Reviews, 7(1), pp.56-61.
Khan, I., Pal, S. and Maiti, M.K., 2018, March. A modified particle swarm optimization algorithm for solving traveling salesman problem with imprecise cost matrix. In 2018 4th International Conference on Recent Advances in Information Technology (RAIT) (pp. 1-8). IEEE.
Yu, M., 2019. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete and Continuous Dynamical Systems-S, 12(4&5), pp.979-987.
Emambocus, B. A. S., Jasser, M. B., Hamzah, M., Mustapha, A., & Amphawan, A. (2021). An Enhanced Swap Sequence-Based Particle Swarm Optimization Algorithm to Solve TSP. IEEE Access, 9, 164820-164836.
Wei, B., Xing, Y., Xia, X., & Gui, L. (2021). A novel particle swarm optimization with genetic operator and its application to tsp. International Journal of Cognitive Informatics and Natural Intelligence (IJCINI), 15(4), 1-17.
Matai, R., Singh, S.P. and Mittal, M.L., 2010. Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1.
Qayyum, A., 2018. Student help-seeking attitudes and behaviors in a digital era. International Journal of Educational Technology in Higher Education, 15(1), pp.1-16.
Chew, S.L., 2010. Improving classroom performance by challenging student misconceptions about learning. APS Observer, 23(4).
Cao, L. and Nietfeld, J.L., 2007. College Students' Metacognitive Awareness of Difficulties in Learning the Class Content Does Not Automatically Lead to Adjustment of Study Strategies. Australian Journal of Educational & Developmental Psychology, 7, pp.31-46.
Salih, S. A., & Rashid, T. A. (2022). Learner Performance-Based Behavior Optimization Algorithm: A Functional Case Study. In The International Conference on Innovations in Computing Research (pp. 467-482). Springer, Cham.
Hassanat, A., Almohammadi, K., Alkafaween, E.A., Abunawas, E., Hammouri, A. and Prasath, V.S., 2019. Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach. Information, 10(12), p.390