Volume 2(59)

CONTENTS

Gurieva Yu., Vasiliev E., Smirnov L. Conservation laws in a neural network approach to numerical solving of the nonlinear Schrodinger equation
Silenko D. I., Lebedev I. G. Global optimization algorithm that uses decision trees to find local extrema
Korotysheva A. A., Zhukov S.N., Milov V.R., Yegorov Y.S., Chekusheva A.Y., Dubov M.S. Classification of unlabeled battery on X-ray images using machine learning methods
Kudryavtsev A. A., Malyshkin V.E., Nushtaev Yu. Yu., Perepelkin V. A., Spirin V. A. Efficient fragmented implementation of the two phase fluid boundary value problem
Matolygina N. A., Gromov M. L., Matolygin A. K. Application of the tensor approach to the software implementation of the cellular automaton flow model
Mikulik I., Blagoveshchenskaya E. Parallel implementation of the ant colony algorithm with parameters update using the genetic algorithm

Yu. Gurieva, E. Vasiliev, L. Smirnov

Lobachevsky State University, 603022, Nizhny Novgorod, Russia

CONSERVATION LAWS IN A NEURAL NETWORK APPROACH TO NUMERICAL SOLVING OF THE NONLINEAR SCHRODINGER EQUATION

DOI: 10.24412/2073-0667-2023-2-5-20

EDN: LFBNWY

We consider a possible modification of a neural network approach to numerical solving of nonlinear partial differential equations (PDE), describing physical systems with integrals of motion. In this approach, we approximate solutions of the equations by deep neural networks, using physics-informed method.

Physics-informed neural network (FINN) approach proposes nonlinear function approximators that integrate the observational data, initial and boundary conditions and description of physical system in form of PDE by embedding the corresponding residuals into the loss function of a neural network. Therefore, the problem of solving nonlinear differential equations turns into the problem of minimizing the squared residuals over domain which is achieved by automatic differentiation and stochastic gradient descent.

The proposed modification of this method means consideration and implementation of corresponding conservation laws for training of the neural networks, and is expected to improve the physical properties of the trained nonlinear regression models. The purpose of this work is to modify a neural network using the conservation law constraint, such that the predicted solution will satisfy the continuity equation better and faster as well as speed up the rate of convergence and provide better accuracy. Improvement of the conservative properties of the approximation is provided by the specific loss function regularization: addition of the conserved quantities’ residuals to the loss function to train the neural network.

To test this method, we considered one-dimensional nonlinear Schrodinger equation and its conservation laws in integral form. Number of quants and energy were used as conserved physical quantities. In our experiments, their values were calculated in several equidistant time moments and compared with reference to find the corresponding residuals and implement the conservation constraint in the loss function. Therefore, the average residuals of number of quants and energy for the prediction are considered as quality metrics in the problem, as well as pointwise difference from the predicted and reference solution (validation error). Reference functions for validation datasets are derived from the analytical expressions for the exact solutions.

This modified neural network approach is applied to the different classes of analytic solutions of the nonlinear Schrodinger equation: one soliton, interaction of two solitons (in breather form), first-order rogue wave. For each solution, we apply three forms of the conservative regularization: quants’ number constraint, energy constraint and the sum of them. The training curves and predictions are compared with the solution obtained with the initial loss function (baseline).

It is shown that introduction of the additional conservative constraints to loss function reduces the conserved quantities’ residuals for training and prediction in all cases. For the simplest one-soliton

solution, the regularizations improve not only conservation quality metrics, but also pointwise difference with the reference in the same training time. The best result was obtained by the combination of constraints: validation error is reduced by more than three times. However, for more complex solution forms, such as two solitons and rogue wave, the results are not as good. The conservative constraints significantly change the form of loss function, so the training curves start to plateau, and the training process becomes more unstable. For the most complex two soliton interaction, it requires about two times more optimization steps to converge. The validation error is improved only for the energy constraint for both cases: for two-soliton solution, validation error is reduced by 13 %; for rogue wave, it is reduced by 67 %. Therefore, the effect of conservative modification of the deep learning approach for nonlinear partial differential equations is individual for different systems and conserved quantities. Generalization ability of such neural networks should be further investigated and tested for different problems.

Key words: deep learning, neural networks, nonlinear Schrodinger equation, conservation laws, solitons.

References

