Статья

Название статьи МОДИФИЦИРОВАННЫЕ МЕХАНИЗМЫ ПЕРЕМЕЩЕНИЯ РОЯ ЧАСТИЦ (АГЕНТОВ) В АФФИННОМ ПРОСТРАНСТВЕ С ЦЕЛОЧИСЛЕННЫМИ ПАРАМЕТРАМИ
Автор Б. К. Лебедев, О. Б. Лебедев, Е. О. Лебедева
Рубрика РАЗДЕЛ III. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ И БИОИНСПИРИРОВАННЫЕ АЛГОРИТМЫ
Месяц, год 04, 2018
Индекс УДК 004.896
DOI
Аннотация Предложена композитная архитектура многоагентной системы бионического поиска для решения комбинаторных задачи на основе интеграции роевого интеллекта и генетической эволюции. Интеграция метаэвристик популяционных алгоритмов обеспечивает более широкий обзор простран¬ства поиска и более высокую вероятность локализации глобального экстрему¬ма задачи. Связующим звеном такого подхода является единая структура данных, описывающая в виде хромосомы решение задачи. В отличие от канонической парадигмы роя частиц гибридные алгоритмы в качестве моделей для представления решений используют широкий диапазон графовых структур (маршрут, дерево, двудольный граф, паросочетание, внутреннеустойчивое множество и т.д.). Такой подход является эффективным способом поиска рациональных решений для задач оптимизации, допускающих интерпретацию решений в виде различного рода графовых структур. В работе описывается модифицированная парадигма роя частиц, обеспечивающая, в отличие от канонического метода, возможность поиска решений в аффинном пространстве позиций с целочисленными значениями параметров. Рассмотрены механизмы перемещения частиц в аффинном пространстве для уменьшения веса аффинных связей. Описываются операторы направленной мутации, суть которых заключается в изменения целочисленных значений генов в хромосоме. Анализ существующих методов и алгоритмов решения комбинаторных задач показал, что в качестве структуры данных, несущих информацию о решении, чаще всего используются списки, фактически являющимися интерпретациями решений. Разработанные структуры пространства поиска и позиций позволяют отображать: Списки, элементы которых могут иметь два значения 0 или 1; Списки, содержащие фиксированные числа нулей и единиц; Списки с фиксированной суммой значений элементов; Списки, описывающие структуру бинарного дерева; Списки, задающие последовательность элементов. Разработанные структуры позиций (хромосом) ориентированы на интеграцию роевого интеллекта и генетической эволюции. В ряде алгоритмов качестве структуры данных используется кодированное представление списков. Переход от кодированного представления к списку производится с помощью декодера. Разработаны новые структуры хромосом для представления решений и методы декодирования. Эксперименты показали, что качество решений, полученных гибридным алгоритмом на 10–15 % лучше, чем у генетического и роевого алгоритмов. Вероятность получения глобального оптимума составила 0.9. Общая оценка временной сложности при любом подходе к гибридизации не превышает оценки временной сложности генетического алгоритма и лежит в пределах О(n2 ) -О(n3).

Скачать в PDF

Ключевые слова Рой частиц; генетическая эволюция; аффинное пространство; целочисленные параметры; структуры позиций; оператор направленной мутации; механизмы перемещения частиц; интеграция; гибридизация.
Библиографический список 1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 448 с.
2. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation. – Helsinki University of Technology, TKK Dissertations, Espoo 2009. – 161 p.
3. Raidl G.R. A Unified View On Hybrid Metaheuristics. In: Lecture Notes In Computer Science, 2006. – Springer, Verlag. – P. 1-12.
4. Лебедев Б.К., Лебедев О.Б. Распределение ресурсов на основе гибридных моделей роевого интеллекта // Научно-технический вестник информационных технологий, механики и оптики. – 2017. – Т. 17, № 6. – С. 1063-1073.
5. Лебедев Б.К., Лебедев О.Б., Лебедев В.Б. Гибридизация роевого интеллекта и генетической эволюции на примере размещения // Программные продукты, системы и алгоритмы. – 2017. – № 4.
6. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006.
7. Kennedy J., Eberhart R.C. Particle swarm optimization // In Proceedings of IEEE International Conference on Neural Networks. – 1995. – P. 1942-1948.
8. Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison // ACM computing surveys. – 2003. – No. 35. – P. 268-308.
9. Лебедев Б.К., Лебедев О.Б. Гибридный биоинспирированный алгоритм решения задачи символьной регрессии // Известия ЮФУ. Технические науки. – 2015. – № 6 (167).
– С. 28-41.
10. Емельянов В.В, Курейчик В.М, Курейчик В.В. Теория и практика эволюционного моделирования. – М.: Физматлит, 2003. – 412 с.
11. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 37-44.
12. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Меметический алгоритм разбиения // Вестник Ростовского государственного университета путей сообщения. – 2017. – № 2 (62).
– С. 136-145.
13. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Разбиение на классы методом альтернативной коллективной адаптации статья // Известия ЮФУ. Технические науки. – 2016. – № 7 (180). – С. 89-101.
14. Курейчик, В.В., Полупанов А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 7-12.
15. Sha D.Y. and Cheng-Yu. A hybrid particle swarm optimization for job shop scheduling problem // Computers & Industrial Engineering. – 2006. – P. 791-808.
16. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Распределение ресурсов на основе гибридных моделей роевого интеллекта // Научно-технический вестник информационных технологий, механики и оптики. – 2017. – Т. 17, № 6. – С. 1063-1073.
17. Лебедев Б.К., Лебедев О.Б. Лебедева Е.М..Модернизированный муравьиный алгоритм синтеза идентифицированного дерева гильотинного разреза при планировании СБИС // Известия ЮФУ. Технические науки. – 2017. – № 7 (192). – С. 15-28.
18. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизации: монография. – М.: Физматлит, 2009. – 384 с.
19. Лебедев Б.К., Лебедев О.Б. Лебедева Е.О. Роевой алгоритм планирования работы многопроцессорных вычислительных систем // Инженерный вестник Дона. – 2017. – № 3.
20. Cong J., Romesis M., and Xie M. Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms // Proc. of the International Symposium on Physical Design.
– Monterey, CA, April 2003. – P. 88-94.

Comments are closed.