Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158

• Datum: 2021
• Hauptverfasser: Kozin, Igor, Maksyshko, Natalia, Tereshko, Yaroslav
• Format: Artikel
• Sprache: Ukrainisch
• Veröffentlicht: Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2021
• Schlagworte: дискретна оптимізація; метаевристика; фрагментарна структура; метод імітації відпалу; задача рівноважного розміщення
• Online Zugang: https://www.fmmit.lviv.ua/index.php/fmmit/article/view/178
• Назва журналу: Physico-mathematical modeling and informational technologies

The paper proposes a modification of the simulated annealing algorithm as applied to problems that have a fragmented structure. An algorithm for simulating annealing for the traveling salesman problem is considered and its applicability to the optimization problem on a set of permutations is shown. It is proved that the problem of equilibrium placement of point objects on a plane has a fragmentary structure and, therefore, reduces to an optimization problem on a set of permutations. The results of numerical experiments for various types of algorithms for finding the optimal solution in the equilibrium placement problem are presented. References Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco. Shherbina, O. A. (2014). Metae`vristicheskie algoritmy` dlya zadach kombinatornoj optimizaczii (obzor). Tavricheskij vestnik informatiki i matematiki, 1, 56-72. Skobczov, Yu. A., Fedorov, E. E. (2013). Osnovy` e`volyuczionny`kh vy`chislenij. Doneczk: Izd-vo «Noulindzh». Lopatin, A. S. (2005). Metod otzhiga. Stokhasticheskaya optimizacziya v informatike. SPb. : Izd-vo SPbGU, 1, 133–149. Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680. DOI doi.org/10.1126/science.220.4598.671 van Laarhoven, P. J. M., Aarts E.H.L. (1987). Simulated Annealing: Theory and Applications. Dordrecht:Springer. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., Teller, E. (1953). Equation of State Calculations by Fast Computer Machines. J. Chemical Physics, 21(6), 1087-1092. DOI doi.org/10.2172/4390578 Szu, H. H., Hartley R. L. (1987). Fast Simulated Annealing. Physical Letters A., 122, 157-162. Kozin, I. V., Maksyshko, N. K., Perepelitsa, V. A. (2017). Fragmentary Structures in Discrete Optimization Problems, Cybernetics and Systems Analysis November, 53(6), 931–936. DOI doi.org/10.1007/s10559-017-9995-6