Optimization of the composition of software packages


Аuthors

Shably . D.

PJSC UAC Sukhoi Design Bureau, 23A, Polikarpova str., Moscow, 125284, Russia

e-mail: alexey.shabliy@gmail.com

Abstract

This article solves a topical optimization problem of selecting the composition of software packages. The problem is limited to the subject area of plug-in architectures, and the cost of the formed delivery is chosen as a metric.

First, the subject area is formalized, entities and relationships between them are identified. This formalization is completed by the formation of a graph model and a description of two algorithms: determining the composition of the supplied plug-ins and the cost of their delivery.

In the article, the distribution of functionality among plug-ins is considered as an argument for the operation of the described algorithms and two methods are proposed for finding the optimal distribution: mathematical formalization followed by solving a linear programming problem and the use of a genetic algorithm.

Mathematical expressions for solving an optimization problem are generally nonlinear. However, by applying the restrictions on the values ​​of parameters in expressions described in the article, their linearization is achieved, the implementation of which was carried out in accordance with the formulated and proven theorems.

A hypothesis about the graph configuration is formulated, in which the use of a genetic algorithm will have an advantage over the use of MILP solvers for the formed linear programming problem. This hypothesis is confirmed experimentally: the required running time of MILP solvers shows exponential growth with an increase in the size of the mathematical model, while the required running time of the genetic algorithm does not depend on the size of the model.

To conduct experiments and implement the genetic algorithm, two methods of its operation are considered: with binary data and discrete. The analysis method shows the advantage of working with discrete data over binary data and several configurations of the genetic algorithm with different functions of selection, crossover and mutation are proposed.

In conclusion, the prospects of further research and the feasibility of using open source software solutions to confirm the obtained theoretical results in practice are stated.

Keywords:

optimization problem, graph model, linear programming problem, linearization, genetic algorithm

