Simulated  Annealing

 

Simulated annealing Àº Ä¿´Ù¶õ Ž»ö°ø°£¿¡¼­ ÁÖ¾îÁø ÇÔ¼öÀÇ Àü¿ª ÃÖÀûÁ¡ (global optimum) ¿¡ ´ëÇÑ ÈǸ¢ÇÑ ±Ù»çÄ¡¸¦ ãÀ¸·Á°í ÇÏ´Â Àü¿ªÃÖÀûÈ­ (global optimization) ¹®Á¦¿¡ ´ëÇÑ ÀϹÝÀûÀÎ È®·üÀû ÈÞ¸®½ºÆ½ (probabilistic heuristic) Á¢±Ù¹æ½ÄÀÌ´Ù. ÀÌ ¹æ¹ýÀº 1983 ³â¿¡ S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, 1985 ³â¿¡ V. Cerny ÀÌ °¢°¢ µ¿½Ã¿¡ ¹ß¸íÇÑ °ÍÀÌ´Ù.

±× ¸íĪ°ú Á¤½ÅÀº ¾ß±ÝÇÐ (metallurgy) ¿¡¼­ ´ã±ÝÁú (annealing)¿¡¼­ µû¿Â °ÍÀÌ´Ù. Áï °áÁ¤Ã¼ (crystals) ÀÇ Å©±â¸¦ Å©°ÔÇÏ°í °áÇÔ (defects) À» ÀÛ°Ô ÇÏ·Á°í ±Ý¼Ó¿¡ ¿­À» °¡ÇÏ°í ³Ã°¢½ÃÅ°´Â ¼Óµµ¸¦ Á¶ÀýÇÏ´Â (controlled cooling) ±â¼ú¿¡¼­ µû¿Â °ÍÀÌ´Ù. ¿­À» °¡ÇÏ¸é ¿øÀÚ (atoms) ´Â ÃÖÃÊÀÇ À§Ä¡ (³»ºÎ ¿¡³ÊÁöÀÇ ±¹¼Ò ÃÖÀûÁ¡ (local minimum)) ¿¡¼­ ¶³¾îÁ® ³ª°¡°í ´õ ³ôÀº ¿¡³ÊÁö »óÅ·ΠÁ¤Ã³¾øÀÌ ¹æȲÇÏ°Ô µÈ´Ù ; ¼­¼­È÷ ³Ã°¢½ÃÅ°¸é ÃÖÃÊÀÇ »óź¸´Ù ´õ ³·Àº ³»ºÎ ¿¡³ÊÁö¸¦ °¡Áö´Â ȯ°æÀ» ãÀ» ¼ö ÀÖ´Â ±âȸ¸¦ ´õ ¸¹ÀÌ °¡Áö°Ô µÈ´Ù.....  ....... (Wikipedia : Simulated annealing)

Áö¿ª ÃÖ¼Ò°ª¿¡¼­ÀÇ Å»Ãâ

ÀÌ·¯ÇÑ °³³äµéÀº °íüÀÇ ¹°¸®ÀûÀÎ ´ã±ÝÁú°ú ¾ÆÁÖ ¸¹Àº °æ¿ìÀÇ ¼ö¸¦ °¡Áø Á¶ÇÕ ÃÖÀûÈ­ (Combinatorial Optimization) ¹®Á¦ »çÀÌÀÇ ¹ÐÁ¢ÇÑ °ü°è¿¡ ÀÇ°ÅÇÑ´Ù......... Simulated annealing Àº ½Å°æ¸Á (Neural Network) ÀÇ ±¸Á¶¸¦ °®´Â °ÍÀº ¾Æ´Ï´Ù. ´ÜÁö ÀÌ·¯ÇÑ °³³äÀ¸·Î ¿©·¯ ´Ù¸¥ ½Å°æ¸ÁÀÇ ÇнÀ°úÁ¤À» º¯È­½ÃÄÑÁÙ ¼ö ÀÖ´Ù. ½ÇÁ¦ ¸¹Àº ½Å°æ¸Á ½Ã½ºÅÛ¿¡¼­ ÇнÀÇÑ´Ù´Â °³³äÀº minimization °úÁ¤À¸·Î º¼ ¼ö ÀÖÀ¸¸ç, ±×°ÍÀº energy function À̳ª error function¿¡¼­ downward ¹æÇâÀ¸·Î °£´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. ÇÏÁö¸¸ ±×·¯ÇÑ °æ¿ì initial weight °ªÀ» À߸ø ¼±ÅÃÇϸé local minimum °ª¿¡ ºüÁö°í ¸¶´Â °æ¿ì°¡ »ý±â°Ô µÈ´Ù. ÀÌ·¯ÇÑ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÑ ¹æ¾ÈÀ¸·Î simulated annealing °³³äÀÌ µµÀԵǾú´Ù.

