Меню
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2017-17-6-1063-1073
УДК 681.385
РАСПРЕДЕЛЕНИЕ РЕСУРСОВ НА ОСНОВЕ ГИБРИДНЫХ МОДЕЛЕЙ РОЕВОГО ИНТЕЛЛЕКТА
Читать статью полностью
Язык статьи - русский
Ссылка для цитирования: Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Распределение ресурсов на основе гибридных моделей роевого интеллекта // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 6. С. 1063–1073. doi: 10.17586/2226-1494-2017-17-6-1063-1073
Аннотация
Ссылка для цитирования: Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Распределение ресурсов на основе гибридных моделей роевого интеллекта // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 6. С. 1063–1073. doi: 10.17586/2226-1494-2017-17-6-1063-1073
Аннотация
Предложена композитная архитектура многоагентной системы бионического поискадля решения общей распределительной задачи на основе интеграции роевого интеллекта и генетической эволюции. Рассмотрены три подхода к построению такой архитектуры. Связующим звеном такого подхода является единая структура данных, описывающая в виде хромосомы решение задачи. Рассмотренные в работе новые принципы и способы кодирования и декодирования хромосом для представления решения общей распределительной задачи исключают некорректные решения, отличаются простотой и линейными оценками временной и пространственной сложности. Предложена модифицированная парадигма метода роя частиц. Для организации перемещения роя частиц в гиперпространстве решений разработан оператор направленной мутации. Эксперименты показали, что качество решений у гибридного алгоритма на 10–15% лучше, чем у генетического и роевого алгоритмов. Общая оценка временной сложности при любом подходе к гибридизации не превышает оценки временной сложности генетического алгоритма и лежит в пределах О(n2)–О(n3).
Ключевые слова: распределительная задача, многоагентная система, роевой интеллект, генетическая эволюция, бионический поиск, гибридизация
Благодарности. Работа выполнена при финансовой поддержке РФФИ грант № 17-07-00997.
Список литературы
Благодарности. Работа выполнена при финансовой поддержке РФФИ грант № 17-07-00997.
Список литературы
1. Золотарев А.А. Методы оптимизации распределительных процессов. М.: Инфра-Инженерия, 2014. 160 с.
2. Brucker P. Scheduling Algorithms. 5th ed. Springer, 2007.
379 p.
379 p.
3. Нейдорф Р.А., Кобак В.Г., Красный Д.Г. Точное решение неоднородной распределительной задачи модификацией алгоритма Алексеева // Известия вузов. Северо-Кавказский регион. Серия: Технические науки. 2008. №1. С. 17–21.
4. Серая О.В. Распределительная задача линейного программирования // Системы обработки информации. 2013. № 2 (109). С. 167–170.
5. Акулич И.Л. Математическое программирование в примерах и задачах. 3-e изд. СПб.: Лань, 2011. 352с.
6. Костюкевич В.М., Давыдков Г.А., Хотина И.Г. Оптимальное распределение ресурсов с использованием динамического программирования // ResourcesandTechnology. 2006. T. 7. C. 49–51.
7. Lorigeon T., Billaut J.C., Bouquar J.L. A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint // Journal of the Operational Research Society. 2002. V. 53. N11. P. 1239–1246.doi: 10.1057/palgrave.jors.2601421
8. Прилуцкий М.Х., Кумагина Е.А. Метод ветвей и границ решения задачи многоресурсного сетевого планирования // Системы управления и информационные технологии. 2014. № 2(56). С. 48–51.
9. Artigues C., Feillet D. A branch and bound method for the job shop problem with sequence dependent setup times // Annals of Operations Research. 2008.V. 159. N 1. P. 135–159. doi: 10.1007/s10479-007-0283-0
10. Пантелеев А.В., Скавинская Д.В., Алёшина Е.A. Метаэвристические алгоритмы поиска оптимального программного управления. М.: ИНФРА-М,2017. 396с.
11. Богданов С.И., Петров А.В. Эффективные процессы распределения товаров: концепции, модели, методы реализации. Екатеринбург: УрГЭУ, 2008. 234 с.
12. Золотарев А.А., Венцов Н.Н., Агибалов О.И., Деева А.С. Оптимизация распределительных процессов на основе аналитических методов и эвристических алгоритмов // Вестник науки и образования Северо-Запада России. 2016. Т. 2. № 1. С. 74–82.
13. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: МГТУ им. Н.Э. Баумана, 2014. 448с.
14. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация. Tеория и практика. М.: Физматлит, 2006. 272 с.
15. Verma S., Jain M., Choudhary D. Solving the job-shop scheduling problem by using genetic algorithm // International Journal of Computational Science and Mathematics. 2011. V. 3. N 1. P. 93–98.
16. Moon I., Lee S., Bae H. Genetic algorithms for job shop scheduling problems with alternative routings // International Journal of Production Research. 2008. V. 46. N 10. P. 2695–2705. doi: 10.1080/00207540701244820
17. LiangS., Cheng X., Liang Y. Solving job shop scheduling problem using genetic algorithm with penalty function // International Journal of Intelligent Information Processing. 2010. V. 1. N 2. P. 65–77. doi: 10.4156/ijiip.vol1.issue2.7
18. Nickabadi A., Ebadzadeh M.M., Safabakhsh R. A novel particle swarm optimization algorithm with adaptive inertia weight // Applied Soft Computing Journal. 2011. V. 11. N 4. P. 3658–3670. doi: 10.1016/j.asoc.2011.01.037
19. Sha D.Y., Hsu C.Y. A hybrid particle swarm optimization for job shop scheduling problem // Computers and Industrial Engineering. 2006. V. 51. N4. P. 791–808.doi: 10.1016/j.cie.2006.09.002
20. Лебедев Б.К., Лебедев В.Б. Покрытие на основе метода роя частиц // Материалы Международной конференции по нейрокибернетике. 2011. Т.2. С. 417–425.
21. Лебедев Б.К., Лебедев В.Б. Планирование на основе роевого интеллекта и генетической эволюции // Известия ЮФУ. Технические науки. 2009. №4. С. 25–33.
22. Blum Ch., Aguilera M.J.B., Roli A., Sampels M. Hybrid Metaheuristics: An Emerging Approach to Optimization. Springer, 2008. 299 p. doi: 10.1007/978-3-540-78295-7
23. Hegazy Z., Mahmoud El-S., Naglaa R.S., Heba S. A novel improved bat algorithm for job shop scheduling problem // International Journal of Computer Applications. 2017. V. 164. N 5. P. 24–30.doi: 10.5120/ijca2017913627
24. Beasley J.E. Distributing test problems by electronic mail // Journal of the Operational Research Society. 1990. V. 41. N 11. P. 1069–1072. doi: 10.1057/jors.1990.166