РАСПРЕДЕЛЕНИЕ РЕСУРСОВ НА ОСНОВЕ ГИБРИДНЫХ МОДЕЛЕЙ РОЕВОГО ИНТЕЛЛЕКТА

Предложена композитная архитектура многоагентной системы бионического поискадля решения общей распределительной задачи на основе интеграции роевого интеллекта и генетической эволюции. Рассмотрены три подхода к построению такой архитектуры. Связующим звеном такого подхода является единая структура данных, описывающая в виде хромосомы решение задачи. Рассмотренные в работе новые принципы и способы кодирования и декодирования хромосом для представления решения общей распределительной задачи исключают некорректные решения, отличаются простотой и линейными оценками временной и пространственной сложности. Предложена модифицированная парадигма метода роя частиц. Для организации перемещения роя частиц в гиперпространстве решений разработан оператор направленной мутации. Эксперименты показали, что качество решений у гибридного алгоритма на 10–15% лучше, чем у генетического и роевого алгоритмов. Общая оценка временной сложности при любом подходе к гибридизации не превышает оценки временной сложности генетического алгоритма и лежит в пределах О(n²)–О(n³).

 1.      Золотарев А.А. Методы оптимизации распределительных процессов. М.: Инфра-Инженерия, 2014. 160 с.

2.      Brucker P. Scheduling Algorithms. 5^th ed. Springer, 2007.
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

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License