Moxley F., Chuss D., Dai W. A generalized finite-difference time domain scheme for solving nonlinear Schrodinger equations // Computer Physics Communications, 2013. N 184 (8). P. 1834¬1841. [El. Res.]: https://doi.org/10.1016/j .cpc.2013.03.006.
Vasiliev E.P., Bolotov D.I., Bolotov M. I., Smirnov L.A. Neyrosetevoy podhod к resheniyu zadachi samovozdeistviva volnovvh polei v nelineinvh sredah // Problemv Informatiki. 2022. N 1. P. 5-16. [El. Res.]: https://doi.org/10.24412/2073-0667-2022-l-5-16.
Karniadakis, G.E., Kevrekidis, EG., Lu, L. et al. Physics-informed machine learning // Nature Reviews Physics. 2021. N 3. P. 422-440. [El. Res.]: https://doi.org/10.1038/s42254-021-00314-5.
Raissi M., Perdikaris P., Karniadakis G.E.: Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations // Journal of Computational Physics. 2019. N 378. P. 686-707. [El. Res.]: https://doi.org/10.1016/ j. jcp.2018.10.045.
Pu J.C., Li J., Chen Y. Soliton, breather, and rogue wave solutions for solving the nonlinear Schrodinger equation using a deep learning method with physical constraints // Chinese Physics B, 2021. N 30 (6), 060202. [El. Res.]: https://dx.doi.org/10.1088/1674-1056/abd7e3.
Wu G. Z., Fang Y., Wang Y. Y., Wu G. C., Dai C. Q. Predicting the dynamic process and model parameters of the vector optical solitons in birefringent fibers via the modified PINN // Chaos, Solitons and Fractals. 2021. N 152, 111393. [El. Res.]: https://doi.Org/10.1016/j.chaos.2021.111393.
Wang L., Yan. Z. Data-driven rogue waves and parameter discovery in the defocusing nonlinear Schrodinger equation with a potential using the PINN deep learning // Physics Letters A. 2021. V. 404. P. 127408. [El. Res.]: https://doi.Org/10.1016/j .physleta.2021.127408.
Jagtap, A., Kharazmi, E., Karniadakis. G.E. Conservative physics-informed neural networks on discrete domains for conservation laws: Applications to forward and inverse problems // Computer Methods in Applied Mechanics and Engineering. 2020. N 365, 113028. [El. Res.]: https://doi.org/ 10.1016/j.cma.2020.113028.
Wu G.Z., Fang Y., Kudryashov N., Wang Y.Y., Dai C.Q. Prediction of optical solitons using an improved physics-informed neural network method with the conservation law constraint // Chaos, Solitons and Fractals, 2022. 159(C), 112143. [El. Res.]: https://doi.Org/10.1016/j.chaos.2022. 112143.
Lin S., Chen Y. A two-stage physics-informed neural network method based on conserved quantities and applications in localized wave solutions // Journal of Computational Physics, 2022. 457(C), 111053. [El. Res.]: https://doi.Org/10.1016/j.jcp.2022.111053.
[El. Res.]: https://docs.nvidia.com/deeplearning/modulus/user_guide/theory/ recommended_practices.html.
Zakharov V., Manakov S. On the complete integrability of a nonlinear Schrodinger equation // Theoretical and Mathematical Physics. 1974. N 19 (3). P. 551-559. [El. Res.]: https://doi.org/10. 1007/BF01035568.
[El. Res.]: https://docs.nvidia.com/deeplearning/modulus/user_guide/foundational/ scalar_transport.html.
Stein M. Large sample properties of simulations using Latin hypercube sampling, Technometrics. 1987. N 29. P. 143-151. [El. Res.]: https://www.jstor.org/stable/1269769.
Schraudolph N.N., Yu J., Gunter S. A Stochastic Quasi-Newton Method for Online Convex Optimization // International Conference on Artificial Intelligence and Statistics, 2007. P. 436-443. [El. Res.]: http: //proceedings.mlr.press/v2/schraudolph07a/schraudolph07a.pdf.

Bibliographic reference: Gurieva Yu., Vasiliev E., Smirnov L. Conservation laws in a neural network approach to numerical solving of the nonlinear Schrodinger equation //journal “Problems of informatics”. 2023, № 2. P.5-20. DOI:10.24412/2073-0667-2023-2-5-20

article

D.L Silenko, I. G. Lebedev

Lobachevsky State University of Nizhny Novgorod, 603022, Nizhny Novgorod, Russia

GLOBAL OPTIMIZATION ALGORITHM THAT USES DECISION TREES TO FIND LOCAL EXTREMA

DOI: 10.24412/2073-0667-2023-2-21-33

EDN: MLGKOX

