AccScience Publishing / IJOSI / Volume 6 / Issue 5 / DOI: 10.6977/IJoSI.202109_6(5).0004
Submit to IJOSI
Cite this article
4
Views
Related Info Links
Google Scholar
More by Authors Links
Ayad Mohammed Jabbar
Journal Browser
Volume | Year
Issue
Search
News and Announcements
View All
ARTICLE

Hybrid Black Widow Optimization and Variable Neighborhood Descent Algorithm for Traveling Salesman Problem

Ayad Mohammed Jabbar1* ,  Ku Ruhana Ku-Mahamud2
Show Less
1 Computer Science Department, Shatt Al-Arab University College , Iraq
2 School of Computing, Universiti Utara Malaysia , Malaysia
IJOSI 2020, 6(5), 32–43; https://doi.org/10.6977/IJoSI.202109_6(5).0004
Received: 11 July 2021 | Revised: 22 July 2021 | Accepted: 7 September 2021 |
© Invalid date by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )
Download PDF
XML
Cite
Abstract

Local search algorithms in general are better than population-based algorithms in the terms of exploitation capability in finding more local regions in the search space which provide more ability to explore search space in finding global regions. Black widow optimization (BWO) algorithm is one of the best population-based algorithms which was proposed in 2020 to solve engineering optimization problems. However, this algorithm has a limitation in the exploitation of search space and reactivate a search when stagnation occurs during the algorithm run. Thus, deep search and effectively exploring the search space are not possible during the algorithm run. To overcome these drawbacks, this study proposes two modifications to the BWO algorithm. The first modification is the integration of variable neighborhood descent used to enhance the exploitation process in finding more local regions in the neighborhood during the algorithm run. The second modification focuses on the reactive search process by integrating a new convergence indicator for the algorithm during the algorithm run and online reactive search process. Two benchmark datasets were used to evaluate the proposed modification. The minimum tour distance provided by each algorithm has been used as the performance metric in determining the credibility of the hybrid BWO algorithm and results have been compared with best-known algorithms include African buffalo optimization (ABO), ant colony optimization (ACO), artificial bee colony (ABC), particle swarm optimization (PSO) and a hybrid algorithm consisting of harmony search, particle swarm and ACO (HPSACO). The hybrid BWO algorithm has produced better minimum tour distance compared to ABO, ACO, ABC, PSO and HPSACO algorithms which demonstrate that the hybrid BWO can be applied to solve several optimization problems including vehicle routing problem, classification and clustering.

