Improved scatter search algorithm based on meerkat clan algorithm to solve NP-hard problems

Saif Ali Abd Alradha Alsaidi, Dena Kadhim Muhsen, Sura Mazin Ali

Abstract


A modified Scatter Search (SS) algorithm based on Meerkat Clan Algorithm (MCA) has been presented in this paper. SS is one of the important metaheuristic algorithms, while the MCA is one of the recent swarm intelligence algorithms. The modified SS algorithm, including the main steps of MCA, through it the diversity and exploration of SS-MCA's solutions, have improved. The proposed algorithm has been applied to two important NP-Hard problems (Travelling Salesman Problem (TSP) and Flexible Job Shop Scheduling Problem (FJSSP)) to verify the performance of SS-MCA. The experimental results show that the performance of SS-MCA is better than both SS and MCA, respectively.

Full Text:

PDF

References


R. K. Sahoo, D. P. Mohapatra, M. R. J. I. J. o. C. S. Patra, and Engineering, "A firefly algorithm based approach for automated generation and optimization of test cases," vol. 4, no. 8, pp. 54-58, 2016.

X.-S. Yang, "Metaheuristic optimization: algorithm analysis and open problems," in International Symposium on Experimental Algorithms, 2011, pp. 21-32: Springer.

X. Wang and J. J. P. E. Tian, "Dynamic programming for NP-hard problems," vol. 15, pp. 3396-3400, 2011.

T. Narwadi and Subiyanto, "An application of traveling salesman problem using the improved genetic algorithm on android google maps," in AIP Conference Proceedings, 2017, vol. 1818, no. 1, p. 020035: AIP Publishing LLC.

J. J. L. Žerovnik and S. Transport, "Heuristics for NP-hard optimization problems-simpler is better!?," vol. 6, no. 1, pp. 1-10, 2015.

B. Mohammed, R. Chisab, and H. Alrikabi, "Efficient RTS and CTS Mechanism Which Save Time and System Resources," 2020.

R. Martı́, Corberán, Á., and Peiró, J. , Handbook of heuristics. Springer,Cham, 2015

F. C. G. López, M. G. Torres, J. A. M. Pérez, and J. M. M. Vega, "Scatter search for the feature selection problem," in Conference on Technology Transfer, 2003, pp. 517-525: Springer.

N. Mansour, I. Ghalayini, S. Rizk, and M. El-Sibai, "Evolutionary algorithm for predicting all-atom protein structure," 2011.

A. M. Sagheer, A. T. Sadiq, and M. S. Ibrahim, "Improvement of scatter search using Bees Algorithm," in 2012 6th International Conference on Signal Processing and Communication Systems, 2012, pp. 1-7: IEEE.

T. Zhang, W. A. Chaovalitwongse, Y. J. C. Zhang, and O. Research, "Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries," vol. 39, no. 10, pp. 2277-2290, 2012.

A. T. Sadiq, A. M. Sagheer, and M. S. J. I. J. o. R.-b. I. S. Ibrahim, "Improved scatter search for 4–colour mapping problem," vol. 4, no. 4, pp. 221-226, 2012.

A. T. S. J. I. J. o. A. R. i. A. I. Al-Obaidi, "Improved scatter search using cuckoo search," vol. 2, no. 2, pp. 61-67, 2013.

M. A. Remli, M. S. Mohamad, S. Deris, R. Sinnott, and S. J. C. P. Napis, "An Improved Scatter Search Algorithm for Parameter Estimation in Large-Scale Kinetic Models of Biochemical Systems," vol. 16, no. 5, pp. 427-438, 2019.

Z. Zhang, L. Mao, C. Guan, L. Zhu, and Y. J. S. C. Wang, "An improved scatter search algorithm for the corridor allocation problem considering corridor width," vol. 24, no. 1, pp. 461-481, 2020.

N. Hussien, I. Ajlan, M. M. Firdhous, and H. Alrikabi, "Smart Shopping System with RFID Technology Based on Internet of Things," 2020.

R. Baños, C. Gil, J. Reca, J. J. C. O. Martínez, and Applications, "Implementation of scatter search for multi-objective optimization: a comparative study," vol. 42, no. 3, pp. 421-441, 2009.

H. T. S. Al-Rikabi, Enhancement of the MIMO-OFDM Technologies. California State University, Fullerton, 2013.

I. G. Amo, M. G. Torres, B. M. Batista, J. M. Pérez, J. M. Vega, and R. R. Martín, "Data Mining with Scatter Search," in Computer Aided Systems Theory–EUROCAST 2005.

I. A. Aljazaery, H. T. S. Alrikabi, and M. R. J. i. Aziz, "Combination of Hiding and Encryption for Data Security," vol. 14, no. 9, p. 35, 2020.