The paper considers the algorithms for solving the multidimensional global optimization problems using decision tree to reveal the attraction regions of the local minima. We suppose, that the target function is defined as a “black box” and satisfied Lipschitz condition with unknown constant. We propose a method for selecting the local extrema neighborhood of the target function based on analysis of accumulated search information using machine learning methods. This allows us to make a decision to run a local method, which can speed up the convergence of the algorithm. The proposition was confirmed by the results of numerical experiments demonstrating the speedup when solving a series of test problems.

Key words: Global optimization, multiextremal functions, parallel computing, decision tree.

The work was supported by the Ministry of Science and Higher Education of the Russian Federation (project- no. FSWR-2023-0034), and by the Research and Education Mathematical Center (project no. 075-02-2022-883).

References

Ferreiro M. , Garcia J. A. , Lopez-Salas J. G., Vazquez C. An efficient implementation of parallel simulated annealing algorithm in GPUs / / Journal of global optimization, 2013. V. 57. N 3. P. 863-890.
Garcia-Martinez J.M., Garzon E. M., Ortigosa P. M. A GPU implementation of a hybrid evolutionary algorithm: Gpuego / / Journal of super-computing, 2014. V. 70. N 2. P. 684-695.
Langdon W.B. Graphics processing units and genetic programming: an overview // Soft Computing, 2011. V. 15. N 8, P. 1657-1669.
Evtushenko Yu. G., Malkova V. U., Stancvichyus A. A. Parallel global optimization of functions of several variables // Computational Mathematics and Mathematical Physics, 2009. V. 49. N 2. P. 246-260.
He J., Verstak A., Watson L. T., Sosonkina M. Design and implementation of a massively parallel version of direct / / Computational optimization and applications, 2008. V. 40. N 2. P. 217-245.
Paulavicius R., Zilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds / / Optimization methods and software, 2011. V. 26. N 3. P. 487-498.
Strongin R. G., Gcrgcl V. P., Grishagin V. A., Barkalov K.A. Parallel Computations in Global Optimization Problems. Izd. Mosk. Gos. Univ., 2013.
Gcrgcl V. P. A global optimization algorithm for multivariate functions with lipschitzian first derivatives / / Journal of Global Optimization, 1997. V. 10. N 3. P. 257-281.
Himmclblau D. Applied Nonlinear Programming. Mir Publishers, 1975.
Nelder J., Mead R. A simplex method for function minimization // Computer Journal, 1965. V. 7. N 4. P. 308-313.
Brahmbhatt S. Practical OpenCV (Technology in Action). New York: Apress, 2013.
OpenCV (open source computer vision) documentation (accessed: 10 July 2022). [El. Res.]: https://docs.opencv.org/4.x/de/dd6/ml\_intro.html.
Sysoyev, Barkalov K., Sovrasov V., Lebedev I., Gergel V. Globalizer — a parallel software system for solving global optimization problems // Lecture Notes in Computer Science, 2017. V. 10421. N LNCS. P. 492-499.
Gaviano M., Lera D., Kvasov D.E., Sergeyev Y. D. Software for generation of classes of test functions with known local and global minima for global optimization // ACM Transactions on Mathematical Software, 2003. V. 29. P. 469-480.
Sergeev Ya. D., Kvasov D.E. Diagonal Global Optimization Methods. Fizmatlit, 2008.
Sergeyev Y.D., Kvasov D.E. Global search based on efficient diagonal partitions and a set of Lipschitz constants // SIAM Journal on Optimization, 2006. V. 16. N 3. P. 910-937.

Bibliographic reference: Silenko D. I., Lebedev I. G. Global optimization algorithm that uses decision trees to find local extrema //journal “Problems of informatics”. 2023, № 2. P.21-33. DOI:10.24412/2073-0667-2023-2-21-33

article

A. A. Korotysheva*, S.N. Zhukov*, V. R. Milov**,Y. S. Yegorov**, A.Y. Chekusheva**, M.S. Dubov***

*Lobachevsky State University of Nizhny Novgorod, 603022, Nizhny Novgorod, Russia

**Nizhny Novgorod State Technical University n. a. R. E. Alekseev, 603950, Nizhny Novgorod, Russia

***LLC “Mabex”, 603122, Nizhny Novgorod, Russia

CLASSIFICATION OF UNLABELED BATTERY ON X-RAY IMAGES USING MACHINE LEARNING METHODS

DOI: 10.24412/2073-0667-2023-2-34-44

EDN: ACWWCK

