Algorithm for solving the problem of irregular pattern cutting using of artificial neural networks
Аннотация
The article is devoted to the problem of placing non-standard geometric shapes on a rectangular sheet with the condition of maximum filling density. This task belongs to the class of irregular cutting-packaging and meant to minimize waste after cutting sheet material. The article describes the formulation of the problem of cutting sheet material. The parameters influencing the solution of the cutting problem are identified. The restrictions imposed on the implementation apparatus are determined. A brief analysis of existing methods suitable for solving the problem of location and spacing of blanks sheet material is carried out. The features of the operation of neural networks that affect the solution of the problem are specified. The choice of a neural network model with a description of the necessary mathematical apparatus for solving the cutting problem are made. A new combined algorithm for solving the problem of cutting sheet material based on the technology of artificial neural networks is proposed. A procedure for training an agent with a formula for his rewarding is introduced. The results of experimental studies of a software product based on the proposed algorithm are presented.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Yagudin R. R. (2012) Optimization of the layout of three-dimensional geometric objects based on the locus of the vector function of dense placement. Engineering Bulletin of Don. № 3.(in Russian)...
2. Petunin A. A. (2010) Automatic choice of the calculating methodof the figure cutting using the comparative analysis of TPU. 5. (in Russian)
3. Petrenko S. V. (2005 ) Optimization of the two-dimensional geometric objects on Aniso tropic material placement using mathematical programming methods [AutoAction]: PhD thesis: 05.15.18: Defended 22.12.2005: approved. Petrenko Semyon Vasilyevich. Ufa. 16 p. (in Russian)
4. Murzakaev R. T., Shilov V. S. and Burkova A. V. (2013) Basic methods for solving the problem of figured irregular stacking of flat parts. IVD. № 4 (27).(in Russian)
5. Kononov A. A. (2019) Using the Hopfield neural network method for solving the problem of routing in a network. Moscow Economic Journal. No. 9. (in Russian)
6. Hassanin Hatem Mohamed Abdel Maksud (2015) Solving optimization problems using a Hopfield neural network. Fundamental research. No. 2 (part 22). P. 4886–4892.
7. Petunin A. A. About one approach to the choice of an algorithm for calculating true figure cutting. III International Scientific Conference “Modern Problems of Informatization in Modeling Systems, Programming and Telecommunications”. (in Russian)
8. Dykhoff H. (1990 ) A typology of cutting and packing problems. European Journal of OperationalResearch. V. 44. P. 145–159
9. Aryanezhad M. B., Fakhim Hashemi N., Makui A. et al. (2012) A simple approach to the two-dimensional guillotine cutting stock problem. J IndEngInt 8, 21. DOI
10. Jahromi M. H., Tavakkoli-Moghaddam R., Makui A. et al. (2012) Solving an one-dimensional cutting stock problem by simulated annealing and tabu search. J IndEngInt 8, 24. DOI
11. Kochetov Yu. A. (2009 ) Methods of local search for discrete placement problems: abstract of thesis. ... of Doctor of physical and mathematical sciences: 05.13.18 / Kochetov Yuri Andreevich. Novosibirsk. 29 p. (in Russian)
12. Volchenko E. V. and Drozd I. V. (2009) Hybrid algorithm for optimal pattern placement. Bulletin of Khmelnitsky National University. Section: “Technical Sciences”. No. 1. (in Russian)
13. Orlov A. N., Kureichik V. V. and Glushchenko A. E. (2016) Combined genetic algorithm for solving the cutting problem. Izvestiya YuFU. Technical science. No. 6 (179). (in Russian)
14. Verkhoturov M. A. (2001) The problem of irregular placement of geometric objects: the current state of solution methods. Resource-saving technologies. S. Petersburg : TsNIITS. P. 33–56. (in Russian)
15. Emelyanov V. V., Kureichik V. V. and Kureichik V. M. (2003) Theory and practice of evolutionary modeling. M. : FIZMAT LIT. 432 p. (in Russian)
16. Podlazova A. V. (2008) Genetic algorithms on examples of solving cutting problems. Management problems. No. 2. (in Russian)
17. Dao S. D., Abhary K. and Marian R. (2017) An improved genetic algorithm for multidimensional optimization of precedence-constrained production planning and scheduling. J IndEngInt 13. P. 143–159. DOI
18. Shtovba S. D. (2003) Ant algorithms. ExponentaPro. Mathematics in applications. No. 4. P. 70–75.
19. Valeeva A. F., Petunin A. A. and Fayzrakhmanov R. I. (2007) Application of constructive metaheuristics “ant colony” to the problem of rectangular guillotine cutting. Bulletin of BashkirianUniversity. No. 3. (in Russian)
20. Yusupova N. I., Valeeva A. F. and Fayzrakhmanov R. I. (2012 ) Probabilistic algorithm of an ant colony for solving problems of cutting industrial materials into blanks of various geometric shapes. Information technologies. 5. P. 35–42 (in Russian)
21. Xiaoping Liao, Junyan Ma, Chengyi Ou, Fengying Long and Xiangsha Liu (2016) Visual nesting system for irregular cutting-stock problem based on rubber band packing algorithm. Advances in Mechanical Engineering. Vol. 8(6). P. 1–15.
22. Gafarov F. M. and Galimyanov A. F. (2018) Artificial neural networks and their applications: teaching material. Kazan : Kazan UniversityPublishing House. 121 p. (in Russian)
23. Kruglov V. V. and Borisov V. V. (2002) Artificial neural networks. Theory and practice. 2nd ed., Stereotype. M. : Hot line – Telecom. 382 p. (in Russian)
24. Sosnin A. S. and Suslova I. A. (2019) Neural network activation functions: sigmoid, line ar, stepwise, relu, than. Science. Informatization. Technologies. Education. Materials of the XII International Scientific and Practical Conference. 2019 Publisher: Russian State Vocational Pedagogical University (Yekaterinburg). 9 p.(in Russian)
25. Sozykin A. V. (2017) Review of methods for teaching deep neural networks. Bulletin of YuUrGU. Series: Computational Mathematics and Informatics. Vol. 6, No. 3. P. 28–59. DOI
26. Burakov M. V. (2013 ) Neural networks and neurocontrollers: textbook. allowance. SPb. : GUAP. 284 p. (in Russian)
27. Rashchenko Yu. V. (2018) Application of modified artificial neural networks in machine vision problems [text]: master’s degree thesis. Rashchenko Yulia Vladimirovna. St. Petersburg. – 62 p. (in Russian)
28. Mazurov M. E. (2018) Teaching selective neural networks without mathematics and without a teacher based on self-organization. Reports of the International Conference “Mathematical Biology and Bioinformatics”. Ed. V. D. Lakhno. Volume 7. Pushchino: IMPB RAS. Article No. e32 (in Russian)
29. Yuxi Li (2017 ) Deep Reinforcement Learning: An Overview. Computer Science, arXiv:1701.07274 [cs.LG] 25 Jan 2017.
30. Tai L. and Liu M. (2016) Mobile robots exploration through cnn-based reinforcement learning. Robot. Biomim. 3, 24. DOI
31. Arthur Charpentier, Romuald Elie and Carl Remlinger (2020) Reinforcement Learning in Economics and Finance // arXiv:2003.10014v1 [econ.TH] 22 Mar 2020
32. Sutton R. S. and Barto E. J. (2020 ) P21 Reinforcement Learning: Introduction / trans. from English A. A. Slinkina. M. : DMK Press. 552 p.
33. Hado van Hasselt and Marco A. Wiering (2007) Reinforcement Learning in Continuous Action Spaces. Proceedings of the 2007 IEEE Symposium on ApproximateDynamic Programming and Reinforcement Learning (ADPRL 2007)
34. Hado van Hasselt (2012) Reinforcement Learning in Continuous State and Action Spaces. M. Wiering and M. van Otterlo (Eds.): Reinforcement Learning, ALO 12. Springer-Verlag Berlin Heidelberg. P. 207–251
35. Murzakaev R. T. and Lyalin D. A. (2013) Algorithm for compacting the cutting chart based on a two-dimensional gravity simulation model. Modern Science: Actual Problems of Theory and Practice. No. 9–10. P. 34–41. (in Russian)
36. Vetchaninov A. A. (2016) Software for the coverage problem based on a gravity-simulation model with a random vector of force application [text]: bak. vkr. Arseny A. Vetchaninov. Perm. 79 p. (in Russian)
2. Petunin A. A. (2010) Automatic choice of the calculating methodof the figure cutting using the comparative analysis of TPU. 5. (in Russian)
3. Petrenko S. V. (2005 ) Optimization of the two-dimensional geometric objects on Aniso tropic material placement using mathematical programming methods [AutoAction]: PhD thesis: 05.15.18: Defended 22.12.2005: approved. Petrenko Semyon Vasilyevich. Ufa. 16 p. (in Russian)
4. Murzakaev R. T., Shilov V. S. and Burkova A. V. (2013) Basic methods for solving the problem of figured irregular stacking of flat parts. IVD. № 4 (27).(in Russian)
5. Kononov A. A. (2019) Using the Hopfield neural network method for solving the problem of routing in a network. Moscow Economic Journal. No. 9. (in Russian)
6. Hassanin Hatem Mohamed Abdel Maksud (2015) Solving optimization problems using a Hopfield neural network. Fundamental research. No. 2 (part 22). P. 4886–4892.
7. Petunin A. A. About one approach to the choice of an algorithm for calculating true figure cutting. III International Scientific Conference “Modern Problems of Informatization in Modeling Systems, Programming and Telecommunications”. (in Russian)
8. Dykhoff H. (1990 ) A typology of cutting and packing problems. European Journal of OperationalResearch. V. 44. P. 145–159
9. Aryanezhad M. B., Fakhim Hashemi N., Makui A. et al. (2012) A simple approach to the two-dimensional guillotine cutting stock problem. J IndEngInt 8, 21. DOI
10. Jahromi M. H., Tavakkoli-Moghaddam R., Makui A. et al. (2012) Solving an one-dimensional cutting stock problem by simulated annealing and tabu search. J IndEngInt 8, 24. DOI
11. Kochetov Yu. A. (2009 ) Methods of local search for discrete placement problems: abstract of thesis. ... of Doctor of physical and mathematical sciences: 05.13.18 / Kochetov Yuri Andreevich. Novosibirsk. 29 p. (in Russian)
12. Volchenko E. V. and Drozd I. V. (2009) Hybrid algorithm for optimal pattern placement. Bulletin of Khmelnitsky National University. Section: “Technical Sciences”. No. 1. (in Russian)
13. Orlov A. N., Kureichik V. V. and Glushchenko A. E. (2016) Combined genetic algorithm for solving the cutting problem. Izvestiya YuFU. Technical science. No. 6 (179). (in Russian)
14. Verkhoturov M. A. (2001) The problem of irregular placement of geometric objects: the current state of solution methods. Resource-saving technologies. S. Petersburg : TsNIITS. P. 33–56. (in Russian)
15. Emelyanov V. V., Kureichik V. V. and Kureichik V. M. (2003) Theory and practice of evolutionary modeling. M. : FIZMAT LIT. 432 p. (in Russian)
16. Podlazova A. V. (2008) Genetic algorithms on examples of solving cutting problems. Management problems. No. 2. (in Russian)
17. Dao S. D., Abhary K. and Marian R. (2017) An improved genetic algorithm for multidimensional optimization of precedence-constrained production planning and scheduling. J IndEngInt 13. P. 143–159. DOI
18. Shtovba S. D. (2003) Ant algorithms. ExponentaPro. Mathematics in applications. No. 4. P. 70–75.
19. Valeeva A. F., Petunin A. A. and Fayzrakhmanov R. I. (2007) Application of constructive metaheuristics “ant colony” to the problem of rectangular guillotine cutting. Bulletin of BashkirianUniversity. No. 3. (in Russian)
20. Yusupova N. I., Valeeva A. F. and Fayzrakhmanov R. I. (2012 ) Probabilistic algorithm of an ant colony for solving problems of cutting industrial materials into blanks of various geometric shapes. Information technologies. 5. P. 35–42 (in Russian)
21. Xiaoping Liao, Junyan Ma, Chengyi Ou, Fengying Long and Xiangsha Liu (2016) Visual nesting system for irregular cutting-stock problem based on rubber band packing algorithm. Advances in Mechanical Engineering. Vol. 8(6). P. 1–15.
22. Gafarov F. M. and Galimyanov A. F. (2018) Artificial neural networks and their applications: teaching material. Kazan : Kazan UniversityPublishing House. 121 p. (in Russian)
23. Kruglov V. V. and Borisov V. V. (2002) Artificial neural networks. Theory and practice. 2nd ed., Stereotype. M. : Hot line – Telecom. 382 p. (in Russian)
24. Sosnin A. S. and Suslova I. A. (2019) Neural network activation functions: sigmoid, line ar, stepwise, relu, than. Science. Informatization. Technologies. Education. Materials of the XII International Scientific and Practical Conference. 2019 Publisher: Russian State Vocational Pedagogical University (Yekaterinburg). 9 p.(in Russian)
25. Sozykin A. V. (2017) Review of methods for teaching deep neural networks. Bulletin of YuUrGU. Series: Computational Mathematics and Informatics. Vol. 6, No. 3. P. 28–59. DOI
26. Burakov M. V. (2013 ) Neural networks and neurocontrollers: textbook. allowance. SPb. : GUAP. 284 p. (in Russian)
27. Rashchenko Yu. V. (2018) Application of modified artificial neural networks in machine vision problems [text]: master’s degree thesis. Rashchenko Yulia Vladimirovna. St. Petersburg. – 62 p. (in Russian)
28. Mazurov M. E. (2018) Teaching selective neural networks without mathematics and without a teacher based on self-organization. Reports of the International Conference “Mathematical Biology and Bioinformatics”. Ed. V. D. Lakhno. Volume 7. Pushchino: IMPB RAS. Article No. e32 (in Russian)
29. Yuxi Li (2017 ) Deep Reinforcement Learning: An Overview. Computer Science, arXiv:1701.07274 [cs.LG] 25 Jan 2017.
30. Tai L. and Liu M. (2016) Mobile robots exploration through cnn-based reinforcement learning. Robot. Biomim. 3, 24. DOI
31. Arthur Charpentier, Romuald Elie and Carl Remlinger (2020) Reinforcement Learning in Economics and Finance // arXiv:2003.10014v1 [econ.TH] 22 Mar 2020
32. Sutton R. S. and Barto E. J. (2020 ) P21 Reinforcement Learning: Introduction / trans. from English A. A. Slinkina. M. : DMK Press. 552 p.
33. Hado van Hasselt and Marco A. Wiering (2007) Reinforcement Learning in Continuous Action Spaces. Proceedings of the 2007 IEEE Symposium on ApproximateDynamic Programming and Reinforcement Learning (ADPRL 2007)
34. Hado van Hasselt (2012) Reinforcement Learning in Continuous State and Action Spaces. M. Wiering and M. van Otterlo (Eds.): Reinforcement Learning, ALO 12. Springer-Verlag Berlin Heidelberg. P. 207–251
35. Murzakaev R. T. and Lyalin D. A. (2013) Algorithm for compacting the cutting chart based on a two-dimensional gravity simulation model. Modern Science: Actual Problems of Theory and Practice. No. 9–10. P. 34–41. (in Russian)
36. Vetchaninov A. A. (2016) Software for the coverage problem based on a gravity-simulation model with a random vector of force application [text]: bak. vkr. Arseny A. Vetchaninov. Perm. 79 p. (in Russian)
Опубликован
2024-05-28
Как цитировать
Zykin, S. A., Valiakhmetova, Y. I., Petrenko, A. A., & Fayzrakhmanov, R. A. (2024). Algorithm for solving the problem of irregular pattern cutting using of artificial neural networks. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (1), 127-136. https://doi.org/10.17308/sait/1995-5499/2024/1/127-136
Выпуск
Раздел
Интеллектуальные системы, анализ данных и машинное обучение
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
