Статья

Название статьи РОЕВОЙ АЛГОРИТМ ПОИСКОВОЙ ОПТИМИЗАЦИИ НА ОСНОВЕ МОДЕЛИРОВАНИЯ ПОВЕДЕНИЯ ЛЕТУЧИХ МЫШЕЙ
Автор Э.В. Кулиев, А.А. Лежебоков, Ю.А. Кравченко
Рубрика РАЗДЕЛ II. БИОИНСПИРИРОВАННЫЙ ПОИСК
Месяц, год 07, 2016
Индекс УДК УДК 519.6
DOI DOI 10.18522/2311-3103-2016-7-5362
Аннотация Работа посвящена решению ключевой проблемы искусственного интеллекта – разра-ботке новых эффективных эвристических механизмов поиска. В качестве наиболее перспективных направлений развития теории поисковой оптимизации рассматриваются вопросы применения принципов и правил поведения объектов живой природы для решения NP-полных оптимизационных задач. Наибольший интерес представляют методы и алгоритмы на основе принципов мультиагентного управления и роевого интеллекта. В основу работы положен роевой алгоритм на основе моделирования поведения летучих мышей. Приведена модель поведения одной особи – эмулируется процесс движения в ограниченном пространстве поиска с целью нахождения квазиоптимальных решений. Представлены подходы к изменению управляющих параметров алгоритма – частот и амплитуды эхолокационных сигналов, вероятностных правил изменения направления движения. Разработана структурная схема алгоритма, который решает оптимизационную задачу размещения на плоскости некоторых одногабаритных элементов, в качестве которых могут выступать компоненты сверхбольших интегральных схем. В работе представлен универсальный подход к кодированию решений в виде стринга, позволяющий использовать разработанный алгоритм для разных исходных данных и ограничений задачи размещения. Исходная область на пространстве поиска формируется путем последовательного выполнения последовательного, случайного и итерационного алгоритмов. Выполнена программная реализация алгоритма и графического интерфейса пользователя на объектно-ориентированном языке программирования высокого уровня. Проведена серия экспериментальных исследований, целью которых являлось подтверждение оценок временной сложности и эффективности разработанного алгоритма. Сложность роевого алгоритма на основе поведения летучих мышей линейно зависит от количества особей и имеет квадратичный характер зависимости от размерности исходной задачи, то есть от количества размещаемых элементов, определяющих длину стринга решения.

Скачать в PDF

Ключевые слова Размещение; адаптивные процедуры; моделирование эволюции; роевой алгоритм; ге-нетический алгоритм; летучие мыши; программная реализация.
Библиографический список 1. Норенков И.П., Арутюнян Н.М. Эволюционные методы в задачах выбора проектных решений // Научно-техническое издание МГТУ им. Н.Э. Баумана «Наука и образование». – 2007. – № 9.
2. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохнов-ленные природой: учебное пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 448 c.
3. Ахмедова Ш.А. Об эффективности «стайного» алгоритма оптимизации // Труды XLIII Краевой научной студенческой конференции по математике и компьютерным наукам. – Красноярск: СФУ, 2010. – С. 9-12.
4. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
5. Кулиев Э.В., Лежебоков А.А. О гибридном алгоритме размещения компонентов СБИС // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 188-192.
6. Курейчик В.В., Бова В.В., Курейчик В.В. Комбинированный поиск при проектировании // Образовательные ресурсы и технологии. – 2014. – № 2 (5). – С. 90-94.
7. Курейчик В.В., Курейчик Вл.Вл. Бионический поиск при проектировании и управле-нии // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 178-183.
8. Zaporozhets D.U., Zaruba D.V., Kureichik V.V. Representation of solutions in genetic VLSI placement algorithms // Proceedings of IEEE East-West Design and Test Symposium, EWDTS 2014.
9. Zaporozhets D.Yu., Zaruba D.V., Kureichik V.V. Hybrid bionic algorithms for solving problems of parametric optimization // World Applied Sciences Journal. – 2013. – No. 23 (8). – P. 1032-1036.
10. Kuliev E.V., Dukkardt A.N., Kureychik V.V., Legebokov A.A. Neighborhood research approach in swarm intelligence for solving the optimization problems // Proceedings of IEEE East-West Design and Test Symposium, EWDTS 2014.
11. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 28-32.
12. Bova V.V., Lezhebokov A.A., Gladkov L.A. Problem-oriented algorithms of solutions search based on the methods of swarm intelligence // World Applied Sciences Journal. – 2013. – No. 27 (9). – P. 1201-1205.
13. Zaruba D., Zaporozhets D., Kureichik V. VLSI placement problem based on ant colony opti-mization algorithm // Advances in Intelligent Systems and Computing. – 2016. – No. 464. – P. 127-133.
14. Kureichik V., Kureichik V., Bova V. Placement of VLSI fragments based on a multilayered approach // Advances in Intelligent Systems and Computing. – 2016. – No. 464. – P. 181-190.
15. Kureichik V.V., Zaruba D.V. The bioinspired algorithm of electronic computing equipment schemes elements placement // Advances in Intelligent Systems and Computing. – 2015. – No. 347. – P. 51-58.
16. Zaporozhets D., Zaruba D.V., Kureichik V.V. Hierarchical approach for VLSI components placement // Advances in Intelligent Systems and Computing. – 2015. – No. 347. – P. 79-87.
17. Zaporozhets D.U., Zaruba D.V., Kureichik V.V. Representation of solutions in genetic VLSI placement algorithms // Proceedings of IEEE East-West Design and Test Symposium, EWDTS 2014.
18. Кулиев Э.В., Лежебоков А.А., Дуккардт А.Н. Подход к исследованию окрестностей в роевых алгоритмах для решения оптимизационных задач // Известия ЮФУ. Технические науки. – 2014. – № 7 (156). – С. 15-26.
19. Кулиев Э.В.. Запорожец Д.Ю., Ксалов А.М. Биоинспирированный поиск при решении задачи размещения компонентов СБИС // Известия Кабардино-Балкарского научного центра РАН. – 2014. – № 6 (62). – C. 58-65.
20. Кулиев Э.В., Лежебоков А.А. Исследование характеристик гибридного алгоритма раз-мещения // Известия ЮФУ. Технические науки. – 2013. – № 3 (140). – C. 255-261.

Comments are closed.