The problem of identifying and classifying hazardous and valuable species of municipal solid waste (MSW), especially unlabeled cell batteries, has become increasingly important in the light of current global environmental policies, which emphasize the need for increased recycling and utilization of waste. With the introduction of a variety of environmental initiatives, it is essential to ensure that proper identification and classification of MSW is carried out in order to reduce the environmental impact of MSW. This includes identifying and classifying hazardous and valuable materials, such as cell batteries, to ensure they are reused and recycled rather than disposed of in landfills. Furthermore, the development of effective strategies for the detection and classification of MSW is essential in order to maximize the economic and environmental benefits associated with the recycling and utilization of waste. This article describes an approach to the standard-size, unlabeled cylindrical cell batteries identification, powered by computer vision. To achieve this goal, a video camera and an X-ray machine are used to analyze and process images. The images captured by the video camera are first processed by a series of steps involving data preprocessing, feature extraction and model training. All the extracted features are then combined to form a model which can be used to accurately detect and recognize the cell batteries in the MSW stream on the conveyor belt. The developed procedures ensure a sufficiently high-quality classification of intact label batteries, and thus can be used to effectively identify the batteries in multiple scenarios. An extra step of digital radiography image processing is proposed, which allows for recognition even when the marking is significantly damaged. This novel approach to image processing offers a dependable and accurate method for the classification of batteries, even when their markings are no longer clearly visible or are completely obscured. This is a great benefit, as previous techniques relied on the clarity of the markings, which created difficulties when those markings were faint or absent. The core of the batteries identification system is a neural network, trained on a data set containing X-ray images of various types of batteries along with the associated classes. This neural network MobilcNctV2 is used to extract features from the images, allowing it to correctly classify the batteries for further sorting. The proposed method of batteries neural network classification, including the optical images and X-ray images processing, thus forms the backbone of a software and hardware complex for automated MSW sorting lines. The use of this system to identify and sort batteries would greatly reduce manual labor, improve accuracy and increase the efficiency of the sorting process. Additionally, the use of this system could also potentially reduce the amount of time required to sort the batteries, as the neural network can process the images much faster than a human can. This system could thus revolutionize the MSW sorting process, making it more accurate and efficient than ever before.

Key words: machine learning, X-ray images, neural network, batteries, image classification.

This work was funded by the Fund for the Development- of Small Forms of Enterprises in the Scientific and Technical Sphere (Agreement No. 57GS1IIS12-D7/72200 of 21.12.2021)

References

Blohin M. A. Rentgenovskoe izluchenie // Fizicheskaya enciklopediya: [v 5 t.] / Gl. red. A.M. Prohorov. M.: Bol’shava rossiiskava enciklopediva, 1994. T. 4: Pointinga-Robertsona-Strimerv. S. 375-377.
Principy postroeniya dosmotrovoj rentgenovskoj tekhniki. [Electron. Res.]: http://tstk.narod. ru/tsiotk/ppdrt.html (accessed: 14.01.2023) (in Russian).
Leshchenko V. G., Il’ich G.K. Medicinskaya i biologicheskaya fizika / M.: INFRA-M, 2012.
Kaggle: Your Home for Data Science. [Electron. Res.]: https://www.kaggle.com/ (accessed: 16.01.2023).
Mahsotova, С. V. Issledovanie metodov klassifikacii pri nesbalansirovannosti klassov // Nauchnyj zhurnal. 2017. № 5(18). S. 35-36. (in Russian).
Sandler M., Howard A. G., Zhu M., Zhmoginov A., Chen L.-C. MobileNetV2: Inverted Residuals and Linear Bottlenecks // Computer Vision and Pattern Recognition. 2018. P. 4510-4520.
Blatov R. L, Vostryakova E. A., Moskvin A. S., Chuprov D. A., Egorov Yu. S., Korotysheva A. A., Milov V.R., Dubov M.S., Kerbeneva A.Yu. Svidetel’stvo о registracii programmy dlya EVM RUS 2022663863. Zayavka№ 2022662975 ot 11.07.2022. (in Russian).

Bibliographic reference: Korotysheva A. A., Zhukov S.N., Milov V.R., Yegorov Y.S., Chekusheva A.Y., Dubov M.S. Classification of unlabeled battery on X-ray images using machine learning methods //journal “Problems of informatics”. 2023, № 2. P.34-44. DOI:10.24412/2073-0667-2023-2-34-44

article

A. A. Kudryavtsev*, V. E. Malyshkin*’**’***, Yu. Yu. Nushtaev*, V.A. Perepelkin*’**’***, V.A. Spirin*

*Novosibirsk State University, 630090, Novosibirsk, Russia,

**Institute of computational mathematics and mathematical geophysics SB RAS, 630090, Novosibirsk, Russia,

***Novosibirsk State Technical University, 630073, Novosibirsk, Russia

