DISTRIBUTION OF RESOURCES BASED ON HYBRID MODELS OF SWARM INTELLIGENCE

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 О(n²)–О(n³).

1.      Zolotarev A.A. Methods for Optimizing Distribution Processes. Moscow, Infra-Inzheneriya Publ., 2014, 160 p. (In Russian)

2.      Brucker P. Scheduling Algorithms. 5^th 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. 3^rd 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

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