Optimalno podešavanje parametara simuliranog kaljenja

  • Allaoua Hemmak Univerzitet Mohamed Budijaf u Msili, Odsek za računarske nauke, Laboratorija za primenjenu informatiku (LIAM), Msila, Narodna Demokratska Republika Alžir https://orcid.org/0000-0002-5799-8882
DOI: https://doi.org/10.5937/vojtehg72-47242
Ključne reči: simulirano kaljenje, podešavanje parametara, optimizacija, metaheuristika

Sažetak


Uvod/cilj: Simulirano kaljenje je moćna tehnika široko primenjivana u problemima optimizacije. Kritični momenat pri efikasnom korišćenju simuliranog kaljenja jeste pravilno i optimalno podešavanje njegovih parametara. U radu je predstavljen inovativni pristup efikasnom podešavanju parametara simuliranog kaljenja čiji je cilj poboljšanje njegovih performansi i brzine konvergencije.  

Metode: Budući da je simulirani algoritam inspirisan Metropolis procesom hlađenja, osnovna ideja je da se ovaj proces simulira i analizira pomoću matematičkog modela. Predloženi rad se fokusira na pravilno preslikavanje Metropolis procesa hlađenja u oblast algoritama. Inteligentno podešavajući temperaturni raspored, kao i brzinu redukcije temperature i hlađenja, algoritam optimizuje ravnotežu između eksploracije i eksploatacije, što rezultira poboljšanom konvergencijom i rešenjima visokog kvaliteta. 

Rezultati: Da bi se ispitala efikasnost ovog pristupa, najpre je primenjen za minimizaciju izabranog uzorka funkcije, a zatim na već poznatim funkcijama optimizacije. Rezultati pokazuju da naš pristup, nazvan optimalno podešavanje parametara simuliranog kaljenja (Optimal Adjusting of Simulated Annealing parameters (OASA)), demonstrira superiorne performanse u poređenju sa tradicionalnim statičkim podešavanjima parametara, kao i sa ostalim postojećim pristupima, tako što pokazuje kako da se uspešno podese parametri algoritma simuliranog kaljenja radi poboljšavanja njegove efikasnosti, odnosno kvaliteta rešenja i vremena procesiranja.

Zaključak: Podešavanje parametara algoritma moglo bi značajno da doprinese oblasti optimizacije, čak i kada je reč o drugim metaheuristikama.

Reference

Bertsimas, D. & Nohadani, O. 2010. Robust optimization with simulated annealing. Journal of Global Optimization, 48, pp.323-334. Available at: https://doi.org/10.1007/s10898-009-9496-x.

Bertsimas, D. & Tsitsiklis, J.N. 1993. Simulated Annealing. Statistical Science, 8(1), pp.10-15. Available at: https://doi.org/10.1214/ss/1177011077.

Benvenuto, N., Marchesi, M. & Uncini, A. 1992. Applications of simulated annealing for the design of special digital filters. IEEE Transactions on Signal Processing, 40(2), pp.323-332. Available at: https://doi.org/10.1109/78.124942.

Bierlaire, M. 2006. Introduction à l’optimisation différentiable. Lausanne, Switzerland: EPFL Press. ISBN: 978-2-88074-669-8.

Chen, T.-Y. & Su, J.-J. 2002. Efficiency improvement of simulated annealing in optimal structural designs. Advances in Engineering Software, 33(7-10), pp.675-680. Available at: https://doi.org/10.1016/S0965-9978(02)00058-3.

Frausto-Solis, J., Román, E.F., Romero, D., Soberon, X. & Liñán-García, E. 2007. Analytically Tuned Simulated Annealing Applied to the Protein Folding Problem. In: Shi, Y., van Albada, G.D., Dongarra, J. & Sloot, P.M.A. (Eds.) Computational Science – ICCS 2007, 7th International Conference, Beijing, China, May 27-30. Berlin, Heidelberg: Springer, vol 4488. Available at: https://doi.org/10.1007/978-3-540-72586-2_53.

Gao, Y., Wang, C. & Liu, C. 2016. An Archived Multi-Objective Simulated Annealing Algorithm for Vehicle Routing Problem with Time Window. International Journal of u- and e- Service, Science and Technology, 9(12) pp.187-198. Available at: https://doi.org/10.14257/ijunesst.2016.9.12.17.

Hu, Q. & Lim, A. 2014. An iterative three-component heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 232(2), pp.276-286. Available at: https://doi.org/10.1016/j.ejor.2013.06.011.