EFFICIENT FRAGMENTED IMPLEMENTATION OF THE TWO PHASE FLUID BOUNDARY VALUE PROBLEM

DOI: 10.24412/2073-0667-2023-2-45-73

EDN: IWCDKX

Programs construction automation is an approach which can potentially reduce complexity and laboriousness of development, debugging and modification of numerical parallel programs for multicomputers. In high performance computing it is important not just to construct a valid program, but also to make it efficient, which is a challenging problem with no satisfactory general solution. Thus various programming systems are only capable of providing high efficiency of constructed programs for a limited range of applications. To achieve this the systems employ various heuristics and particular effective solutions. Evolution of parallel program construction automation means consists in accumulating such heuristics and particular solutions in order to improve efficiency of constructed programs, as well as to widen the range of applications the system can handle effectively. It is important to investigate various particular manual implementations of numerical programs from the perspective of the possibilities of further automation of such construction. Fragmented programming technology is an approach for numerical parallel programs development and construction automation. The approach is based on the theory of parallel programs synthesis on the basis of computational models. The approach is partially supported by LuNA system, which is a system for numerical parallel programs construction automation for distributed memory systems (multicomputers). The paper is devoted to study of a particular application — a two phase fluid boundary value problem solver for a 3D case and presence of wells. The application is implemented as a fragmented program in two versions: the first one is based on conventional means (MPI and OpenMP), and the second one is using LuNA system.

The basic idea behind fragmented programming is to consider a parallel program as an aggregate of sequential parts called computational fragments (CF). Each CF is implemented by a conventional sequential subroutine with no side effects. Input and output arguments of CFs are immutable pieces of data called data fragments (DFs). The execution process is considered as execution of a set of CFs in a data-flow manner, where each CF is ready for execution once all its input DFs are computed. CF’s execution produces a number of output DFs. If the program is represented as a set of CFs and DFs a system can be used to perform execution and provide dynamic properties of the execution, such as dynamic load balancing.

LuNA system offers a domain specific language LuNA to describe the set of CFs and DFs as LuNA- program. The system then translates the program into an intermediate representation, executable bv the runtime subsystem. The runtime subsystem is basically a distributed virtual machine, which implements CFs execution in data-flow manner. Such an approach significantly simplifies the process of parallel program construction, since the programmer does not do parallel programming as such. He only describes the set of CFs and DFs, provides conventional sequential subroutines which implement CFs in C++, and that’s all. No programming of communications, synchronizations, memory management and other low-level details is required. However, the efficiency of execution of LuNA programs may be significantly lower, than that of manually developed program using conventional parallel programming means. That is caused by the fact that construction of an efficient parallel program from its high-level specification is algorithmically hard in general case. To help LuNA system to construct more efficient programs the programmer is provided with means to tune the construction process. The means are called recommendations and directives. Usage of the means can significantly increase the efficiency of the constructed program by supplying the system with the programmer’s insight on how he suggests to execute fragments. Such information includes hints on CFs and DFs distribution and redistribution to nodes, order of CFs execution, garbage collection directives, etc.

In the paper an in-depth analysis of the considered application is provided to elaborate an efficient parallel implementation of the numerical algorithm in a multi-core distributed environment. Then an efficient conventional distributed program is developed and described in the paper. The program is developed using MPI and OpenMP. Then, a LuNA program is developed and optimized. The process of development and optimization of LuNA program is presented in the paper to allow reuse of the experience for future development of similar fragmented programs. Then the experimental study of the efficiency of the constructed programs is presented. The implementations were examined on a representative set of parameters for three different hardware environments, namely, Novosibirsk State University Computing Center and Joint Supercomputer Center of RAS with Ethernet and InfiniBand interconnects. The conventional distributed program has shown the speedup of 2.3x on 6 nodes, which is a satisfactory result for the application class. The LuNA program has shown about 3x slowdown on up to 16 computing nodes as compared to MPI implementation, which is a good result for an automatic parallel programs construction system.

To conclude, the research has resulted in development of an efficient MPI implementation of the application, based on an in-depth analysis of the numerical algorithm. Current version of LuNA system was tested for its ability to construct efficient parallel program in real life computations, and the tests showed, that LuNA is capable of it. All the implementations are described in the paper in details to allow other programmers to reuse the experience for implementation and optimization of other fragmented programs. The conducted research can also be used as the basis for development of system algorithms, capable of automatic optimization of efficiency of similar LuNA programs.

Key words: Fragmented programming, LuNA system, parallel programs construction automation, high performance computing, case study.

This work was carried out under state contract with ICMMG SB RAS 0251-2021-0005.

References

