Article

Article title DISTRIBUTION COMPLEX PROGRAM IN A MULTIPROCESSOR COMPUTER SYSTEM BY CRYSTALLIZATION OF ALTERNATIVES FIELD METHOD
Authors B.K. Lebedev, V.B. Lebedev
Section SECTION VI. COMPUTING SYSTEMS OF NEW GENERATION AND NEUROCOMPUTERS
Month, Year 06, 2015 @en
Index UDC 621.3.049.771.14
DOI
Abstract This paper considers the problem of uniform distribution (UD). Shows the formulation of the problem. The advantages and disadvantages of the main groups algorithms- exact and approximate. Based on the analysis of the developed algorithms (sequential, iterative, selectively commute, etc.) concluded on the need to create an efficient algorithm that meets modern requirements based on new technologies and approaches. In this paper, based on a graphic representation of the uniform distribution solution in the form of bipartite graph suggests a new paradigm of combinatorial optimization, based on the method of crystallization of alternatives field. In the сrystallization of alternatives field method (CAF)) each solution is formed (seems) a plurality of agents. Each agent corresponds to a set of alternative states. Each agent can be in one of the alternative states. The decision is determined by a set of alternative states of the plurality of agents. Proposed new mechanisms for solving the problems of uniform distribution. Such methods are iterative, heuristic methods of random search. Development of new algorithms was based on the use of metaheuristics embedded in the natural decision-making mechanisms. Along with metaheuristics, which built swarms algorithms used metaheuristics, which tends to use alternatives (variants of components) of the best solutions found. In the process of evolutionary collective adaptation by methods of discriminate analysis are formed fitness of assessment alternatives. Fitness of alternatives is considered as a possibility of its use in the formed solution. The collection of data on alternatives and their assessments are deposit alternatives field. In the process of evolutionary adaptation made collective isolation of the many options the most adapted alternatives. Experimental studies were carried out on the computer type IBM PC / AT. The time complexity of the algorithm is an opinion O (n2), where n - the number of vertices of a bipartite graph. For the objective of the experiments were used test tasks represented in the literature and the Internet. In comparison with existing algorithms to improve the results achieved from 2 to 6%.

Download PDF