Ingber, L. 1989. Very fast simulated re-annealing. Mathematical and Computer Modelling, 12(8), pp.967-973. Available at: https://doi.org/10.1016/0895-7177(89)90202-1.

Ingber, L. 2000. Adaptive Simulated Annealing (ASA): Lessons learned. arXiv:cs/0001018. Available at: https://doi.org/10.48550/arXiv.cs/0001018.

Jeong, S.-J., Kim, K.-S. & Lee, Y.-H. 2009. The efficient search method of simulated annealing using fuzzy logic controller. Expert Systems with Applications, 36(3), pp.7099-7103. Available at: https://doi.org/10.1016/j.eswa.2008.08.020.

Jones, A.E.W. & Forbes, G.W. 1995. An adaptive simulated annealing algorithm for global optimization over continuous variables. Journal of Global Optimization, 6, pp.1-37. Available at: https://doi.org/10.1007/BF01106604.

Kim, S.-S., Baek, J.-Y. & Kang, B.-S. 2017. Hybrid Simulated Annealing for Data Clustering. Journal of Korean Society of Industrial and Systems Engineering, 40(2), pp.92-98. Available at: https://doi.org/10.11627/jkise.2017.40.2.092.

Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. 1983. Optimization by Simulated Annealing. Science, 220(4598), pp.671-680. Available at: https://doi.org/10.1126/science.220.4598.671.

Lin, S.-W. & Yu, V.-F. 2012. A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 217(1), pp.94-107. Available at: https://doi.org/10.1016/j.ejor.2011.08.024.

Najid, N.M., Dauzere-Peres, S. & Zaidat, A. 2017. A modified simulated annealing algorithm for solving flexible job shop scheduling problem. In: IEEE International Conference on Systems, Man and Cybernetics, Yasmine Hammamet, Tunisia, 5, October 6-9. Available at: https://doi.org/10.1109/ICSMC.2002.1176334.

Pan, X., Xue, L., Lu, Y. & Sun, N. 2019. Hybrid particle swarm optimization with simulated annealing. Multimedia Tools and Applications, 78, pp.29921-29936. Available at: https://doi.org/10.1007/s11042-018-6602-4.

Rajasekaran, S. 2000. On Simulated Annealing and Nested Annealing. Journal of Global Optimization, 16, pp.43-56. Available at: https://doi.org/10.1023/A:1008307523936.

Saruhan, H. 2014. Differential evolution and simulated annealing algorithms for mechanical systems design. Engineering Science and Technology, an International Journal, 17(3), pp.131-136. Available at: https://doi.org/10.1016/j.jestch.2014.04.006.

Zhang, R. 2013. A Simulated Annealing-Based Heuristic Algorithm for Job Shop Scheduling to Minimize Lateness. International Journal of Advanced Robotic Systems, 10(4), pp.1-9. Available at: https://doi.org/10.5772/55956.

Objavljeno
2024/03/05
Broj časopisa
Vol. 72 Br. 1 (2024): januar-mart
Rubrika
Originalni naučni radovi

Sva prava zadržana (c) 2024 Allaoua Hemmak

Creative Commons License

Ovaj rad je pod Creative Commons Autorstvo 4.0 međunarodnom licencom.

Vojnotehnički glasnik omogućava otvoreni pristup i, u skladu sa preporukom CEON-a, primenjuje Creative Commons odredbe o autorskim pravima:

Autori koji objavljuju u Vojnotehničkom glasniku pristaju na sledeće uslove:

  1. Autori zadržavaju autorska prava i pružaju časopisu pravo prvog objavljivanja rada i licenciraju ga Creative Commons licencom koja omogućava drugima da dele rad uz uslov navođenja autorstva i izvornog objavljivanja u ovom časopisu.
  2. Autori mogu izraditi zasebne, ugovorne aranžmane za neekskluzivnu distribuciju rada objavljenog u časopisu (npr. postavljanje u institucionalni repozitorijum ili objavljivanje u knjizi), uz navođenje da je rad izvorno objavljen u ovom časopisu.
  3. Autorima je dozvoljeno i podstiču se da postave objavljeni rad onlajn (npr. u institucionalnom repozitorijumu ili na svojim internet stranicama) pre i tokom postupka prijave priloga, s obzirom da takav postupak može voditi produktivnoj razmeni ideja i ranijoj i većoj citiranosti objavljenog rada (up. Efekat otvorenog pristupa).