Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158
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....
Gespeichert in:
| Datum: | 2021 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2021
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/178 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479506906775552 |
|---|---|
| author | Kozin, Igor Maksyshko, Natalia Tereshko, Yaroslav |
| author_facet | Kozin, Igor Maksyshko, Natalia Tereshko, Yaroslav |
| author_institution_txt_mv | [
{
"author": "Igor Kozin",
"institution": "Запорізький національний університет, вул.Жуковського 66, 69600,Запоріжжя"
},
{
"author": "Natalia Maksyshko",
"institution": "Запорізький національний університет, вул.Жуковського 66, 69600,Запоріжжя"
},
{
"author": "Yaroslav Tereshko",
"institution": "Запорізький національний університет, вул.Жуковського 66, 69600,Запоріжжя"
}
] |
| author_sort | Kozin, Igor |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2021-09-06T08:16:14Z |
| description | 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
|
| doi_str_mv | 10.15407/fmmit2021.32.152 |
| first_indexed | 2026-06-09T01:07:22Z |
| format | Article |
| fulltext | |
| id | oai:ojs2.www.fmmit.lviv.ua:article-178 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:07:22Z |
| publishDate | 2021 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-1782021-09-06T08:16:14Z Simulated annealing method for equilibrium placement problem: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 Kozin, Igor Maksyshko, Natalia Tereshko, Yaroslav дискретна оптимізація метаевристика фрагментарна структура метод імітації відпалу задача рівноважного розміщення discrete optimization metaheuristics fragmented structure simulated annealing method equilibrium placement problem 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 У роботі пропонується модифікація алгоритму імітації відпалу стосовно задач, які мають фрагментарну структуру. Розглянуто алгоритм імітації відпалу для задачі комівояжера і показано його придатність до задачі оптимізації на множині перестановок. Доведено, що задача рівноважного розміщення точкових об'єктів на площині має фрагментарну структуру і, отже, зводиться до задачі оптимізації на множині перестановок. Наведено результати чисельних експериментів для різних видів алгоритмів пошуку оптимального розв’язку задачі рівноважного розміщення. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2021-07-08 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/178 10.15407/fmmit2021.32.152 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 32 (2021): Physico-mathematical modeling and informational technologies, 2021, Issue 32; 152-158 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 32 (2021): Фізико-математичне моделювання та інформаційні технології, 2021, Вип. 32; 152-158 2617-5258 1816-1545 10.15407/fmmit2021.32 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/178/168 Авторське право (c) 2021 Igor Kozin, Natalia Maksyshko, Yaroslav Tereshko (Автор) |
| spellingShingle | дискретна оптимізація метаевристика фрагментарна структура метод імітації відпалу задача рівноважного розміщення Kozin, Igor Maksyshko, Natalia Tereshko, Yaroslav Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title | Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title_alt | Simulated annealing method for equilibrium placement problem: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title_full | Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title_fullStr | Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title_full_unstemmed | Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title_short | Метод імітації відпалу для задачі рівноважного розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| title_sort | метод імітації відпалу для задачі рівноважного розміщення: fìz.-mat. model. ìnf. tehnol. 2021, 32:152-158 |
| topic | дискретна оптимізація метаевристика фрагментарна структура метод імітації відпалу задача рівноважного розміщення |
| topic_facet | дискретна оптимізація метаевристика фрагментарна структура метод імітації відпалу задача рівноважного розміщення discrete optimization metaheuristics fragmented structure simulated annealing method equilibrium placement problem |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/178 |
| work_keys_str_mv | AT kozinigor simulatedannealingmethodforequilibriumplacementproblemfizmatmodelinftehnol202132152158 AT maksyshkonatalia simulatedannealingmethodforequilibriumplacementproblemfizmatmodelinftehnol202132152158 AT tereshkoyaroslav simulatedannealingmethodforequilibriumplacementproblemfizmatmodelinftehnol202132152158 AT kozinigor metodímítacíívídpaludlâzadačírívnovažnogorozmíŝennâfizmatmodelinftehnol202132152158 AT maksyshkonatalia metodímítacíívídpaludlâzadačírívnovažnogorozmíŝennâfizmatmodelinftehnol202132152158 AT tereshkoyaroslav metodímítacíívídpaludlâzadačírívnovažnogorozmíŝennâfizmatmodelinftehnol202132152158 |