" />
Evolution Strategy
Google : ÁøÈÀü·« Google : Evolution Strategy
ÁøÈÀü·« : ȲÈñ¼ö : 1963 ³â¿¡ µ¶ÀÏ º£¸¦¸°±â¼ú´ëÇÐ (TUB) ÀÇ µÎ ÇлýÀÌ °ø±âÀúÇ×À» ÃÖ¼ÒÈÇÏ´Â ¹°Ã¼ÀÇ Çü»óÀ» ã±â À§ÇØ Ç³µ¿ ½ÇÇèÀ» ÇÏ¿´´Ù. ±âÁ¸ÀÇ °æ»ç¹ý¿¡ ÀÇÇÑ Å½»öÀÌ ½ÇÆÐÇÏ¿´À» ¶§, µÎ Çлý °¡¿îµ¥ ÇѸíÀ̾ú´ø ·¹Ä˺£¸£±× (Ingo Rechenberg) ´Â Çü»óÀ» Á¤ÀÇÇÏ´Â ÆÄ¶ó¸ÞŸ¸¦ µ¹¿¬º¯ÀÌ¿Í °°ÀÌ ·£´ýÇÏ°Ô º¯È½Ãų »ý°¢À» ÇÏ¿´´Ù. À̰ÍÀÌ ¹Ù·Î ÁøÈÀü·«ÀÌ Åº»ýÇÏ°Ô µÈ °è±â´Ù. 1973 ³â¿¡ ·¹Ä˺£¸£±×´Â 2 °³ÀÇ °³Ã¼·Î µÈ ÁøÈÀü·«À» ¹ßÇ¥ÇÏ¿´°í À̸¦ ´Ù¼öÀÇ °³Ã¼·Î È®ÀåÇÒ °ÍÀ» Á¦¾ÈÇÏ¿´´Ù.
ÁøÈÀü·«À» ¹ßÀü½ÃŲ ¶Ç ´Ù¸¥ »ç¶÷ÀÎ ½¬º£Æç (Hans Paul Schwefel) Àº 1977 ³â¿¡ ÁøÈÀü·«°ú ¼öÄ¡ ÃÖÀûȶó´Â ³í¹®À» ¹ßÇ¥ÇÏ¿´´Ù. ÁøÈÀü·«Àº ¸ñÀûÇÔ¼ö¸¦ ÇØ¼®Àû ÇüÅ·Π¸¸µé ¼ö ¾ø¾î¼ ±âÁ¸ÀÇ ÃÖÀûÈ ¹æ¹ýÀ» »ç¿ëÇÒ ¼ö ¾ø¾ú´ø ±â¼úÀûÀÎ ÃÖÀûÈ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇØ °í¾ÈµÇ¾ú´Ù. µÎ°³ÀÇ °³Ã¼·Î ±¸¼ºµÇ´Â ÃʱâÀÇ (1 + 1) ÁøÈÀü·«¿¡¼´Â, ¸Å ¼¼´ë¸¶´Ù ÇϳªÀÇ ºÎ¸ð °³Ã¼¿¡ Ç¥ÁØ Á¤±ÔºÐÆ÷¸¦ ÀÌ¿ëÇÑ µ¹¿¬º¯À̸¦ Àû¿ëÇØ¼ ºÎ¸ðº¸´Ù ¿ì¼öÇÑ ÀÚ½Ä °³Ã¼°¡ ¹ß»ýÇϸé, À̰ÍÀ¸·Î ºÎ¸ð °³Ã¼¸¦ ´ëüÇÑ´Ù.
ÀÌó·³ ´Ü¼øÇÑ ±¸Á¶¸¦ °®´Â ÃʱâÀÇ ÁøÈÀü·«¿¡ ´ëÇØ¼´Â µ¹¿¬º¯ÀÌ ¾çÀÇ Á¦¾î¿Í ¼ö·Å¼Óµµ¿Í °°Àº ÀÌ·ÐÀûÀÎ ¿¬±¸°¡ ¼öÇàµÇ¾ú´Ù. ÀÌ ¿¬±¸¿¡ µû¸£¸é, ¸ðµç µ¹¿¬º¯ÀÌ °¡¿îµ¥ ¼º°øÀûÀÎ µ¹¿¬º¯ÀÌ ºñÀ²Àº 1/5 ÀÌ´Ù. À̸¦ ÈçÈ÷ 1/5 ¼º°ø ±ÔÄ¢À̶ó ºÎ¸¥´Ù. µ¹¿¬º¯À̸¸À» »ç¿ëÇÏ´Â ÃʱâÀÇ ÁøÈÀü·«Àº ¥ì °³ÀÇ ºÎ¸ð °³Ã¼¸¦ »ç¿ëÇÔÀ¸·Î½á Àç°áÇÕ °úÁ¤À» Æ÷ÇÔÇÒ ¼ö ÀÖ´Â (¥ì + ¥ë) ÁøÈÀü·«À¸·Î ¹ßÀüÇÏ°Ô µÇ¾ú´Ù. µ¹¿¬º¯ÀÌ Ã¼°è¿Í ±× Å©±â¸¦ Á¦¾îÇÏ´Â ¹æ½ÄÀº (1 + 1) ÁøÈÀü·«°ú Â÷À̰¡ ¾ø´Ù. ½¬º£ÆçÀº ´Ù¼ö °³Ã¼¸¦ °®´Â ÁøÈÀü·«À» (¥ì + ¥ë) ÁøÈÀü·«°ú (¥ì, ¥ë) ÁøÈÀü·«À¸·Î ÀϹÝȽÃÄ×´Ù. ¿©±â¼ ¥ì ´Â Áý´ÜÀÇ Å©±â¸¦ ¸»ÇÏ¸ç ¥ë ´Â ¸Å ¼¼´ë¿¡¼ ¹ß»ýÇÏ´Â ÀÚ½Ä °³Ã¼ÀÇ ¼öÀÌ´Ù.
ÀÌ ÀϹÝÈµÈ ÁøÈÀü·«Àº ´Ù¼ö °³Ã¼·Î ±¸¼ºµÈ Áý´ÜÀ̶ó´Â °³³äÀ» µµÀÔÇÔÀ¸·Î½á ·£´ý ±³¹è, µ¹¿¬º¯ÀÌ¿Í ¼±ÅÃÀ̶ó´Â ÀÚ¿¬°èÁøÈ ¿ø¸®¸¦ ¸ð¹æÇÒ ¼ö ÀÖ°Ô µÇ¾ú´Ù. ÁøÈÀü·«Àº ¸¹Àº ½ÃÇè »ç·Ê¿¡¼ ¹Ýº¹ÀûÀÎ ´Ù¸¥ ¹æ¹ý¿¡ ºñÇØ ¼º°øÀûÀÓÀÌ ÀÔÁõµÇ¾ù´Ù. ÁøÈÀü·«Àº °³Ã¼ÀÇ Æò°¡ ¹æ¹ý ¿Ü¿¡´Â ¹®Á¦¿¡ ´ëÇÑ Á¤º¸¸¦ °ÅÀÇ ÇÊ¿ä·Î ÇÏÁö ¾Ê±â ¶§¹®¿¡, °ÅÀÇ ¸ðµç Á¾·ùÀÇ ÃÖÀûÈ ¹®Á¦¿¡ Àû¿ëµÉ ¼ö ÀÖ´Ù. ÁøÈÀü·«Àº ¼±Çü ¹× ºñ¼±Çü Á¦¾àÁ¶°ÇÀ» °®´Â °íÂ÷¿ø, ¸ÖƼ¸ð´ÞÀÇ ºñ¼±Çü ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Ù. ¸ñÀûÇÔ¼ö´Â ÇØ¼®Àû ÇüÅÂÀÏ ÇÊ¿ä´Â ¾øÀ¸¸ç, ½Ã¹Ä·¹ÀÌ¼Ç °á°ú°¡ ¸ñÀûÇÔ¼ö·Î »ç¿ëµÉ ¼öµµ ÀÖ´Ù. ÀÌ´Â Á¦¾àÁ¶°ÇÀÇ °æ¿ìµµ ¸¶Âù°¡ÁöÀÌ´Ù .......
ÁøÈÀü·«°ú À¯Àü¾Ë°í¸®ÁòÀÇ Æ¯¼º ºñ±³
|
ÁøÈÀü·« |
À¯Àü¾Ë°í¸®Áò |
Ç¥Çö¹æ½Ä |
½Ç¼ö |
º¸Åë ÀÌÁø ¹®ÀÚ¿ (½Ç¼öÇüµµ °¡´É) |
ÀÚ±â-ÀûÀÀ¼º |
Ç¥ÁØÆíÂ÷¿Í »óÈ£ºÐ»ê |
¾øÀ½ |
ÀûÇÕµµ |
¸ñÀûÇÔ¼ö °ª |
ºñÀ² Á¶Á¤µÈ ¸ñÀûÇÔ¼ö °ª |
µ¹¿¬º¯ÀÌ |
À¯ÀÏÇÑ ¿¬»êÀÚ |
º¸Á¶ ¿¬»êÀÚ |
±³¹è |
¾øÀ½ |
ÁÖ¿ä ¿¬»êÀÚ |
¼±Åà |
Á¾ÀÇ ¼öÁØ¿¡¼ ÁøÈ¸¦ ¸ð¹æÇÑ °ÍÀ¸·Î ±³¹è °úÁ¤ÀÌ ¾øÀ½. |
È®·üÀûÀÌ¸ç º¸Á¸¼ºÀÌ ÀÖÀ½ |
ÁøÈÀü·« : Áß¾Ó´ë Àΰø»ý¸í ¹× Áö´ÉÁ¤º¸ ½Ã½ºÅÛ ¿¬±¸½Ç : ÁøÈÀü·«(ES)Àº ÀÚ¿¬°èÀÇ ÁøÈÇö»ó¿¡ ±â¹ÝÇÑ °è»ê ¸ðµ¨·Î¼ ±¹¼ÒÇØ°¡ ¸¹Àº ÃÖÀûÈ ¹®Á¦ÀÇ ÇØ¸¦ ±¸ÇÏ´Â °ÍÀ» ¸ñÀûÀ¸·Î Rechenberg¿Í Schwefel¿¡ ÀÇÇÏ¿© 1960³â´ë¿¡ °³¹ßµÈ ¾Ë°í¸®ÁòÀÌ´Ù. ÁÖ ¿¬»êÀڷδ µ¹¿¬º¯À̸¦ »ç¿ëÇÏ°í °¡²û ±³¹è¸¦ »ç¿ëÇϱ⵵ ÇÑ´Ù ........ ESÀÇ °¢ °³Ã¼´Â (x,¥ò)¿Í °°ÀÌ ÇѽÖÀÇ ½Ç¼öº¤Åͷμ Ç¥ÇöµÈ´Ù. À̰ÍÀÇ x´Â Ž»ö°ø°£³»ÀÇ À§Ä¡ º¤ÅÍÀÌ¸ç ¥ò´Â Ç¥ÁØÆíÂ÷ º¤ÅͰ¡ µÈ´Ù. À̶§ µ¹¿¬º¯ÀÌ¿¡ ÀÇÇÑ ´ÙÀ½ ¼¼´ëÀÇ °³Ã¼´Â ´ÙÀ½°ú °°ÀÌ Ç¥ÇöµÈ´Ù.
xt+1 = xt + N(0,¥ò)
´Ü, N(0,¥ò)´Â Æò±ÕÀÌ, 0 Ç¥ÁØÆíÂ÷°¡ ¥òÀÎ
°¡¿ì½º ºÐÆ÷¸¦ µû¸£´Â ÀÓÀÇÀÇ ³¼öÀÌ´Ù.
¿©±â¼, ¥òÀÇ ¿ø¼Ò°¡ ¸ðµÎ °°À» ¶§, Áï ¥ò = (¥ò,¥ò,¡¦,¥ò)ÀÏ ¶§¸¦ Ưº°È÷
identical problem À̶ó°í ÇÑ´Ù.
ÃʱâÀÇ ES¿¡´Â ÇϳªÀÇ °³Ã¼·ÎºÎÅÍ Áý´ÜÀÇ Å½»öÀ» ÇàÇÏ¿´´Ù. ÀÌ·± °æ¿ì µ¹¿¬º¯ÀÌ¿¡ ÀÇÇØ ¸¸µé¾îÁø ÀÚ¼Õ(À§ ½ÄÀÇ xt+1)Àº ºÎ¸ð(xt) º¸´Ù ÀûÇÕµµ°¡ ÁÁ°Ô µÉ ¶§ ºÎ¸ð·Î¼ Áý´ÜÀÇ ÀÏ¿øÀ¸·Î ä¿ëÇÏ¿´´Ù.(°á±¹, ´ÙÀ½¼¼´ëÀÇ ºÎ¸ð°¡ µÈ´Ù). ±× ÈÄ ES´Â º¹¼ö°³Ã¼ÀÇ Áý´Ü¿¡ ÀÇÇÑ Å½»ö¼ö¹ýÀ¸·Î¼ ¿©·¯ °¡Áö ÇüÅ·Π¹ßÀüµÇ¾îÁ® ¿Ô´Ù .....