USING OF EVOLUTIONAL ALGORITHMS FOR SEARCHING OPTIMAL CLASSIFICATIONS

  • I. V. Kozin Zaporizhzhia National University
  • Ye. K. Selyutin Zaporizhzhia National University
Keywords: classification, evolutionary algorithm, genetic algorithm, crossing, mutation, selection

Abstract

The article discusses the task of classification, the need to fulfill conditions and relations on the set. The relevance of the fragmentary structure of the task was emphasized. It was illustrated an example of a classification problem that will be considered in this paper, and the task of covering stars with stars that occurs in many economic applications. As elementary fragments all edges appear to the graph. The conditions for joining an edge – this edge is the beam of an already existing star or has no common vertices with already built-up stars of coverage. The emphasis is on the lack of optimality of such a solution. The relevance of the fragmentary structure of the task was emphasized. The possibility of constructing classes is given, considering the entire list of objects classified in a certain sequence. Based on the fragmentary structure, it is proposed to use an evolutionary algorithm. The work analyzed the examples of the practical application of the evolutionary (genetic) algorithm for solving the classification problems. The prospect of using a genetic algorithm for finding optimal classifications is estimated. The following is a step-by-step sequence of operations of the genetic algorithm with examples: selection, crossing, mutation, selection. Examples of key operators, namely crossover and mutations, are given. The detailed algorithm of the evolutionary model is clearly illustrated. The principle of the evolutionary-fragmentary algorithm is written in detail. As a set of admissible solutions, a subset of maximal fragments on a given fragmentary structure is considered. The mechanism of testing the quality of the genetic algorithm on a fragmentary structure, which is reduced to the enumeration of many variants, is determined.

References

1. Скобцов Ю. А. Основы эволюционных вычислений: учеб. пособ. Донецк: ДонНТУ, 2008. 326 с.
2. Kozin I. V. Maksyshko N. K., Perepelitsa V. A. Fragmentary Structures in Discrete Optimization Problems. Cybernetics and Systems Analysis November. 2017. Vol. 53. Р. 931–936.
3. Козин И. В., Батовский С. Е., Сардак В. И. Фрагментарная модель и эволюционный алгоритм 2d упаковки объектов. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. 2017. Вип. 15. С. 74–79.
4. Козин И. В., Кривцун Е. В., Пинчук В. П. Эволюционно-фрагментарная модель задачи трассировки. Кибернетика и системный анализ. 2015. № 3. C. 35–50.
5. Козин И. В., Полюга С. И. Фрагментарные модели для некоторых экстремальных задач на графах. Математические машины и системы. 2014. № 1. С. 143–150.
6. Зенкин А. А., Зенкин А. И. Задача построения оптимальных классификаций. Сборник работ по математической кибернетике ВЦ АН СССР. 2010. С. 20–33.
7. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов (статистические проблемы обучения). Москва: Наука, 1974. 313 с.
8. Журавлев Ю. И. Избранные научные труды. Москва: Изд-во Магистр, 1998. 360 с.
9. Айвазян С. А., Бухштабер В. М. Прикладная статистика: Классификация и снижение раз-мерности. Москва: Финансы и статистика, 1989. 276 c.
10. Айзерман М. А., Браверманн Э. М. Метод потенциальных функций в теории обучения машин. Москва: Наука, 1970. 356 с.
11. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999. 250 с.
12. Мазуров В. Д. Метод комитетов в задачах оптимизации и классификации. Москва: Наука, 1990. 290 с.
13. Растригин Л. А., Эренштейн Р. Х. Метод коллективного распознавания. Москва: Энергоиздат, 1981. 325 с.
14. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Addison Wesley Longman, 1989. 293 p.
15. Перепелиця В. О., Козін І. В., Терещенко Е. В. Задачі класифікації: підходи, методи, алгоритми. Запоріжжя: Поліграф, 2008. 188 с.
16. Максишко Н. К., Заховалко Т. В. Моделі та методи розв’язання прикладних задач покриття на графах та гіперграфах. Запоріжжя: Полиграф, 2009. 244 с.
17. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor. MI: University of Michigan Press, 1975. 300 p.
Published
2020-03-02
How to Cite
Kozin, I. V., & Selyutin, Y. K. (2020). USING OF EVOLUTIONAL ALGORITHMS FOR SEARCHING OPTIMAL CLASSIFICATIONS. Bulletin of Zaporizhzhia National University. Physical and Mathematical Sciences, (2), 62-68. Retrieved from http://journalsofznu.zp.ua/index.php/phys-math/article/view/238