Hill  Climbing

 

³¸¼± ¿µ¿ª¿¡¼­ »ç¶÷µéÀÌ ¾²´Â ¸Å¿ì ÈçÇÑ ¹®Á¦ ÇØ°á ¹æ¹ýÀº ÇöÀç »óÅÂ¿Í ¸ñÇ¥ »óÅ°£ÀÇ Â÷À̸¦ ÁÙÀÌ´Â °ÍÀÌ´Ù. Àΰ£Àº ¹®Á¦ÇØ°á (Problem Solving) À» ÇÒ ¶§ ÀÚÁÖ Â÷ÀÌ°¨¼Ò¹ý (difference reduction, ÇöÀç»óÅÂ¿Í ¸ñÇ¥»óÅÂÀÇ Â÷À̸¦ ÁÙ¿©¼­ ¸ñÇ¥¿¡ Á¢±ÙÇÏ´Â ¹æ¹ý) ¶Ç´Â ±× ¹Ý´ëÀÎ À¯»ç¼º (similarity, Nearest neighbour) ¿¡ ÀÇÇØ ¶È°°ÀÌ °­ÇÑ ¿µÇâÀ» ¹Þ´Â´Ù. ±×µéÀº Â÷À̸¦ ÁÙ¿©¼­ ÇöÀç »óź¸´Ù´Â ¸ñÇ¥ »óÅÂ¿Í ´õ °¡±õ°Ô ´àÀº »õ »óÅ·ΠÇöÀç »óŸ¦ ¹Ù²Ù´Â Á¶ÀÛÀÚµéÀ» ÅÃÇÑ´Ù..... Â÷ÀÌ °¨¼Ò¸¦ ¶§·Î´Â ¾ð´ö ¿À¸£±â (hill climbing) ¶ó°í ºÎ¸¥´Ù. ¸¸ÀÏ ¸ñÇ¥°¡ ¶¥¿¡¼­ °¡Àå ³ôÀº ÁöÁ¡À̶ó°í »ó»óÇÒ ¶§, °Å±â¿¡ µµ´ÞÇÏ´Â ¹æ¹ýÀº Ç×»ó À§·Î ¿Ã¶ó°¡´Â ´Ü°è¸¦ ¹â´Â °ÍÀÌ´Ù. ¸ñÇ¥¿Í ÇöÀç »óÅ °£ÀÇ Â÷À̸¦ ÁÙÀ̸鼭 ¹®Á¦ ÇØ°áÀÚ´Â ¸ñÇ¥¸¦ ÇâÇØ '´õ ³ôÀº' ´Ü°è¸¦ ¹â¾Æ°¡°í ÀÖ´Ù. ¾ð´ö ¿À¸£±â´Â ±æÀ» °è¼Ó µû¶ó°¡´Ù º¸¸é °¡Àå ³ôÀº ÁöÁ¡ (global maximum) ÀÎ ¸ñÇ¥º¸´Ù ³·Àº ¾î¶² ¾ð´öÀÇ ²À´ë±â¿¡ µµ´ÞÇÏ°Ô µÉÁöµµ ¸ð¸¥´Ù´Â ÀáÀçÀû À§ÇèÀ» °®°í ÀÖ´Ù (local maxima (maximum ÀÇ º¹¼öÇü)). µû¶ó¼­, Â÷ÀÌ °¨¼Ò°¡ ¹®Á¦ ÇØ°áÀ» º¸ÀåÇÏ´Â °ÍÀº ¾Æ´Ï´Ù. ±×°ÍÀº ´ÙÀ½ ´Ü°èÀÇ Çâ»ó ¿©ºÎ¸¸À» °í·ÁÇÏ°í ´õ Å« °èȹÀÇ ´Þ¼º ¿©ºÎ´Â °í·ÁÇÏÁö ¾Ê´Â ±Ù½Ã¾ÈÀû ¹æ¹ýÀÌ´Ù. ..... ¼ö´Ü¸ñÇ¥ ºÐ¼® (Means Ends Analysis) Àº ´õ ÃÑüÀûÀÎ ½Ã°¢À» ¹®Á¦ ÇØ°á¿¡ µµÀÔÇÏ·Á´Â ½ÃµµÀÌ´Ù ...... (John R. Anderson 1995)