References

  1. Titov Yu.P., Sudakov V.A. Modification of the asynchronous ant colony method for searching for rational solutions to a parametric problem. Trudy MAI. 2024. No. 135. (In Russ.). URL: https://trudymai.ru/eng/published.php?ID=179694

  2. Sayapin O.V., Tikhanychev O.V., Bezvesil'naya A.A., Chiskidov S.V. On one trend in the development of algorithms implemented in decision support systems. Programmnye produkty i sistemy. 2023. Vol. 36, No. 3. P. 388–397. (In Russ.). DOI: 10.15827/0236-235X.142.388-397

  3. Ai Min Taik, Lupin S.A., Fedyashin D.A. Using the MPI Library for Parallel Implementation of the Enumeration Algorithm. Programmnye produkty i sistemy. 2023. Vol. 36, No. 4. P. 607–614. (In Russ.). DOI: 10.15827/0236-235X.142.607 614

  4. Zubkova T.M., Kupyrev S.A. Calculation of Costs in Software Design. Mezhdunarodnyi nauchnyi zhurnal «Simvol nauki». 2024. Vol. 3, No. 4-1. P. 12-18. (In Russ.)

  5. Goncharov A.N., Klochai M.S. Review of Modular Design in Mobile Application Development: From Principles to Implementation. Vestnik nauki. 2024. Vol. 4, No. 3 (72). P. 320-327. (In Russ.)

  6. Zemskov M.A. Using modular monoliths to develop scalable web applications. Universum: tekhnicheskie nauki. 2024. No. 10 (127). (In Russ.). DOI: 10.32743/UniTech.2024.127.10.18445

  7. Vakushin A.A., Klebanov B.I. Application of large language models in simulation modeling. Inzhenernyi vestnik Dona. 2024. No. 2. P. 624-636. (In Russ.)

  8. Dagaev D.V. Instrumental approach to programming in the MultiOberon system. Programmnye sistemy i vychislitel'nye metody. 2024. No. 1. P. 31-47. (In Russ.). DOI: 10.7256/2454-0714.2024.1.69437

  9. Evglevskaya N.V., Kazantsev A.A. Ensuring the security of complex systems with the integration of large language models: analysis of threats and protection methods. Ekonomika i kachestvo sistem svyazi. 2024. No. 4. P. 129-143. (In Russ.)

  10. Masyukov I.I. Method and device for arranging tasks in reconfigurable computing systems. Trudy MAI. 2021. No. 120. (In Russ.). URL: https://trudymai.ru/eng/published.php?ID=161427. DOI: 10.34759/trd-2021-120-13

  11. Timofeeva O.P., Gordeev M.M., Sannikov A.N. Graph neural networks in solving problems with network structure. Trudy NGTU im. R.E. Alekseeva. 2023. No. 3. P. 43-50. (In Russ.). DOI: 10.46960/1816-210X_2023_3_43

  12. Noskov S.I. Linear programming problem with alternative constraints. Izvestiya TulGU. 2023. No. 7. P. 637-639. (In Russ.). DOI: 10.24412/2071-6168-2023-7-639-640

  13. Borodin D.V., Prutskov A.V. Application of graph model and heuristic function for software testing. Izvestiya TulGU. 2024. No. 3. P. 650-657. (In Russ.). DOI: 10.24412/2071-6168-2024-3-650-651

  14. Bogdanov I.P., Nesterov V.A., Sudakov V.A., Sypalo K.I., Toporov N.B. Optimization of the load of an ordered set of aircraft. Izvestiya RAN. Teoriya i sistemy upravleniya. 2021. No. 3. P. 57–70. (In Russ.). DOI: 10.31857/S0002338821030033

  15. Kobak V.G., Belodedov V.A. Influence of migrations in solving a heterogeneous minimax problem by an island model. Izvestiya vuzov. Severo-Kavkazskii region. Tekhnicheskie nauki. 2024. No. 2. P. 5–10. (In Russ.). URL: http://dx.doi.org/10.17213/1560-3644-2024-2-5-10

  16. Abuzyarov A.A., Makarov A.A. Application and comparison of evolutionary algorithms in the framework of reinforcement learning for unstable systems. Inzhenernyi vestnik Dona. 2023. No. 6. (In Russ.). URL: http://ivdon.ru/ru/magazine/archive/n6y2023/8477

  17. Panteleev A.V. Metaevristicheskie algoritmy optimizatsii zakonov upravleniya dinamicheskimi sistemami (Metaheuristic algorithms for optimizing control laws for dynamic systems). Moscow: Faktorial Publ., 2020. 564 p.

  18. Panteleev A.V., Skavinskaya D.V. Metaevristicheskie strategii i algoritmy global'noi optimizatsii (Metaheuristic strategies and algorithms for global optimization). Moscow: Faktorial Publ., 2023. 564 p.

  19. Kobak V.G., Ryazanov A.A. Solution of the traveling salesman problem using a modified Goldberg model using a generational strategy with different heuristics. Izvestiya vuzov. Severo-Kavkazskii region. Tekhnicheskie nauki. 2024. No. 1. P. 5–11. (In Russ.). URL: http://dx.doi.org/10.17213/1560-3644-2024-105-11

  20. Sivakova T.V., Sudakov V.A., Shimko V.S. Study of methods for solving mixed integer linear programming problems. Preprinty IPM im. M.V.Keldysha. 2024. No. 24. 18 p. (In Russ.). URL: https://doi.org/10.20948/prepr-2024-24 https://library.keldysh.ru/preprint.asp?id=2024-24

  21. Alpatov A.N., Bogatyreva A.A. Data storage format for analytical systems based on metadata and dependency graphs between CSV and JSON. Programmnye sistemy i vychislitel'nye metody. 2024. No. 2. (In Russ.). DOI: 10.7256/2454-0714.2024.2.70229

  22. Krotov K.V. Algorithm of the branch and bound method for optimizing schedules for executing task packages in conveyor systems. Informatsionno-upravlyayushchie sistemy. 2023. No. 2. P. 15-26. (In Russ.). DOI: 10.31799/1684-8853-2023-2-15-26

  23. Avramenko A.D., Sudakov V.A. Creating Synthetic Graphs for the Traveling Salesman Problem. Preprinty IPM im. M.V.Keldysha. 2024. No. 8. 16 p. (In Russ.). URL: https://doi.org/10.20948/prepr-2024-8 https://library.keldysh.ru/preprint.asp?id=2024-8

  24. Medvedik M.Yu., Barysheva A.D., Demidova A.P., Mekaeva V.A., Akashkina Yu.A. Finding the Eigenvalues of a Matrix Using the Sign Change Method. Vestnik Penzenskogo gosudarstvennogo universiteta. 2023. No. 2. P. 92–98. (In Russ.)

  25. Torishnyi R.O. On the Application of Second-Order Numerical Methods to Stochastic Programming Problems with a Probability Function. Trudy MAI. 2021. No. 121. (In Russ.). URL: https://trudymai.ru/eng/published.php?ID=162664. DOI: 10.34759/trd-2021-121-17

Download

mai.ru — informational site MAI

Copyright © 2000-2025 by MAI

 Вход