Дискретный алгоритм оптимизации на основе распределения вероятностей с трансформацией целевых значений

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Оптимизационные задачи поиска в дискретном пространстве и, в частности, бинарном, где переменная может принимать только два значения, имеют большое прикладное значение. В статье предлагается новый популяционный алгоритм дискретной оптимизации, основанный на распределениях вероятностей переменных. Распределения определяют вероятность выбора дискретных значений переменных при поиске и формируются с помощью трансформации целевых значений решений в их весовые коэффициенты. Работоспособность алгоритма оценивалась на унимодальных и мультимодальных тестовых функциях с бинарными переменными. Результаты эксперимента показали высокую эффективность предлагаемого алгоритма на оценках сходимости и стабильности.

Полный текст

Доступ закрыт

Об авторах

К. С. Сарин

Томский государственный университет систем управления и радиоэлектроники

Автор, ответственный за переписку.
Email: sarin.konstantin@mail.ru
Россия, 634510 Томск, ул. Ленина, д. 40

Список литературы

  1. Aly R.H.M., Rahouma K.H., Hamed H.F. Brain Tumors Diagnosis and Prediction Based on Applying the Learning Metaheuristic Optimization Techniques of Particle Swarm, Ant Colony and Bee Colony. Procedia Computer Science. 2019. V. 163. P. 165–179.
  2. Ходашинский И.А., Смирнова И.Н., Бардамова М.Б., Сарин К.С., Светлаков М.О., Зайцев А.А., Тицкая Е.В., Тонкошкурова А.В., Антипова И.И., Ходашинская А.И., Зарипова Т.Н. Метод нахождения подмножеств согласованных признаков при прогнозировании эффективности реабилитации пациентов после перенесенной коронавирусной инфекции // Сибирский журнал клинической и экспериментальной медицины. T. 38. № 4. С. 270–279.
  3. Phogat M. Kumar D. Classification of complex diseases using an improved binary cuckoo search and conditional mutual information maximization. Computacion y Sistemas. 2020. V. 24. P. 1121–1129.
  4. Houssein E.H., Ibrahim I.E., Neggaz N., Hassaballah M., Wazery Y.M. An efficient ECG arrhythmia classification method based on Manta ray foraging optimization. Expert Systems with Applications. 2021. V. 181. P. 115131.
  5. Aytimur A., Babayigit B. Binary Artificial Bee Colony Algorithms for {0–1} Advertisement Problem. Proceedings of the 2019 6th International Conference on Electrical and Electronics Engineering (ICEEE), Istanbul, Turkey, 16–17 April 2019. P. 91–95.
  6. Mohammadzadeh A., Masdari M., Gharehchopogh F.S., Jafarian A. Improved chaotic binary grey wolf optimization algorithm for workflow scheduling in green cloud computing. Evolutionary Intelligence. 2021. V. 14. P. 1997–2025.
  7. Pirozmand P., Ebrahimnejad A., Alrezaamiri H., Motameni H. A novel approach for the next software release using a binary artificial algae algorithm. Journal of Intelligent and Fuzzy Systems. 2021. V. 40. P. 5027–5041.
  8. Almonacid B., Aspee F., Soto, R., Crawford B., Lama J. Solving the manufacturing cell design problem using the modified binary firefly algorithm and the egyptian vulture optimisation algorithm. IET Software. 2017. V. 11. P. 105–115.
  9. Ходашинский И.А., Сарин К.С. Отбор классифицирующих признаков с помощью популяционного случайного поиска с памятью. Автоматика и телемеханика. 2019. № 2. С. 161–172.
  10. Ходашинский И.А., Сарин К.С. Отбор классифицирующих признаков: сравнительный анализ бинарных метаэвристик и популяционного алгоритма с адаптивной памятью // Программирование. 2019. № 5. С. 3–9.
  11. Sarin K., Hodashinsky I., Slezkin A. Feature selection and identification of fuzzy classifiers based on the cuckoo search algorithm. Communications in Computer and Information Science. 2018. V. 934. P. 22–34.
  12. El-Dakroury H.E.D.M., Gad A., Abdelaziz A.Y. Load Restoration in Primary Distribution Networks Using the Binary Particle Swarm Optimization. Proceedings of the 2019 IEEE Electrical Power and Energy Conference (EPEC), Ottawa, ON, Canada, 12–14 October 2016. P. 1–6.
  13. Xiong G., Shi D., Zhang J., Zhang Y. A binary coded brain storm optimization for fault section diagnosis of power systems. Electric Power Systems Research. 2018. V. 163. P. 441–451.
  14. Dahi Z.A.E.M., Mezioud C., Draa A. A 0–1 bat algorithm for cellular network optimisation: A systematic study on mapping techniques. International Journal of Reasoning-based Intelligent Systems. 2017. V. 9. P. 22–42.
  15. Hussien A.G., Hassanien A.E., Houssein E.H., Amin M., Azar A.T. New binary whale optimization algorithm for discrete optimization problems. Engineering Optimization. 2020. V. 52. P. 945–959.
  16. Mourad K., Boudour R. A modified binary firefly algorithm to solve hardware/software partitioning problem. Informatica. 2021. V. 45. P. 1–12.
  17. Kennedy J., Eberhart R.C. A discrete binary version of the particle swarm algorithm. Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation, Orlando, FL, USA, 12–15 October 1997. 1997. V. 5. P. 4104–4108.
  18. Serigne G., Philippe M. A linearization framework for unconstrained quadratic (0–1) problems. Discrete Applied Mathematics. 2009. V. 157. P. 1255–1266.
  19. Sherali H.D., Driscoll P.J. Evolution, and state-of-the-art in integer programming. Journal of Computational and Applied Mathematics. 2000. V. 124. P. 319–340.
  20. Ходашинский И.А. Методы повышения эффективности роевых алгоритмов оптимизации // Автоматика и телемеханика. 2021. № 6. С. 3–45.
  21. Gendreau M., Potvin J.-Yv. (Eds.) Handbook of methaheuristics. Springer, 2019, 604 p.
  22. Карпенко А.П. Методы повышения эффективности метаэвристических алгоритмов глобальной оптимизации // Математические методы в технике и технологиях – ММТТ. 2017. Т. 1. С. 77–83.
  23. Курейчик В.В., Родзин С.И. Биоэвристики, инспирированные фауной (обзор) // Информационные технологии. 2023. Т. 29. № 11. С. 559–573.
  24. Pardalos P.M., Rasskazova V., Vrahatis M.N. (Eds.) Black box optimization, machine learning, and no-free lunch theorems. Springer, 2021. 388 p.
  25. Wolpert D.H., Macready W.G. No free lunch theorems for optimization. IEEE. Transactions on Evolutionary Computation. 1997. V. 1. P. 67–82.
  26. Becerra-Rozas M., Lemus-Romani J., Cisternas-Caneo F., Crawford B., Soto R., Astorga G., Castro C., Garcia J. Continuous Metaheuristics for Binary Optimization Problems: An Updated Systematic Literature Review. Mathematics. 2022. V. 11. № 1. P. 129.
  27. Бардамова М.Б., Буймов А.Г., Тарасенко В.Ф. Способы адаптации алгоритма прыгающих лягушек к бинарному пространству поиска при решении задачи отбора признаков // Доклады Томского государственного университета систем управления и радиоэлектроники. 2020. Т. 23. № 4. С. 57–62.
  28. Mirjalili S., Lewis A. S-shaped versus V-shaped transfer functions for binary Particle Swarm Optimization. Swarm and Evolutionary Computation. 2013. V. 9. P. 1–14.
  29. Turkoglu B., Uymaz S.A., Kaya E. Binary Artificial Algae Algorithm for feature selection. Applied Soft Computing. 2022. V. 120. P. 108630.
  30. Pashaei E., Pashaei E. An efficient binary chimp optimization algorithm for feature selection in biomedical data. Neural Computing and Applications. 2022. V. 34. P. 6427–6451.
  31. Jain S., Dharavath R. Memetic salp swarm optimization algorithm based feature selection approach for crop disease detection. Journal of Ambient Intelligence and Humanized Computing. 2023. V. 14. – P. 1817–1835.
  32. Mohd Yusof N., Muda A.K., Pratama S.F., Abraham A. A novel nonlinear time-varying sigmoid transfer function in binary whale optimization algorithm for descriptors selection in drug classification. Molecular Diversity. 2023. V. 27. № 1. P. 71–80.
  33. Merikhi B., Soleymani M. Automatic data clustering framework using nature-inspired binary optimization algorithms. IEEE Access. 2021. V. 9. P. 93703–93722.
  34. Zhong C., Chen Y., Peng J. Feature selection based on a novel improved tree growth algorithm. International Journal of Computational Intelligence Systems. 2020. V. 13. P. 247–258.
  35. Pandey A.C., Rajpoot D.S., Saraswat M. Feature selection method based on hybrid data transformation and binary binomial cuckoo search. Journal of Ambient Intelligence and Humanized Computing. 2020. V. 11. P. 719–738.
  36. Yepes V., Marti J.V., Garcia J. Black hole algorithm for sustainable design of counterfort retaining walls. Sustainability. 2020. V. 12. P. 2767.
  37. Lai X., Hao J.K., Fu Z.H., Yue D. Diversity-preserving quantum particle swarm optimization for the multidimensional knapsack problem. Expert Systems with Applications. 2020. V. 149. P. 113310.
  38. Barani F., Mirhosseini M., Nezamabadi-Pour H. Application of binary quantum-inspired gravitational search algorithm in feature subset selection. Applied Intelligence. 2017. V. 47. P. 304–318.
  39. Ross O.H.M. A review of quantum-inspired metaheuristics: Going from classical computers to real quantum computers. IEEE Access. 2019. V. 8. P. 814–838.
  40. Shreem S.S., Turabieh H., Al Azwari S., Baothman F. Enhanced binary genetic algorithm as a feature selection to predict student performance. Soft Computing. 2022. V. 26. P. 1811–1823.
  41. Nicolau M. Application of a simple binary genetic algorithm to a noiseless testbed benchmark. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers. 2009. P. 2473–2478.
  42. Haupt R.L., Haupt S.E. Practical genetic algorithms. John Wiley & Sons, Inc., Hoboken, New Jersey, 2004. 253 p.
  43. Ghosh M., Guha R., Alam I., Lohariwal P., Jalan D., Sarkar R. Binary Genetic Swarm Optimization: A Combination of GA and PSO for Feature Selection. Journal of Intelligent Systems. 2019. V. 29. P. 1598–1610.
  44. Bas E., Ulker E. A binary social spider algorithm for continuous optimization task. Soft Computing. 2020. V. 24. P. 12953–12979.
  45. Mirjalili S., Mirjalili S.M., Yang X.-S. Binary bat algorithm. Neural Computing and Applications. 2014. V. 25. P. 663–681.
  46. Pan J.-S., Hu P., Chu S.-C. Binary fish migration optimization for solving unit commitment. Energy. 2021. V. 226. P. 120329.
  47. Derrac J., Garcia S., Molina D., Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation. 2011. V. 1. P. 3–18.
  48. Garcia S., Molina D., Lozano M., Herrera F. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization. Journal of Heuristics. 2009. V. 15. № 6. P. 617–644.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Рис. 1. Блок-схема алгоритма.

Скачать (53KB)
Метаданные
3. Рис. 2. Графики функций трансформаций для перевода целевых значений в веса решений.

Скачать (16KB)
Метаданные
4. Рис. 3. Графики тестовых функций в двумерном пространстве поиска.

Скачать (86KB)
Метаданные
5. Рис. 4. Перевод бинарного вектора решения в непрерывный вектор для вычисления значения целевой функции.

Скачать (26KB)
Метаданные
6. Рис. 5. Графики сходимости алгоритмов.

Скачать (78KB)
Метаданные

© Российская академия наук, 2024