¾î¶² ¹®Á¦´Â ¸í½ÃÀûÀÎ ¸ñÇ¥ Á¶°Ç ´ë½Å¿¡ ÀÚ·á ±¸Á¶¿¡ ´ëÇÑ ÇÔ¼ö °¡ ÀÖ°í, ÀÌ ÇÔ¼ö°¡ ÃÖ´ë (ȤÀº ÃÖ¼Ò) °¡ µÇ´Â ÀÚ·á ±¸Á¶¸¦ ã°íÀÚ ÇÏ´Â °æ¿ì°¡ ÀÖ´Ù. ÇϳªÀÇ ÀÚ·á ±¸Á¶¸¦ °ø°£¿¡ ÀÖ´Â ÇϳªÀÇ Á¡À̶ó°í »ý°¢Çϸé, ÀÌ ÇÔ¼ö´Â ÀÌ °ø°£»óÀÇ ÁöÇü (land-scape) À̶ó°í ÇÒ ¼ö ÀÖ´Ù. ÀÌ ÁöÇüÀ» µ¹¾Æ´Ù´Ï¸é¼­ °íµµ°¡ ³ôÀº Á¡À» ã´Â ÀÏ·ÃÀÇ ¹æ¹ýµéÀÌ ÀÖ´Ù. ÀÌ °æ¿ì Àü¿ª ÃÖ´ë°ª (global maximum) À» ¸ð¸£±â ¶§¹®¿¡ °íµµ°¡ ÃÖ´ëÀÎ Á¡¿¡ ´Ù´Þ¾Ò´ÂÁö È®½ÇÇÏ°Ô ¾Ë ¼ö ¾ø´Ù ............. °ø°£À» µ¹¾Æ´Ù´Ï´Â ±â¹ý °¡¿îµ¥ ¾ð´ö ¿À¸£±â (hill-climbing) ¹æ¹ýÀº ÇÑ Á¡¿¡¼­ °íµµ°¡ °¡Àå ³ôÀº ÀÎÁ¢ÇÑ Á¡À¸·Î À̵¿Çϸ鼭 ´Ù´Ï´Â °ÍÀÌ´Ù. ¾ð´ö ¿À¸£±â ¹æ¹ýÀº º¸Åë ÇöÀçÀÇ Á¡º¸´Ù ³ôÀº °íµµ¸¦ °¡Áø ÀÎÁ¢ÇÑ Á¡ÀÌ ¾øÀ¸¸é Á¾·áµÈ´Ù. µû¶ó¼­ Áö¿ª ÃÖ´ë°ª (local maxima) ¿¡ °É¸± ¼ö ÀÖ´Ù ........... (Nils J.Nilsson 1998)

Hill climbing search : Demo (¡Ú¡Ú¡Ú) : ÀÌ°ÍÀº ±íÀÌ¿ì¼± Ž»ö (Depth First Search) ¿¡ ±âÃÊÇÑ´Ù. Ž»ö È¿À²À» ³ôÀ̱â À§ÇØ ÈÞ¸®½ºÆ½ (Heuristic) ÀÌ »ç¿ëµÈ´Ù. °¢ ´Ü°è¿¡¼­ ¼±ÅÃÇÑ °ÍÀÌ ´Ù¸¥ °Íº¸´Ù ´õ ³ªÀºÁö¸¦ ÃøÁ¤ÇÏ°í °è¼ÓÇؼ­ ´Ù¸¥ ¼±ÅÃÀ» ÇÑ´Ù. ¾Ë°í¸®ÁòÀº ´ÙÀ½°ú °°´Ù

  1. root node¸¦ queue Q ¿¡ ³Ö¾î ù ¹ø° ¿ä¼Ò·Î ÇÑ´Ù. ÀÌÈÄ ±íÀÌ¿ì¼± Ž»öÀ» ¼öÇàÇÑ´Ù.
  2. Q °¡ ºñ¾î Àֵ簡 ¸ñÇ¥¿¡ À̸¦ ¶§±îÁö ¼öÇàÇÑ´Ù. Q ¿¡ Àִ ù ¹ø° ¿ä¼Ò°¡ ¸ñÇ¥ (remaining distance °¡ 0 ÀÎ »óÅÂ) ÀÎÁö¸¦ °áÁ¤ÇÑ´Ù. ¸¸ÀÏ ¸ñÇ¥°¡ ¾Æ´Ï¶ó¸é Q¿¡¼­ ù ¹ø° ¿ä¼Ò¸¦ Á¦°ÅÇÏ°í, ±× ÀڽijëµåµéÀ» ÀÜ¿©°Å¸® (remaining distance) ¿¡ µû¶ó sortÇÏ°í, sort µÈ ¸®½ºÆ®¸¦ Q ÀÇ ¾ÕÂÊ¿¡ ¹èÄ¡ÇÑ´Ù. ¸ñÇ¥°¡ ¾Æ´Ñ»óÅ¿¡¼­ Àڽijëµå°¡ ¾øÀ¸¸é ºÎ¸ð³ëµå·Î °£´Ù.
  3. ¸¸ÀÏ ¸ñÇ¥¿¡ µµ´ÞÇÏ¸é ¼º°øÀ̸ç, ±×·¸Áö ¾ÊÀ¸¸é ½ÇÆÐÀÌ´Ù.

