Розробка удосконаленого алгоритму розкиданого пошуку з використанням дискретно-хаотичної карти кота Арнольда

Автор(и)

DOI:

https://doi.org/10.15587/1729-4061.2021.234915

Ключові слова:

розкиданий пошук, карта кота Арнольда, хаотичний, ЗК, метаевристика, завдання оптимізації

Анотація

Вирішення задач оптимізації є предметом постійно зростаючого інтересу з величезною кількістю алгоритмів. Прикладами таких алгоритмів є розкиданий пошук (РП) і генетичні алгоритми. Зміна та вдосконалення алгоритмів може здійснюватися шляхом додавання різноманітності та орієнтованості. Хаотичні карти досить чутливі до початкової точки, що означає, що навіть невелика зміна значення початкової точки призведе до різкої зміни послідовності, створюваної хаотичною картою кота Арнольда. Карта кота Арнольда – це техніка хаотичної карти, яка надає довгі неповторювані випадкові послідовності. 

Хаотичні карти відіграють важливу роль у вдосконаленні алгоритмів еволюційної оптимізації та метаевристики, уникаючи локальних оптимумів та прискорюючи збіжність. У даній роботі пропонується реалізація алгоритму розкиданого пошуку з комівояжером в якості прикладу, реалізується і порівнюється розроблений гіпер-метод розкиданого пошуку по карті кота Арнольда (РПККА) з традиційним алгоритмом розкиданого пошуку. РПККА – це гіпер-алгоритм розкиданого пошуку з хаотичним алгоритмом карти кота Арнольда. Розкиданий пошук по карті кота Арнольда показує багатообіцяючі результати за рахунок зменшення кількості ітерацій, необхідних для алгоритму розкиданого пошуку для отримання оптимального рішення (рішень). У даній роботі для демонстрації результатів модифікованого алгоритму розкиданого пошуку по карті кота Арнольда (РПККА) реалізована задача комівояжера, яка є популярним і добре відомим прикладом оптимізації. Реалізація обох алгоритмів здійснюється з однаковими параметрами: розмір популяції, кількість міст, максимальна кількість ітерацій, розмір еталонного набору і т.д. Результати показують поліпшення модифікованого алгоритму за кількістю ітерацій, необхідних для РП, зі скороченням ітерацій на 10–46 % і поліпшенням часу отримання рішень зі скороченням часу на 65 %.

Біографії авторів

Amaal Ghazi Hamad Rafash, Al Ma’moon University College

PhD, Lecturer

Department of Computer Science

Enas Mohammed Hussein, Al- Mustansiriyah University

PhD, Lecturer

Department of Computer Science

Al-Sharify Mushtaq Talib, Taras Shevchenko National University of Kyiv

PhD, Assistant

Department of Radio Engineering and Radio Electronics Systems