Keywords
Exploration
Exploitation
Local search
Neighborhood search
Swarm algorithms
Traveling salesman problem.
References
  1. Abuhamdah, A. (2020). Adaptive black widow optimisation algorithm for data clustering. Journal Mathematics in Operational Research, 2002, 1–25.
  2. Al-behadili, H. N. K., Ku-mahamud, K. R., & Sagban, R. (2019). Annealing strategy for an enhance rule pruning technique in ACO-based rule classification. Indonesian Journal of Electrical Engineering and Computer Science, 16(3), 1499–1507.
  3. Al-Behadili, H. N. K., Ku-Mahamud, K. R., & Sagban, R. (2020a). Hybrid ant colony optimization and iterated local search for rules-based classification. Journal of Theoretical and Applied Information Technology, 98(04), 657–671.
  4. AL-Behadili, H. N. K., Ku-Mahamud, K. R., & Sagban, R. (2020b). Hybrid ant colony optimization and genetic algorithm for rule induction. Journal of Computer Science, 16(7), 1019–1028.
  5. Al-Behadili, H. N. K., Sagban, R., & Ku-Mahamud, K. R. (2020c). Adaptive parameter control strategy for ant-miner classification algorithm. Indonesian Journal of Electrical Engineering and Informatics, 8(1), 149–162.
  6. Dao, S. D., Abhary, K., & Marian, R. (2015). An adaptive restarting genetic algorithm for global optimization. Lecture Notes in Engineering and Computer Science, 2219, 455–459.
  7. Das, A. K., & Pratihar, D. K. (2018). Performance improvement of a genetic algorithm using a novel restart strategy with elitism principle. International Journal of Hybrid Intelligent Systems, 15(1), 1–15.
  8. Desale, S., Rasool, A., Andhale, S., & Rane, P. (2015). Heuristic and Meta-Heuristic Algorithms and Their Relevance to the Real World: A Survey. International Journal of Computer Engineering in Research Trends, 351(5), 2349–7084.
  9. Duarte, A., Mladenović, N., Sánchez-Oro, J., & Todosijević, R. (2016). Variable Neighborhood Descent. Handbook of Heuristics, 1–27.
  10. El-Ghazali Talb. (2009). METAHEURISTICS from design to implementation.
  11. Ghany, K. K. A., AbdelAziz, A. M., Soliman, T. H. A., & Sewisy, A. A. E. M. (2020). A hybrid modified step Whale Optimization Algorithm with Tabu Search for data clustering. Journal of King Saud University - Computer and Information Sciences, 5(1), 1–8.
  12. Goh, S. L., Kendall, G., Sabar, N. R., & Abdullah, S. (2020). An effective hybrid local search approach for the post enrolment course timetabling problem. Opsearch, 57(4), 1131–1163.
  13. Hayyolalam, V., & Pourhaji Kazem, A. A. (2020). Black Widow Optimization Algorithm: A novel meta-heuristic approach for solving engineering optimization problems. Engineering Applications of Artificial Intelligence, 87(September 2019).
  14. Hore, S., Chatterjee, A., & Dewanji, A. (2018). Improving variable neighborhood search to solve the traveling salesman problem. Applied Soft Computing Journal, 68, 83–91.
  15. Hore, S., Dewanji, A., & Chatterjee, A. (2014). Design issues related to allocation of experimental units with known covariates into two treatment groups. Journal of Statistical Planning and Inference, 155, 117–126.
  16. Hore, S., Dewanji, A., & Chatterjee, A. (2016). On Optimal Allocation of Experimental Units with Known Covariates into Multiple Treatment Groups. Calcutta Statistical Association Bulletin, 68(1–2), 69–81.
  17. Hossain, M. Z., Akhtar, M. N., Ahmad, R. B., & Rahman, M. (2019). A dynamic K-means clustering for data mining. Indonesian Journal of Electrical Engineering and Computer Science, 13(2), 521–526.
  18. Houssein, E. H., Helmy, B. E. din, Oliva, D., Elngar, A. A., & Shaban, H. (2020). A novel Black Widow Optimization algorithm for multilevel thresholding image segmentation. Expert Systems with Applications, (12), 114-159.
  19. Jabbar, A. M., Ku-Mahamud, K. R., & Sagban, R. (2019a). An improved ACS algorithm for data clustering. Indonesian Journal of Electrical Engineering and Computer Science, 17(3), 1506–1515.
  20. Jabbar, A. M., Ku-Mahamud, K. R., & Sagban, R. (2019b). Balancing exploration and exploitation in acs algorithms for data clustering. 97(16), 4320–4333.
  21. Jabbar, A. M., Ku-Mahamud, K. R., & Sagban, R. (2019c). Modified ACS Centroid Memory for Data Clustering. Journal of Computer Science, 15(10), 1439–1449.
  22. Jia, H. (2015). A Novel Hybrid Optimization Algorithm and its Application in Solving Complex Problem. International Journal of Hybrid Information Technology, 8(2), 1–10.
  23. Moriguchi, K., Ueki, T., & Saito, M. (2015). An Evaluation of the Use of Simulated Annealing to Optimize Thinning Rates for Single Even-Aged Stands. International Journal of Forestry Research, 2015, 1–15.
  24. Odili, J. B., & Mohmad Kahar, M. N. (2016). Solving the Traveling Salesman's Problem Using the African Buffalo Optimization. Computational Intelligence and Neuroscience. 3(1), 1–13.
  25. Rasekh, A., & Osawa, N. (2020). Direct and indirect effect of cannibalism and intraguild predation in the two sibling Harmonia ladybird beetles. Ecology and Evolution, 10(12), 5899–5912.
  26. Sathish, & Ananthapadmanabha. (2021). Improved black widow-bear smell search algorithm for optimal planning and operation of distributed generators in distribution system. Journal of Engineering, Design and Technology. 7(1), 1–21.
  27. Sheriba, S. T., & Rajesh, D. H. (2021). Energy-efficient clustering protocol for WSN based on improved black widow optimization and fuzzy logic. Telecommunication Systems. 15(10), pages213–230.
  28. Sicilia, J. A., Quemada, C., Royo, B., & Escuín, D. (2016). An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics. Journal of Computational and Applied Mathematics, 291, 468–477.
  29. Stegherr, H., Heider, M., & Hähner, J. (2020). Classifying Metaheuristics: Towards a unified multi-level classification system. 7(3), 1–17.
  30. Stützle, T., & Hoos, H. H. (2000). MAX–MIN Ant System. Future Generation Computer Systems, 16, 889–914.
  31. Tan, J. S., Goh, S. L., Sura, S., Kendall, G., & Sabar, N. R. (2020). Hybrid particle swarm optimization with particle elimination for the high school timetabling problem. Evolutionary Intelligence. (3). 1-16.
  32. TSPLIB. (1995). Symmetric traveling salesman problem (TSP).
  33. Venkatesh, B., & Anuradha, J. (2019). A review of Feature Selection and its methods. Cybernetics and Information Technologies, 19(1), 3–26.
  34. Yang, X.-S., & Yang, X.-S. (2014). Simulated Annealing. In Nature-Inspired Optimization Algorithms (pp. 67–75).
  35. Zhou, K., Wan, W., Chen, X., Shao, Z., & Biegler, L. T. (2013). A parallel method with hybrid algorithms for mixed integer nonlinear programming. In Computer Aided Chemical Engineering, 19(1). 271-276.
Share
Back to top
International Journal of Systematic Innovation, Electronic ISSN: 2077-8767 Print ISSN: 2077-7973, Published by AccScience Publishing
We use cookies on our website to ensure you get the best experience.
Read more about our cookies here
Accept