Ivanov M. L, Kremer LA., Laevsky Yu. M. On the streamline upwind scheme of solution to the filtration problem // Siberian Electronic Mathematical Reports. 2019. V. 16. P. 757-776.
Ivanov M. L, Kremer LA., Laevsky Yu.M. On wells modeling in filtration problems // Siberian Electronic Mathematical Reports. 2019. V. 16. P. 1868-1884.
Malyshkin V. E., Perepelkin V. A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2011. Lecture Notes in Computer Science. V. 6873. Springer, Berlin, Heidelberg, https://doi.org/ 10.1007/978-3-642-23178-0\_5.
Sintez parallelnykh programm i sistem na vychislitelnykh modelyah / V. A. Valkovsky, V. E. Malyshkin. Novosibirsk: Nauka. 1988. 126 p. (In Russian).
Malyshkin V. E. Tekhnologiya fragmentirovannogo programmirovaniya // Vestnik YuUrGU. Seriya: Vychislitelnaya matematika i informatika. 2012. N 46 (305) (In Russian).
Perepelkin V. A., Ivanov M. I. Povysheniye proizvoditelnosti LuNA-programm na ostove vosproizvedeniva trass / / Desvatava Sibirskava konferenciva po parallelnvm i vvsokoproizvoditelnvm vychisleniyam. Sbornik statey. Tomsk, 2021. P. 29-36 (In Russian).
Informacionno-vychislitelnyi tsentr Novosibirskogo gosudarstvennogo universiteta. [Electron. Res.]: http: //nusc. nsu. ru/wiki/doku. php/doc/index.
Joint supercomputing center of Russian academy of sciences. [Electron. Res.]: http://www.jscc. ru.

Bibliographic reference: Kudryavtsev A. A., Malyshkin V.E., Nushtaev Yu. Yu., Perepelkin V. A., Spirin V. A. Efficient fragmented implementation of the two phase fluid boundary value problem //journal “Problems of informatics”. 2023, № 2. P.45-73. DOI:10.24412/2073-0667-2023-2-45-73

article

N.A. Matolygina, M.L. Gromov, A. K. Matolygin

National Research Tomsk State University, 634050, Tomsk, Russia

APPLICATION OF THE TENSOR APPROACH TO THE SOFTWARE IMPLEMENTATION OF THE CELLULAR AUTOMATON FLOW MODEL

DOI: 10.24412/2073-0667-2023-2-74-85

EDN: JIPOXl

Cellular-automaton models are actively used to model physical processes. The cellular automata in these models are large and require a large number of iterations to observe effects of interest. Researchers use parallel technologies to organize calculations in order to get the result quickly. The choice of technology usually depends on the level of the researcher’s skills in the field of parallel programming. Parallel programming is a complex skill, and to get it you need to learn a lot of theory and even more practice. We have proposed a special tensor approach to the software implementation of cellular automata to free the researcher from these difficulties and help to create a parallel software product.

A special framework that automatically parallelizes computations at NVIDIA GPU cores is central to the approach. The chosen framework is TensorFlow. The main data structure of TensorFlow is a tensor (multidimensional matrix). Thus, in order to implement a cellular automaton using the tensor approach, it is necessary to represent the cellular automaton as a tensor, and the logic of the automaton transition from one state to another as operations on tensors.

There are two options for applying tensor operations. The first option is to use ready-made operations. The framework implements simple operations that work with ordinary matrices, and more complex operations, such as convolution. In this case, the researcher needs to analyze how the cellular automaton works and select the necessary tensor operations that implement the automaton. The second option is to create your own tensor operation. A custom operation is created using CUDA technology. In this case, the structural elements are ordinary two-dimensional arrays that represent tensors. The user needs to independently allocate the number of threads and blocks required for calculations. The TensorFlow developer libraries allow you to implement operations on data both as programs for the central processor and as programs for graphics adapters in the CUDA C programming language.

In this paper, to demonstrate the performance and capabilities of the tensor approach, the well- known cellular automaton FHP flow model is implemented. There are two phases in this model: collision and propagation. It was decided to implement our own operation, which describes the logic of the automaton, after analyzing the existing TensorFlow operations. Both phases of the FHP model are implemented by us with one custom operation, which is implemented in TensorFlow. The operation takes as input a tensor corresponding to a cellular automaton and a tensor of random numbers to determine the propagation direction. At the output, the operation generates a tensor, to the elements of which the propagation phase and the collision phase are applied. Experiments with the model implemented using the tensor approach were carried out. The gas flow in an open longitudinal pipe is simulated. The particle source is located on one side of the pipe. In the first part of the experiment, an obstacle in the form of a small oblong object is located in the pipe, in the second part — a small round object. The experimental results are visualized and the picture of the process agrees with the results obtained in other literature sources.

