Discrete optimization algorithm based on probability distribution with transformation of target values

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Optimization problems of searching in discrete space and, in particular, binary space, where a variable can take only two values, are of great practical importance. This paper proposes a new population discrete optimization algorithm based on probability distributions of variables. Distributions determine the probability of accepting one or another discrete value and are formed by transforming the target values of decisions into their weighting coefficients. The performance of the algorithm was assessed using unimodal and multimodal test functions with binary variables. The experimental results showed the high efficiency of the proposed algorithm in terms of convergence and stability estimates.

Full Text

Restricted Access

About the authors

K. S. Sarin

Tomsk State University of Control Systems and Radioelectronics

Author for correspondence.
Email: sarin.konstantin@mail.ru
Russian Federation, Prospect Lenina 40, Tomsk, 634050

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Fig. 1. Block diagram of the algorithm.

Download (53KB)
Indexing metadata
3. Fig. 2. Graphs of transformation functions for converting target values ​​into decision weights.

Download (16KB)
Indexing metadata
4. Fig. 3. Graphs of test functions in a two-dimensional search space.

Download (86KB)
Indexing metadata
5. Fig. 4. Transformation of a binary solution vector into a continuous vector for calculating the value of the objective function.

Download (26KB)
Indexing metadata
6. Fig. 5. Graphs of convergence of algorithms.

Download (78KB)
Indexing metadata

Copyright (c) 2024 Russian Academy of Sciences