ОСОБЛИВОСТІ ПОШУКУ ОПТИМАЛЬНИХ КЛАСИФІКАЦІЙ: ЕВОЛЮЦІЙНІ АЛГОРИТМИ
Анотація
Проаналізовано сутність задачі класифікації, а також необхідність виконання умов й відносин на множині. Зазначено властивості відношення еквівалентності. Наведено приклад задачі класифікації, який буде розглядатиметься у даній роботі, а саме: задача покриття графа зірками, яка виникає у багатьох економічних додатках. В якості елементарних фрагментів виступають усі ребра графа. Умови приєднання ребра – це ребро є променем вже існуючої зірки або не має спільних вершин із вже побудованими зірками покриття. Акцентована увага на недостатній оптимальності такого рішення. Була підкреслена актуальність фрагментарної структури задачі. Вказана можливість побудови класів, розглядаючи весь список об’єктів, що класифікуються у певній послідовності. На базі фрагментарної структури запропоновано використовувати еволюційний алгоритм. Були проаналізовані роботи, в яких розглядаються приклади практичного застосування еволюційного (генетичного) алгоритму для вирішення задач класифікації. Оцінена перспектива використання генетичного алгоритму для пошуку оптимальних класифікацій. Вказана поетапна послідовність операцій генетичного алгоритму з прикладами: відбір, схрещування, мутація, селекція. Наведені приклади роботи ключових операторів, а саме кросовера та мутації. Наочно проілюстрований детальний алгоритм еволюційної моделі. Детально описано принцип дії еволюційно-фрагментарного алгоритму. В якості множини допустимих рішень розглядається підмножина максимальних фрагментів на заданій фрагментарній структурі. Визначений механізм перевірки якості генетичного алгоритму на фрагментарній структурі, який зводиться до перебору багатьох варіантів.
Посилання
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.
ISSN 
