doi: 10.17586/2226-1494-2017-17-6-1063-1073


B. K. Lebedev., O. B. Lebedev, E. M. Lebedeva

Read the full article  ';
Article in Russian

For citation: Lebedev B.K., Lebedev О.B., Lebedeva E.M. Distribution of resources based on hybrid models of swarm intelligence. Scientific and Technical Journal of Information Technologies, Mechanics and Optics , 2017, vol. 17, no. 6, pp. 1063–1073 (in Russian). doi: 10.17586/2226-1494-2017-17-6-1063-1073

The composite architecture of the multi-agent bionic search system is proposed to solve the general distribution problem based on swarm intelligence and genetic evolution. Three approaches to the construction of such architecture are considered. The connecting link of this approach is a unified data structure that describes the solution of the problem in the form of a chromosome. The new principles and methods of coding and decoding of chromosomes for the representation of the general distribution problem considered in this paper exclude incorrect solutions, are distinguished by simplicity and linear estimates of temporal and spatial complexity. A modified paradigm of the particle swarm method is proposed. To organize the swarm movement of particles in hyperspace of solutions, a directed mutation operator has been developed. Experiments have shown that the quality of the solutions in the hybrid algorithm is 10 to 15% better than the genetic and swarm algorithms. The overall estimate of time complexity for any hybridization approach does not exceed the estimate of the time complexity of the genetic algorithm and lies within the range О(n2)–О(n3).

Keywords: general distribution problem, multi-agent system, swarm intelligence, genetic evolution, bionic search, hybridization

Acknowledgements. This research was supported by the grant from the Russian Foundation for Basic Research No.17-07-00997.

1.      Zolotarev A.A. Methods for Optimizing Distribution Processes. Moscow, Infra-Inzheneriya Publ., 2014, 160 p. (In Russian)
2.      Brucker P. Scheduling Algorithms. 5th ed. Springer, 2007,
379 p.
3.      Neydorf R.A., Kobak V.G., Krasniy D.G. The exact decision non-uniform of problems by modification of algorithm Alekseev. University News. North-Caucasian Region. Technical Sciences Series, 2008, no. 1, pp. 17–21. (In Russian)
4.      Seraya O.V. Distribution problem of linear programing. Sistemy Obrabotki Informatsii, 2013, no. 2, pp. 167–170. (In Russian)
5.      Akulich I.L. Mathematical Programming in Examples and Tasks. 3rd ed. St. Petersburg, Lan' Publ., 2011, 352 p. (In Russian)
6.      Kostyukevich V.M., Davydkov G.A., Khotina I.G. Resources optimal distribution on the basis of dynamic programming. Resources and Technology,2006, vol. 7, pp. 49–51.(In Russian)
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, vol. 53, no. 11, pp. 1239–1246. doi: 10.1057/palgrave.jors.2601421
8.      Prilutskii M.Kh., Kumagina E.A. Method of branches and boundaries for solving the problem of multi-resource network planning. Sistemy Upravleniya i Informatsionnye Tekhnologii, 2014, no. 2, pp. 48–51. (In Russian)
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, vol. 159, no. 1, pp. 135–159. doi: 10.1007/s10479-007-0283-0
10.   Panteleev A.V., Skavinskaya D.V., Aleshina E.A. Metaheuristic Algorithms of Search of Optimum Program Control. Moscow, Infra-M Publ., 2017, 396 p. (In Russian)
11.   Bogdanov S.I. Effective Processes of Product Distribution: Concepts, Models, Implementation Methods. Ekaterinburg, UrSEU Publ., 2008, 234 p. (In Russian)
12.   ZolotarevA.A., Ventsov N.N., Agibalov O.I., Deeva A.S. Distribution process optimization based on analytical methods and heuristic algorithms. Journal of Science and Education of North-West Russia, 2016, vol. 2, no. 1, pp. 74–82. (In Russian)
13.   Karpenko A.P. Modern Algorithms of Search Optimization. Algorithms Inspired by Nature. Moscow, Bauman MSTU Publ., 2014, 448 p. (In Russian)
14.   Kureichik V.M., Lebedev B.K., Lebedev O.B. Search Adaptation. Theory and Practice. Moscow, Fizmatlit Publ., 2006, 272 p.(In Russian)
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, vol. 3, no. 1, pp. 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, vol. 46, no. 10, pp. 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, vol. 1, no. 2, pp. 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, vol. 11, no. 4, pp. 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, vol. 51, no. 4, pp. 791–808. doi: 10.1016/j.cie.2006.09.002
20.   Lebedev B.K., Lebedev V.B. Coverage based on the particle swarm method. Proc. Int. Conf. on Neurocybernetics, 2011, vol. 2, pp. 417–425. (In Russian)
21.   Lebedev B.K., Lebedev V.B. Planning on a basis swarm intelligence and genetic evolution. Izvestiya SFedU. Engineering Sciences, 2009, no. 4, pp. 25–33. (In Russian)
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, vol. 164, no. 5, pp. 24–30.doi: 10.5120/ijca2017913627 
24.   Beasley J.E. Distributing test problems by electronic mail. Journal of the Operational Research Society, 1990, vol. 41, no. 11, pp. 1069–1072. doi: 10.1057/jors.1990.166

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2024 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.