Additionally, a comparative experiment was carried out to evaluate the effectiveness of the tensor approach. In this case, we compared the number of automaton cells processed per second in our implementation on TensorFlow and in an implementation written using only CUDA technology. The results of the comparison showed that when implementing the FHP flow model using the tensor approach, fewer (by 10 or 100 times, depending on the size of the cellular automaton) cells are processed in the same time than in an implementation built on only one CUDA technology. Despite the fact that the implementation of the flow model in TensorFlow is inferior to the implementation written in CUDA in terms of time, the process of building a parallel software implementation is simpler and does not require the researcher to have a deep understanding of the features of parallel programming.

Key words: cellular automaton, tensor approach, gas flow.

References

Kalgin К. V. Kletochno-avtomatnoe modelirovanie fiziko-himicheskih processov na vychisliteljah s parallel’noj arhitekturoj: dis. .. .kand. tehn. nauk. Novosibirsk: 2012. 82 s.
Subbotina A. Ju., Hohlov N. I. Realizacija kletochnyh avtomatov «Igra “Zhizn”’» i kletochnogo avtomata Kohomoto-Oono s primeneniem tehnologii MPI // Komp’juternye issledovanija i modelirovanie. 2010. T. 2. № 3. S. 319-322.
Sharifulina A. E. Parallel’naja realizacija kataliticheskoj reakcii (CO+O2>CO2) // Vestnik JuUrGU. 2012. № 47(306). S. 112-126.
Szkoda S., Koza Z., Tykierko M. Accelerating cellular automata simulations using AVX and CUDA // arXiv preprint . 2012. arXiv:1208.2428vl.
Kalgin К. V. Realizacija algoritmov s melkozernistym parallelizmom na graficheskih uskoriteljah // Sib. zhurn. vychisl. matem. 2011. T. 14. № 1. S. 46-55.
TensorFlow [Electron, res.]: https://www.tensorflow.org.
Shalyapina N. A., Gromov M. L. «Life» in Tensor: Implementing Cellular Automata on Graphics Adapters // Proceedings of the Institute for System Programming of the RAS. 2019. T. 31. N 3. S. 217-228. DOI: https://doi.org/10.15514/ISPRAS-2019-31(3)-17.
Frisch U., Hasslacher B., Pomeau Y. Lattice-Gas automata for Navier-Stokes equations // Phys. Rev. Lett. 1986. N 56. P. 1505.
Tumakov D. N. Tehnologija programmirovanija CUDA: uchebnoe posobie / Kazanskij gosudarstvennyj universitet. Kazan’, 2017. 112 s.
Szkoda S., Koza Z., Tykierko M. Multi-GPGPU Cellular Automata Simulations using OpenACC // Zenodo. 2014. P. 1-6. DOI: 10.5281/zenodo.822901.

Bibliographic reference: Matolygina N. A., Gromov M. L., Matolygin A. K. Application of the tensor approach to the software implementation of the cellular automaton flow model //journal “Problems of informatics”. 2023, № 2. P.74-85. DOI:10.24412/2073-0667-2023-2-74-85

article

I.Mikulik, E. Blagoveshchenskaya

Petersburg State Transport University, 190031, Saint Petersburg, Russia

PARALLEL IMPLEMENTATION OF THE ANT COLONY ALGORITHM WITH PARAMETERS UPDATE USING THE GENETIC ALGORITHM

DOI: 10.24412/2073-0667-2023-2-86-97

EDN: HBTPLC

The paper considers the possibility of using a joint implementation of a hybrid method using the ant colony optimization with genetic algorithm for solving traveling salesman problem. It is known that the ant colony optimization is sensitive to its parameters, so the search for the optimal parameters of the ant colony is suitable as a problem, the solution of which is related to the genetic algorithm. The one of the purposes of calculations parallelization is to reduce execution time, but not every algorithm has an effective parallel implementation. It is known that the genetic algorithm and the ant colony optimization are parallelized. The paper studies the possibility of constructing parallel computations for the hybrid method presented. The traveling salesman problem on which the research is conducted is an NP-complete problem and it is often used to test combinatorial optimization algorithms. It is shown that parallelization of the method used leads to an increase in the speed of the algorithm.

Key words: traveling salesman problem, optimization methods, ant colony optimization, genetic algorithm, parallel computing.

The research was supported by the Russian Science Foundation (project No. 22-21-00267).

References

