КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 23-21-00089
НазваниеЭффективные биоэвристики, инспирированные животным миром, на основе выявления паттернов поведения для задач оптимизации многомерных функций и сегментации изображений
Руководитель Родзин Сергей Иванович, Кандидат технических наук
Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Южный федеральный университет" , Ростовская обл
Конкурс №78 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-210 - Проблемно-ориентированные алгоритмы
Ключевые слова инспирированная животным миром биоэвристика, сходимость алгоритма, диверсификация пространства поиска решений, популяция, фитнес-функция, бенчмаркинг, оптимизация
Код ГРНТИ28.23.19
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Биоэвристики, являясь классом методов машинного обучения, представляют собой стратегии, которые «управляют» процессом поиска решений, используя инспирированные природой механизмы самоорганизации, варьирующиеся от простых итеративных процедур стохастического поиска до сложных процессов обучения. Проект направлен на решение научной проблемы, связанной с установлением баланса между скоростью сходимости роевых биоэвристик и диверсификацией пространства поиска оптимальных решений на основе выявления паттернов индивидуального и коллективного поведения агентов, а также разработки вычислительных моделей и эффективных алгоритмов для решения оптимизационных задач.
Актуальность выявления паттернов индивидуального и коллективного поведения агентов, инспирированных животным миром, в том, что они позволяют улучшить баланс между скоростью сходимости алгоритма и диверсификацией пространства поиска решений. Это открытая исследовательская проблема, имеющая важное значение для обеспечения точности и производительности алгоритмов оптимизации в таких областях как распознавание образов, информационная безопасность, инженерное проектирование, интеллектуальный анализ данных, цифровая экономика. Активный интерес к этой проблеме наблюдается на международном уровне – многочисленные конференции, на которых докладываются теоретические и практические попытки изменить положение дел с этой проблемой, что подчеркивает актуальность проблемы.
Целью проекта является развитие новой для научного коллектива тематики путем разработки эффективных алгоритмов на основе выявления паттернов поведения биологических агентов для задач оптимизации многомерных функций и сегментации изображений. Эффективность планируется достичь за счет установления баланса между скоростью сходимости биоэвристик и диверсификацией пространства поиска решений оптимизационных задач.
Анализ современного состояния исследований по данной проблеме показывает, что в существующих биоэвристиках этот баланс, зачастую, слабо выражен, к тому же отсутствуют соответствующие инструменты измерения этого баланса, позволяющие понять, как влияют механизмы поиска оптимального решения на результаты работы алгоритма. Еще один фактор, влияющий на баланс – выбор параметров алгоритма для управления балансом.
По результатам выполнения проекта будут получены новые данные о таких характеристиках биоэвристик как скорость сходимости, вычислительная трудоемкость, требуемый объем памяти, настройка параметров алгоритма, трудность программной реализации. Для эффективного решения задач оптимизации многомерных мультиэкстремальных функций и сегментации изображений будут разработаны новые вычислительной модели «стая хищников – стадо травоядных», коллаборативного поведения колонии пауков, индивидуального и коллективного поведения саранчи, стаи животных в поисках пищи. Эти вычислительные модели и выявленные паттерны поведения агентов будут положены в основу создания эффективных оптимизаторов с установленным балансом между скоростью сходимости алгоритма и диверсификацией пространства поиска решений. Речь идет о равновесии между способностью алгоритма находить новые, хорошие решения и возможностью алгоритма достигать оптимума целевой функции или подходить достаточно близко к нему за конечное число шагов. Будут созданы программные приложения и проведена экспериментальная проверка биоэвристик на бенчмарках многомерных функций путем сравнения с конкурирующими алгоритмами по показателям производительности и обоснования статистической значимости результатов.
По результатам проекта предполагается создание научного задела для решения прикладных оптимизационных задач в области цифровой обработки изображений и компьютерного зрения, анализа и обработки данных, поиска информации, инженерного проектирования, энергоменеджмента, медицинской диагностики.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Публикации
1.
Родзин С.И.
Коэволюционный самонастраивающийся алгоритм оптимизации
Вестник ВГУ. Серия: Системный анализ и информационные технологии, №1 (2023), стр. 16-27 (год публикации - 2023)
10.17308/sait/1995-5499/2023/1/16-27
2.
Родзин С.И., Родзина Л.С.
Spider Colony Optimization Algorithm: A Bio-Heuristic for Global Optimization Problem
CSOC 2023. Lecture Notes in Networks and Systems,, стр. 661–669 (год публикации - 2023)
10.1007/978-3-031-35311-6_63
3.
Родзин С.И., Кулиев Э.В., Запорожец Д.Ю., Родзина Л.С., Родзина О.Н.
Locust Swarm Optimization Algorithm: A Bio-Heuristic for Global Optimization Problem
Lecture Notes in Networks and Systems, стр. 670–678 (год публикации - 2023)
10.1007/978-3-031-35311-6_64
4.
Родзин С.И.
Модифицированный метаэвристический алгоритм синус-косинуса для многомерных задач глобальной оптимизации
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И ПРИНЯТИЕ РЕШЕНИЙ, №3, стр. 59-69 (год публикации - 2023)
10.14357/20718594230306
5.
Курейчик В.В., Родзин С.И.
Модель коллаборативного поведения роя саранчи для оптимизации многомерных многоэкстремальных функций
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ. СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. ТЕХНИЧЕСКИЕ НАУКИ, №1 (2023), стр. 10-16 (год публикации - 2023)
10.17213/1560-3644-2023-1-10-16
6.
Родзин С.И.
Современное состояние биоэвристик: классификация, бенчмаркинг, области применения
Известия ЮФУ. Технические науки, № 2 (2023), стр.280-298 (год публикации - 2023)
10.18522/2311-3103-2023-2-280-298
7. Родзин С.И. Биоэвристика колонии пауков: поисковый механизм и алгоритм оптимизации Труды межд. научно-технического конгресса "Интеллектуальные системы и информационные технологии - 2023" («ИС & ИТ-2023», «IS&IT’23»), Т.1. С. 161-174 (год публикации - 2023)
8.
Курейчик В.В., Родзин С.И.
Биоэвристики, инспирированные фауной (обзор)
Информационные технологии, Т. 29. № 11. С. 559-573 (год публикации - 2023)
10.17587/it.29.559-573
9. Эль-Хатиб С., Скобтцов Ю., Родзин С.И. DETERMINATION OF OPTIMAL HEURISTIC IMAGE SEGMENTATION COEFFICIENTS FOR MODIFIED ANT COLONY OPTIMIZATION METHOD FOR COMPLEXLY STRUCTURED IMAGES XXV Международная научно-техническая конференция «НЕЙРОИНФОРМАТИКА-2023», стр. 5456 (год публикации - 2023)
10. Кравченко Д.Ю., Кравченко Ю.А., Кулиев Э.В., Родзин С.И. , Родзина Л.С. The Swarm Bacterial Algorithm Based on New Attractive Operators and Patterns of Agent Behavior Computational Methods in Systems and Software 2023 (год публикации - 2023)
11. Родзина О.Н., Кравченко Д.Ю. Баланс между скоростью сходимости биоэвристики и диверсификацией пространства поиска решений (на примере модели роя саранчи) Труды межд. научно-технического конгресса "Интеллектуальные системы и информационные технологии" («ИС&ИТ-2023», «IS&IT’23»)., Т.1. С. 208-217. (год публикации - 2023)
12. Мансур А., Мохаммад Ж., Кравченко Ю.А., Кравченко Д.Ю., Силега Н. Harnessing key phrases in constructing a concept-based semantic representation of text using clustering techniques VIII International Congress on Artificial Intelligence and Pattern Recognition (IWAIPR 2023) (год публикации - 2023)
Аннотация результатов, полученных в 2024 году
В ходе выполнения Проекта в 2024 году:
1. Разработан и экспериментально исследован новый метод автоматической сегментации изображений с использованием паттернов индивидуального и коллективного поведения саранчи. Метод включает два новых механизма поиска, основанных на природных явлениях: операторы индивидуального и коллективного поведения саранчи. В отличие от методов, требующих больших объемов данных, предлагаемый метод саранчи может работать с ограниченными данными, способен итеративно улучшать параметры, находя оптимальные значения для задачи сегментации. Метод легко подстраивается на различные типы изображений, обеспечивая более точные и адаптивные результаты даже в сложных условиях, в отличие от конкурирующих подходов.
Основной целью экспериментов было сравнение способности выделять объекты на изображениях и отделять их от фона у предлагаемого метода и его конкурентов - алгоритмами пчелиной колонии и светлячковым. Использовались предварительно размеченные области объектов для каждого изображения как эталонные для сравнения с результатами сегментации.
По результатам экспериментов метод саранчи демонстрировал лучшие результаты по скорости сходимости, точности выделения объектов на изображении и четкости границ объектов.
2. Разработан и экспериментально исследована новая биоэвристика, инспирированная поведением колонии саранчи, для решения задачи сопоставления шаблонов, имеющей важное значение при обработке изображений в системах компьютерного зрения. Разработанная биоэвристика позволила проводить поиск на ограниченном подмножестве пикселей в плоскости изображения и существенно сократить количество оценок функций для измерения сходства, которые требуются для процесса сопоставления.
Поисковыми агентами в алгоритме являются особи в стае саранчи, которые взаимодействуют друг с другом на основе ряда роевых операторов. Разработанная поведенческая модель позволяет избежать концентрации агентов в текущих лучших позициях (решениях), что препятствует преждевременной сходимости.
Задача сопоставления состоит в том, чтобы учитывая исходное изображение и эталонное изображение, найти смещение в пределах области поиска такое, что сходство между сдвинутым опорным изображением и соответствующим шаблоном было максимальным.
Было разработано программное приложение для экспериментальной проверки биоэвристики на бенчмарках путем сравнения с конкурирующими методами по показателям производительности и точности. Результаты сравнивались с учетом нескольких показателей эффективности. Эксперименты показали, что разработанная биоэвристика обеспечивает значительно лучшие результаты по сравнению с алгоритмами PSO и ABC. Разработанная биоэвристика для сопоставления шаблонов превосходит конкурирующие методы по времени вычислений и дает значительно лучшие результаты с точки зрения качества решения.
3. Разработан и экспериментально исследован эффективный алгоритм АКПЖ, моделирующий коллективное поведение стаи животных в поисках пищи с использованием общей памяти для решения прикладных задач глобальной оптимизации. Поведенческая биологическая модель группы животных была использована при построении алгоритма коллективного поведения животных, включая новые операторы, реализующие передвижения агентов относительно ближайших соседей, случайные передвижения, а также обновление общей памяти при поиске оптимального решения.
Для оценки эффективности алгоритма в ходе экспериментов использовался набор из представительного множества тестовых унимодальных и мультиэкстремальных функций, а также результаты их тестирования конкурирующими метаэвристиками для многомерных задач глобальной оптимизации. Сравнение производительности алгоритма на тестовых функциях производилось с результатами, полученными с помощью генетического алгоритма, алгоритма роя частиц, алгоритм гравитационного поиска и алгоритма дифференциальной эволюции. Алгоритм показал лучшие результаты, нежели конкуренты на всех тестовых функциях. Также проводилось сравнение с одним из наиболее эффективных алгоритмов непрерывной оптимизации BFGS - квазиньютоновским итерационным алгоритмом численной оптимизации, предназначенным для нахождения экстремума нелинейных унимодальных функций без ограничений. При размерности функции, начиная с 70, результаты по алгоритму AКПЖ становились сопоставимыми с результатами BFGS.
АКПЖ также сравнивался по производительности с популярным методом мультистарта (MS) на множестве мультиэкстремальных функций по показателям среднего затраченного времени, среднего числа итераций и среднего наилучшего значения функции. Результаты свидетельствуют о преимуществе АКПЖ по времени и точности найденных решений.
4. Разработан и экспериментально исследован модифицированный метод, инспирированный поведением кукушек в процессе гнездового паразитизма, для решения задачи оценки эквивалентной семантической близости при анализе сходства онтологий. Метод предполагает, что начальные координаты гнезд и кукушек являются случайными, равномерно распределенными в пространстве вершин заданных онтологий. Кукушка свои передвижения осуществляет в виде полетов Леви. Доказано, что предлагаемый модифицированный метод кукушки имеет временную сложность O(n*n), где n – количество анализируемых методом входных данных.
Эксперименты показали, что предложенный модифицированный метод кукушки дает лучшие результаты по сравнению с конкурирующими бактериальным и обезьяньим методами. Высокая скорость работы предложенного метода обусловлена его стохастичностью, а необходимое качество получаемых решений – эффективностью поисковых процедур. Сравнение предлагаемого метода с методом роя частиц (PSO) также подтвердило его эффективность..
5. Сформулированы рекомендации по использованию всего комплекса разработанных вычислительных моделей и биоинспирированных алгоритмов для решения оптимизационных задач на основе выявления паттернов индивидуального и коллективного поведения животных.
Достигнуты все результаты второго года выполнения проекта. Опубликовано 6 статей в рецензируемых российских и зарубежных научных изданиях (3 проиндексированы в Scopus/WoS, 3 – в RSCI), а также 1 монография, 3 статьи, индексируемых в РИНЦ и 1 РИД (программа на ЭВМ). Результаты, полученные в ходе выполнения Проекта, представлены на 4-х международных конференциях и 1-й Всероссийской конференции.
Ссылки на информационные ресурсы в сети Интернет (url-адреса), посвященные проекту:
https://www.nkj.ru/prtnews/48153/
https://news-life.pro/350890887/
Публикации
1.
Родзин С.И.
Вычислительная модель коллективного поведения группы животных: эффективная биоэвристика для решения прикладных задач глобальной оптимизации
Известия ЮФУ. Технические науки, № 2 (238), стр. 6-16 (год публикации - 2024)
10.18522/2311-3103-2024-2-6-16
2.
Гладков Л.А., Кравченко Ю.A., Курейчик В.В., Родзин С.И.
Интеллектуальные системы: модели и методы метаэвристической оптимизации
ИД "Среда", 2024. - 228 с. , 224 стр. (год публикации - 2024)
10.31483/a-10639
3.
Родзин С.И.
Глобальная оптимизация на основе гибридизации алгоритмов роя саранчи и колонии пауков
Программные продукты и системы. 2024, Т. 37. № 2. С. 146–154 (год публикации - 2024)
10.15827/0236-235X.146.146-154
4.
Запорожец Д.Ю., Кравченко Ю.А., Кулиева Н.В., Семенова М.М., Кулиев Э.В.
Исследование эффективности алгоритма саранчи в задачах сегментации изображений
Программные продукты и системы., Т. 37. № 2. С. 238–246. (год публикации - 2024)
10.15827/0236-235X.142.238-246
5.
Кравченко Д.Ю., Кравченко Ю.А., Мансур А., Мохаммад Ж., Павлов Н.С.
АЛГОРИТМ ОПТИМИЗАЦИИ ИЗВЛЕЧЕНИЯ КЛЮЧЕВЫХ СЛОВ НА ОСНОВЕ ПРИМЕНЕНИЯ ЛИНГВИСТИЧЕСКОГО ПАРСЕРА
Информатика и автоматизация, Выпуск 23 (2), 2024: Информатика и автоматизация, стр. 467-494 (год публикации - 2024)
10.15622/ia.23.2.6
6.
Кравченко Ю.Ю., Родзин С.И., Кравченко Д.Ю., Родзина Л.С., Кулиев Э.В., Павлов Н.С.
Computational Model of Swarm Algorithm for Optimizing Process of Keywords Extraction from Text Information Presented as Graph
2024 7th International Conference on Information Technologies in Engineering Education (Inforino), 2024 7th International Conference on Information Technologies in Engineering Education (Inforino) (год публикации - 2024)
10.1109/Inforino60363.2024.10552028
7.
Родзин С.И., Родзина Л.С.
Hybrid algorithm of locust swarm and spider colony for global optimization problems
2024 7th International Conference on Information Technologies in Engineering Education (Inforino), 2024 7th International Conference on Information Technologies in Engineering Education (Inforino) (год публикации - 2024)
10.1109/Inforino60363.2024.10552010
8.
Родзин С.И., Боженюк А.В., Родзина Л.С.
Bioheuristics as tool for global optimization problem based on collective behavior model of animals
Conference: 2024 International Russian Automation Conference (RusAutoCon), том 2, страницы 420-425 (год публикации - 2024)
10.1109/rusautocon61949.2024.10694243
9. Родзин С.И. КВАНТОВО-ЭВОЛЮЦИОННЫЙ КОМПЬЮТИНГ Труды межд. научно-технического конгресса "Интеллектуальные системы и информационные технологии - 2024" («ИС & ИТ-2024», «IS&IT’24») , Т.1. С. 154-170. (год публикации - 2024)
Возможность практического использования результатов
Формирование научных и технологических заделов в рамках реализации мероприятий программы развития Передовой инженерной школы «Инженерия киберплатформ» Южного федерального университета, где создается уникальный экспериментальный полигон по проведению испытаний систем группового управления робототехническими комплексами.