...... ±Ý¼ÓÀÇ ´ã±ÝÁú (annealing) À̶õ °íü¸¦ ³ìÀ» ¶§±îÁö °¡¿­ÇÏ°í ³­ ÈÄ ±×°ÍÀ» ¿ÏÀüÇÑ °ÝÀÚ »óÅÂÀÇ °áÁ¤Ã¼°¡ µÉ ¶§±îÁö ½ÄÈ÷´Â ¹°¸®ÀûÀÎ °úÁ¤ÀÌ´Ù. ÀÌ·± °úÁ¤ Áß¿¡ ±× °íüÀÇ ÀÚÀ¯ ¿¡³ÊÁö (free energy) ´Â ÃÖ¼ÒÈ­µÈ´Ù. ¿À·¡ ÀüºÎÅÍÀÇ °æÇè¿¡ ÀÇÇÏ¸é °íüȭµÇ´Â °úÁ¤¿¡¼­ Áö¿ª ÃÖ¼ÒÁ¡¿¡ ºüÁöÁö ¾Êµµ·Ï Çϱâ À§Çؼ­´Â Á¶½É½º·´°Ô ¼­¼­È÷ ½ÄÇô¾ß ÇÑ´Ù.

...... ±Ý¼ÓÀç·á µîÀ» °¡¿­ÇÑ ÈÄ ¼­¼­È÷ ³Ã°¢½ÃÄÑ ³»ºÎÀÇ °áÇÔÀ» ¾ø¾Ö´Â ¹æ¹ý°ú À¯»çÇÏ¿© ½Ã¹Ä·¹ÀÌƼµå ¾î´Ò¸µ (simulated annealing) À̶ó ºÎ¸¥´Ù. ¿©±â¿¡¼­ Áß¿äÇÑ °ÍÀº ¿Âµµ¸¦ ³·Ã߾´Â ¹æ¹ýÀÌ´Ù. ¿Âµµ¸¦ ³Ê¹« ±Þ¼ÓÈ÷ ³·Ã߸é ÆòÇà»óŸ¦ ÀÌ·ç¾îµµ ÃÖ¼Ò ¿¡³ÊÁö »óÅ¿¡ µµ´ÞÇÒ È®·üÀÌ Àû°í, ³Ê¹« õõÈ÷ ³·Ã߸é ÃÖ¼Ò ¿¡³ÊÁö¿¡ µµ´ÞÇÒ È®·üÀº Ä¿ÁöÁö¸¸ ¸¹Àº ¹Ýº¹À» ÇÊ¿ä·Î ÇϹǷΠ½Ã°£ÀÌ ¸¹ÀÌ °É¸°´Ù. ......

Á¶ÇÕ ÃÖÀûÈ­ (combinatorial optimization) ¹®Á¦¿¡¼­µµ ÀÌ¿Í À¯»çÇÑ °úÁ¤À» Á¤ÀÇÇÒ ¼ö ÀÖ´Ù. ÀÌ °úÁ¤Àº ÀáÀçÀûÀ¸·Î ¸Å¿ì ¸¹Àº ÇØ°á¹æ¾È Áß¿¡¼­ ÃÖ¼ÒÀÇ ºñ¿ëÀÌ µå´Â ÇØ´äÀ» ±¸ÇÏ´Â ¹®Á¦·Î °ø½ÄÈ­µÉ ¼ö ÀÖ´Ù. ¿ì¸®´Â ¿©±â¼­ ºñ¿ë ÇÔ¼ö (cost function) ¿Í ÀÚÀ¯ ¿¡³ÊÁö »çÀÌÀÇ °ü°è, ±×¸®°í ÇØ´ä°ú ¹°¸®ÀûÀÎ »óÅÂÀÇ °ü°è¸¦ Á¤¸³ÇÔÀ¸·Î½á ¹°¸®ÀûÀÎ ´ã±ÝÁú °úÁ¤ÀÇ ½Ã¹Ä·¹À̼ǿ¡ ÀÇ°ÅÇÑ Á¶ÇÕ ÃÖÀûÈ­ ¹®Á¦ÀÇ ÇØ°á ¹æ¾ÈÀ» ¼Ò°³ÇÒ ¼ö Àִµ¥ ÀÌ·¯ÇÑ ¹æ¹ýÀÌ ¹Ù·Î Simulated Annealing ÀÌ´Ù.