Zhang N. Moore’s law is dead, long live moorc’s law! / / arXiv preprint arXiv:2205.15011, 2022.
Pujol R., Jorba J., Tabani H., Kosmidis L., Mezzetti E., Abella J., Cazorla F. Vector extensions in cots processors to increase guaranteed performance in real-time systems, 2022. ACM Transactions on Embedded Computing Systems (TECS).
Zhou K. Feng X. A collaborative grouping aggregation query scheme on heterogeneous computing systems / / in 2022 7th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA), 2022. P. 53-61.
Regassa D., Ycom H., Son Y. Harvesting the aggregate computing power of commodity computers for supcrcomputing applications // Applied Sciences, 2022. V. 12, N 10, P. 5113.
Ong B. W., Schroder J. B. Applications of time parallelization // Computing and Visualization in Science, 2020. V. 23, N 1. P. 1-15.
Blagoveshchenskaya E., Zuev D., Kuznecova I., Tihomirov S. Prilozhcniya algoritmov prvamvh razlozhcnii abclcvvh grupp bez kruchcniva к zadacham rasparallelivaniva vvchislitcl’nvh i konstruktivnyh processov / / in Mczhdunarodnyc Kolmogorovskic chtcniya-XIV, posvyashchennye 100- letiyu professora Z. A. Skopcca, 2017. P. 38-40.
Stutzle Т. Parallelization strategies for ant colony optimization //in International Conference on Parallel Problem Solving from Nature. Springer, 1998. P. 722-731.
Hassan M., Hasan M., Hashem M. et al. An improved acs algorithm for the solutions of larger tsp problems. arXiv preprint arXiv:1304.3763, 2013.
Liang D., Zhan Z.-H., Zhang Y., Zhang J. An efficient ant colony system approach for new energy vehicle dispatch problem // IEEE Transactions on Intelligent Transportation Systems, 2019. V. 21. N 11. P. 4784-4797.
Zhou X., Ma H., Gu J., Chen H., Deng W. Parameter adaptation-based ant colony optimization with dynamic hybrid mechanism // Engineering Applications of Artificial Intelligence, 2022. V. 114. P. 105139.
Olivas F., Valdez F., Castillo O., Gonzalez С. I., Martinez G., Melin P. Ant colony optimization with dynamic parameter adaptation based on interval type-2 fuzzy logic systems // Applied Soft Computing, 2017. V. 53. P. 74-87.
Blagoveshchenskaya E. A., Mikulik I. I., Strbungmann L. H. Ant colony optimization with parameter update using a genetic algorithm for travelling salesman problem // Models and Methods for Researching Information Systems in Transport 2020 (MMRIST 2020), 2020. N 1. P. 20-25.
Baydogmus G. K. A parallelization based ant colony optimization for travelling salesman problem //in 2022 1st International Conference on Information System & Information Technology (ICISIT). IEEE, 2022. P. 166-169.
Liu G., Xu X., Wang F., Tang Y. Solving traveling salesman problems based on artificial cooperative search algorithm // Computational Intelligence and Neuroscience, 2022. V. 2022.
El-Khatib S. , Skobtsov Y. , Rodzin S. , Zakharov V. Comparison of modified object detected graph cut and hybrid ant colony optimization-k-means for mri images segmentation //in Computer Science On-line Conference. Springer, 2021. P. 701-708.
Brand M., Masuda M., Wehner N., Yu X.-H. Ant colony optimization algorithm for robot path planning // in 2010 international conference on computer design and applications, V. 3. IEEE, 2010. P. V3-436.
Whitley D. Next generation genetic algorithms: a user’s guide and tutorial //in Handbook of metaheuristics. Springer, 2019. P. 245-274.
Katoch S., Chauhan S. S., Kumar V. A review on genetic algorithm: past, present, and future // Multimedia Tools and Applications, 2021. V. 80, N 5. P. 8091-8126.
Singh G., Gupta N. A study of crossover operators in genetic algorithms //in Frontiers in Nature-Inspired Industrial Optimization. Springer, 2022. P. 17-32.
Lambora A., Gupta K., Chopra K. Genetic algorithm-a literature review //in 2019 international conference on machine learning, big data, cloud and parallel computing (COMITCon). IEEE, 2019. P. 380-384.

Bibliographic reference: Mikulik I., Blagoveshchenskaya E. Parallel implementation of the ant colony algorithm with parameters update using the genetic algorithm //journal “Problems of informatics”. 2023, № 2. P.86-97. DOI:10.24412/2073-0667-2023-2-86-97

article

Main menu

Volume 2(59)

Languages

Main menu

You are here

Volume 2(59)

Languages