Hill climbing ¹æ¹ýÀÇ ´ÜÁ¡Àº À¯»çÇÑ »óȲÀÌ »ý±æ ¼ö ÀÖ´Ù´Â °ÍÀÌ´Ù. Áï ÀÛÀº¾ð´ö (foothill)¿¡¼­ ½ÃÀÛÇÒ °æ¿ì´Â °Å±â¼­ ³Ê¹« ¸¹Àº ½Ã°£À» ¼ÒºñÇÏ¿© ¸ñÇ¥¿¡ À̸£Áö ¸øÇÒ °ÍÀÌ´Ù. ¶ÇÇÑ °í¿øÀÇ ÆòÁö (plateaus) ¿Í °°Àº ÆòźÇÑ °÷¿¡¼­´Â ºñ±³ÇÒ ´ë»óÀ» ãÁö ¸øÇØ ¾î¶² ¹æÇâÀ¸·Î °¡¾ßÇÒÁö¸¦ °áÁ¤¸øÇØ ¸ñÀû¾øÀÌ ¹æȲÇÒ ¼ö ÀÖ´Ù. ¾î´À ¿Ï¸¸ÇÑ »êµî¼ºÀÌ (ridge) ¿¡¼­´Â ¸ñÇ¥ÀÎÁö ¾Ë°í ³»·Á¿Ã ¼öµµ ÀÖ°ÚÁö¸¸ ±×°ÍÀÌ Á¤»óÀº ¾Æ´Ï´Ù.

Hill climbing ¹æ¹ýÀº ¿ÏÀüŽ»ö (complete search) ÀÌ´Ù. ´Ù¾çÇÑ Å½»ö¹æ¹ý Áß¿¡¼­ ¾î¶² °ÍÀÌ °¡Àå È¿À²¼ºÀ» Áõ°¡½ÃÄÑ search cost¸¦ ³·Ãâ ¼ö ÀÖ´ÂÁö´Â ¸ð¸£³ª heuristic Àº Hill climbing ¹æ¹ýÀÇ ´ÜÁ¡À» º¸¿ÏÇØÁÙ ÁÁÀº ¹æ¹ýÀÌ´Ù. Áï Hill climbing Àº »óÅ°ø°£¿¡¼­ °¡Àå È¿À²ÀûÀÎ °æ·Î¸¦ ¹Ýµå½Ã ã°Ô ÇØÁÖ´Â °ÍÀº ¾Æ´Ï´Ù.

Ž»ö (Search)   ±íÀÌ¿ì¼± Ž»ö (Depth First Search)   ÈÞ¸®½ºÆ½ (Heuristic)

Â÷ÀÌ °¨¼Ò¹ý (Difference Reduction) : John R. Anderson

ÇÔ¼ö ÃÖÀûÈ­ (Function Optimization) : Nils J.Nilsson