Посилання

  1. AlObaidi, A. T. S., Hamad, A. G. (2010). BSA: A Hybrid Bees’ Simulated Annealing Algorithm To Solve Optimization & NP-Complete Problems. Engineering And Technology Journal, 28 (2), 271–281.
  2. Saeed, E. M. H., Hammood, B. A. (2021). Estimation and evaluation of Students’ behaviors in E-learning Environment using adaptive computing. Materials Today: Proceedings. Elsevier. doi: http://doi.org/10.1016/j.matpr.2021.04.519
  3. Woźniak, M., Połap, D. (2017). Hybrid neuro-heuristic methodology for simulation and control of dynamic systems over time interval. Neural Networks, 93, 45–56. doi: http://doi.org/10.1016/j.neunet.2017.04.013
  4. Brociek, R., Słota, D. (2016). Application and comparison of intelligent algorithms to solve the fractional heat conduction inverse problem. Information Technology And Control, 45 (2), 184–194. doi: http://doi.org/10.5755/j01.itc.45.2.13716
  5. AlSudani, H. A., Hussain, E. M., Khalil, E. A. (2020). Classification the Mammograms Based on Hybrid Features Extraction Techniques Using Multilayer Perceptron Classifier. Al-Mustansiriyah Journal of Science, 31 (4), 72–79. doi: http://doi.org/10.23851/mjs.v31i4.902
  6. Stallings, W. (2013). Cryptography and Network Security: Principles and Practice. Pearson, 752.
  7. Bassham, L. E., Rukhin, A. L., Soto, J., Nechvatal, J. R., Smid, M. E., Barker, E. B. et. al. (2010). A statistical test suite for random and pseudorandom number generators for cryptographic applications. Gaithersburg, 131. doi: http://doi.org/10.6028/nist.sp.800-22r1a
  8. Brown, R. G. (2020). Dieharder: A Random Number Test Suite. Available at: http://webhome.phy.duke.edu/~rgb/General/dieharder.php
  9. Saeed, E. M. H., Hammood, B. A. (2021). Article Review: Survey Fuzzy Logic and Aprior Algorithms Employed for E-learning Environment. Turkish Journal of Computer and Mathematics Education, 12 (9), 1393–1402.
  10. Brownlee, J. (2012). Clever Algorithms: Nature-Inspired Programming Recipes. Lulu, 436.
  11. Borisenko, A., Gorlatch, S. (2018). Comparing GPU-parallelized metaheuristics to branch-and-bound for batch plants optimization. The Journal of Supercomputing, 75 (12), 7921–7933. doi: http://doi.org/10.1007/s11227-018-2472-9
  12. Abdulelah, A. J., Shaker, K., Sagheer, A. M., Jalab, H. A. (2017). A Dynamic Scatter Search Algorithm for Solving Traveling Salesman Problem. 9th International Conference on Robotic, Vision, Signal Processing and Power Applications. Lecture Notes in Electrical Engineering LNEE. Singapore: Springer, 398, 117–124. doi: http://doi.org/10.1007/978-981-10-1721-6_13
  13. Sagheer, A. M., Sadiq, A. T., Ibrahim, M. S. (2012). Improvement of scatter search using Bees Algorithm. 2012 6th International Conference on Signal Processing and Communication Systems. Gold Coast. doi: http://doi.org/10.1109/icspcs.2012.6507943
  14. Souza, D. S., Santos, H. G., Coelho, I. M. (2017). A Hybrid Heuristic in GPU-CPU Based on Scatter Search for the Generalized Assignment Problem. Procedia Computer Science, 108, 1404–1413. doi: http://doi.org/10.1016/j.procs.2017.05.188
  15. Prerna, D., Bhawna, K. (2015). Image Encryption Using Arnold’s Cat Map and Logistic Map for Secure Transmission. International Journal of Computer Science and Mobile Computing, 4 (6), 194–199.
  16. Shrivastava, S. (2011). A Novel 2D Cat Map based Fast Data Encryption Scheme. International Journal of Electronics and Communication Engineering, 4 (2), 217–223.
  17. Meymand, M. Z., Rashidinejad, M., Khorasani, H., Rahmani, M., Mahmoudabadi, A. (2012). An Implementation of Modified Scatter Search Algorithm to Transmission Expansion Planning. Turkish Journal of Electrical Engineering Computer Sciences, 20 (1), 1206–1219.
  18. Laguna, M., Martí, R. (2003). Scatter Search Methodology and Implementations in C. Research/Computer Science Interfaces Series ORCS Vol. 24. Erratum E1. Springer. doi: http://doi.org/10.1007/978-1-4615-0337-8
  19. Yas, R. M. (2017). Permuting Convergence Overcoming of Genetic Algorithm Using Arnold Cat Map. International Journal of Science and Research, 6 (5), 2588–2590.
  20. AlObaidi, A. T. S., Hamad, A. G. (2012). Exploration-Balanced Bees Algorithms to Solve Optimization and NP-Complete Problems. International Journal of Research and Reviews in Soft and Intelligent Computing, 2 (1), 108–113.
  21. Mohammed, R. S., Hussien, E. M., Mutter, J. R. (2016). A novel technique of privacy preserving association rule mining. 2016 Al-Sadeq International Conference on Multidisciplinary in IT and Communication Science and Applications (AIC-MITCSA), 1–6. doi: http://doi.org/10.1109/aic-mitcsa.2016.7759930
  22. Gilbert, N. (1993). Analyzing Tabular Data: Loglinear and Logistic Models for Social Researchers. London: UCL Press, 196.
  23. Dorian, G. (2004). Natural Algorithms for Optimisation Problems. Imperial College, 143.
  24. Yas, R. M., Hashem, S. H. (2020). Unequal clustering and scheduling in Wireless Sensor Network using Advance Genetic Algorithm. Journal of Physics: Conference Series, 1530, 012076. doi: http://doi.org/10.1088/1742-6596/1530/1/012076
  25. Yas, R. M., Hashem, S. H. (2020). A Survey on Enhancing Wire/Wireless Routing Protocol Using Machine Learning Algorithms. IOP Conference Series: Materials Science and Engineering, 870, 012037. doi: http://doi.org/10.1088/1757-899x/870/1/012037

##submission.downloads##

Опубліковано

2021-12-16

Як цитувати

Rafash, A. G. H., Saeed, E. M. H., & Talib, A.-S. M. (2021). Розробка удосконаленого алгоритму розкиданого пошуку з використанням дискретно-хаотичної карти кота Арнольда. Eastern-European Journal of Enterprise Technologies, 6(4 (114), 15–20. https://doi.org/10.15587/1729-4061.2021.234915

Номер

Том 6 № 4 (114) (2021): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2021 Amaal Ghazi Hamad Rafash, Enas Mohammed Hussein Saeed, Al-Sharify Mushtaq Talib

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.