GA : ±×µéÀº ¹«¾ùÀΰ¡?
À¯ÀüÀÚ ¾Ë°í¸®Áò : Zbigniew Michalewicz Àú¼, °ø¼º°ï.±èÀÎÅÃ.¹Ú´ëÈñ.¹ÚÁÖ¿µ.½Å¿ä¾È °ø¿ª, µµ¼ÃâÆÇ ±×¸° (¿ø¼ : Genetic Algorithm + Data Structure = Evolution Programs, 1996), Page 20~42
4. µî¹Ý, ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ, ±×¸®°í À¯ÀüÀÚ ¾Ë°í¸®Áò
ÃæºÐÈ÷ ºü¸¥ ¾Ë°í¸®ÁòÀÌ °³¹ßµÇÁö ¾ÊÀº ¸¹Àº ºÎ·ùÀÇ Èï¹ÌÀÖ´Â ¹®Á¦µéÀÌ ÀÖ´Ù. ÀÌ·¯ÇÑ ¹®Á¦µéÀº ¿©·¯ ÀÀ¿ë¿¡¼ ÈçÈ÷ Á¦±âµÇ´Â ÃÖÀûÈ ¹®Á¦ÀÌ´Ù. ¾î·Á¿î ÃÖÀûȹ®Á¦°¡ ÁÖ¾îÁ³À» ¶§ ±Ù»ç ÃÖÀûÇØ¸¦ Á¦°øÇÏ´Â È¿°úÀûÀÎ ¾Ë°í¸®ÁòÀ» ã¾Æ³»´Â °ÍÀÌ Á¾Á¾ °¡´ÉÇÏ´Ù. ¾î¶² ¾î·Á¿î ÃÖÀûÈ ¹®Á¦¿¡ ´ëÇÏ¿© È®·üÀûÀÎ ¾Ë°í¸®ÁòÀ» »ç¿ëÇÒ ¼ö Àִµ¥, ÀÌ·¯ÇÑ ¾Ë°í¸®ÁòµéÀº ÃÖÀû°ªÀ» º¸ÀåÇØ ÁÖÁö´Â ¸øÇÏÁö¸¸, ÃæºÐÈ÷ ¸¹Àº "¸ñ°ÝÀÚ" µéÀ» ÀÓÀÇ·Î ¼±ÅÃÇÔÀ¸·Î½á ¿ÀÂ÷ È®·üÀ» ¿øÇÏ´Â ¸¸Å ÀÛ¾ÆÁöµµ·Ï ÇÒ ¼ö ÀÖ´Ù.
±×·¯ÇÑ °íǰÁúÀÇ ¾Ë°í¸®ÁòµéÀ» Àû¿ëÇÒ ¼ö ÀÖ´Â Áß¿äÇÑ ½ÇÁ¦ÀûÀÎ ÃÖÀûÈ ¹®Á¦°¡ ¸¹ÀÌ Á¸ÀçÇÑ´Ù [53]. ¿¹¸¦ µé¾î VLSI ÀÇ ¼³°è¿¡¼ ¼±·ÎÀÇ ¶ó¿ìÆÃ ¹× ºÎǰÀÇ ¹èÄ¡¹®Á¦¿¡ ´ëÇØ ¶Ç´Â ¼øÈ¸ ÆÇ¸Å¿ø ¹®Á¦¿¡ ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ±â¹ýÀ» Àû¿ë½Ãų ¼ö ÀÖ´Ù. °Ô´Ù°¡ ¸¹Àº ´Ù¸¥ ´ë±Ô¸ð Á¶ÇÕÃÖÀûÈ ¹®Á¦µé (ÀÌ·¯ÇÑ ¹®Á¦µéÀº NP-hard ¶ó°í ¾Ë·ÁÁ® ÀÖ´Ù) ÀÌ ÀÌ·¯ÇÑ Á¾·ùÀÇ ¸óÅ× Ä®¸¦·Î ±â¹ý¿¡ ÀÇÇØ ÇöÀç ¼öÁØÀÇ ÄÄÇ»ÅÍ¿¡¼ ±Ù»çÀûÀ¸·Î ÇØ°áµÉ ¼ö ÀÖ´Ù.
ÀϹÝÀûÀ¸·Î ¼ºÃëµÇ¾î¾ß ÇÒ ¾î¶² Ãß»óÀûÀÎ °úÁ¦´Â ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °ÍµéÀÇ °ø°£¿¡¼ÀÇ Å½»ö¹®Á¦·Î »ý°¢ÇÒ ¼ö ÀÖ´Ù. ¿ì¸®´Â "ÃÖÀû" ÇØ¸¦ Ãß±¸Çϰí ÀÖÀ¸¹Ç·Î ÀÌ·¯ÇÑ °úÁ¦¸¦ ÃÖÀûÈ °úÁ¤À¸·Î º¼ ¼ö ÀÖ´Ù. º¸Åë ÀÛÀº °ø°£¿¡¼´Â °íÀüÀûÀÎ ¿ÏÀü°Ë»ö ¹æ¹ýÀ¸·Î ÃæºÐÇÏÁö¸¸, Å« °ø°£¿¡¼´Â Ư¼öÇÑ ÀΰøÁö´É ±â¹ýÀÌ »ç¿ëµÇ¾î¾ß ÇÑ´Ù. À¯ÀüÀÚ ¾Ë°í¸®Áò (GA) Àº ±×·¯ÇÑ ±â¹ýµé Áß ÇϳªÀε¥, À¯ÀüÀû °è½Â°ú ´Ù¾ÆÀ©Àû »ýÁ¸ °æÀïÀ̶ó´Â ÀÚ¿¬ÀÇ Çö»óÀ» ¸ðµ¨¸µÇÑ È®·üÀûÀΠŽ»ö¹æ¹ýÀÌ´Ù. [54] ¿¡¼ ¾ð±ÞµÈ ¹Ù¿Í °°ÀÌ :
"... À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¹èÈÄ¿¡´Â ÀÚ¿¬ÁøÈ°¡ ÀºÀ¯µÇ¾î ÀÖ´Ù. ÁøÈ¿¡¼ °¢ Á¾ÀÌ Á÷¸éÇϰí ÀÖ´Â ¹®Á¦´Â º¹ÀâÇÏ°í º¯ÈÇϴ ȯ°æ¿¡ À¯¸®ÇÏ°Ô ÀûÀÀÇÏ´Â °ÍÀÌ´Ù. °¢ Á¾ÀÌ ½ÀµæÇÑ 'Áö½Ä' Àº °¢ °³Ã¼ÀÇ ¿°»öüÀÇ ±¸¼º¼ººÐ¿¡ Æ÷ÇԵǾî ÀÖ´Ù."
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¹èÈÄÀÇ ¾ÆÀ̵ð¾î´Â ÀÚ¿¬ÀÌ ÇàÇÏ´Â °ÍÀ» ±×´ë·Î ½ÇÇöÇÏ´Â °ÍÀÌ´Ù. ¿¹¸¦ µé¾î Åä³¢¸¦ »ý°¢ÇØ º¸ÀÚ. ¾î¶² ½ÃÁ¡¿¡ Åä³¢µéÀÇ Áý´ÜÀÌ Á¸ÀçÇϰí, ±×µé Áß ¾î¶² °ÍµéÀº ´Ù¸¥ °Í¿¡ ºñÇØ ´õ ºü¸£°í ¿µ¸®ÇÏ´Ù. ºü¸£°í ¿µ¸®ÇÑ Åä³¢´Â ¿©¿ì¿¡°Ô Àâ¾Æ ¸ÔÈú °¡´É¼ºÀÌ ÀÛÀ¸¹Ç·Î ¸¹Àº ¼ö°¡ »ýÁ¸ÇÒ ¼ö ÀÖÀ¸¸ç ´õ ¸¹Àº Åä³¢¸¦ ¸¸µé¾î ³¾ °ÍÀÌ´Ù. ¹°·Ð ´À¸®°í ¿µ¸®ÇÏÁö ¸øÇÑ Åä³¢´Â ¿îÀÌ ÁÁ¾Æ¾ß¸¸ »ýÁ¸ÇÒ ¼ö ÀÖ´Ù. »ì¾Æ³²Àº Åä³¢µéÀÇ Áý´ÜÀº ¹ø½ÄÇϱ⠽ÃÀÛÇÏ°í ¹ø½Ä °á°ú·Î Åä³¢ÀÇ À¯ÀüÀç·áµéÀÌ Àß È¥Çյȴ٠: ´À¸° Åä³¢¿Í ºü¸¥ Åä³¢ÀÇ È¥ÇÕ, ºü¸¥ Åä³¢¿Í ºü¸¥ Åä³¢ÀÇ È¥ÇÕ, ¿µ¸®ÇÑ Åä³¢¿Í ¿µ¸®ÇÏÁö ¾ÊÀº Åä³¢ÀÇ È¥ÇÕ, µî. À̹ۿ¡µµ ÀÚ¿¬Àº °¡²û¾¿ Åä³¢ÀÇ À¯ÀüÀç·á¿¡ µ¹¿¬º¯À̸¦ ÁÖ¾î '¾ß»ýÅä³¢' ÀÇ ±âȸ¸¦ ÁØ´Ù. ºü¸£°í ¿µ¸®ÇÑ ºÎ¸ð Åä³¢µéÀÌ ¿©¿ì·ÎºÎÅÍ »ýÁ¸ÇÏ¿´À¸¹Ç·Î °á°úÀûÀ¸·Î ¾î¸° Åä³¢µéÀº (Æò±ÕÀûÀ¸·Î) ¿ø·¡ÀÇ °³Ã¼Áý´Üº¸´Ù ´õ ºü¸£°í ¿µ¸®ÇÒ °ÍÀÌ´Ù (Åä³¢µéÀÌ ºü¸£°í ¿µ¸®ÇØÁ®¼ ±×µéÀ» ÀâÀ» ¼ö ¾ø°Ô µÇ¸é ¿©¿ìµéµµ ºñ½ÁÇÑ °úÁ¤À» °Þ´Â´Ù).
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº Åä³¢ÀÇ À̾߱â¿Í ¹ÐÁ¢ÇÏ°Ô ´ëÀÀµÇ´Â ´Ü°èº° °úÁ¤À» µû¸¥´Ù. À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ±¸Á¶¸¦ ÁÖÀÇ ±í°Ô »ìÆìº¸±â Àü¿¡ À¯ÀüÇÐÀÇ ¿ª»ç¸¦ °£·«È÷ »ìÆìº¸µµ·Ï ÇÏÀÚ ([289] ·ÎºÎÅÍ).
"ÁøÈÀÇ ÁÖµÈ ¿ø¸®·Î¼ÀÇ ÀÚ¿¬µµÅ¼³ÀÇ ±Ùº»¿ø¸®´Â
À¯Àü ¸ÞÄ¿´ÏÁòÀÇ ¹ß°ß ÀÌÀü¿¡ C. Darwin ¿¡ ÀÇÇØ ü°èȵǾú´Ù. ±âº»ÀûÀÎ À¯Àü ¿ø¸®¿¡
Áö½Ä¾øÀÌ Darwin Àº ºÎ¸ðÀÇ ¼ºÁúµéÀÌ ¾×ü¿Í °°ÀÌ ÀÚ¼Õ¼¼´ëÀÇ ±â°ü¿¡ È¥ÇյȴٴÂ
°¡Á¤ÇÏ¿¡ À¯Àü¹°ÁúÀÇ À¶ÇÕ ¶Ç´Â È¥ÇÕÀ» °¡¼³È ÇÏ¿´´Ù. ±×ÀÇ ½Å¼ÓÇÏ°Ô ÆòÁØÈµÇ¸é
µ¿ÁúÈµÈ °³Ã¼Áý´Ü¿¡¼´Â µµÅ°¡ ÀϾÁö ¾Ê´Â´Ù (¼ÒÀ§ 'Jenkins ÀÇ ¾Ç¸ù') ´Â °ÍÀ̾ú´Ù.
1865 ³âÀÌ µÇ¾î¼¾ß G. Mendel ÀÌ ºÎ¸ð·ÎºÎÅÍ ÀÚ¼Õ¼¼´ë·ÎÀÇ À¯Àü¿ä¼ÒÀÇ Àü´Þ¿¡ °üÇÑ ÀÌ»êÀûÀÎ ¼ºÁúÀ» º¸¿©ÁÖ´Â ±âº» ¿ø¸®¸¦ ¹ß°ßÇÏ¿´´Âµ¥, ÀÌ·¯ÇÑ ÀÌ»êÀûÀÎ ¼ºÁú ¶§¹®¿¡ À¯ÀüÀû Â÷ÀÌÁ¡ÀÇ 'ºØ±«' °¡ ÀϾÁö ¾Ê±â ¶§¹®¿¡ 'Jenkins ¾Ç¸ù' ÀÌ ¼³¸íµÉ ¼ö ÀÖ¾ú´Ù.
Mendel ÀÇ ¹ýÄ¢Àº 1900 ³â¿¡ H. de Vries, K. Correns ¹× K. von Tschermak ¿¡ ÀÇÇØ µ¶¸³ÀûÀ¸·Î Àç¹ß°ßµÇ°í ³ª¼¾ß °úÇа迡 ¾Ë·ÁÁö°Ô µÇ¾ú´Ù. À¯ÀüÇÐÀº T. Morgan °ú ±×ÀÇ µ¿·áµé¿¡ ÀÇÇØ ¿ÏÀüÈ÷ ¹ßÀüµÇ¾ú´Âµ¥, ±×µéÀº ½ÇÇèÀûÀ¸·Î ¿°»öüµéÀÌ À¯ÀüÁ¤º¸ÀÇ ÁÖµÈ Àü´Þ¸ÅüÀ̰í À¯Àü¿ä¼Ò¸¦ ³ªÅ¸³»´Â À¯ÀüÀÚµéÀÌ ¿°»öü¿¡ ¹è¿µÇ¾î ÀÖ´Ù´Â °ÍÀ» Áõ¸íÇÏ¿´´Ù. ³ªÁß¿¡ ÃàÀûµÈ ½ÇÇèÀûÀÎ »ç½ÇµéÀ» ÅëÇÏ¿© ¼ºÀûÀ¸·Î Àç»ý»êÇÏ´Â ¸ðµç °³Ã¼µé¿¡ ´ëÇØ Mendel ÀÇ ¹ýÄ¢ÀÌ À¯È¿ÇÏ´Ù´Â °ÍÀÌ ÀÔÁõµÇ¾ú´Ù.
±×·¯³ª Àç¹ß°ßµÈ ÀÌÈÄ¿¡µµ Mendel ÀÇ ¹ýÄ¢°ú Darwin ÀÇ ÀÚ¿¬µµÅ¼³Àº µ¶¸³ÀûÀ̾ú°í, ¼·Î ¿¬°ü¼ºÀÌ ¾ø´Â °³³äµéÀ̾ú´Ù. °Ô´Ù°¡ ±× ¹ýÄ¢µéÀº ¼·Î°£¿¡ ¹Ý´ëµÇ¾ú´Ù. 1920 ³â´ë°¡ µÇ¾î¼¾ß (¿¹¸¦ µé¾î Cetverikov ÀÇ °íÀüÀûÀÎ ¾÷Àû [44] À» ÂüÁ¶ÇÒ °Í) Mendel ÀÇ À¯ÀüÇаú Darwin ÀÇ ÀÚ¿¬µµÅ·ÐÀÌ ÀüÇô ¹Ý´ëµÇÁö ¾ÊÀ¸¸ç ±×µéÀÇ ÇູÇÑ °áÈ¥ÀÌ Çö´ëÀÇ ÁøÈ·ÐÀ» ¸¸µé¾î ³½ °ÍÀ̶ó´Â °ÍÀÌ Áõ¸íµÇ¾ú´Ù."
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ÀÚ¿¬ÀÇ À¯ÀüÇÐÀ¸·ÎºÎÅÍ ºô¾î ¿Â ¾îÈÖ¸¦ »ç¿ëÇÑ´Ù. °³Ã¼Áý´Ü¿¡¼ °³Ã¼ (¶Ç´Â À¯ÀüÀÚÇü, ±¸Á¶) ¿¡ °üÇÏ¿© À̾߱âÇϴµ¥, ÈçÈ÷ ÀÌµé °³Ã¼µéÀº ½ºÆ®¸µ ¶Ç´Â ¿°»öü¶ó°íµµ ºÒ¸°´Ù. À̰ÍÀº ¾à°£ ¿ÀÇØ¸¦ ºÒ·¯ÀÏÀ¸Å³ ¼öµµ Àִµ¥, ¾î¶² Á¾ÀÇ Á¶Á÷¼¼Æ÷´Â ÀÏÁ¤ÇÑ ¼öÀÇ ¿°»öü (¿¹¸¦ µé¾î Àΰ£Àº 46 °³) ¸¦ °®´Â´Ù. ±×·¯³ª ÀÌ Ã¥¿¡¼´Â ÇϳªÀÇ ¿°»öü¸¦ °¡Áö´Â °³Ã¼, Áï ¹Ý¼ö ¿°»öü¸¸À» Ãë±ÞÇÑ´Ù. ¹è¼ö, Áï ¿°»öüÀÇ ½Ö¿¡ °üÇÑ Ãß°¡ÀûÀÎ Á¤º¸¿Í À¯ÀüÀÚ ¾Ë°í¸®Áò°ú ¿¬°üµÇ´Â ´Ù¸¥ °ü·ÃµÈ ¹®Á¦¸¦ À§Çؼ´Â [113] °ú Greene [124] ÀÇ ÃÖ±Ù ¿¬±¸¸¦ Âü°íÇ϶ó). ¿°»öüµéÀº ¼±ÇüÀûÀ¸·Î ¹è¿µÇ¾î ÀÖ´Â À¯ÀüÀÎÀÚ (Ư¡, Ư¼º, ÇØµ¶±â) ¶ó´Â ´ÜÀ§·Î ±¸¼ºµÇ¾î Àִµ¥, ¸ðµç À¯ÀüÀÎÀÚ´Â Çϳª ¶Ç´Â ¿©·¯ Ư¡ÀÇ À¯Àü¼ºÀ» ÅëÁ¦ÇÑ´Ù. ¾î¶² Ư¡ÀÇ À¯ÀüÀÎÀÚµéÀÌ ¿°»öü¿¡ ³õ¿© ÀÖ´Â À§Ä¡¸¦ ·ÎÄ¿½º (½ºÆ®¸µ À§Ä¡) ¶ó°í ºÎ¸¥´Ù. °³Ã¼ÀÇ ¾î¶² Ư¡µé (¸Ó¸®Ä«¶ô »ö±ò°ú °°Àº) Àº ½º½º·Î¸¦ ´Ù¸£°Ô º¸ÀÏ ¼öµµ Àִµ¥, ÀÌ À¯ÀüÀÚ´Â ´ë¸³À¯ÀüÀÚ (Ư¡°ª) ¶ó ºÒ¸®´Â ¿©·¯ »óŸ¦ °¡Áú ¼ö ÀÖ´Ù.
°¢ À¯ÀüÀÚÇü (ÀÌ Ã¥¿¡¼´Â ÇϳªÀÇ ¿°»öü) Àº ¹®Á¦¿¡ ´ëÇÑ ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °ÍÀ» ³ªÅ¸³½´Ù (Ưº°ÇÑ ¿°»öüÀÇ ÀǹÌ, Ç¥ÇöÇüÀº »ç¿ëÀÚ¿¡ ÀÇÇØ Á¤ÀǵȴÙ). ¿°»öüÀÇ °³Ã¼Áý´Ü À§¿¡¼ ÁøÇàÇÏ´Â ÁøÈ°úÁ¤Àº ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °ÍµéÀÇ °ø°£À» ÅëÇÑ Å½»ö¿¡ ÇØ´çÇÑ´Ù. ±×·¯ÇÑ Å½»öÀº ÃÖ¼±ÀÇ ÇØ¸¦ ÀÌ¿ëÇÏ´Â °Í°ú Ž»ö°ø°£À» Á¶»çÇÏ´Â °ÍÀ̶ó´Â µÎ °³ÀÇ (ºÐ¸íÈ÷ ¼·Î »óÃæµÇ´Â) ¸ñÀûµé »çÀÌ¿¡ ±ÕÇüÀ» ÇÊ¿ä·Î ÇÑ´Ù [35]. µî¹ÝÀº °³¼±½Ã۱â À§ÇØ ÃÖ¼±ÀÇ ÇØ¸¦ ÀÌ¿ëÇÏ´Â ¹Ý¸é¿¡ Ž»ö°ø°£ÀÇ Àü¿ªÅ½»öÀ» ¹«½ÃÇÏ´Â Àü·«ÀÇ ÇÑ ¿¹ÀÌ´Ù. ÀÓÀÇ Å½»öÀº Àüü°ø°£¿¡¼ ÇØ°¡ Á¸ÀçÇÒ °¡´É¿µ¿ªÀ» ÀÌ¿ëÇÏÁö ¾Ê°í °ø°£À» Àü¿ª Ž»öÇÏ´Â ÀüÇüÀûÀÎ Àü·«ÀÌ´Ù. À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº Ž»ö°ú ÇØÀÇ °¡´É¿µ¿ªµéÀ» ³î¶ö¸¸Å ±ÕÇüÀÖ°Ô ÀÌ¿ëÇÏ´Â ÀϹݼºÀÖ´Â (¹®Á¦¿µ¿ª°ú ¹«°üÇÑ) ºÎ·ùÀÇ Å½»ö¹æ¹ýÀÌ´Ù.
GA ´Â ¼±·Î ¶ó¿ìÆÃ, ½ºÄÉÁÙ¸µ, ÀûÀÀÁ¦¾î, °ÔÀÓ³îÀÌ, ÀÎÁö ¸ðµ¨¸µ, ¿î¼Û¹®Á¦, ¼øÈ¸ÆÇ¸Å¿ø¹®Á¦, ÃÖÀûÁ¦¾î¹®Á¦, µ¥ÀÌÅͺ£À̽ºÀÇ ÁúÀÇ ÃÖÀûȹ®Á¦¿¡ »ó´çÈ÷ ¼º°øÀûÀ¸·Î Àû¿ëµÇ¾î ¿Ô´Ù (Âü°í¹®Çå [25], [34], [64], [113], [126], [129], [130], [209], [206], [259], [299], [300]). ±×·¯³ª De Jong [64] Àº GA ¸¦ ÃÖÀûÈ µµ±¸·Î °£ÁÖÇÏ´Â °Í¿¡ ´ëÇØ ´ÙÀ½°ú °°ÀÌ °æ°íÇÏ¿´´Ù :
"...ÇÔ¼ö ÃÖÀûÈ ÀÀ¿ë¿¡ ´ëÇÑ ÀÌ·¯ÇÑ ¿ª»çÀûÀÎ ÃÊÁ¡°ú °Á¶ ¶§¹®¿¡ GA ¸¦ ±× ÀÚü·Î¼ ÃÖÀûÈ ¾Ë°í¸®ÁòÀ¸·Î °£ÁÖÇÏ°í ±×¸®°í ¾î¶² ƯÁ¤ÇÑ Å½»ö°ø°£¿¡¼ '¸í¹éÇÑ' ÃÖÀûÁ¡À» ã¾Æ³»Áö ¸øÇÏ¿´À» ¶§ ³î¶ó°Å³ª ½Ç¸ÁÇÏ´Â ÇÔÁ¤¿¡ ºüÁö±â ½±´Ù. ÀÌ·¯ÇÑ °ü³äÀûÀÎ ÇÔÁ¤À» ÇÇÇϱâ À§Çؼ´Â GA °¡ (¾ÆÁÖ ÀÌ»óȵÈ) ÀÚ¿¬°úÁ¤ÀÇ ¸ðÀÇ ½ÇÇèÀ¸·Î, ±×¸®°í ±×·¯ÇÑ ÀÚ¿¬ÀÇ °úÁ¤ÀÇ ¸ñÇ¥¿Í ¸ñÀûÀ» (¸¸ÀÏ Á¸ÀçÇÑ´Ù¸é) Çü»óÈÇÏ´Â °ÍÀ¸·Î »ý°¢Ç϶ó´Â °ÍÀ» Ãæ°íÇϰíÀÚ ÇÑ´Ù. ´©±º°¡ ÁøÈ ½Ã½ºÅÛÀÇ ¸ñÇ¥¿Í ¸ñÀûÀ» Á¤ÀÇÇÏ·Á°í ÇÏ´ÂÁö ¸ð¸£Áö¸¸, ³ª´Â ±×·¯ÇÑ ½Ã½ºÅÛÀÌ ÀϹÝÀûÀ¸·Î ÇÔ¼ö ÃÖÀû±â·Î °£ÁÖµÇÁö ¾Ê´Â´Ù°í ¸»ÇÏ´Â °ÍÀÌ °øÁ¤ÇÏ´Ù°í »ý°¢ÇÑ´Ù."
±×·¸Áö¸¸ ÃÖÀûÈ´Â GA ÀÇ Àû¿ë°¡´É¼ºÀÇ ÁÖµÈ ºÐ¾ßÀÌ´Ù. [263] ¿¡¼ (1981) Schwefel Àº ´ÙÀ½°ú °°ÀÌ ¸»ÇÏ¿´´Ù :
"°øÇÐ, °æÁ¦ÇÐ, °æ¿µÇÐ, ¼öÇÐ, ¹°¸®ÇÐ, ¶Ç´Â »çȸ°úÇÐÀ» ºÒ±¸ÇÏ°í »öÀο¡¼ 'ÃÖÀûÈ' ÀÇ °³³äÀÌ ´©¶ôµÇ¾î ÀÖ´Â Çö´ëÀÇ Àú³ÎÀº °ÅÀÇ ¾ø´Ù. ¸¸ÀÏ ¸ðµç Àü¹®°¡ÀÇ °üÁ¡¿¡¼ ¿ä¾àÇÑ´Ù¸é, ¸¹Àº ¼öÀÇ °¡´ÉÇÑ »óÅ °¡¿îµ¥¼ º¸´Ù ÁÁÀº ¶Ç´Â °¡Àå ÁÁÀº (Leibniz ¿¡ ÀÇÇϸé, ÃÖÀûÀÇ) °ÍÀ» ¼±ÅÃÇÏ´Â ¹®Á¦°¡ µÇÇ®À̵ǰí ÀÖ´Ù."
Áö³ 10³â°£ ÃÖÀûÈÀÇ Á߿伺Àº ´õ¿í Å©°Ô Áõ°¡Çϰí Àִµ¥, ¸¹Àº Áß¿äÇÑ ´ë±Ô¸ð Á¶ÇÕ ÃÖÀûÈ ¹®Á¦¿Í ±¸¼ÓÁ¶°ÇÀÌ ¸¹Àº °øÇй®Á¦µéÀÌ ÇöÀç ¼öÁØÀÇ ÄÄÇ»Åͻ󿡼 ±Ù»çÀûÀ¸·Î ÇØ°áµÉ ¼ö ÀÖ´Ù.
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ±×·¯ÇÑ º¹ÀâÇÑ ¹®Á¦¸¦ °Ü³ÉÇÑ´Ù. ±×µéÀº È®·üÀûÀÎ ¾Ë°í¸®ÁòÀÇ ºÎ·ù¿¡ ¼ÓÇØ ÀÖÁö¸¸ ¹æÇ⼺Àִ Ž»ö°ú È®·üŽ»öÀÇ ¿ä¼Ò¸¦ °áÇÕÇÏ¿´À¸¹Ç·Î ÀÓÀÇ ¾Ë°í¸®Áò°ú´Â »ó´çÈ÷ ´Ù¸£´Ù. ÀÌ ¶§¹®¿¡ GA ´Â ÇöÁ¸ÇÏ´Â ¹æÇ⼺Àִ Ž»ö¹æ¹ýº¸´Ù ´õ °ÀÎÇÏ´Ù. À¯ÀüÀÚ±â¹Ý Ž»ö¹æ¹ýÀº ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °³Ã¼Áý´ÜÀ» À¯ÁöÇÏÁö¸¸, ´Ù¸¥ ¹æ¹ýµéÀº Ž»ö°ø°£¿¡¼ ´Ü ÇϳªÀÇ Á¡À» ó¸®ÇÑ´Ù´Â °ÍÀÌ ¶Ç´Ù¸¥ Áß¿äÇÑ Æ¯Â¡ÀÌ´Ù.
µî¹Ý ¹æ¹ýÀº ¹Ýº¹ÀûÀÎ °³¼±±â¹ýÀ» »ç¿ëÇϴµ¥, Ž»ö°ø°£³»¿¡¼ ÇϳªÀÇ Á¡ (ÇöÀçÁ¡) ¿¡ Àû¿ëµÈ´Ù. ÇϳªÀÇ ¹Ýº¹°úÁ¤µ¿¾È »õ·Î¿î Á¡ÀÌ ÇöÀçÁ¡ÀÇ ÀÌ¿ô¿¡¼ºÎÅÍ ¼±Åõȴ٠(ÀÌ ¶§¹®¿¡ ÀÌ ±â¹ýÀº ÀÌ¿ôŽ»ö ¶Ç´Â ±¹¼ÒŽ»öÀ̶ó°íµµ ºÒ¸°´Ù [173]). ¸¸ÀÏ »õ·Î¿î Á¡ÀÌ ´õ ÁÁÀº ¸ñÀûÇÔ¼ö°ªÀ» Á¦°øÇÑ´Ù¸é, »õ·Î¿î Á¡Àº ÇöÀçÀÇ Á¡ÀÌ µÈ´Ù. ±×·¸Áö ¾ÊÀ¸¸é ´Ù¸¥ ÀÌ¿ôÁ¡ÀÌ ¼±Åõǰí ÇöÀçÁ¡°ú ºñ±³µÈ´Ù. ÀÌ ¹æ¹ýÀº ´õ ÀÌ»ó °³¼±ÀÌ ºÒ°¡´ÉÇÒ ¶§ ¸ØÃß°Ô µÈ´Ù.
µî¹Ý ¹æ¹ýÀÌ ±¹¼Ò ÃÖÀû°ª¸¸À» Á¦°øÇϰí ÀÌ °ªµéÀº ½ÃÀÛÁ¡ÀÇ ¼±Åÿ¡ µû¶ó Á¿ìµÈ´Ù´Â »ç½ÇÀº ºÐ¸íÇÏ´Ù. ´õ¿íÀÌ ±¸ÇØÁø ÇØÀÇ (Àü¿ªÃÖÀû°ª¿¡ ´ëÇÑ) »ó´ëÀûÀÎ ¿ÀÂ÷¿¡ ´ëÇÏ¿© ¾Æ¹«·± Á¤º¸¸¦ ¾òÀ» ¼ö ¾ø´Ù.
¼º°øÇÒ ±âȸ¸¦ Áõ°¡½Ã۱â À§ÇÏ¿©, µî¹Ý ¹æ¹ýÀº º¸Åë ¸¹Àº ¼öÀÇ ´Ù¸¥ ½ÃÀÛÁ¡¿¡ ´ëÇÏ¿© ½ÃÇàµÈ´Ù (ÀÌ Á¡µéÀº ÀÓÀÇ·Î ¼±ÅÃµÉ ÇÊ¿ä´Â ¾ø°í ÇϳªÀÇ ½ÇÇØ¿¡ ´ëÇÑ ½ÃÀÛÁ¡ÀÇ ¼±ÅÃÀº ÀÌÀüÀÇ ½ÇÇàÀÇ °á°ú¿¡ ÀÇÇØ Á¿îµÈ´Ù).
½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ ±â¹ý [1] Àº µî¹Ý ¹æ¹ýÀÇ
´ëºÎºÐÀÇ ´ÜÁ¡µéÀ» Á¦°ÅÇϴµ¥, ÇØ´Â ´õ ÀÌ»ó ½ÃÀÛÁ¡¿¡ ÀÇÇØ Á¿ìµÇÁö ¾ÊÀ¸¸ç (º¸Åë)
ÃÖÀûÁ¡¿¡ ¾ÆÁÖ °¡±õ°Ô µÈ´Ù. À̰ÍÀº ¼ö¶ôÈ®·ü (ÇöÀçÁ¡À» »õ·Î¿î Á¡À¸·Î ¹Ù²Ù´Â È®·ü) ¸¦ µµÀÔÇÔÀ¸·Î½á ÀÌ·ç¾îÁø´Ù. ¸¸ÀÏ
»õ·Î¿î Á¡ÀÌ ´õ ³ªÀº ¸ñÀûÇÔ¼ö °ªÀ» Á¦°øÇϸé
ÀÌ°í ±×·¸Áö ¾ÊÀ¸¸é
ÀÌ´Ù. ³ªÁßÀÇ °æ¿ì¿¡ ¼ö¶ôÈ®·ü
´Â ÇöÀçÁ¡°ú »õ·Î¿î Á¡, ±×¸®°í Ãß°¡ÀûÀÎ Á¦¾î ¸Å°³º¯¼öÀÎ "¿Âµµ"
¿¡ ´ëÇÑ ¸ñÀûÇÔ¼ö°ªÀÇ ÇÔ¼öÀÌ´Ù. ÀϹÝÀûÀ¸·Î ¿Âµµ
°¡ ³·À»¼ö·Ï »õ·Î¿î Á¡ÀÌ ¼ö¶ôµÉ ±âȸ°¡ ´õ ÀÛ¾ÆÁø´Ù. ¾Ë°í¸®ÁòÀÇ ½ÇÇൿ¾È ½Ã½ºÅÛÀÇ
¿Âµµ
´Â ´Ü°èÀûÀ¸·Î ³·¾ÆÁö¸ç, ½ÇÁúÀûÀ¸·Î ´õ ÀÌ»ó ¾Æ¹«·± º¯È°¡ ÀϾÁö ¾Ê´Â ÀÛÀº
°ª¿¡¼ ¸ØÃá´Ù.
¾Õ¼ ¾ð±ÞµÈ ¹Ù¿Í °°ÀÌ, GA ´Â ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °³Ã¼Áö¹ÝÀ» À¯ÁöÇÔÀ¸·Î½á ¿©·¯¹æÇâÀÇ Å½»öÀ» ½ÇÇàÇϰí ÀÌµé ¹æÇâ°£ÀÇ Á¤º¸Çü¼º°ú ±³È¯À» Àå·ÁÇÑ´Ù. °³Ã¼Áý´ÜÀº ÁøÈ°úÁ¤À» Èä³»³»´Âµ¥, °¢ ¼¼´ë¿¡¼ ºñ±³Àû "ÁÁÀº" ÇØµéÀÌ Àç»ý»êµÇ°í, ¹Ý¸é¿¡ ºñ±³Àû "³ª»Û" ÇØµéÀº ¼Ò¸êµÈ´Ù. ´Ù¸¥ ÇØµé°£ÀÇ Â÷À̸¦ ±¸º°Çϱâ À§ÇØ È¯°æÀÇ ¿ªÇÒÀ» ¼öÇàÇÏ´Â ¸ñÀû (Æò°¡) ÇÔ¼ö¸¦ »ç¿ëÇÑ´Ù.
µî¹Ý, ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ, ±×¸®°í À¯ÀüÀÚ ¾Ë°í¸®Áò±â¹ýÀÇ ÇÑ ¿¹°¡ 1.4 Àý¿¡ ÁÖ¾îÁ® ÀÖ´Ù.
´Ü¼øÇÑ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ±¸Á¶´Â ¾î¶°ÇÑ ÁøÈ
ÇÁ·Î±×·¥ÀÇ ±¸Á¶¿Í µ¿ÀÏÇÏ´Ù (¼·ÐÀÇ ±×¸² 0-1 ÂüÁ¶). ¼øÈ¯ µ¿¾È¿¡ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °Í (¿°»öü º¤ÅÍ),
ÀÇ °³Ã¼Áý´ÜÀ» À¯ÁöÇÑ´Ù. °¢ ÇØ
´Â Æò°¡µÇ¾î "ÀûÇÕµµ" ÀÇ Ã´µµ¸¦ ÁØ´Ù. ±×·¯¸é ´õ ÀûÇÕÇÑ °³Ã¼µéÀ»
¼±ÅÃÇÔÀ¸·Î½á »õ·Î¿î °³Ã¼Áý´Ü (°úÁ¤ t+1) ÀÌ ±¸¼ºµÈ´Ù. ÀÌ »õ·Î¿î °³Ã¼Áý´ÜÀÇ ¾î¶²
ȸ¿øµéÀº ±³¹è¿Í µ¹¿¬º¯ÀÌ¿¡ ÀÇÇØ º¯°æ°úÁ¤À» °Þ¾î »õ·Î¿î ÇØ¸¦ ±¸¼ºÇÑ´Ù. ±³¹è´Â
ºÎ¸ðÀÇ ¿°»öüÀÇ ÀϺκÐÀ» ¼·Î ¹Ù²ÞÀ¸·Î½á ºÎ¸ðÀÇ Æ¯Â¡À» °áÇÕÇÏ¿© µÎ °³ÀÇ À¯»çÇÑ
ÀÚ¼ÕµéÀ» ±¸¼ºÇÑ´Ù. ¿¹¸¦ µé¾î ¸¸ÀÏ ºÎ¸ð°¡ 5 Â÷¿ø º¤ÅÍ
¿Í
¿¡ ÀÇÇØ Ç¥ÇöµÈ´Ù¸é, µÎ ¹øÂ° À¯ÀüÀÎÀÚ ÀÌÈÄÀÇ ¿°»öü¸¦ ±³Â÷½ÃŰ¸é µÎ °³ÀÇ
ÀÚ¼Õ
¿Í
ÀÌ »ý¼ºµÈ´Ù. Á÷°üÀûÀ¸·Î ±³¹è¿¬»êÀÚ´Â ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °Íµé »çÀÌÀÇ Á¤º¸
±³È¯À» À§ÇØ Àû¿ëµÈ´Ù.
µ¹¿¬º¯ÀÌ´Â µ¹¿¬º¯ÀÌÀ²°ú µ¿ÀÏÇÑ È®·üÀ» °¡Áö°í ÀÓÀÇ·Î º¯È½ÃÅ´À¸·Î½á ¼±ÅÃµÈ ¿°»öü¿¡¼ Çϳª ¶Ç´Â ±× ÀÌ»óÀÇ À¯ÀüÀÎÀÚ¸¦ ÀÓÀÇ·Î º¯°æÇÏ´Â °ÍÀÌ´Ù. Á÷°üÀûÀ¸·Î µ¹¿¬º¯ÀÌ ¿¬»êÀÚ´Â °³Ã¼Áý´Ü¿¡ Ãß°¡·Î º¯È¸¦ µµÀÔÇϱâ À§ÇØ Àû¿ëµÈ´Ù.
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº (¸ðµç ÁøÈ ÇÁ·Î±×·¥Ã³·³) ƯÁ¤ÇÑ ¹®Á¦¿¡ ´ëÇØ ´ÙÀ½°ú °°Àº ´Ù¼¸°¡ÁöÀÇ ¿ä¼Ò¸¦ °¡Á®¾ß¸¸ ÇÑ´Ù :
¼¼ °¡Áö ¿¹Á¦¸¦ ÅëÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÁÖ¿ä Æ¯Â¡À» ³íÀÇÇØ º¸ÀÚ. ù ¹øÂ° ¿¹Á¦¿¡¼ ÇϳªÀÇ ½Ç¼ö º¯¼öÀÇ ´Ü¼øÇÑ ÇÔ¼öÀÇ ÃÖÀûÈ¿¡ ´ëÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» Àû¿ëÇÏ¿´´Ù. µÎ ¹øÂ° ¿¹Á¦´Â À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» »ç¿ëÇÏ¿© °£´ÜÇÑ °ÔÀÓ (Á˼öÀÇ µô·¹¸¶) ¿¡ ´ëÇÑ Àü·«À» ÇнÀÇÏ´Â ¹æ¹ýÀ» º¸¿©ÁÙ °ÍÀÌ´Ù. ¼¼ ¹øÂ° ¿¹Á¦´Â Á¶ÇÕÀû NP-hard ¹®Á¦ÀÎ ¼øÈ¸ ÆÇ¸Å¿ø ¹®Á¦¿¡ ´ëÇÑ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ Àû¿ë °¡´É¼º¿¡ ´ëÇØ ³íÀÇÇÏ¿´´Ù.
ÀÌ Àý¿¡¼´Â ÇÑ °³ÀÇ º¯¼öÀÇ °£´ÜÇÑ ÇÔ¼öÀÇ ÃÖÀûȸ¦ À§ÇÑ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ±âº»ÀûÀΠƯ¡À» ³íÀÇÇÒ °ÍÀÌ´Ù. ÀÌ ÇÔ¼ö´Â ´ÙÀ½°ú °°ÀÌ Á¤ÀÇµÇ¸ç ±×¸² 1 ¿¡ ³ªÅ¸³»¾ú´Ù.
±×¸² 1 ÇÔ¼ö ÀÇ ±×·¡ÇÁ
¹®Á¦´Â ±¸°£ [-1, 2] ¿¡¼ ÇÔ¼ö ¸¦ ÃÖ´ëÈÇÏ´Â, Áï ´ÙÀ½ Á¶°ÇÀ» ¸¸Á·½ÃŰ´Â
¸¦ ã¾Æ³»´Â °ÍÀÌ´Ù.
ÇÔ¼ö ¸¦ ÇØ¼®ÇÏ´Â °ÍÀº ºñ±³Àû ½±´Ù. ´ÙÀ½°ú °°ÀÌ 1 Â÷ µµÇÔ¼ö
ÀÇ ¿µÀ» °áÁ¤ÇÏ¸é µÈ´Ù.
ÀÌ ½ÄÀº ´ÙÀ½°ú °°ÀÌ µÈ´Ù :
À§ ¹æÁ¤½ÄÀÌ ´ÙÀ½°ú °°ÀÌ ¹«ÇÑÈ÷ ¸¹Àº ¼öÀÇ ÇØ¸¦ °®´Â´Ù´Â °ÍÀº ºÐ¸íÇÏ´Ù.
¿©±â¼ Ç×Àº (
±×¸®°í
¿¡ ´ëÇØ) 0 À¸·Î °¨¼ÒÇÏ´Â ½Ç¼öÀÇ ¼ö¿À» ³ªÅ¸³½´Ù.
¸¸ÀÏ °¡ Ȧ¼öÀ̸é
¿¡¼ ÇÔ¼ö
ÀÇ ±¹¼ÒÃÖ´ë°ª¿¡ µµ´ÞÇϰí, ¸¸ÀÏ
°¡ ¦¼öÀ̸é
¿¡¼ ÇÔ¼ö
ÀÇ ±¹¼ÒÃÖ¼Ò°ª¿¡ µµ´ÞÇÑ´Ù (±×¸² 1 ÂüÁ¶).
¹®Á¦ÀÇ Á¤ÀÇ¿µ¿ªÀÌ À̹ǷΠÀÌ ÇÔ¼ö´Â
¿¡¼ ÃÖ´ë°ª¿¡ µµ´ÞÇϴµ¥, ¿©±â¼
´Â
º¸´Ù ¾à°£ ´õ Å©´Ù.
À§ÀÇ ¹®Á¦¸¦ Ç®±â À§ÇÏ¿©, ´Ù½Ã ¸»ÇÏ¿© ÇÔ¼ö ¸¦ ÃÖ´ëÈÇϱâ À§ÇØ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» ±¸¼ºÇϱ⸦ ¿øÇÑ´Ù°í °¡Á¤Çϰí, À¯ÀüÀÚ
¾Ë°í¸®ÁòÀÇ ÁÖ ¿ä¼Òµé¿¡ ´ëÇÏ¿© »ý°¢ÇØ º¸ÀÚ.
º¯¼ö ÀÇ ½Ç¼ö°ªÀ» Ç¥ÇöÇϱâ À§ÇÑ ¿°»öü·Î¼ ÀÌÁø º¤Å͸¦ »ç¿ëÇÑ´Ù. º¤ÅÍÀÇ ±æÀÌ´Â
¿ä±¸µÇ´Â Á¤¹Ðµµ¿¡ ÀÇÇØ Á¿ìµÇ´Âµ¥, ÀÌ ¿¹Á¦¿¡¼´Â ¼Ò¼ýÁ¡ÀÌÇÏ 6 ¹øÂ° ÀÚ¸®¸¦ »ç¿ëÇÑ´Ù.
º¯¼ö ÀÇ Á¤ÀÇ¿µ¿ªÀº ±æÀÌ 3 ÀÌ´Ù. Á¤È®µµ¿¡ ´ëÇÑ ¿ä±¸Á¶°ÇÀº Á¤ÀÇ¿µ¿ª [-1, 2] °¡
ÃÖ¼ÒÇÑ 3¤ý1000000 °³ÀÇ µ¿ÀÏÇÑ Å©±âÀÇ ¿µ¿ªÀ¸·Î ³ª´µ¾îÁ®¾ß ÇÑ´Ù´Â °ÍÀ» ¾Ï½ÃÇÑ´Ù.
À̰ÍÀº ÀÌÁø º¤ÅÍ (¿°»öü) ·Î¼ 22 ºñÆ®°¡ ÇÊ¿äÇÏ´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù.
2097152 = 221 < 2000000 ¡Â 222 = 4194304
ÀÌÁø ½ºÆ®¸µ ¸¦ Á¤ÀÇ¿µ¿ª [-1, 2] »çÀÌÀÇ ½Ç¼ö
·Î ¸ÅÇÎÇÏ´Â °ÍÀº Á÷Á¢ÀûÀÌ°í ´ÙÀ½ÀÇ µÎ ´Ü°è¿¡¼ ¿Ï°áµÈ´Ù :
ÀÌÁø ½ºÆ®¸µ À» ÀÌÁø¼ö·ÎºÎÅÍ 10 Áø¼ö·Î º¯È¯ÇÑ´Ù.
ÀÌ¿¡ ÇØ´çÇÏ´Â ½Ç¼ö ¸¦ ±¸ÇÑ´Ù.
¿©±â¼ -1.0 Àº Á¤ÀÇ¿µ¿ªÀÇ ¿ÞÂÊ °æ°èÀ̰í 3 Àº Á¤ÀÇ¿µ¿ªÀÇ ±æÀÌÀÌ´Ù.
¿¹¸¦ µé¾î ¿°»öü
(1000101110110101000111)
´Â ¼ýÀÚ 0.637197 À» ³ªÅ¸³½´Ù. ¿Ö³ÄÇϸé
= (1000101110110101000111)2 = 2288967
À̰í
À̱⠶§¹®ÀÌ´Ù. ¹°·Ð ¿°»öüµé (000000000000000) °ú (111111111111111) ´Â °¢°¢ Á¤ÀÇ¿µ¿ªÀÇ °æ°è°ªµéÀÎ -1.0 °ú 2.0 À» ³ªÅ¸³½´Ù.
ÃʱâÈ °úÁ¤Àº ¸Å¿ì °£´ÜÇѵ¥, °¢ ¿°»öü°¡ 22 ºñÆ®°¡ ÀÌÁø º¤ÅÍÀÎ ¿°»öüÀÇ °³Ã¼Áý´ÜÀ» ¸¸µé¾î ³»¸é µÈ´Ù. °¢ ¿°»öü¿¡ ´ëÇÑ ¸ðµç 22 ºñÆ®µéÀº ÀÓÀÇ·Î ÃʱâȵȴÙ.
ÀÌÁø º¤ÅÍ v ¿¡ ´ëÇÑ Æò°¡ÇÔ¼ö Àº ÇÔ¼ö
¿Í µ¿ÀÏÇÏ´Ù.
¿©±â¼ ¿°»öü v ´Â ½Ç¼ö°ª ¸¦ ³ªÅ¸³½´Ù.
¾Õ¿¡¼¿Í °°ÀÌ Æò°¡ÇÔ¼ö´Â ÀûÇÕµµÀÇ °üÁ¡¿¡¼ ÇØ°¡ µÉ °¡´É¼ºÀÌ ÀÖ´Â °ÍµéÀº Æò°¡Çϴ ȯ°æÀÇ ¿ªÇÒÀ» ¼öÇàÇÑ´Ù. ¿¹¸¦ µé¾î ¼¼ °³ÀÇ ¿°»öü
= (1000101110110101000111)
= (0000001110000000010000)
= (1110000000111111000101)
Àº °ª = 0.637197,
= -0.958973, ±×¸®°í
= 1.627888 À» °¢°¢ ³ªÅ¸³½´Ù. °á°úÀûÀ¸·Î Æò°¡ÇÔ¼ö´Â ´ÙÀ½°ú °°ÀÌ Æò°¡ÇÒ °ÍÀÌ´Ù.
ºÐ¸íÈ÷ ¿°»öü ´Â Æò°¡ÇÔ¼öÀÇ °ªÀÌ °¡Àå Å©¹Ç·Î ¼¼ ¿°»öüÁß¿¡¼ °¡Àå ÁÁ´Ù.
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ º¯È°úÁ¤Áß¿¡¼ µÎ °¡Áö °íÀüÀûÀÎ À¯Àü ¿¬»êÀÚµéÀÎ µ¹¿¬º¯ÀÌ¿Í ±³¹è¸¦ »ç¿ëÇÒ °ÍÀÌ´Ù.
¾Õ¼ ¾ð±ÞÇÑ ¹Ù¿Í °°ÀÌ µ¹¿¬º¯ÀÌ´Â µ¹¿¬º¯ÀÌÀ²°ú
µ¿ÀÏÇÑ È®·üÀ» °¡Áö°í Çϳª ¶Ç´Â ±× ÀÌ»óÀÇ À¯ÀüÀÎÀÚµé (ÇÑ ¿°»öü³»¿¡¼ÀÇ À§Ä¡µé)
À» º¯È½ÃŲ´Ù. ¿°»öü ·ÎºÎÅÍ ´Ù¼¸ ¹øÂ° À¯ÀüÀÎÀÚ°¡ µ¹¿¬º¯À̸¦ À§ÇØ ¼±ÅõǾú´Ù°í °¡Á¤ÇÏÀÚ. ÀÌ ¿°»öü¿¡¼ÀÇ
´Ù¼¸ ¹øÂ°ÀÇ À¯ÀüÀÎÀÚ°¡ 0 À̹ǷΠ1 ·Î ¹Ù²î¾îÁø´Ù. ±×·¡¼ µ¹¿¬º¯ÀÌ ÈÄ¿¡ ¿°»öü
´Â ´ÙÀ½°ú °°ÀÌ µÈ´Ù.
=(1110100000111111000101)
ÀÌ ¿°»öü´Â °ú
= -0.082257 À» ³ªÅ¸³½´Ù. À̰ÍÀº µ¹¿¬º¯À̰¡ ¿°»öü
ÀÇ °ªÀ» »ó´çÈ÷ °¨¼Ò½ÃÄ×´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. ¹Ý¸é¿¡ ¸¸ÀÏ ¿°»öü
¿¡¼ 10 ¹øÂ° À¯ÀüÀÚ°¡ µ¹¿¬º¯À̸¦ À§ÇØ ¼±ÅõǾú´Ù¸é
=(1110000001111111000101)
ÀÌ µÈ´Ù. À̰Ϳ¡ ÇØ´çÇÏ´Â °ª = 1.630818 ±×¸®°í
= 2.343555 °¡ µÇ¾î ¿ø·¡ÀÇ °ª
º¸´Ù °³¼±µÇ¾ú´Ù.
¿°»öü ¿Í
¿¡ ´ëÇÑ ±³¹è ¿¬»êÀÚÀÇ ¿¹¸¦ µéµµ·Ï ÇÏÀÚ. ±³¹èÀ§Ä¡°¡ (ÀÓÀÇ·Î) 5 ¹øÂ°
À¯ÀüÀÎÀÚ ÀÌÈÄ¿¡ ¼±ÅõǾú´Ù°í °¡Á¤ÇÏÀÚ :
= (00000|01110000000010000)
= (11100|00000111111000101)
µÎ °³ÀÇ °á°úÀûÀÎ ÀÚ¼Õ¼¼´ë´Â ´ÙÀ½°ú °°´Ù.
= (00000|00000111111000101)
= (11100|01110000000010000)
À̵é ÀÚ¼Õ ¼¼´ëµéÀº ´ÙÀ½°ú °°ÀÌ Æò°¡µÈ´Ù.
=
(-0.998113) = 0.940865
=
(1.666028) = 2.459245
µÎ ¹øÂ° ÀÚ¼ÕÀÌ ºÎ¸ðµéº¸´Ù ´õ ÁÁÀº Æò°¡°ªÀ» °¡Áö°í ÀÖ´Ù.
ÀÌ ¹®Á¦¿¡¼´Â ´ÙÀ½ ¸Å°³º¯¼öµéÀÌ »ç¿ëµÇ¾ú´Ù :
°³Ã¼Áý´ÜÀÇ Å©±â pop_size = 50, ±³¹èÈ®·ü = 0.25, µ¹¿¬º¯ÀÌ È®·ü
= 0.01. ´ÙÀ½ ÀýÀº ÀÌ À¯ÀüÀÚ ½Ã½ºÅÛ¿¡ ´ëÇÑ ¸î °¡Áö ½ÇÇè °á°úµéÀ» º¸¿©ÁØ´Ù.
Ç¥ 1 Àº Æò°¡ÇÔ¼öÀÇ °ªÀÌ °³¼±µÈ ¼¼´ë¹øÈ£¸¦ ±×¶§ÀÇ ÇÔ¼ö°ª°ú ÇÔ²² ³ªÅ¸³½ °ÍÀÌ´Ù. 150 ¼¼´ë ÀÌÈÄÀÇ ÃÖÀûÀÇ ¿°»öü´Â
= (1111001101000100000101)
À̸ç À̰ÍÀº = 1.850773 ¿¡ ÇØ´çÇÑ´Ù.
±â´ëÇß´ø ¹Ù¿Í °°ÀÌ = 1.85 + ¥å À̰í
´Â 2.85 º¸´Ù ¾à°£ ´õ Å©´Ù.
Ç¥ 1 150 ¼¼´ë ÀÌÈÄÀÇ °á°ú
¼¼´ë¹øÈ£ |
Æò°¡ÇÔ¼ö°ª |
1 6 8 9 10 12 39 40 51 99 137 145 |
1.441942 2.250003 2.250283 2.250284 2.250363 2.328077 2.344251 2.345087 2.738930 2.849246 2.850217 2.850227 |
ÀÌ Àý¿¡¼´Â À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÌ Á˼öÀÇ µô·¹¸¶ (prisoner's dilemma) ¶ó°í ¾Ë·ÁÁø ´Ü¼øÇÑ °ÔÀÓ¿¡ ´ëÇÑ Àü·«À» ÇнÀÇϱâ À§ÇÏ¿© ¾î¶»°Ô »ç¿ëµÉ ¼ö ÀÖ´ÂÁö ¼³¸íÇÒ °ÍÀÌ´Ù. Axelrod [10] ¿¡ ÀÇÇØ ¾ò¾îÁø °á°ú¸¦ Á¦½ÃÇÑ´Ù.
µÎ ¸íÀÇ Á˼ö°¡ µ¶¸³µÈ ¹æ¿¡ ¼ö°¨µÇ¾î ÀÖ¾î¼ ¼·Î Åë½ÅÇÒ ¼ö°¡ ¾ø´Ù. Á˼öµéÀº °¢°¢ »ó´ë¹æÀ» ÀÌÅ»ÇÏ°í ¹è½ÅÇϵµ·Ï ¿ä±¸µÈ´Ù. ¸¸ÀÏ ÇÑ¸í¸¸ÀÌ ¹è½ÅÇÏ¸é ±×´Â »óÀ» ¸Ã°í ´Ù¸¥ Á˼ö´Â ¹úÀ» ¹Þ´Â´Ù. ¸¸ÀÏ µÑ ´Ù ¹è½ÅÇÏ¸é ¸ðµÎ °¨¿Á¿¡ ³²¾Æ ÀÖ°Ô µÇ¸ç °í¹®À» ´çÇÑ´Ù. ¸¸ÀÏ ¾Æ¹«µµ ¹è½ÅÇÏÁö ¾ÊÀ¸¸é µÑ ´Ù Àû´çÈ÷ »óÀ» ¹Þ´Â´Ù. ±×·¡¼ À̱âÀûÀÎ ¼±ÅÃÀÇ ¹è½ÅÀº ´Ù¸¥ Á˼ö°¡ ¾î¶»°Ô ÇÏµç »ó°ü¾øÀÌ Ç×»ó Çù·Âº¸´Ù´Â ´õ ³ªÀº º¸»óÀ» °¡Á®´Ù ÁØ´Ù. ±×·¯³ª µÑ ´Ù ¹è½ÅÇϸé Çù·ÂÇÑ °Íº¸´Ù ´õ ³ª»Û °á°ú¸¦ ¾ò´Â´Ù. Á˼öÀÇ µô·¹¸¶´Â ´Ù¸¥ Á˼ö¸¦ ¹è½ÅÇÒ °ÍÀΰ¡ ¶Ç´Â Çù·ÂÇÒ °ÍÀΰ¡¸¦ °áÁ¤ÇÏ´Â °ÍÀÌ´Ù.
Á˼öÀÇ µô·¹¸¶´Â µÎ »ç¶÷ »çÀÌÀÇ °ÔÀÓÀ¸·Î ÇÒ ¼ö Àִµ¥, °¢ Â÷·Ê¸¶´Ù Ç÷¹À̾î´Â ´Ù¸¥ Á˼ö¸¦ ¹è½ÅÇϰųª ¶Ç´Â Çù·ÂÇÑ´Ù. ±×·¯¸é Ç÷¹À̾î´Â Ç¥ 2 ¿¡ ÁÖ¾îÁ® ÀÖ´Â º¸»ó¿¡ ÇØ´çÇÏ´Â Á¡¼ö¸¦ ¾ò´Â´Ù.
Ç¥ 2 Á˼öÀÇ µô·¹¸¶ °ÔÀÓ¿¡ ´ëÇÑ º¸»óÇ¥
( ´Â Ç÷¹À̾î
¿¡ ´ëÇÑ º¸»óÀÌ´Ù)
Ç÷¹À̾î 1 |
Ç÷¹À̾î 2 |
P1 |
P2 |
³» ¿ë |
¹è½Å (D) |
¹è½Å (D) |
1 |
1 |
»óÈ£ ¹è½Å¿¡ ´ëÇÑ Ã³¹ú |
¹è½Å (D) |
ÇùÁ¶ (C) |
5 |
0 |
¹è½ÅÀÇ À¯È¤°ú ¹è½ÅÀÚÀÇ º¸»ó |
ÇùÁ¶ (C) |
¹è½Å (D) |
0 |
5 |
¹è½ÅÀÚÀÇ º¸»ó°ú ¹è½ÅÀÇ À¯È¤ |
ÇùÁ¶ (C) |
ÇùÁ¶ (C) |
3 |
3 |
»óÈ£ Çù·Â¿¡ÀÇ º¸»ó |
ÀÌÁ¦ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÌ Á˼öÀÇ µô·¹¸¶¿¡ ´ëÇÑ Àü·«À» ÇнÀÇϴµ¥ ¾î¶»°Ô »ç¿ëµÉ ¼ö ÀÖ´ÂÁö °í·ÁÇØ º¸ÀÚ. GA Á¢±ÙÀº "Ç÷¹À̾îµé" ÀÇ °³Ã¼Áý´ÜÀ» À¯ÁöÇÏ´Â °ÍÀ̰í, °¢ Ç÷¹À̾î´Â Ưº°ÇÑ Àü·«À» °¡Áö°í ÀÖ´Ù. Ãʱ⿡ °¢ Ç÷¹À̾îÀÇ Àü·«Àº ÀÓÀÇ·Î ¼±ÅõȴÙ. ±× ÀÌÈÄ¿¡ °¢ ´Ü°è¿¡¼ Ç÷¹À̾î´Â °ÔÀÓÀ» ÁøÇàÇÏ°í ±×µéÀÇ Á¡¼ö°¡ Áý°èµÈ´Ù. ¾î¶² Ç÷¹À̾îµéÀº ´ÙÀ½ ¼¼´ë¸¦ À§ÇÏ¿© ¼±ÅÃµÇ°í ±×µé Áß ¾î¶² °ÍµéÀº °áÇյȴÙ. µÎ Ç÷¹À̾ °áÇÕµÉ ¶§ »ý¼ºµÈ »õ·Î¿î Ç÷¹À̾î´Â ºÎ¸ðÀÇ Àü·«µé·ÎºÎÅÍ ±¸¼ºµÈ Àü·«À» °®°Ô µÈ´Ù (±³¹è). º¸Åë µ¹¿¬º¯À̰¡ µµÀԵǾî ÀÌ Àü·«µéÀÇ Ç¥Çö¿¡ ÀÓÀÇÀûÀÎ º¯È¸¦ °¡ÇÔÀ¸·Î½á Ç÷¹À̾îµéÀÇ Àü·«¿¡ º¯È¸¦ ºÎ¿©ÇÏ°Ô µÈ´Ù.
¸ÕÀú Àü·« (°¡´ÉÇÑ ÇØ) À» Ç¥ÇöÇϱâ À§ÇÑ ¹æ¹ýÀÌ ÇÊ¿äÇÏ´Ù. °£´ÜÇϰÔ, °áÁ¤ÀûÀÎ Àü·«À» °í·ÁÇϰí ÀÌÀüÀÇ ¼¼ °¡Áö ÇൿÀÇ °á°ú¸¦ »ç¿ëÇÏ¿© ÇöÀç ÇൿÀ» ¼±ÅÃÇÑ´Ù. ¸Å Çൿ¸¶´Ù ³× °¡ÁöÀÇ °¡´ÉÇÑ °á°ú°¡ Á¸ÀçÇϹǷΠ4 × 4 × 4 = 64 °³ÀÇ ¼·Î ´Ù¸¥ ÀÌÀü ÇൿµéÀÌ Á¸ÀçÇÑ´Ù.
ÀÌ ÇüÅÂÀÇ Àü·«Àº °¡´ÉÇÑ °¢ ÀÌÀü Çൿµé¿¡ ´ëÇØ ¾î¶°ÇÑ ÇൿÀ» °áÁ¤ÇÏ¿©¾ß ÇÏ´ÂÁö Áö½ÃÇÔÀ¸·Î½á ±ÔÁ¤µÉ ¼ö ÀÖ´Ù. ±×·¡¼ ÇÑ Àü·«ÀÌ 64 ºñÆ®ÀÇ (¶Ç´Â D ¿Í C ÀÇ) ½ºÆ®¸µ¿¡ ÀÇÇØ Ç¥ÇöµÉ ¼ö Àִµ¥, °¢°¢Àº 64 °³ÀÇ °¡´ÉÇÑ ÀÌÀü Çൿ¿¡ °üÇÑ Ãʱ⠰¡Á¤À» ±ÔÁ¤ÇÒ Çʿ䰡 ÀÖ´Ù. À̰ÍÀº Ãß°¡·Î 6 °³ÀÇ À¯ÀüÀÎÀÚ¸¦ ÇÊ¿ä·Î ÇϹǷÎ, ¿°»öü¿¡ ÃÑ 70 °³ÀÇ ·ÎÄ¿½º¸¦ ±¸¼ºÇÑ´Ù.
ÀÌ 70 ºñÆ®ÀÇ ½ºÆ®¸µÀº Ç÷¹À̾ °¢ °¡´ÉÇÑ »óȲ¿¡¼ ¾î¶»°Ô ÇÏ¿©¾ß ÇÏ´ÂÁö¸¦ ±ÔÁ¤ÇÏ°í µû¶ó¼ ¾î¶² Ưº°ÇÑ Àü·«À» ¿ÏÀüÈ÷ Á¤ÀÇÇÑ´Ù. 70 °³ÀÇ À¯ÀüÀÎÀÚÀÇ ½ºÆ®¸µÀº ÁøÈ°úÁ¤¿¡¼ »ç¿ëµÉ Ç÷¹À̾îÀÇ ¿°»öü·Î ÇൿÇÑ´Ù.
Á˼öÀÇ µô·¹¸¶¿¡ ´ëÇÑ Àü·«À» ÇнÀÇϱâ À§ÇÑ Axelrod ÀÇ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ´ÙÀ½°ú °°Àº ³× °¡Áö °úÁ¤À¸·Î ÀÌ·ç¾îÁø´Ù :
1. Ãʱ⠰³Ã¼Áý´ÜÀ» ¼±ÅÃÇÑ´Ù. °¢ Ç÷¹À̾î´Â À§¿¡¼ ¾ð±ÞµÈ °Íó·³ ÇϳªÀÇ Àü·«À» ³ªÅ¸³»´Â 70 ºñÆ®ÀÇ ÀÓÀÇÀÇ ½ºÆ®¸µ¿¡ ÇÒ´çµÈ´Ù.
2. °¢ Ç÷¹À̾ Å×½ºÆ®ÇÏ¿© À¯È¿¼ºÀ» °áÁ¤ÇÑ´Ù. °¢ Ç÷¹À̾î´Â ÀÚ½ÅÀÇ ¿°»öü¿¡ ÀÇÇØ Á¤ÀÇµÈ Àü·«À» »ç¿ëÇÏ¿© ´Ù¸¥ Ç÷¹À̾î¿Í °ÔÀÓÇÑ´Ù. ±× Ç÷¹À̾îÀÇ Á¡¼ö´Â ±×°¡ ÇÏ´Â ¸ðµç °ÔÀÓ¿¡ ÀÖ¾î¼ÀÇ Æò±ÕÀÌ´Ù.
3. Áõ½Ä½Ãų Ç÷¹À̾ ¼±ÅÃÇÑ´Ù. Æò±ÕÁ¡¼ö¸¦ °¡Áø Ç÷¹À̾ ÇѹøÀÇ Áõ½Ä ±âȸ¸¦ ºÎ¿©ÇÑ´Ù. Æò±ÕÁ¡¼öº¸´Ù ÇϳªÀÇ Ç¥ÁØÆíÂ÷ ÀÌ»óÀÇ Á¡¼ö¸¦ °¡Áø Ç÷¹À̾´Â µÎ ¹øÀÇ Áõ½Ä ±âȸ¸¦ ºÎ¿©ÇÑ´Ù. Æò±ÕÁ¡¼öº¸´Ù ÇϳªÀÇ Ç¥ÁØÆíÂ÷ ÀÌÇÏÀÇ Á¡¼ö¸¦ °¡Áø Ç÷¹À̾î´Â Áõ½Ä±âȸ¸¦ °®Áö ¸øÇÑ´Ù.
4. ¼º°øÀûÀÎ Ç÷¹À̾î´Â ÀÓÀǷΠ¦À» Áö¾î ±³¹è´ç µÎ¸íÀÇ ÀÚ¼ÕÀ» ¸¸µé¾î ³½´Ù. °¢ ÀÚ¼ÕÀÇ Àü·«Àº ±×ÀÇ ºÎ¸ðÀÇ Àü·«À¸·ÎºÎÅÍ °áÁ¤µÈ´Ù. À̰ÍÀº µÎ °³ÀÇ À¯Àü ¿¬»êÀÚÀÎ ±³¹è¿Í µ¹¿¬º¯ÀÌ¿¡ ÀÇÇØ ÀÌ·ç¾îÁø´Ù.
ÀÌ·¯ÇÑ ³× ´Ü°è ÀÌÈÄ¿¡ »õ·Î¿î °³Ã¼ Áý´ÜÀ» ¾ò´Â´Ù. »õ·Î¿î °³Ã¼Áý´ÜÀº ÀÌÀü ¼¼´ëÀÇ ¼º°øÀûÀÎ °³Ã¼µéÀÇ ÇൿÆÐÅϰú À¯»çÇÏÁö¸¸ ¼º°øÀûÀÌÁö ¸øÇÑ °ÍµéÀÇ ÆÐÅϰú´Â À¯»çÇÏÁö ¾ÊÀº ÇൿÆÐÅÏÀ» º¸¿©ÁØ´Ù. °¢ »õ·Î¿î ¼¼´ë¿Í ÇÔ²² ºñ±³Àû ³ôÀº Á¡¼ö¸¦ °¡Áø °³Ã¼µéÀº ÀÚ½ÅÀÇ Àü·«ÀÇ ÀϺκÐÀ» Àü´ÞÇØ ÁÖ´Â ¹Ý¸é¿¡, »ó´ëÀûÀ¸·Î ¼º°øÀûÀÌÁö ¸øÇÑ °³Ã¼µéÀº ¾î¶² ºÎºÐÀÇ Àü·«µµ ÀüÆÄÇÏÁö ¸øÇÏ´Â °æÇâÀÌ ÀÖ´Ù.
ÀÌ ÇÁ·Î±×·¥À» ½ÇÇàÇÏ°í ³ª¼ Axelrod ´Â »ó´çÈ÷ ³î¶ö ¸¸ÇÑ °á°ú¸¦ ¾ò¾ú´Ù. ¿ÏÀüÈ÷ ÀÓÀÇÀûÀÎ ½ÃÀÛÀ¸·ÎºÎÅÍ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº Áß¾Ó°ª ȸ¿øÀÌ Áö±Ý±îÁö °¡Àå Àß ¾Ë·ÁÁø °æÇèÀûÀÎ ¾Ë°í¸®Áò¸¸Å ¼º°øÀûÀÎ °³Ã¼Áý´ÜÀ¸·Î ÁøÈ½ÃÄ×´Ù. ¾î¶² ÇൿÆÐÅϵéÀº ´ë´Ù¼öÀÇ °³Ã¼µé·Î ÁøÈÇÏ¿´´Âµ¥ À̵éÀº ´ÙÀ½°ú °°´Ù.
1. ¹è¸¦
ÈçµéÁö ¸»¶ó : ¼¼ ¹øÀÇ »óÈ£Çù·Â ÀÌÈÄ¿¡´Â °è¼Ó Çù·ÂÇÑ´Ù
((CC)(CC)(CC)2
ÀÌÈÄ¿¡ C).
2. ȸ¦
³»¶ó : ´Ù¸¥ Ç÷¹À̾ ¹è½ÅÇÏ¿´À» ¶§´Â °°ÀÌ ¹è½ÅÇ϶ó
((CC)(CC)(CD) ÀÌÈÄ¿¡
D).
3. »ç°ú¸¦
¹Þ¾ÆµéÀ̶ó : Çù·Â°ü°è°¡ ´Ù½Ã Á¤¸³µÇ¾úÀ» ¶§ °è¼Ó Çù·ÂÇ϶ó
((CD)(DC)(CC)
ÀÌÈÄ¿¡ C).
4. Àؾî
¹ö¸®¶ó : ¹è½Å ÈÄ¿¡ Çù·Â°ü°è°¡ ÀçÁ¤¸³µÇ¾úÀ» ¶§ Çù·ÂÇ϶ó
((DC)(CC)(CC)
ÀÌÈÄ¿¡ C).
5. °ü·Ê¸¦
¹Þ¾ÆµéÀ̶ó : ¼¼ ¹øÀÇ »óÈ£ ¹è½Å ÀÌÈÄ¿¡ ¹è½ÅÇ϶ó
((DD)(DD)(DD) ÀÌÈÄ¿¡ D).
´õ ÀÚ¼¼ÇÑ ¼³¸íÀ» À§Çؼ´Â [10] À» Âü°íÇ϶ó.
ÀÌ Àý¿¡´Â ¼øÈ¸ ÆÇ¸Å¿ø ¹®Á¦ (Traveling Salesman Problem, TSP) ¿¡ ¾î¶»°Ô À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» Àû¿ëÇÏ´ÂÁö ¼³¸íÇÑ´Ù. ¿©±â¼´Â ´Ü ÇϳªÀÇ °¡´ÉÇÑ Á¢±ÙÀ» ³íÀÇÇϴµ¥, 10 Àå¿¡¼´Â TSP ¿¡ ´ëÇÑ ´Ù¸¥ Á¢±Ù¹æ¹ýµµ ³íÀÇÇϰڴÙ.
°£´ÜÈ÷ ¸»ÇÏ¿© ¼øÈ¸ÆÇ¸Å¿øÀº ¹®Á¦¿µ¿ª³»ÀÇ ¸ðµç µµ½Ã¸¦ ´Ü Çѹø¸¸ ¹æ¹®Çϰí Ãâ¹ßÁ¡À¸·Î µ¹¾Æ¿Í¾ß ÇÑ´Ù. ¸ðµç µµ½Ãµé »çÀÌÀÇ ¹æ¹®¿¡ ´ëÇÑ ¿©Çà °æºñ°¡ ÁÖ¾îÁ³À» ¶§, Àüü ¿©ÇàÀÇ ÃѰæºñ¸¦ ÁÙÀ̱â À§Çؼ ¿©Çà ÀÏÁ¤À» ¾î¶»°Ô °èȹÇÏ¿©¾ß Çϴ°¡?
TSP ´Â Á¶ÇÕÃÖÀûȹ®Á¦ÀÌ°í ¿©·¯ °¡ÁöÀÇ ÀÀ¿ëºÐ¾ß¿¡¼ Á¦±âµÈ´Ù. ÀÌ ¹®Á¦¿¡ Á¢±ÙÇÏ´Â ¿©·¯ °¡ÁöÀÇ °¡Áö-°æ°è ¾Ë°í¸®Áò, ±Ù»ç ¾Ë°í¸®Áò, ±×¸®°í °æÇèÀûÀΠŽ»ö ¾Ë°í¸®ÁòµéÀÌ Á¸ÀçÇÑ´Ù. Áö³ ¸î ³âµ¿¾È À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ ÀÇÇØ TSP ¸¦ ±Ù»çÈÇÏ·Á´Â ¿©·¯ °¡ÁöÀÇ ½ÃµµµéÀÌ ÀÖ¾î ¿Ô´Âµ¥ [113, ÆäÀÌÁö 166-179], ¿©±â¼´Â ±×µé Áß Çϳª¸¦ Á¦½ÃÇÑ´Ù.
¿ì¼± ¿°»öü Ç¥Çö°ú °ü·ÃµÈ Áß¿äÇÑ Áú¹®À» Á¦±âÇØ¾ß
ÇÑ´Ù : ¿°»öü¸¦ Á¤¼ö º¤ÅÍ·Î ÇØ¾ß Çϴ°¡ ¶Ç´Â ÀÌÁø ½ºÆ®¸µÀ¸·Î º¯È¯ÇÏ¿©¾ß Çϴ°¡?
ÀÌÀüÀÇ µÎ ¿¹Á¦ (ÇÔ¼ö ÃÖÀûÈ¿Í Á˼öÀÇ µô·¹¸¶) ¿¡¼´Â ¿°»öü¸¦ ´Ù¼Ò°£ ÀÚ¿¬½º·¯¿î
¹æ½ÄÀ¸·Î) ÀÌÁø º¤ÅͷΠǥÇöÇÏ¿´´Ù. ÀÌ·Î ÀÎÇÏ¿© ÀÌÁøÀÇ µ¹¿¬º¯ÀÌ¿Í ±³¹è¸¦ »ç¿ëÇÏ¿´°í,
ÀÌ·¯ÇÑ ¿¬»êÀÚµéÀ» Àû¿ëÇÏ¿© ÀûÇÕÇÑ ÀÚ¼Õ, Áï Ž»ö°ø°£³»¿¡ Á¸ÀçÇÏ´Â ÀÚ¼ÕµéÀ» ¾ò¾ú´Ù.
¼øÈ¸ÆÇ¸Å¿ø¹®Á¦¿¡ ´ëÇÑ °æ¿ì´Â À̰Ͱú ´Ù¸£´Ù. °³ÀÇ µµ½ÃÀÇ TSP ¹®Á¦ÀÇ ÀÌÁøÇ¥Çö¿¡¼ °¢ µµ½Ã´Â
ºñÆ®ÀÇ ½ºÆ®¸µÀ¸·Î ÄÚµùµÇ¾î¾ß Çϴµ¥ ¿°»öü´Â
ºñÆ®ÀÇ ½ºÆ®¸µÀÌ´Ù. µ¹¿¬º¯ÀÌ¿¡ ÀÇÇØ¼´Â ¿©ÇàÀÌ µÇÁö ¾Ê´Â µµ½Ã ¼ö¿ÀÌ µÉ ¼öµµ
Àִµ¥, ±× ÀÌÀ¯´Â ÇÑ ¼ö¿¿¡¼ °°Àº µµ½Ã¸¦ µÎ ¹ø ¾òÀ» ¼öµµ Àֱ⠶§¹®ÀÌ´Ù. °Ô´Ù°¡
20 °³ÀÇ µµ½Ã¸¦ °¡Áø TSP ¿¡¼ (ÇÑ µµ½Ã¸¦ ³ªÅ¸³»´Âµ¥ 5 ºñÆ®°¡ ÇÊ¿äÇÏ´Ù) ¾î¶² 5
ºñÆ®ÀÇ ¿ (¿¹¸¦ µé¾î 10101) Àº ¾Æ¹«µµ½Ã¿¡µµ ÇØ´çµÇÁö ¾ÊÀ» ¼öµµ ÀÖ´Ù. ±³¹è¿¬»êÀÚ¸¦
Àû¿ë½Ãų ¶§¿¡µµ À¯»çÇÑ ¹®Á¦°¡ ³ªÅ¸³´Ù. ¸¸ÀÏ ¾Õ¿¡¼ Á¤ÀÇµÈ °Í°ú °°Àº µ¹¿¬º¯ÀÌ
¹× ±³¹è ¿¬»êÀÚ¸¦ »ç¿ëÇÑ´Ù¸é ºÐ¸íÈ÷ ¿°»öü¸¦ "º¹±¸" ÇÏ¿© Ž»ö°ø°£À¸·Î
µÇµ¹·Á º¸³»´Â ÀÏÁ¾ÀÇ "º¹±¸ ¾Ë°í¸®Áò" ÀÌ ÇÊ¿äÇÒ °ÍÀÌ´Ù.
º¹±¸ ¾Ë°í¸®ÁòÀ» »ç¿ëÇÏ´Â ´ë½Å Á¤¼öº¤ÅͷΠǥÇöÇÏ´Â
°ÍÀÌ ´õ ³ªÀº °Íó·³ º¸ÀδÙ. ¹®Á¦°íÀ¯ÀÇ Áö½ÄÀ» ¿¬»êÀÚ¿Í °áÇÕÇÏ¿© ºÎÀûÇÕÇÑ °³Ã¼°¡
»ý¼ºµÇ´Â °ÍÀ» "Áö´ÉÀûÀ¸·Î" ÇÇÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ÀÌ Á¢±Ù ¹æ½Ä¿¡¼´Â
Á¤¼ö Ç¥ÇöÀ» ¹Þ¾ÆµéÀδ٠: º¤ÅÍ Àº
¿¡¼
·Î,
¿¡¼
À¸·Î, ±×¸®°í ´Ù½Ã
À¸·Î ¿©ÇàÇÏ´Â °ÍÀ» ³ªÅ¸³½´Ù. (
´Â <1 2 ...
> ÀÇ ¼ø¿ÀÌ´Ù).
ÃʱâÈ °úÁ¤¿¡¼´Â ÈÞ¸®½ºÆ½À» »ç¿ëÇϰųª (¿¹¸¦
µé¾î ´Ù¸¥ µµ½Ã·ÎºÎÅÍ Ãâ¹ßÇÏ´Â TSP ¿¡ ´ëÇÑ °æ»ç ¾Ë°í¸®ÁòÀ¸·ÎºÎÅÍÀÇ ¸î °¡Áö °á°ú¸¦
¹Þ¾ÆµéÀÏ ¼ö ÀÖ´Ù), ¶Ç´Â <1 2 ... > ÀÇ ¼ø¿ÀÇ ·£´ýÇ¥º»¿¡ ÀÇÇØ Ãʱ⠰³Ã¼Áý´ÜÀ» »ý¼ºÇÒ ¼ö ÀÖ´Ù.
¿°»öüÀÇ Æò°¡´Â ´Ü¼øÇϸç, °¢ µµ½Ã »çÀÌÀÇ ¿©Çà °æºñ°¡ ÁÖ¾îÁ³À» ¶§ Àüü ¿©ÇàÀÇ ÃѰæºñ¸¦ ½±°Ô °è»êÇÒ ¼ö ÀÖ´Ù.
TSP ¿¡¼´Â °¡Àå ÁÁÀº ¿©ÇàÀ» À§ÇÑ µµ½ÃÀÇ ¹è¿À» Ž»öÇÑ´Ù. ´õ ÁÁÀº ½ºÆ®¸µÀÇ ¹è¿À» Ž»öÇÏ´Â ¾î¶² ´ÜÀÏ ¿¬»êÀÚ (´ÜÀÏ ÇüÅ ¿¬»êÀÚ) ¸¦ °í¾ÈÇØ ³»´Â °ÍÀº ºñ±³Àû ½±´Ù. ±×·¯³ª ´ÜÀÏ ¿¬»êÀÚ¸¸À» »ç¿ëÇϸé (°¡Àå ÁÁÀº °ÍÀº Â÷ÁöÇϰí) ÁÁÀº ¹è¿À» ã´Â´Ù´Â Èñ¸ÁÀÌ Àû´Ù [119]. °Ô´Ù°¡ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ´É·ÂÀº ¾ÆÁÖ ÀûÇÕÇÑ °³Ã¼µéÀÇ ±³¹è Á¶ÇÕÀÇ ±¸Á¶ÈµÈ Á¤º¸ ±³È¯À¸·ÎºÎÅÍ Á¦±âµÈ´Ù. ±×·¡¼ ¿°»öüµé°£ÀÇ Áß¿äÇÑ À¯»ç¼ºµéÀ» ÀÌ¿ëÇÏ´Â ±³¹è¿Í °°Àº ¿¬»êÀÚ°¡ ÇÊ¿äÇÏ´Ù. ±× ¸ñÀûÀ¸·Î OX ¿¬»êÀÚ [51] ÀÇ º¯ÇüÀ» ÀÌ¿ëÇϴµ¥, ±×°ÍÀº ÁÖ¾îÁø µÎ ºÎ¸ð¿¡ ´ëÇØ ÇÑ ºÎ¸ð·ÎºÎÅÍ ¿©ÇàÀÇ ÀϺκÐÀ» ¼±ÅÃÇÏ°í ´Ù¸¥ ºÎ¸ð·ÎºÎÅÍ µµ½ÃÀÇ »ó´ëÀûÀÎ ¼ø¼¸¦ À¯Áö½ÃÅ´À¸·Î½á ÀÚ¼ÕÀ» ±¸¼ºÇÑ´Ù. ¿¹¸¦ µé¾î ¸¸ÀÏ ºÎ¸ð°¡
< 1 2 3 4 5 6 7 8 9 10 11 12 > ¿Í < 7 3 1 11 4 12 5 2 10 9 6 8 >
À̰í, ¼±ÅÃµÈ ºÎºÐÀÌ
(4 5 6 7)
À̶ó¸é °á°ú·Î ´ÙÀ½°ú °°Àº ÀÚ¼ÕÀÌ »ý¼ºµÈ´Ù.
< 1 11 12 4 5 6 7 2 10 9 8 3 >
¿ä±¸µÇ´Â ´ë·Î ÀÚ¼ÕÀº ¾çÂÊ ºÎ¸ð¿¡ ´ëÇÑ ±¸Á¶ÀûÀÎ °ü°è¸¦ Æ÷ÇÔÇÑ´Ù. µÎ ¹øÂ° ÀÚ¼ÕÀ» ±¸¼ºÇϴµ¥ ÀÖ¾î¼ ºÎ¸ðÀÇ ¿ªÇÒµéÀÌ ¹ÝÀüµÉ ¼ö ÀÖ´Ù.
À§ÀÇ ¿¬»êÀÚ¿¡ ±âÃÊÇÑ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ·£´ýŽ»öº¸´Ù ¼º´ÉÀÌ ¿ì¼öÇÏÁö¸¸ ´õ¿í °³¼±½Ãų ¼ö ÀÖ´Â ¿©Áö¸¦ ³²°Ü ³õ°í ÀÖ´Ù. ÀÌ ¾Ë°í¸®ÁòÀÇ ÀüÇüÀûÀÎ °á°ú´Â (20 ¹ø ÀÌ»óÀÇ ·£´ý¼öÇàÀÇ Æò±Õ¿¡¼) Àüü ¿©ÇàÀÇ °ªÀÌ (2000 ¼¼´ë ÀÌÈÄ¿¡) ÃÖÀûÁ¡ÀÌ»ó 9.4 % À̾ú´Ù.
»ç¿ëµÈ Ç¥Çö¹®Á¦¿Í À¯Àü ¿¬»êÀÚµî TSP ¿¡ ´ëÇÑ ¿ÏÀüÇÑ ÅäÀÇ¿¡ ´ëÇØ¼´Â 10 ÀåÀ» Âü°íÇ϶ó.
ÀÌ Àý¿¡¼´Â ´Ü¼øÇÑ ÃÖÀûÈ ¹®Á¦¿¡ Àû¿ëµÈ ¼¼ °¡Áö ¾Ë°í¸®Áòµé, µî¹Ý ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ, ±×¸®°í À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ °üÇÏ¿© ³íÀÇÇÑ´Ù. ÀÌ ¿¹Á¦´Â GA Á¢±Ù ¹æ½ÄÀÇ µ¶Æ¯ÇÔÀ» °Á¶Çϰí ÀÖ´Ù.
Ž»ö°ø°£Àº ±æÀÌ 30 ÀÇ ÀÌÁø ½ºÆ®¸µ ÀÇ ÁýÇÕÀÌ´Ù. ÃÖ´ëȵǾî¾ß ÇÒ ¸ñÀûÇÔ¼ö
´Â ´ÙÀ½°ú °°ÀÌ ÁÖ¾îÁø´Ù.
¿©±â¼ ÇÔ¼ö ´Â ½ºÆ®¸µ
³»ÀÇ 1 ÀÇ °³¼ö¸¦ ¾Ë·ÁÁØ´Ù. ¿¹¸¦ µé¾î, ´ÙÀ½°ú °°Àº ¼¼ °³ÀÇ ½ºÆ®¸µ
= (110110101110101111111011011011)
= (111000100100110111001010100011)
= (000010000011001000000010001000)
Àº ´ÙÀ½°ú °°ÀÌ Æò°¡µÈ´Ù.
,
,
.
().
ÇÔ¼ö ´Â ¼±ÇüÀ̰í ÃÖÀûÈ °úÁ¦·Î¼ ¾Æ¹«·± ¾î·Á¿î ¹®Á¦¸¦ °¡Áö°í ÀÖÁö ¾ÊÁö¸¸ À̵é
¼¼ ¾Ë°í¸®ÁòÀÇ ¹èÈÄÀÇ ¾ÆÀ̵ð¾î¸¦ º¸À̱â À§ÇØ »ç¿ëÇÑ´Ù. ÇÔ¼ö
ÀÇ Èï¹Ì·Î¿î Ư¡Àº
¿¡ ´ëÇØ ÇϳªÀÇ Àü¿ª ÃÖ´ë°ªÀ» °¡Áö°í ÀÖ´Ù´Â °ÍÀÌ´Ù.
= (111111111111111111111111111111)
À̰í
¿¡ ´ëÇØ ÇϳªÀÇ ±¹¼Ò ÃÖ´ë°ªÀ» °¡Áö°í ÀÖ´Ù.
= (000000000000000000000000000000)
ÀÌ´Ù.
¸î °³ÀÇ µî¹Ý ¾Ë°í¸®ÁòµéÀÌ Àִµ¥, »õ·Î¿î ½ºÆ®¸µÀÌ
ÇöÀçÀÇ ½ºÆ®¸µ°ú ºñ±³µÇ±â À§ÇÏ¿© ¼±ÅõǴ ¹æ½Ä¿¡¼ Â÷ÀÌÁ¡ÀÌ ÀÖ´Ù. ÇÑ ´Ü¼øÇÑ (¼øÈ¯µÇ´Â)
µî¹Ý ¾Ë°í¸®Áò (MAX ¼øÈ¯) ÀÌ ±×¸² 2 ¿¡ ÁÖ¾îÁ® ÀÖ´Ù (ÃÖ±Þ»ó½Â µî¹Ý). Ãʱ⿡ ¸ðµç
30 °³ÀÇ ÀÌ¿ôµéÀÌ °í·ÁµÇ°í, °¡Àå Å« °ªÀ» Á¦°øÇÏ´Â
ÀÌ ¼±ÅõǾî ÇöÀçÀÇ ½ºÆ®¸µ
¿Í °æÀïÇÑ´Ù. ¸¸ÀÏ
À̸é, »õ·Î¿î ½ºÆ®¸µÀÌ ÇöÀçÀÇ ½ºÆ®¸µÀÌ µÈ´Ù. ±×·¸Áö ¾ÊÀ¸¸é ±¹¼ÒÀûÀÎ °³¼±ÀÌ
ºÒ°¡´ÉÇѵ¥, ¾Ë°í¸®ÁòÀº (±¹¼Ò ¶Ç´Â Àü¿ª) ÃÖÀû°ª¿¡ µµ´ÞÇÑ´Ù (
= TRUE). ±×·¯ÇÑ °æ¿ì¿¡ ¾Ë°í¸®ÁòÀÇ ´ÙÀ½ ¼øÈ¯ (
) ÀÌ ÀÓÀÇ·Î ¼±ÅÃµÈ »õ·Î¿î ÇöÀç ½ºÆ®¸µÀ» °¡Áö°í ¼öÇàµÈ´Ù.
procedure interated hillclimber begin t¡ç0 repeat local¡çFALSE select
a current string repeat select
30 new strings in the neighborhood of by
flipping single bits of select
the string with
the largest value of objective function if
then
else local¡çTRUE until local until
end |
±×¸² 2 °£´ÜÇÑ (¼øÈ¯ÀûÀÎ) µî¹Ý
ÀÌ»óÀÇ µî¹Ý ¾Ë°í¸®ÁòÀÇ ÇѹøÀÇ ¼øÈ¯ (Àü¿ª ¶Ç´Â ±¹¼Ò ÃÖÀû°ªÀÇ °è»ê) ÀÇ ¼º°ø ¶Ç´Â ½ÇÆÐ°¡ (ÀÓÀÇ·Î ¼±ÅõÈ) Ãʱ⠽ºÆ®¸µ¿¡ ÀÇÇÏ¿© °áÁ¤µÈ´Ù´Â °ÍÀº Èï¹ÌÀÖ´Â ÀÏÀÌ´Ù. ¸¸ÀÏ Ãʱ⠽ºÆ®¸µÀÌ 13 ¶Ç´Â ±× ÀÌÇÏÀÇ 1 µéÀ» °¡Áö°í ÀÖ´Ù¸é ±× ¾Ë°í¸®ÁòÀº ºÐ¸íÈ÷ Ç×»ó ±¹¼Ò ÃÖÀûÁ¡¿¡¼ ³¡³ª°Ô µÈ´Ù (½ÇÆÐ). ±× ÀÌÀ¯´Â 13 °³ÀÇ 1 À» °¡Áø ½ºÆ®¸µÀÌ ¸ñÀûÇÔ¼öÀÇ °ª 7 À» ÁÖ°í, Àü¿ª ÃÖÀû°ªÀ» ÇâÇÑ ÇÑ ´Ü°è °³¼±ÀÌ 1 ÀÇ °³¼ö¸¦ 14 ·Î Áõ°¡½ÃŰ°í ¸ñÀû ÇÔ¼öÀÇ °ªÀ» 4 ·Î °¨¼Ò½Ã۱⠶§¹®ÀÌ´Ù. ¹Ý¸é¿¡ 1 ÀÇ ¼öÀÇ °¨¼Ò´Â ÇÔ¼öÀÇ °ªÀ» Áõ°¡½Ã۴µ¥, 12 °³ÀÇ 1 À» °¡Áø ½ºÆ®¸µÀº 18 ÀÇ °ªÀ» Á¦°øÇϰí 11 °³ÀÇ 1 À» °¡Áø ½ºÆ®¸µÀº 29 ÀÇ °ªÀ» Á¦°øÇÑ´Ù. À̰ÍÀº Ž»öÀ» "À߸øµÈ" ¹æÇâ, ±¹¼Ò ÃÖ´ë°ªÂÊÀ¸·Î ¹Ð¾î³½´Ù.
±¹¼Ò ÃÖÀû°ªµéÀÌ ¸¹Àº ¹®Á¦¿¡ ´ëÇØ¼ Àü¿ªÃÖÀû°ªÀ» ã¾Æ³»±â À§ÇÑ ±âȸ´Â (´Ü ÇѹøÀÇ ¼øÈ¯¿¡¼) Àû´Ù.
½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ °úÁ¤ÀÇ ±¸Á¶¸¦ ±×¸² 3 ¿¡ ³ªÅ¸³»¾ú´Ù.
procedure simulated annealing begin t¡ç0 initialize temperature T select
a current string evaluate
repeat repeat select
a new string in
the neighborhoof of by
flipping a single bit of if
then
else
if random [0, 1] <exp{ then
until (termination-condition) until (stop-criterion) end |
±×¸² 3 ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ
ÇÔ¼ö random (0, 1) Àº ¹üÀ§ (0, 1) »çÀÌÀÇ ³¼ö¸¦
Á¦°øÇÑ´Ù. (termination-condition) Àº '¿ÀûÆòÇü' ¿¡ µµ´ÞÇß´ÂÁö, Áï ¼±ÅÃµÈ »õ·Î¿î
½ºÆ®¸µÀÇ È®·ü ºÐÆ÷°¡ º¼Â길 ºÐÆ÷ [1] Á¢±ÙÇÏ¿´´ÂÁö¸¦ üũÇÑ´Ù. ±×·¯³ª ¾î¶² ±¸Çö¿¡¼
[2] ÀÌ ¹Ýº¹·çÇÁ´Â ¹ø¸¸ ¼öÇàµÈ´Ù (
´Â ÀÌ ¹æ¹ýÀÇ Ãß°¡ÀûÀÎ ¸Å°³º¯¼öÀÌ´Ù).
¿Âµµ T ´Â ´Ü°èÀûÀ¸·Î ³·¾ÆÁø´Ù (¸ðµç ¿¡ ´ëÇØ¼
). ¾Ë°í¸®ÁòÀº ÀÛÀº T °ª¿¡ ´ëÇØ¼ Á¾·áÇÑ´Ù : (stop-criterion) Àº ÀÌ ½Ã½ºÅÛÀÌ
'¾ó¾îºÙ¾ú´ÂÁö,' Áï ½ÇÁúÀûÀ¸·Î ¾Æ¹«·± º¯Èµµ ¹Þ¾Æµé¿©ÁöÁö ¾Ê´ÂÁö üũÇÑ´Ù.
¾Õ¼ ¾ð±ÞÇÑ ´ë·Î ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ ¾Ë°í¸®ÁòÀº ±¹¼Ò ÃÖÀû°ªµé·ÎºÎÅÍ Å»ÃâÇÒ ¼ö ÀÖ´Ù. 12 °³ÀÇ 1 ·Î ±¸¼ºµÇ¾î ÀÖ´Â ´ÙÀ½ ½ºÆ®¸µÀ» °í·ÁÇÏÀÚ.
= (111000000100110111001010100000)
À̶§ ÀÌ´Ù. ½ÃÀÛ ½ºÆ®¸µÀ¸·Î
¸¦ °í·ÁÇÏ¸é µî¹Ý ¾Ë°í¸®ÁòÀº (¾Õ¿¡¼ ³íÀÇÇÑ ´ë·Î) 13 °³ÀÇ 1 À» °¡Áø ¾î¶²
½ºÆ®¸µ (Àü¿ªÃÖÀû°ªÀ» 'ÇâÇÑ' ÇѴܰè) µµ 7 (18 ÀÌÇÏ) ·Î Æò°¡µÇ¹Ç·Î ´ÙÀ½ÀÇ ±¹¼Ò
ÃÖ´ë°ªÀ¸·Î Á¢±ÙÇÒ °ÍÀÌ´Ù.
= (000000000000000000000000000000)
¹Ý¸é¿¡ ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ ¾Ë°í¸®ÁòÀº 13 °³ÀÇ 1 À» °¡Áø ½ºÆ®¸µÀ» ´ÙÀ½ È®·ü¿¡ ÀǰÅÇÏ¿© »õ·Î¿î ÇöÀç ½ºÆ®¸µÀ¸·Î ¹Þ¾ÆµéÀÏ °ÍÀÌ´Ù.
¿©±â¼ ¾î¶² ¿Âµµ, À̸¦Å׸é T = 20 ¿¡ ´ëÇØ¼ ´ÙÀ½°ú °°ÀÌ µÈ´Ù.
,
Áï ¹Þ¾Æµé¿©Áú È®·üÀº 50 ÆÛ¼¾Æ® ÀÌ»óÀÌ´Ù.
1. Àý¿¡¼ ³íÀÇÇÑ °Íó·³ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ½ºÆ®¸µÀÇ °³Ã¼Áý´ÜÀ» À¯ÁöÇÑ´Ù. µÎ °³ÀÇ ºñ±³Àû ³ª»Û ½ºÆ®¸µµé
= (111110000000110111001110100000)
= (000000000001101110010101111111)
Àº °¢°¢ 16 À¸·Î Æò°¡µÇ°í, ÈξÀ ´õ ÁÁÀº ÀÚ¼ÕÀ» »ý»êÇÒ ¼ö ÀÖ´Ù (¸¸ÀÏ ±³¹è À§Ä¡°¡ 5 ¹øÂ°¿Í 12 ¹øÂ° À§Ä¡ »çÀÌ¿¡ ¾î´À °÷À̶ó°í Çϸé) :
= (111110000000110111001110100000)
»õ·Î¿î ÀÚ¼Õ Àº ´ÙÀ½°ú °°ÀÌ Æò°¡µÈ´Ù.
¿©·¯ °¡Áö ´Ù¸¥ Ư¼ºµéÀ» °¡Áø ¿©·¯ ÇÔ¼öµé¿¡ ´ëÇÏ¿© Å×½ºÆ®µÈ ÀÌµé ±×¸®°í ´Ù¸¥ ¾Ë°í¸®Áòµé (¿©·¯°¡Áö º¯ÇüµÈ ÇüÅÂÀÇ µî¹Ý, À¯ÀüÀÚ Å½»ö, ±×¸®°í ½Ã¹Ä·¹ÀÌÆ¼µå ¾î´Ò¸µ ±â¹ýµé) ¿¡ °üÇÑ ´õ ÀÚ¼¼ÇÑ ¼³¸íÀ» À§Çؼ´Â [2] ¸¦ Âü°íÇ϶ó.
ÇÔ¼ö ÃÖÀûÈ, Á˼öÀÇ µô·¹¸¶, ±×¸®°í ¼øÈ¸ÆÇ¸Å¿ø¹®Á¦¿¡
´ëÇÑ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¿¹Á¦µéÀº À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ±¤¹üÀ§ÇÑ ÀÀ¿ë °¡´É¼ºÀ» º¸¿©ÁÖ°í
ÀÖ´Ù. ±×·¯³ª µ¿½Ã¿¡ ÀáÀçÇϰí ÀÖ´Â ¾î·Á¿òÀÇ ¿ì¼± ½ÅÈ£¸¦ °üÂûÇØ¾ß ÇÑ´Ù.¼øÈ¸ÆÇ¸Å¿ø¹®Á¦¿¡
´ëÇÑ Ç¥Çö¹®Á¦´Â ´Ü¼øÇÏÁö ¾Ê¾Ò´Ù. »ç¿ëµÈ »õ·Î¿î ¿¬»êÀÚ (OX ±³¹è) ´Â ÀüÇô °£´ÜÇÏÁö
¾Ê´Ù. ´Ù¸¥ Á¾·ùÀÇ (¾î·Á¿î) ¹®Á¦µé¿¡ ´ëÇØ Á÷¸éÇÏ°Ô µÇ´Â ´õ¿í ¾î·Á¿î Á¡µéÀº ¾î¶°ÇÑ
°ÍµéÀΰ¡? ù ¹øÂ°¿Í ¼¼ ¹øÂ° ¿¹Á¦ (ÇÔ¼ö ÃÖÀûÈ¿Í ¼øÈ¸ÆÇ¸Å¿ø¹®Á¦) ¿¡¼ Æò°¡ÇÔ¼ö´Â
ºÐ¸íÈ÷ Á¤ÀǵǾú´Ù. µÎ ¹øÂ° ¿¹Á¦ (Á˼öÀÇ µô·¹¸¶) ¿¡¼ °£´ÜÇÑ ¸ðÀǽÇÇè °úÁ¤ÀÌ
¿°»öüÀÇ Æò°¡¸¦ Á¦°øÇÒ °ÍÀÌ´Ù (°¢ Ç÷¹À̾ Å×½ºÆ®ÇÏ¿© À¯È¿¼ºÀ» Å×½ºÆ®ÇÏ¿´´Âµ¥,
°¢ Ç÷¹À̾î´Â ¿°»öü¿¡ ÀÇÇØ¼ Á¤ÀÇµÈ Àü·«À» »ç¿ëÇÏ¿© ´Ù¸¥ Ç÷¹À̾î¿Í °ÔÀÓÀ»
ÇÏ¿´°í ±× Ç÷¹À̾îÀÇ Á¡¼ö´Â ±×°¡ ÇÑ ¸ðµç °ÔÀÓ¿¡ ´ëÇÑ Æò±ÕÀÌ´Ù). Æò°¡ ÇÔ¼ö°¡
ºÐ¸íÇÏ°Ô Á¤ÀǵÇÁö ¾ÊÀº °æ¿ì¿¡´Â ¾î¶»°Ô ÁøÇàÇÏ¿©¾ß Çϴ°¡? ¿¹¸¦ µé¾î Boolean
¸¸Á·¹®Á¦ (SAT) ´Â ÀÚ¿¬½º·¯¿î ½ºÆ®¸µÀÇ Ç¥Çö¹æ¹ýÀ» °¡Áö°í ÀÖ´Â °Í °°´Ù ( ¹øÂ° ºñÆ®´Â
¹øÂ° Boolean º¯¼öÀÇ Áø¸® °ªÀ» ³ªÅ¸³½´Ù). ±×·¯³ª Æò°¡ ÇÔ¼ö¸¦ ¼±ÅÃÇÏ´Â °úÁ¤Àº
±×·¸°Ô °£´ÜÇÏÁö ¾Ê´Ù [68].
±¸¼ÓÁ¶°ÇÀÌ ¾ø´Â ÇÔ¼öÀÇ ÃÖÀûÈÀÇ Ã¹ ¹øÂ° ¿¹Á¦¿¡¼´Â Æí¸®ÇÑ Ç¥Çö ¹æ¹ýÀ» »ç¿ëÇÒ ¼ö Àִµ¥, ¾î¶°ÇÑ ÀÌÁø ½ºÆ®¸µµµ ¹®Á¦¿µ¿ª (¿¹¸¦ µé¾î, [-1, 2]) À¸·ÎºÎÅÍÀÇ ÇÑ °ª¿¡ ÇØ´çÇÑ´Ù. À̰ÍÀº ¾î¶°ÇÑ µ¹¿¬º¯ÀÌ¿Í ±³¹èµµ ÀûÇÕÇÑ ÀÚ¼ÕÀ» ¸¸µé¾î ³¾ °ÍÀ̶ó´Â °ÍÀ» ÀǹÌÇÑ´Ù. µÎ ¹øÂ° ¿¹Á¦¿¡¼µµ ¸¶Âù°¡Áö·Î ¾î¶°ÇÑ ºñÆ®µéÀÇ Á¶ÇÕµµ ÀûÇÕÇÑ Àü·«À» Ç¥ÇöÇÑ´Ù. ¼¼ ¹øÂ° ¹®Á¦¿¡¼´Â °¢ µµ½Ã´Â ÇϳªÀÇ ÀûÇÕÇÑ ¿©Çà¿¡¼ ´Ü Çѹø¸¸ ³ªÅ¸³ª¾ß ÇÑ´Ù´Â ±¸¼ÓÁ¶°ÇÀ» °¡Áö°í ÀÖ´Ù. À̰ÍÀº ¾à°£ÀÇ ¹®Á¦¸¦ ¾ß±âÇÏ¿´À¸¹Ç·Î (ÀÌÁøÇ¥Çö ´ë½Å¿¡) Á¤¼ö º¤Å͸¦ »ç¿ëÇÏ¿´°í ±³¹è¿¬»êÀÚ¸¦ º¯°æÇÏ¿´´Ù. ±×·¯³ª ÀϹÝÀûÀ¸·Î ¾î¶»°Ô ±¸¼ÓÁ¶°ÇÀÌ ÀÖ´Â ¹®Á¦¿¡ Á¢±ÙÇÒ °ÍÀΰ¡? ¾î¶°ÇÑ °¡´É¼ºÀ» °¡Áö°í Àִ°¡?
ÀÌ·¯ÇÑ ÇØ´äÀº ½±Áö ¾ÊÀ¸¸ç, ÀÌ Ã¥ÀÇ ³ª¸ÓÁö ºÎºÐ¿¡¼ À̵鿡 °üÇÏ¿© ޱ¸ÇÒ °ÍÀÌ´Ù.