ВИКОРИСТАННЯ ЕВОЛЮЦІЙНИХ АЛГОРИТМІВ ПОШУКУ ОПТИМАЛЬНИХ КЛАСИФІКАЦІЙ
Анотація
Розглянута задача класифікації, необхідність виконання умов й відносин на множині. Указані властивості відношення еквівалентності. Наведений приклад задачі класифікації, який буде розглядатися в роботі, а саме задача покриття графа зірками, яка виникає в багатьох економічних додатках. Як елементарні фрагменти виступають усі ребра графа. Умови приєднання ребра –ребро є променем існуючої зірки або не має спільних вершин із уже побудованими зірками покриття. Акцентована увага на недостатній оптимальності такого рішення. Підкреслена актуальність фрагментарної структури задачі. Указана можливість побудови класів, розглядаючи весь список об’єктів, що класифікуються в певній послідовності. На базі фрагментарної структури запропоновано використовувати еволюційний алгоритм. Проаналізовані роботи, у яких розглядаються приклади практичного застосування еволюційного (генетичного) алгоритму для розв'язування задач класифікації. Оцінена перспектива використання генетичного алгоритму пошуку оптимальних класифікацій. Указана поетапна послідовність операцій генетичного алгоритму з прикладами: відбір, схрещування, мутація, селекція. Наведені приклади роботи ключових операторів, а саме кросовера та мутації. Наочно проілюстрований детальний алгоритм еволюційної моделі. Детально описано принцип дії еволюційно-фрагментарного алгоритму. Як множина допустимих розв'язків розглядається підмножина максимальних фрагментів на заданій фрагментарній структурі. Визначений механізм перевірки якості генетичного алгоритму на фрагментарній структурі, який зводиться до перебору багатьох варіантів.
Посилання
2. Kozin I. V., Maksyshko N.K. & Perepelitsa V.O. (2017). Fragmentary Structures in Discrete Optimization Problems. Cybernetics and Systems Analysis November, 53, 931–936.
3. Kozin I.V., Batovskiy S.E., & Sardak V.I. (2017). Fragmentarna model i evolutsijnii algorytm dlya 2d upakovki obyektiv [Fragmentary model and evolutionary algorithm for 2d object packaging]. Sat. Mathematical and computer model. Physico-mathematical sciences, 15, 74–79 [in Ukrainian].
4. Kozin I.V., Krivtsun E.V, & Pinchuk V.P. (2015). Evolutsijno-fragmentarna model zadachi trassirovki [Evolutionary fragmentary model of the trace problem]. Cybernetics and Systems Analysis, 3, 35–50 [in Ukrainian].
5. Kozin I.V., & Polyuga S.I. (2014). Fragmentarni modeli dlya deyakyh ekstremalnyh zadach na grafah [Fragmentary models for some extremal problems on graphs]. Mathematical machines and systems, 1, 143–150 [in Ukrainian].
6. Zenkin A.A. & Zenkin A.I. (2010) Zadacha postroenia optimalnyh klassifikatsij [The task of building optimal classifications]. Collection of papers on the mat. Cybernetics EC of the USSR, 20—33 [in Russian].
7. Vapnik V.N., & Chervonenkis A.Ya. (1974). Teorija rozpoznanya obrazov (statistichni problemi) [Theory of pattern recognition (statistical learning problems)]. M.: Science [in Russian].
8. Zhuravlev Yu. I. (1998). Izbranny nauchni trudi [Selected Scientific Works]. M: Publishing Master [in Russian].
9. Ayvazyan S. A., & Buchstaber V.M. (1989). Prykladna statistika: klassyfikatsia i znizhenya rozmirnosti [Applied statistics: Classification and reduction of dimension]. M.: Finance and Statistics [in Russian].
10. Aizerman M. A., & Bravermann E.M. (1970). Metod potentsijnyh funksii v teorii obuchenya mashin [The method of potential functions in the theory of learning machines]. M .: Science [in Russian].
11. Zagoruiko N. G. (1999). Prykladnye metody analiza dannyh i znanyi [Applied methods of data and knowledge analysis]. Novosibirsk: Publishing house of the Institute of mathematics [in Russian].
12. Mazurov V.D. (1990). Metod komitetov v zadachah optimizatsii i klasifikatsii [The method of committees in the tasks of optimization and classification]. M. : Science [in Russian].
13. Rastrigin LA, & Erenstein R.H. (1981). Metod kolektivnogo raspoznavanya [The method of collective recognition]. M .: Energoizdat [in Russian].
14. Goldberg D.E. (1989) Genetic algorithms in search, optimization, and machine learning. Addison Wesley Longman.
15. Perepelitsa V.O., Kozin I.V., & Tereshchenko I.V. (2008) Zadachi klasifikatsii: pidhody, metodi, algorytmi [Classification tasks: approaches, methods, algorithms]. Polіgraf, Zaporizhzhya [in Ukrainian].
16. Maksishko N. K., & Zakhovalko T.V. (2009) Modely ta metody rozvyazannya prykladnih zadach pokruttya na grafah i gipergrafah [A model of methods and application of applied problems of covering on graphs and hypergraphs]. Polіgraf, Zaporizhzhya [in Ukrainian].
17. Holland J. H. (1975) Adaptation in natural and artificial systems. Ann Arbor. MI: University of Michigan Press.