Keywords Uniform distribution; bipartite graph; optimization; swarm intelligence; adaptive behavior; сrystallization of alternatives field method.
References 1. Lazarev A.A., Gafarov E.R. Teoriya raspisaniy. Zadachi i algoritmy [Theory schedules. Problems and algorithms]. Moscow: MGU im. M.V. Lomonosova, 2011, 222 p.
2. Larionov A.M., Mayorov S.A., Novikov G.I. Vychislitel'nye kompleksy, sistemy i seti [Computing complexes, systems and networks]. St. Petersburg: Energoatomizdat, 1987, 256 p.
3. Romanovskiy I.V. Algoritmy resheniya ekstremal'nykh zadach [Algorithms for solving extremal problems]. Moscow: Nauka, 1977, 352 p.
4. Neydorf R.A., Zhikulin A.A. Bystrodeystvuyushchaya modifikatsiya algoritma optimizatsii resheniya [Fast-acting modification of the algorithm to optimize the solution], Trudy kongressa po intellektual'nym sistemam i informatsionnym tekhnologiyam «AIS-IT’14». Nauchnoe izdanie [Proceedings of the Congress on intellectual systems and information technologies "AIS-IT'14". Scientific publication] in 4 vol. Vol. 1. Moscow: Fizmatlit, 2010, pp. 15-22.
5. Kobak V.G., Budilovskiy D.M. Sravnitel'nyy analiz priblizhennykh algoritmov resheniya minimaksnoy zadachi dlya odnorodnykh priborov [Comparative analysis of approximate algorithms for solving the minimax problem for homogeneous devices], Vestnik DGTU [Vestnik of DSTU], 2006, No. 4, pp. 327-334.
6. Neydorf R.A., Filippov A.V., Yagubov Z.Kh. Perestanovochnyy algoritm biekstremal'nogo resheniya odnorodnoy raspredelitel'noy zadachi [Permutation algorithm bitstreaming solution of the homogeneous distribution tasks], Vestnik DGTU [Vestnik of DSTU], 2011, Vol. 11, No. 5 (56).
7. Neydorf R.A., Zhikulin A.A. Issledovanie variantov modifikatsii priblizhennykh algoritmov resheniya odnorodnykh raspredelitel'nykh zadach, povyshayushchikh ikh effektivnost' [The study of variants of approximate algorithms for solving homogeneous distribution of tasks, increasing their efficiency], Innovatsiya, ekologiya i resursosberegayushchie tekhnologii (In-ERT-2012): Trudy X Mezhdunar. nauch.-tekhn. foruma [Innovation, ecology and resource saving technologies (Inert-2012): proceedings of the X International scientific-technical forum]. Rostov-on-Don: ITs DGTU, 2012, pp. 370-375.
8. Neydorf R.A., Zhikulin A.A. Selektivno-perestanovochnyy metod priblizhennogo resheniya odnorodnoy raspredelitel'noy zadachi. Kombinatsionnye perestanovki [Selective-permutation method for finding an approximate solution of the open shop scheduling problem. Combinational permutations], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 167-172.
9. Plotnikov V.N., Zverev V.Yu. Metody bystrogo raspredeleniya algoritmov v vychislitel'nykh sistemakh [Quick methods of distribution algorithms in computer systems], Tekhnicheskaya kibernetika [Engineering Cybernetics], 1974, No. 3.
10. Budilovskiy D.M. Geneticheskiy podkhod k resheniyu minimaksnoy zadachi v odnorodnykh sistemakh obrabotki informatsii [Genetic approach to solving the minimax problem in homogeneous information processing systems], Matematicheskie metody v tekhnike i tekhnologiyakh [Mathematical methods in technics and technologies], 2006, Vol. 2, No. 19.
11. Dorigo M. and Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
12. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proektirovaniya: Monografiya [Models of adaptive behaviour of ant colonies in the problems of design: the Monograph]. Taganrog: Izd-vo YuFU, 2013.
13. Lebedev V.B., Lebedev O.B. Roevoy intellekt na osnove integratsii modeley adaptivnogo povedeniya murav'inoy i pchelinoy koloniy [Swarm intelligence on the basis of the adaptive behaviour models integration of the ant and beer colonies], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 41-47.
14. Lebedev B.K., Lebedev O.B. Modelirovanie adaptivnogo povedeniya murav'inoy kolonii pri poiske resheniy, interpretiruemykh derev'yami [Modelling of an ant colony adaptive behaviour by search of the decisions interpreted by trees], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 27-35.
15. Kureychik V.M., Lebedev B.K., Lebedev O.B. Razbienie na osnove modelirovaniya adaptivnogo povedeniya biologicheskikh sistem [Partitioning based on simulation of adaptive behavior of biological systems], Neyrokomp'yutery: razrabotka, primenenie [Neurocomputers: Development, Application], 2010, No. 2, pp. 28-34.
16. Raidl G.R. A Unified View on Hybrid Metaheuristics. In: Lecture Notes in Computer Science. Springer-Verlag, 2006, pp. 1-12.
17. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ [Optimization by the crystallization of alternatives field (CAF) METHOD], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
18. Lebedev B.K., Lebedev V.B. Metod kristallizatsii rossypi al'ternativ [The method of crystallization placers alternatives], Sbornik nauchnykh trudov VII Mezhdunarodnoy nauchno-prakticheskoy konferentsii “Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte” [Proceedings of the VII International scientific-practical conference “Integrated models and soft computations in artificial intelligence”]. Vol. 2. Moscow: Fizmatlit, 2013, pp. 903-912.
19. Lebedev B.K., Lebedev V.B. Global'naya trassirovka metodom kristallizatsii rossypi al'ternativ [Global routing by crystallization of alternatives field (CAF) METHOD], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 42-51.
20. Lebedev B.K., Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh soedineniy metodom kristallizatsii rossypi al'ternativ [The construction of shortest paths linking compounds by the method of crystallization placers alternatives], MES-2014. VI Vserossiyskaya
nauchno-tekhnicheskaya konferentsiya «Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem – 2014». Sbornik trudov [MES-2014. VI all-Russian scientific-technical conference "problems of development of perspective micro- and nanoelectronic systems – 2014". Proceedings of the], Under the General ed. Akademika RAN A.L. Stempkovskogo. Moscow: IPPM RAN, 2014. Part I, pp. 177-183.

Comments are closed.