|Article title||MODIFIED MECHANISMS OF MOVEMENT OF PARTICLE SWARM (AGENTS) IN AFFINE SPACE WITH INTEGRATED PARAMETERS|
|Authors||B. K. Lebedev, O. B. Lebedev, E. O. Lebedeva|
|Section||SECTION III. EVOLUTIONARY MODELING AND BIOINSPIRED ALGORITHMS|
|Month, Year||04, 2018 @en|
|Abstract||The composite architecture of the multi-agent bionic search system is proposed to solve combinatorial problems based on integration of swarm intelligence and genetic evolution. Integration of metaheuristics of population algorithms provides a broader overview of the search space and a higher probability of localization of the problem’s global extremum. The connecting link of this approach is a unified data structure describing the solution of the problem in the form of a chromosome. Unlike the canonical paradigm of a swarm of particles, hybrid algorithms use a wide range of graph structures (routes, tree, bipartite graph, matching, maximal independent set, etc.) as models for representing solutions. Such an approach is an effective way of finding rational solutions for optimization problems that allow the interpretation of solutions in the form of various graph structures. The paper describes a modified paradigm of particle swarm that provides, unlike the canonical method, the possibility of finding solutions in the affine space of positions with integer parameter values. Mechanisms for moving particles in affine space to reduce the weight of affine bonds are considered. Operators of directed mutation are described, the essence of which is to change the integer values of genes in the chromosome. An analysis of existing methods and algorithms for solving combinatorial problems has shown that the list of data that are actually interpretations of solutions is used most often as the data structure carrying information about the solution. The developed structures of search space and positions allow displaying: 1. Lists, the elements of which can have two values 0 or 1; 2. Lists containing fixed numbers of zeros and ones; 3. Lists with a fixed sum of the values of the elements; 4. Lists describing the structure of a binary tree; 5. Lists specifying the sequence of elements. The developed position structures (chromosomes) are focused on the integration of swarm intelligence and genetic evolution. In a number of algorithms, the coded representation of lists is used as the data structure. The transition from the encoded view to the list is performed using the decoder. New chromosome structures have been developed to represent solutions and decoding methods. Experiments have shown that the quality of the solutions obtained by the hybrid algorithm is 10 to 15 % better than the genetic and swarm algorithms. The probability of obtaining a global optimum is 0.9. 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 O (n2) - O (n3).|
|Keywords||Particle swarm; genetic evolution; affine space; integer parameters; position structures; directed mutation operator; particle transport mechanisms; integration, hybridization.|
|References||1. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy: ucheb. posobie [Modern algorithms of search optimization. Algorithms inspired by nature: a tutorial]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 448 p.
2. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation. Helsinki University of Technology, TKK Dissertations, Espoo 2009, 161 p.
3. Raidl G.R. A Unified View on Hybrid Metaheuristics. In: Lecture Notes In Computer Science, 2006. Springer, Verlag, pp. 1-12.
4. Lebedev B.K., Lebedev O.B. Raspredelenie resursov na osnove gibridnykh modeley roevogo intellekta [Distribution of resources on the basis of hybrid models of swarm intelligence], Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and Technical Herald of Information Technologies, Mechanics and Optics], 2017, Vol. 17,
No. 6, pp. 1063-1073.
5. Lebedev B.K., Lebedev O.B., Lebedev V.B. Gibridizatsiya roevogo intellekta i geneticheskoy evolyutsii na primere razmeshcheniya [Hybridization of swarm intelligence and genetic evolution using the example of placement], Programmnye produkty, sistemy i algoritmy [Software products, systems and algorithms], 2017, No. 4.
6. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006.
7. Kennedy J., Eberhart R.C. Particle swarm optimization, In Proceedings of IEEE International Conference on Neural Networks, 1995, pp. 1942-1948.
8. Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM computing surveys, 2003, No. 35, pp. 268-308.
9. Lebedev B.K., Lebedev O.B. Gibridnyy bioinspirirovannyy algoritm resheniya zadachi simvol'noy regressii [Hybrid bioinspiral algorithm for solving the problem of symbolic regression], Izvestiya YUFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, № 6 (167), pp. 28-41.
10. Emel'yanov V.V, Kureychik V.M, Kureychik V.V. Teoriya i praktika evolyutsionnogo modelirovaniya [Theory and practice of evolutionary modeling]. Moscow: Fizmatlit, 2003, 412 p.
11. Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh setey na osnove roevogo intellekta [Construction of the shortest connecting networks on the basis of swarm intelligence], Izvestiya YUFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 37-44.
12. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Memeticheskiy algoritm razbieniya [The Memetic Algorithm of Partitioning], Vestnik Rostovskogo gosudarstvennogo universiteta putey soobshcheniya [Bulletin of the Rostov State Transport University], 2017,No. (62), pp. 136-145.
13. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Razbienie na klassy metodom al'ternativnoy kollektivnoy adaptatsii stat'ya [Splitting into classes by the method of alternative collective adaptation article], Izvestiya YUFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, No. 7 (180), pp. 89-101.
14. Kureychik, V.V., Polupanov A.A. Obzor evolyutsionnykh metodov optimizatsii na osnove roevogo intellekta [Overview of evolutionary optimization techniques based on swarm intelligence], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 7-12.
15. Sha D.Y. and Cheng-Yu. A hybrid particle swarm optimization for job shop scheduling problem, Computers & Industrial Engineering, 2006, pp. 791-808.
16. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Raspredelenie resursov na osnove gibridnykh modeley roevogo intellekta [Distribution of resources on the basis of hybrid models of swarm intelligence], Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and Technical Herald of Information Technologies, Mechanics and Optics], 2017, Vol. 17, No. 6, pp. 1063-1073.
17. Lebedev B.K., Lebedev O.B. Lebedeva E.M. Modernizirovannyy murav'inyy algoritm sinteza identifitsirovannogo dereva gil'otinnogo razreza pri planirovanii SBIS [A modernized ant algorithm for the synthesis of the identified guillotine tree tree in the course of VLSI planning], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 7 (192), pp. 15-28.
18. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii: monografiya [Bioinspired methods in optimization: monograph]. Moscow: Fizmatlit, 2009, 384 p.
19. Lebedev B.K., Lebedev O.B. Lebedeva E.O. Roevoy algoritm planirovaniya raboty mnogoprotsessornykh vychislitel'nykh sistem [Swarm algorithm for planning the work of multiprocessor computer systems], Inzhenernyy vestnik Dona [Engineer's Herald of the Don], 2017, No. 3.
20. Cong J., Romesis M., and Xie M. Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey, CA, April 2003, pp. 88-94.