J. A. Egea, E. Vazquez, J. R. Banga, and R. J. J. o. G. O. Martí, "Improved scatter search for the global optimization of computationally expensive dynamic models," vol. 43, no. 2-3, pp. 175-190, 2009.

R. Martí, M. Laguna, and F. J. e. J. o. o. R. Glover, "Principles of scatter search," vol. 169, no. 2, pp. 359-372, 2006.

H. T. Y. J. E. J. o. O. R. Yoshizaki, "Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil," vol. 199, no. 3, pp. 750-758, 2009.

M. A. a. Roa'a, I. A. Aljazaery, S. K. Al_Dulaimi, H. T. S. J. B. o. E. E. Alrikabi, and Informatics, "Generation of High Dynamic Range for Enhancing the Panorama Environment," vol. 10, no. 1, 2020.

A. Alaidi, I. Aljazaery, H. Alrikabi, I. Mahmood, and F. Abed, "Design and Implementation of a Smart Traffic Light Management System Controlled Wirelessly by Arduino," 2020.

K. Li, H. J. D. D. i. N. Tian, and Society, "A de-based scatter search for global optimization problems," vol. 2015, 2015.

N. S. Alseelawi, E. K. Adnan, H. T. Hazim, H. Alrikabi, and K. Nasser, "Design and Implementation of an E-learning Platform Using N-Tier Architecture," 2020.

A. T. S. Al-Obaidi, H. S. Abdullah, Z. O. J. I. J. o. E. E. Ahmed, and C. Science, "Meerkat clan algorithm: A new swarm intelligence algorithm," vol. 10, no. 1, pp. 354-360, 2018.

A. T. Sadiq, H. S. Abdullah, and Z. O. J. I. J. o. S. Ahmed, "Solving Flexible Job Shop Scheduling Problem Using Meerkat Clan Algorithm," pp. 754-761, 2018.

O. H. Yahya, H. Alrikabi, I. A. J. I. J. o. O. Aljazaery, and B. Engineering, "Reducing the Data Rate in Internet of Things Applications by Using Wireless Sensor Network," vol. 16, no. 03, pp. 107-116, 2020.

C. Perera, M. Barhamgi, A. K. Bandara, M. Ajmal, B. Price, and B. J. I. S. Nuseibeh, "Designing privacy-aware internet of things applications," vol. 512, pp. 238-257, 2020.

A. T. S. J. I. J. o. S. Al-Obaidi, "Harmony-Scatter Search to Solve Travelling Salesman Problem," vol. 54, no. 4, pp. 965-974, 2013.

Z. O. Ahmed, A. T. Sadiq, and H. S. Abdullah, "Solving the Traveling Salesman's Problem Using Camels Herd Algorithm," in 2019 2nd Scientific Conference of Computer Sciences (SCCS), 2019, pp. 1-5: IEEE.

S. A. Hussein, A. T. S. J. J. o. C. Al-Obaidi, and T. Nanoscience, "An Improved Crow Search Algorithm for Solving the Traveling Salesman Problem," vol. 16, no. 3, pp. 978-981, 2019.

J. a. R. Gottlieb, Günther R., " “Evolutionary Computation in Combinatorial Optimization,”" pp. 44-46., 2006. Springer-Verlag

G. Gutin and A. P. Punnen, The traveling salesman problem and its variations. Springer Science & Business Media, 2006.

M. J. v. Staaden, "Suricata suricatta," Mammalian Species, pp. 1--8, 1994.

J. Hurink, B. Jurisch, and M. J. O.-R.-S. Thole, "Tabu search for the job-shop scheduling problem with multi-purpose machines," vol. 15, no. 4, pp. 205-215, 1994.

F. H. a. T. G.L., ""Probabilistic learning combinations of local job shop scheduling rules"," In Industrial Scheduling,J.F. Muth and G.L. Thompson (Eds), pp. 225–251, 1993. Englewood Cliffs, NJ: Prentice-Hall.

A. Alaidi, O. Yahya, and H. Alrikabi, "Using Modern Education Technique in Wasit University," 2020.

Ahmed T. Sadiq Al-Obaidi and Samer Alaa Hussein, ""An Improved Artificial Fish Swarm Algorithm to Solve Flexible Job Shop Scheduling"," New Trends in Information & Communications Technology Applications (NTICT). 2017.

H. S. A. A. T. Sadiq Al-Obaidi, and zied O. Ahmed, " “Camel Herds Algorithm: a New Swarm Intelligent Algorithm to Solve Optimization Problems”,," IJPCC,, vol. vol. 3, no. 1, May 2017.




DOI: http://dx.doi.org/10.21533/pen.v8i3.1563

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Saif Ali Abd Alradha Alsaidi, Dena Kadhim Muhsen, Sura Mazin Ali

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN: 2303-4521

Digital Object Identifier DOI: 10.21533/pen

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License