ÀÌ ¹æ¹ýÀÇ µÎµå·¯Áø Ư¡Àº Æø³ÐÀº ÀÀ¿ë °¡´É¼º°ú ÃÖ»ó¿¡ °¡±î¿î ÇØ´äÀ» ¾òÀ» ¼ö ÀÖ´Ù´Â Á¡ÀÌ´Ù. ±×·¯³ª ÀÌ ¹æ¹ý¿¡µµ »ó´çÈ÷ Å« ´ÜÁ¡ÀÌ ÀÖ´Ù. »ó´çÈ÷ ÁÁÀº ÇØ´äÀ» ¾ò´Âµ¥ °É¸®´Â °è»ê ½Ã°£ÀÌ ¾öû³ª°Ô ±æ´Ù´Â Á¡ÀÌ´Ù. ±×·¯³ª ½Ã¹Ä·¹ÀÌƼµå ¾î´Ò¸µ ¾Ë°í¸®ÁòÀÇ ±¸Çö½Ã ÇÊ¿äÇÑ ¾öû³­ ½Ã°£Àº ´ë±Ô¸ð º´·Äó¸® (massively parallel execution) ¸¦ ±â¹ÝÀ¸·Î ÇÏ´Â °è»ê ¸ðµ¨À» »ç¿ëÇÔÀ¸·Î½á »ó´çÈ÷ ÁÙÀÏ ¼ö Àִµ¥ ±×·¯ÇÑ ¸ðµ¨ ÁßÀÇ Çϳª°¡ ¹Ù·Î º¼Â길 ¸Ó½Å (Boltzmann Machine) ÀÌ´Ù. .... (±è´ë¼ö 1992)

term :

½Å°æ¸Á (Neural Network)   ÁöµµÇнÀ (Supervised Learning)   ½Ã¹Ä·¹ÀÌƼµå ¾î´Ò¸µ (Simulated Annealing)   º¼Â길 ¸Ó½Å (Boltzmann Machine)   Á¶ÇÕÃÖÀûÈ­ (Combinatorial Optimization)   º´·ÄºÐ»êó¸® (Parallel Distributed Processing)

paper :

½Ã¹Ä·¹ÀÌƼµå ¾î´Ò¸µ°ú º¼Â길 ¸Ó½Å : ±è´ë¼ö

À¯ÀüÀÚ ¾Ë°í¸®Áò°ú ½Ã¹Ä·¹ÀÌƼµå ¾î´Ò¸µÀ» ÀÌ¿ëÇÑ È°¼º¿Ü°û¼± ¸ðµ¨ÀÇ ¿¡³ÊÁö ÃÖ¼ÒÈ­ ±â¹ý ºñ±³ (Comparison of Genetic Algorithm and Simulated Annealing Optimization Technique to Minimize the Energy of Active Contour Model) : ¹Ú¼±¿µ, ±è¸íÈñ, ¹ÚÁÖ¿µ, ÄÄÇ»Åͱ׷¡ÇÈÇÐȸ, 1998

site :

Homepage of Emile Aarts

Parallel Simulated Annealing ( F. H. Allisen Lee & Dyke Stiles , Utah State)

Simulated Annealing Information, Taygeta Scientific Inc. [Monterey]

Ensemble Based Simulated Annealing   (Richard Frost , San Diego)

Adaptive Simulated Annealing by Lester Ingber

COSA: Cooperative Simulated Annealing   (Oliver Wendt , Frankfurt)

Parallel Simulated Annealing ( Ralf Diekmann , Paderborn)

Parallel Simulated Annealing for T3E

CalTech Adaptive Simulated Annealing (ASA) site.

Collection of Computer Science Bibliographies has many references on simulated annealing

parSA, Parallel Simulated Annealing Library