Мультиагентное моделирование в задачах формирования расписаний

161

Аннотация

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

Общая информация

Ключевые слова: мультиагентные системы, предпочтения агентов, оптимизация, распределенные системы

Рубрика издания: Методы оптимизации

Тип материала: научная статья

DOI: https://doi.org/10.17759/mda.2019090408

Финансирование. Работа выполнена при поддержке гранта РФФИ проект № 18–00–00012 (18–00–00011) КОМФИ.

Для цитаты: Судаков В.А., Сивакова Т.В. Мультиагентное моделирование в задачах формирования расписаний // Моделирование и анализ данных. 2019. Том 9. № 4. С. 100–111. DOI: 10.17759/mda.2019090408

Фрагмент статьи

Рассмотрим проблему распределения множества задач на множество ресурсов (например, планирование лекций для аудиторий или пакета заданий для нескольких процессоров). Это распространенная и важная проблема, которую можно формализовать, используя мультиагентный подход.

Литература

  1. A. Farinelli, M. Vinyals, A. Rogers, and N. Jennings. “Distributed Constraint Handling and Optimization”, in G. Weiss (ed.), “Multiagent Systems” (second edition), MIT Press, p. 547–584, 2013.
  2. Пантелеев А.В., Метлицкая Д.В., Алешина Е.А. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы. М.: Вузовская книга, 2013. 244 c.
  3. Сивакова Т.В., Судаков В.А. Метод нечетких областей предпочтении для оценки эффективности инноваций // XXVIII Международная научно-техническая конференция «Современные технологии в задачах управления, автоматики и обработки информации». Алушта, 14–20 сентября 2019 г. Сборник трудов. М.: Изд.-во Национальный исследовательский ядерный университет «МИФИ», 2019. С. 81–82.
  4. R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.
  5. Makoto Yokoo. Distributed constraint satisfaction: Foundations of cooperation in multiagent systems. Springer-Verlag, 2001.
  6. P.J. Modi, W. Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artifi cial Intelligence Journal, (161):149–180, 2005.
  7. A. Chechetka and K. Sycara. No-commitment branch and bound search for dis- tribute constraint optimization. In Proceedings of Fifth International Joint Confer- ence on Autonomous Agents and Multiagent Systems, pages 1427–1429, 2006.
  8. Gershman, A. Meisels, and R. Zivan. Asynchronous forward bounding for dis- tribute COPs. Journal Artifi cial Intelligence Research, 34:61–88, 2009.
  9. R. Dechter and R. Mateescu. And/or search spaces for graphical models. Artifi cial Intelligence, 171:73–106, 2007.
  10. Katsutoshi Hirayama and Makoto Yokoo. Distributed partial constraint satisfaction problem. In Principles and Practice of Constraint Programming, pages 222–236, 1997.
  11. A. Petcu and B. Faltings. DPOP: A scalable method for multiagent constraint optimization. In Proceedings of the Nineteenth International Joint Conference on Arti- fi cial Intelligence, pages 266–271, 2005.
  12. R.Maillerand, V.Lesser. Solving distributed constraint optimization problems using cooperative mediation. In Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 438–445, 2004.
  13. Library for research on Distributed Constraints Optimization Problems. URL: https://github.com/Orange-OpenSource/pyDcop (датаобращения: 26.10.2019)
  14. W. Yeoh, A. Felner, and S. Koenig. BnB-ADOPT: An asynchronous branch-and- bound DCOP algorithm. In Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, pages 591–598, 2008.
  15. S.M. Ali, S. Koenig, and M. Tambe. Preprocessing techniques for accelerating the DCOP algorithm ADOPT. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1041–1048, 2005.

Информация об авторах

Судаков Владимир Анатольевич, доктор технических наук, профессор кафедры 805, Московский авиационный институт (МАИ), ведущий научный сотрудник, Федеральное государственное учреждение «Федеральный исследовательский центр Институт прикладной математики им. М.В. Келдыша Российской академии наук» (ИПМ им. М.В. Келдыша РАН), Москва, Россия, ORCID: https://orcid.org/0000-0002-1658-1941, e-mail: sudakov@ws-dss.com

Сивакова Татьяна Владимировна, научный сотрудник, Федеральный исследовательский центр Институт прикладной математики им. М.В. Келдыша Российской академии наук, научный сотрудник, Российский экономический университет имени Г.В. Плеханова (РЭУ им. Г.В. Плеханова), Москва, Россия, ORCID: https://orcid.org/0000-0001-8026-2198, e-mail: sivakova15@mail.ru

Метрики

Просмотров

Всего: 455
В прошлом месяце: 6
В текущем месяце: 0

Скачиваний

Всего: 161
В прошлом месяце: 0
В текущем месяце: 0