Simulated annealing method for equilibrium placement problem

Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158

Abstract

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

1. Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
2. Shherbina, O. A. (2014). Metae`vristicheskie algoritmy` dlya zadach kombinatornoj optimizaczii (obzor). Tavricheskij vestnik informatiki i matematiki, 1, 56-72.
3. Skobczov, Yu. A., Fedorov, E. E. (2013). Osnovy` e`volyuczionny`kh vy`chislenij. Doneczk: Izd-vo «Noulindzh».
4. Lopatin, A. S. (2005). Metod otzhiga. Stokhasticheskaya optimizacziya v informatike. SPb. : Izd-vo SPbGU, 1, 133–149.
5. 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
6. van Laarhoven, P. J. M., Aarts E.H.L. (1987). Simulated Annealing: Theory and Applications. Dordrecht:Springer.
7. 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
8. Szu, H. H., Hartley R. L. (1987). Fast Simulated Annealing. Physical Letters A., 122, 157-162.
9. 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