АЛГОРИТМ МОДЕЛИРОВАНИЯ ПОВЕДЕНИЯ МУРАВЬИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КЛАСТЕРИЗАЦИИ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ДИНАМИЧЕСКОГО КОДИРОВАНИЯ

  • Ю.А. Кравченко Южный Федеральный Университет
  • А. Н. Нацкевич Южный Федеральный Университет
Ключевые слова: Кластеризация, эволюционное моделирование, роевые алгоритмы, машинное обучение, биоинспирированные алгоритмы

Аннотация

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

Литература

1. Ka-Chun Wong. A Short Survey on Data Clustering Algorithms // IEEE Second International Conference on Soft Computing and Machine Intelligence, 2015.
2. IBM Consumer products industry blog. Industry insights. – https://www.ibm.com/blogs/ in-sights-on-business/consumer-products/2-5-quintillion-bytes-of-data-created-every-day-how-does-cpg-retail-manage-it/ (дата обращения: 20.05.2019).
3. Mayr A, Binder H, Gefeller O, Schmid M. The Evolution of Boosting Algorithms – From Ma-chine Learning to Statistical Modelling // Methods Inf. Med. – 2014. – Vol. 53. – P. 419-427.
4. Зайцев А.А., Курейчик В.В., Полупанов А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2010. – № 12 (113). – С. 7-12.
5. Kureichik V.V., Kravchenko Y.A. Bioinspired algorithm applied to solve the travelling sales-man problem // World Applied Sciences Journal. – 2013. – Vol. 22, No. 12. – P. 1789-1797.
6. Gladkov L.A., Kureichik V.V., Kravchenko Y.A. Evolutionary algorithm for extremal subsets comprehension in graphs // World Applied Sciences Journal. – 2013. – Vol. 27, No. 9. – P. 1212-1217.
7. Курейчик В.В., Курейчик В.М., Сороколетов П.В. Анализ и обзор моделей эволюции // Известия РАН. Теория и системы управления. – 2007. – № 5. – С. 114-126.
8. Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик // Программные системы и вычислительные методы. – 2016. – № 2. – С. 158-172.
9. Курейчик В.В., Бова В.В., Курейчик Вл.Вл. Комбинированный поиск при проектировании // Образовательные ресурсы и технологии. – 2014. – № 2 (5). – С. 90-94.
10. Курейчик В.В., Курейчик Вл.Вл. Биоиспирированный поиск при проектировании и управлении // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 178-183.
11. Кравченко Ю.А., Нацкевич А.Н. Модель решения задачи кластеризации данных на осно-ве использования бустинга алгоритмов адаптивного поведения муравьиной колонии и k-средних // Известия ЮФУ. Технические науки. – 2017. – № 7 (192). – С. 90-102
12. Кравченко Ю.А., Нацкевич А.Н., Курситыс И.О. Бустинг биоинспирированных алгорит-мов для решения задачи кластеризации // Международная конференция по мягким вы-числениям и измерениям. – 2018. – Т. 1. – С. 777-780.
13. Donkuan, X. Yingjie T. A comprehensive survey of clastering algorithms // Annals of Data Science. – 2015. – Vol. 2, Issue 2. – P. 165-193.
14. Survay of clustering algorithms. – https://scholarsmine.mst.edu/cgi/viewcontent. cgi?article=1763&context=ele_comeng_facwork (дата обращения: 25.05.2019).
15. Data clustering using particle swarm optimization. – http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.468.819&rep=rep1&type=pdf (дата обращения: 20.05.2019).
16. Chretien. Organisation Spatiale du Materiel Provenant de L’excavation du nidchez Messor Barbarus et des Cadavres d’ouvrieres chez Lasius niger (Hymenopterae: Formicidae), Ph.D. thesis, Universite Libre dr Bruxelles, 1996.
17. Lumer and B. Faieta. Diversity and adaptation in Populations of ClusteringAnts // in Third international Conference on simulation of Adaptive Behavior: Fromanimals to Animats. – MIT Press, Cambridge, 1994. – Vol. 3. – P. 489-508.
18. Курейчик В.М., Курейчик В.В., Родзин С.И.Модели параллелизма эволюционных вы-числений // Вестник Ростовского государственного университета путей сообщения. – 2011. – № 3 (43). – С. 93-97.
19. Курейчик В.М., Курейчик В.В., Родзин С.И., Гладков Л.А. Основы теории эволюционных вычислений. – Ростов-на-Дону: ЮФУ, 2010.
20. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации // Кибернетика и програм-мирование. – 2017. – № 3. – С. 51-79.
Опубликован
2019-09-24
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