À¯ÀüÀÚ ¾Ë°í¸®Áò

 

Áö´ÉÁ¤º¸½Ã½ºÅÛ ¿ø·Ð : Á¤È¯¹¬ ÆíÀú, 21¼¼±â»ç, 1999, Page 354~375

 

ÁøÈ­Àû ¿¬»ê

»ý¹°ÀÇ À¯Àü°ú ÁøÈ­ÀÇ ¿ø¸®

½ÇÁ¦ÀÇ À¯ÀüÀÚ

À¯ÀüÀÚ ¾Ë°í¸®Áò ÀÇ ÇÁ·Î¼¼½º

¿©·¯°¡Áö ¼±Åùý

½ºÄÉÀϸµ

À¯Àü ¿¬»êÀÚ(genetic operator)

À¯ÀüÀÚ ¾Ë°í¸®Áò À» ÀÌÇØÇϱâ À§ÇÑ ÀÀ¿ë ¿¹

À¯ÀüÀÚ ¾Ë°í¸®Áò ÀÇ ÀåÁ¡°ú ´ÜÁ¡

 

 

À¯ÀüÀÚ ¾Ë°í¸®Áò Àº »ý¹°ÀÇ À¯Àü°ú ÁøÈ­ ¸ÞÄ«´ÏÁòÀ» °øÇÐÀûÀ¸·Î ¸ðµ¨È­ÇÏ¿© ¹®Á¦ ÇØ°áÀ̳ª ½Ã½ºÅÛÀÇ ÇнÀ µî¿¡ ÀÀ¿ëÇÏ·Á°í ÇÑ °ÍÀÌ´Ù. ¿©±â¼­´Â °øÇÐÀûÀÎ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» ±Ùº»ÀûÀ¸·Î ÀÌÇØÇϱâ À§Çؼ­ »ý¹°ÀÇ À¯Àü°ú ÁøÈ­¸¦ ¼³¸íÇÏ°í ¿¹¸¦ ÅëÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¿ø¸®¸¦ ½ÀµæÇÑ´Ù. 

ÁøÈ­Àû ¿¬»ê

À¯ÀüÀÚ ¾Ë°í¸®Áò ¶Ç´Â ÁøÈ­Àû ¾Ë°í¸®ÁòÀº ÀÚ¿¬¼¼°èÀÇ ÁøÈ­Çö»ó¿¡ ±â¹ÝÇÑ °è»ê ¸ðµ¨ÀÌ´Ù. ÁøÈ­¾Ë°í¸®ÁòÀº Ç®°íÀÚ ÇÏ´Â ¹®Á¦¿¡ ´ëÇÑ °¡´ÉÇÑ ÇصéÀ» Á¤ÇØÁø ÇüÅÂÀÇ ÀڷᱸÁ¶·Î Ç¥ÇöÇÑ ´ÙÀ½, À̵éÀ» Á¡Â÷ÀûÀ¸·Î º¯ÇüÇÔÀ¸·Î½á Á¡Á¡ ´õ ÁÁÀº ÇصéÀ» »ý¼ºÇÑ´Ù. °¢°¢ÀÇ °¡´ÉÇÑ Çظ¦ ÇϳªÀÇ À¯±âü(organism) ¶Ç´Â °³Ã¼(indivisual)·Î º¸¸ç À̵éÀÇ ÁýÇÕÀ» °³Ã¼±º(population)À̶ó ÇÑ´Ù. ÇϳªÀÇ °³Ã¼´Â º¸Åë ÇÑ °³ ¶Ç´Â ¿©·¯ °³ÀÇ ¿°»öü(chromosomes)·Î ±¸¼ºµÇ¸ç ¿°»öü¸¦ º¯ÇüÇÏ´Â ¿¬»êÀÚµéÀ» À¯Àü¿¬»êÀÚ¶ó ÇÑ´Ù. ÁøÈ­¾Ë°í¸®ÁòÀº Ž»ö, ÃÖÀûÈ­ ¹× ±â°èÇнÀÀ» µµ±¸·Î ¸¹ÀÌ »ç¿ëÇÑ´Ù. ÁøÈ­Àû ¿¬»ê(evolutionary computation)Àº ÁÖ·Î ´ÙÀ½ÀÇ ¹®Á¦ÇØ°á Àü·«¿¡ ÀÇÇØ Æ¯Â¡ Áö¿ï ¼ö ÀÖ´Ù([Ç¥ 1ÂüÁ¶]). 

  ÀÌ»óÀÇ ±â¿øÀº 19¼¼±âÀÇ Charles DarwinÀÇ ÁøÈ­·Ð¿¡ ÀÇÇÑ °ÍÀ¸·Î ÀÚ¿¬¼±Åðú ÀûÀÚ»ýÁ¸(natural selection and survival of fittest)À» ±âÃÊ·Î ÇÑ »ý¹°ÇÐÀû °üÂû Á¦¾ÈÀÌ´Ù. µû¶ó¼­, ÇöÀç ÀÌ¿Í°°Àº ¾Ë°í¸®ÁòÀ» ÁøÈ­Àû ¾Ë°í¸®Áò(evolutinary algorithm : EA)À̶ó ºÎ¸¥´Ù. ÁøÈ­Àû ¿¬»êÁß¿¡´Â °³Ã¼ÀÇ Áý´Ü¿¡ °üÇÑ À¯ÀüÀÇ º¯È­ÀÇ ¸ðµ¨¿¡ ±âÃÊÇÑ ´Ù¼öÀÇ ¹æ¹ý·Ð°ú ±â¼úÀÌ Æ÷ÇԵǾî ÀÖ´Ù. ÇöÀç Àΰø»ý¸íÀ̳ª »ý¹°ÇеîÀÇ ºÐ¾ß¿¡ À־ GA, GP, EP, ES¶ó´Â ÁøÈ­Àû Á¢±Ù(approch)ÀÌ ´Ù¼ö »ç¿ëµÇ°í ÀÖ´Ù.  

 [Ç¥ 1] ÁøÈ­ ¾Ë°í¸®ÁòÀÇ Á¾·ù

ÀÌ         ¸§

¹®Á¦ Ç¥Çö ¹æ½Ä

ÁÖ¿¬»êÀÚ

±â   ¿ø

ÁÖ ÀÀ¿ëºÐ¾ß

À¯ÀüÀÚ ¾Ë°í¸®Áò(GA)

 0/1

½ºÆ®¸µ

±æÀÌ°íÁ¤

crossover

 Holland, J.H.(1975)

¹®ÀÚ¿­,

º¤ÅÍ¿­Å½»ö

ÁøÈ­Àü·«(ES)

 ½Ç¼ö

º¤ÅÍ

±æÀÌ°íÁ¤

mutation

 Rechenberg, I.(1963)

½Ç¼öÄ¡ Ž»ö

ÁøÈ­ ÇÁ·Î±×·¡¹Ö(EP)

 ÀÌ»êÄ¡

±×·¡ÇÁ

Å©±â°íÁ¤

mutation

 Fogel, L.J.

¿ÀÅ丶Åæ ÇÕ¼º

À¯ÀüÀÚ ÇÁ·Î±×·¡¹Ö(GP)

 ±âº»ÇÔ¼ö

Æ®¸®

Å©±â°¡º¯

crossover

 Koza, J.(1990)

ÇÁ·Î±×·¥ ÇÕ¼º

ÁøÈ­Àû ¿¬»ê¿¡ À־ Áß½ÉÀ¸·Î µÇ´Â °ÍÀº °ÅÀÇ DarwinianÀÌ·ÐÀÇ ´Ü¼øÈ­µÈ ¸ÞÄ«´ÏÁòÀÇ ÀÀ¿ëÀÌ´Ù. ƯÈ÷ ´ëºÎºÐÀÇ ÀÀ¿ëÀº ´ÙÀ½ 3°¡ÁöÀÇ ±âº»ÀûÀÎ ±¸¼º¿ä¼Ò¸¦ °®°í ÀÖ´Ù.

ÁøÈ­Àû ¿¬»êÀº ÄÄÇ»Å͸¦ »ç¿ëÇÑ ¹®Á¦ÇØ°á½Ã½ºÅÛÀÇ ¼³°è¿Í ½ÇÇà¿¡ ÁøÈ­Àû ÇÁ·Î¼¼½º¸¦ »ç¿ëÇÑ´Ù. ÇöÀç±îÁö ¿©·¯ °¡Áö ÁøÈ­Àû ÇÁ·Î¼¼½ºÀÇ ¿¬»ê¸ðµ¨ÀÌ Á¦¾ÈµÇ¾î ÀÖ´Ù. À̵éÀº ÁÖ·Î 3°¡ÁöÀÇ ÁøÈ­Àû ÇÁ·Î¼¼½º Áï, ¼±ÅÃ(selection), µ¹¿¬º¯ÀÌ(mutation), »ý½Ä(reproduction)À» »ç¿ëÇÑ´Ù. 

  ¡á ÁøÈ­Àû ¾Ë°í¸®Áò°ú Á¾·¡ÀÇ ÃÖÀûÈ­º¡¹ýÀÇ Â÷ÀÌÁ¡

  ÁøÈ­Àû ¾Ë°í¸®ÁòÀº Æ÷ÀÎÆ®·ÎºÎÅÍ Æ÷ÀÎÆ®·ÎÀÇ Çظ¦ ±¸ÇÏ´Â ±¹¼Ò Ž»ö¹ýÀÌ ¾Æ´Ï°í °³Ã¼±ºÀ¸·Î Çظ¦ ±¸ÇÏ´Â ÃÖÀûÇØ Å½»ö¹ýÀÌ´Ù.

  ¡á ÁøÈ­Àû Àü·«(evolutionary strategy)

ÁøÈ­Àû Àü·«Àº ¹«¼º»ý½Ä¿¡¼­ À¯±âüÀÇ ¹ß´ÞÀ» simulation ÇÑ °ÍÀÌ´Ù. À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÌ ±³¹è¹æ¹ý¿¡ ÀÇÇÑ ÇØÀÇ Àç°áÇÕÀÎ °Í¿¡ ´ëÇÏ¿© ÁøÈ­Àû Àü·«Àº µ¹¿¬º¯ÀÌ¿Í ¼±Åùæ¹ý¸¸À» »ç¿ëÇÑ´Ù.

  ES´Â GA¿Í ´Ù¸¥ ½Ç ÆĶó¹ÌÅ͸¦ »ç¿ëÇÑ´Ù. ¿©±â¼­ ES¿¡ °üÇÏ¿© º¸´Ù ±í°Ô ÀÌÇØÇϱâ À§ÇÏ¿© Schwefel¿¡ ÀÇÇØ Á¦¾ÈµÈ -ES¿¡ ´ëÇÏ¿© ¼³¸íÇÑ´Ù.  

´Ü°è 1

ÃʱâÈ­ : ºÎ¸ðº¤ÅÍÀÇ ÃʱâÈ­µÈ °³Ã¼Áý´Ü Xi(i=1, ¡¦, ¥ì)´Â ½ÇÇà¹üÀ§·ÎºÎÅÍ ·£´ýÇÏ°Ô ¼±ÅõȴÙ.

´Ü°è 2

µ¹¿¬º¯ÀÌ : ÀÚ¼Õº¤ÅÍ Xi(j=1, ¡¦, ¥ì)´Â °¢°¢ÀÇ XiÀÇ ±¸¼º¿¡ ´ëÇÑ GaussianÀÇ ·£´ýÀÎ º¯È­¸¦ ±âÇÏ´Â °Í¿¡ ÀÇÇØ °¢°¢ÀÇ ºÎ¸ð Xi·ÎºÎÅÍ ¸¸µé¾îÁø´Ù.

´Ü°è 3

Æò°¡ : Xi¿Í XjÀÇ ÀûÀÀµµ¸¦ Æò°¡ÇÑ´Ù.

´Ü°è 4

¼±Åà : ´ÙÀ½¼¼´ëÀÇ »õ·Î¿î ºÎ¸ð¸¦ ±×µéÀÇ ÀûÀÀµµ·Î ±âÃÊÇÑ °³Ã¼Áý´ÜÀ¸·ÎºÎÅÍ ¼±ÅÃÇÑ´Ù.

´Ü°è 3

 (´Ü°è2)·ÎºÎÅÍ (´Ü°è4)±îÁö¸¦ ÇØ°¡ ¼ö·ÅÇÒ ¶§±îÁö ¹Ýº¹ÇÑ´Ù.

 

  ¡á ÁøÈ­Àû ÇÁ·Î±×·¡¹Ö(evolutionary programming)

  ÁøÈ­Àû ÇÁ·Î±×·¥Àº -ES¿Í À¯»çÇÏ´Ù. ±×·¯³ª È®·üÀûÀÎ Åä³Ê¸àÆ®¸¦ »ç¿ëÇÑ ÇØÀÇ º¯È­¸¦ °­Á¶ÇÏ°í ÀÖ´Ù. È®·üÀûÀÎ Åä³Ê¸àÆ®¿¡¼­´Â °³Ã¼°¡ ¼­·Î ´ÙÀ½ ¼¼´ë¿¡ ¼±ÅÃµÈ °úÁ¤À» Á÷Á¢ ¿¬»êÇÑ´Ù. µû¶ó¼­ ÇϳªÀÇ ³·Àº ÀûÀÀµµ¸¦ °¡Áø °³Ã¼´Â ¸¸ÀÏ »ó´ë¹æ °³Ã¼ÀÇ ÀûÀÀµµ°¡ ³·À¸¸é ¼±ÅÃµÉ °¡´É¼ºÀÌ ³ô°Ô µÈ´Ù. ÁøÈ­Àû ÇÁ·Î±×·¥À» »ç¿ëÇÑ ÃÖÀûÇظ¦ ¾ò´Â ¹æ¹ýÀº ´ÙÀ½°ú °°´Ù.

´Ü°è 1

ÃʱâÈ­ : ºÎ¸ðº¤ÅÍÀÇ ÃʱâÈ­µÈ °³Ã¼Áý´Ü Xi(i=1, ¡¦, ¥ì)´Â ½ÇÇà¹üÀ§·ÎºÎÅÍ ·£´ýÇÏ°Ô ¼±ÅõȴÙ.

´Ü°è 2

µ¹¿¬º¯ÀÌ : ÀÚ¼Õº¤ÅÍ Xi(j=1, ¡¦, ¥ì)´Â °¢°¢ÀÇ XiÀÇ ±¸¼º¿¡ ´ëÇÑ GaussianÀÇ ·£´ýÀÎ º¯È­¸¦ ±âÇÏ´Â °Í¿¡ ÀÇÇØ °¢°¢ÀÇ ºÎ¸ð Xi·ÎºÎÅÍ ¸¸µé¾îÁø´Ù.

´Ü°è 3

Æò°¡ : Xi¿Í XjÀÇ ÀûÀÀµµ¸¦ Æò°¡ÇÑ´Ù.

´Ü°è 4

°æÇÕ : q°³ÀÇ °æÇÕÀÚ¸¦ Xi¿Í XjÁß¿¡¼­ ·£´ýÇÏ°Ô ¼±ÅÃÇÑ´Ù. ±× ´ÙÀ½¿¡ °¢ °³Ã¼ÀÇ ÀûÀÀµµ¿Í °æÀï »ó´ë¹æÀ» ºñ±³ÇÏ¿© ¹«°Ô °è¼ö Wi(j=1,¡¦, ¥ì)¸¦ °è»êÇÑ´Ù.

´Ü°è 5

 ¼±Åà : ±×µéÀÇ ¹«°Ô¿¡ ÀÇÇØ ´ÙÀ½ ¼¼´ëÀÇ »õ·Î¿î ºÎ¸ð°¡ ¼±ÅõȴÙ.

´Ü°è 6

 (´Ü°è2)·Î ºÎÅÍ (´Ü°è5)±îÁö¸¦ ÇØ°¡ ¼ö·ÅÇÒ ¶§±îÁö ¹Ýº¹ÇÑ´Ù.

 

»ý¹°ÀÇ À¯Àü°ú ÁøÈ­ÀÇ ¿ø¸®

À¯ÀüÀÚ ¾Ë°í¸®Áò (GA) À̶õ ÀÚ¿¬°è¿¡ À־ »ý¹°ÀÇ À¯Àü°ú ÁøÈ­ÀÇ ¸ÞÄ«´ÏÁòÀ» °øÇÐÀûÀ¸·Î ¸ðµ¨È­ÇÏ´Â °Í¿¡ ÀÇÇØ »ý¹°ÀÌ °®´Â ȯ°æ¿¡¼­ ÀûÀÀ´É·ÂÀ» Ãë±ÞÇÏ´Â °ÍÀÌ°í, 1970³â´ë Ãʱ⿡ John Holland(´ç½Ã Michigan´ëÇб³¼ö)¿¡ ÀÇÇØ Á¦¾ÈµÈ ÀÚ¿¬µµÅÂÀÇ ¿ø¸®¸¦ ±âÃÊ·ÎÇÑ ÃÖÀûÈ­ ¹æ¹ýÀÌ´Ù. Áï, À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ÀÚ¿¬°èÀÇ ÁøÈ­Çö»óÀ» ±â¹ÝÀ¸·Î ¸¸µé¾îÁø °è»ê¸ðµ¨·Î½á Ç®°íÀÚÇÏ´Â ¹®Á¦¿¡ ´ëÇÑ °¡´ÉÇÑ ÇصéÀ» Á¤ÇØÁø ÇüÅÂÀÇ ÀڷᱸÁ¶·Î Ç¥ÇöÇÑ ´ÙÀ½, À̵éÀ» Á¡Â÷ÀûÀ¸·Î º¯ÇüÇÔÀ¸·Î½á Á¡Á¡ ´õ ÁÁÀº ÇصéÀ» »ý¼ºÇÏ°Ô µÈ´Ù. À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº Ž»ö ¹× ÃÖÀûÈ­, ±â°èÇнÀÀÇ µµ±¸·Î ¸¹ÀÌ »ç¿ëµÇ°í ÀÖ´Ù. ±×·¯¹Ç·Î °øÇÐÀûÀÎ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» ±Ùº»ÀûÀ¸·Î ÀÌÇØÇϱâ À§Çؼ­ ¿ì¼± »ý¹°ÀÇ À¯Àü°ú ÁøÈ­¿¡ ´ëÇؼ­ ¼³¸íÇÑ´Ù.

ÀϹÝÀûÀ¸·Î »ý¹°Àº ȯ°æ¿¡ Àß ÀûÀÀÇÒ ¼ö ÀÖ´Ù¸é »ý¸íÀÇ Á¸¼Ó°ú Áõ½ÄÀÌ °¡´ÉÇÏ´Ù. Áõ½ÄÀ» ÇÒ ¶§¿¡´Â ÀÚ±âÀÚ½ÅÀÌ °¡Áö°í ÀÖ´Â »ý¹°·Î¼­ÀÇ ¼³°è Á¤º¸¸¦ ¸î °¡ÁöÀÇ ÇüÅ·ΠÀڼյ鿡°Ô Àü¼öÇؾ߸¸ ÇÑ´Ù. ÀÌ·¯ÇÑ ¼³°è Á¤º¸´Â À¯ÀüÀÚ¿¡ ½á³Ö´Â´Ù.

´Ü¼¼Æ÷ »ý¹°°ú °°Àº Çϵî»ý¹°¿¡ À־´Â Áõ½ÄÀº ü¼¼Æ÷ ºÐ¿­¿¡ ÀÇÇØ ÇàÇØÁø´Ù. ÀÌ °æ¿ì, À¯ÀüÀÚ´Â º¹»çµÇ¾î Èļտ¡°Ô Àü´ÞµÈ´Ù. Çϵî»ý¹°Àº ÈÄõÀûÀ¸·Î ȹµæµÈ °ÍÀÌ ¸Å¿ì Àû±â ¶§¹®¿¡ ÀÚ¼ÕÀº ¿ø¸®ÀûÀ¸·Î ¾ÆÁÖ °°Àº ¼ºÁúÀ» °¡Áø´Ù. ±× °á°ú, ¸¹Àº ¼¼´ë¸¦ °ÅÃĵµ °ÅÀÇ º¯È­ÇÏÁö ¾ÊÀº »ý¹°ÀÌ ¸¸µé¾îÁ® °£´Ù.

°íµî»ý¹°¿¡¼­´Â Áõ½ÄÀº ÀûÀÚ»ýÁ¸¿¡ ÀÇÇؼ­ ÇàÇØÁö±â ¶§¹®¿¡ ¾Æ¹öÁö¿Í ¾î¸Ó´ÏÂÊÀÇ À¯ÀüÀÚ°¡ È¥ÇÕÀÌ µÇ°Ô µÈ´Ù. µû¶ó¼­ ¶È°°Àº °³Ã¼´Â »ý¼ºµÇÁö ¾Ê°í, Á¶±Ý¾¿ ´Ù¸¥ °³Ã¼°¡ »ý¼ºµÇ¹Ç·Î ÀÌ ¼¼´ë¿¡ ÀڽŰú ¶È°°Àº Àΰ£Àº ¸¸µé¾îÁöÁö ¾Ê´Â °ÍÀÌ´Ù(À϶õ¼º ½ÖµÕÀÌ´Â À¯ÀüÀûÀ¸·Î´Â ¶È°°Áö¸¸ ÈÄõÀûÀÎ °³Ã¼ Çü¼ºÀÇ °úÁ¤¿¡ À־ Â÷·Ê·Î °³Ã¼ »çÀÌ¿¡ Â÷ÀÌ°¡ »ý±ä´Ù. ±×·¯³ª, À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¿ø¸®¸¦ ÇнÀÇÏ´Â °ÍÀÌ ¸ñÀûÀ̱⠶§¹®¿¡ ´õ ÀÌ»óÀÇ ³íÀÇ´Â »ý·«ÇÑ´Ù).

°íµî»ý¹°Àº [Ç¥ 2]¿¡ ³ªÅ¸³½ ¹Ù¿Í °°ÀÌ °³Ã¼ ±â´ÉÀÇ Á¾ÇÕÀû Á¦¾î¸¦ ¼öÇàÇÏ´Â ³ú½Å°æ°è·ÎºÎÅÍ ³»ºÐºñ°è, È¿¼Ò°è, ¸é¿ª°è µîÀÇ ¿ì¼öÇÑ Á¦¾î ±â±¸¸¦ °¡Áö°í ÀÖ´Ù. ƯÈ÷ ³ú½Å°æ°è´Â ÈÄõÀûÀÎ °æÇèÀ̳ª ÇнÀ¿¡ ÀÇÇØ Å©°Ô ¹ß´ÞÇÑ´Ù.  

 [Ç¥ 2] °íµî»ý¹°ÀÇ Á¦¾î ±â±¸

Á¦  ¾î °è

Á¦¾î ³»¿ë

³ú½Å°æ°è

°³Ã¼ ±â´ÉÀÇ Á¾ÇÕÀû Á¦¾î

³»ºÐºñ°è

È£¸£¸ó¿¡ ÀÇÇÑ Á¦¾î

È¿  ¼Ò °è

»ýü ¹ÝÀÀÀÇ Á¦¾î

¸é  ¿ª °è

¿ÜºÎ·Î ºÎÅÍÀÇ ¹æ¾î

±×·¯³ª °æÇèÀ̳ª ÇнÀÀ» ¹Þ¾ÆµéÀÌ´Â ±â±¸´Â ž ¶§ºÎÅÍ ±¸ºñµÇ¾î ÀÖ´Ù. Áï °íµî »ý¹°Àº ¼±ÃµÀûÀÎ À¯ÀüÀÚ¿¡ ÀÇÇÑ Á¤º¸ Àü´Þ°ú ÈÄõÀûÀÎ °æÇèÀ̳ª ÇнÀ, ÀûÀÀ µîÀÇ 2°¡Áö ¿ä¼Ò¿¡ ÀÇÇØ Çü¼ºµÇ´Â °ÍÀÌ´Ù. ±× ¶§¹®¿¡ °°Àº Á¾·ùÀÇ »ý¹°µµ °¢°¢ ¹Ì¹¦ÇÏ°Ô ´Ù¸£°í, º¸´Ù ¿ì¼öÇÑ °³Ã¼°¡ »ý¼ºµÉ °¡´É¼ºÀÌ ³ô´Ù.

¶ÇÇÑ °íµî»ý¹°, Çϵî»ý¹°¿¡ °ü°è¾øÀÌ À¯ÀüÀÚÀÇ º¹»ç¸¦ ¼öÇàÇÒ ¶§¿¡´Â ¹Ì¹¦ÇÑ ¿À·ù(error)°¡ »ý±æ °¡´É¼ºÀÌ ÀÖ´Ù. ÀÌ°Í¿¡ ´ëÇØ µ¹¿¬º¯ÀÌ(Mutation)°¡ »ý±â°í, »ý¹°ÀÇ ´Ù¾ç¼ºÀÌ È®´ëµÈ´Ù.

ÀÌ»óÀ» Á¤¸®Çϸé, ¿ì¼± ºÎ¸ð·Î ºÎÅÍ À¯ÀüÀÚ¿¡ ÀÇÇØ »ý¹°·Î¼­ÀÇ Á¤º¸ Àü´ÞÀÌ ÇàÇØÁø´Ù. ´ÙÀ½¼¼´ë¿¡´Â °¢ °³Ã¼ Áß¿¡¼­µµ º¸´Ù ¿ì¼öÇÑ Áï, ȯ°æ¿¡ ÀûÀÀµµ°¡ ³ôÀº °³Ã¼ÀÇ À¯Àü Á¤º¸°¡ ¿ì¼±ÀûÀ¸·Î ÀüÇØÁø´Ù. ÀûÀÀµµ°¡ ³·Àº °³Ã¼´Â ¼ö¸íÀÌ Âª°í, Áõ½ÄÇÒ ¼ö ¾ø°Ô µÇ±â ¶§¹®ÀÌ´Ù. µ¿½Ã¿¡ ÀûÀÀµµ°¡ ³·Àº Á¾Á·µµ ÀÚ¿¬ µµÅÂµÇ¾î °£´Ù. ÀÌ·¯ÇÑ ¿ø¸®¿¡ ±âÃÊÇÏ¿© ¼¼´ë¸¦ °ÅµìÇØ °¡¸é Â÷·Ê·Î ȯ°æ¿¡ ÀûÀÀµµ°¡ ³ôÀº °³Ã¼°¡ ¸¹¾ÆÁø´Ù. ÀÌ°ÍÀÌ À¯Àü°ú ÁøÈ­ÀÇ ±âº»ÀûÀÎ ¿ø¸®ÀÌ´Ù.

½ÇÁ¦ÀÇ À¯ÀüÀÚ

¿©±â¼­´Â ¾Ë°í¸®ÁòÀÇ ÀÌÇØ¿¡ µµ¿òÀÌ µÇ´Â »ý¹°ÇÐÀûÀÎ ¹è°æ¿¡ ´ëÇØ ¼³¸íÇÑ´Ù. »ý¹°Àº ¼¼Æ÷·Î ±¸¼ºµÇ°í, ±× ¼¼Æ÷¿¡´Â ÇÙÀÌ ÀÖÀ¸¸ç ±× ÇÙ Áß¿¡´Â ¿°»öü(chromosome)¶ó´Â °ÍÀÌ ÀÖ´Ù. »ç¶÷ÀÇ Ã¼¼¼Æ÷ÀÇ °æ¿ì¿¡´Â 46°³ÀÇ ¿°»öü°¡ ÀÖ°í, ¿°»öü´Â ÁÖ·Î DNA·Î ±¸¼ºµÇ¾î ÀÖ´Ù.

ÀÌ DNA´Â 4Á¾·ùÀÇ ¿°±â¶ó°í ºÎ¸£´Â È­ÇÐ ¹°ÁúÀÌ Áß¿äÇÑ ±¸¼º ¿ä¼Ò¸ç, DNA°¡ °¡Áö´Â Á¤º¸´Â À̵é 4Á¾·ùÀÇ ¿°±âÀÇ ±¸¼º ¹æ¹ý¿¡ ÀÖ´Ù. DNA´Â 2Áß ³ª¼±±¸Á¶·Î µÇ¾î ÀÖÀ¸¸ç, À̵éÀÌ º¹ÀâÇÏ°Ô °ãÃÄÁ®¼­ ¿°»öü¸¦ ±¸¼ºÇÏ°í ÀÖ´Ù.
  [±×¸² 1]¿¡ ³ªÅ¸³½ ¹Ù¿Í °°ÀÌ À¯ÀüÀÚ(gene)¶õ À¯ÀüÁ¤º¸¸¦ ´ã´çÇÏ´Â DNA¸¦ ¸»ÇÑ´Ù. ƯÁ¤ÀÇ À¯ÀüÀÚ´Â ¿°»öüÀÇ Æ¯Á¤ À§Ä¡¿¡ Á¸ÀçÇÏ°í, ±× Àå¼Ò¸¦ ±× À¯ÀüÀÚÀÇ ÀÚ¸®(locus)¶ó°í ºÎ¸£´Â ÀÏÁ¾ÀÇ ÁÂÇ¥¿¡ ÀÇÇØ ±ÔÁ¤µÇ¸ç À¯ÀüÀÚ°¡ ÃëÇÏ°Ô µÇ´Â À¯ÀüÀÚÀÇ È常¦ ´ë¸³À¯ÀüÀÚ(ÇüÁú : allele)¶ó°í ÇÑ´Ù. 

[±×¸² 1] ¿°»öü, À¯ÀüÀÚ, À¯ÀüÀÚ ÀÚ¸®

°á±¹ À¯ÀüÁ¤º¸´Â ¿°»öü»ó¿¡¼­ÀÇ À§Ä¡(À¯ÀüÀÚ À§Ä¡)¿Í ¿°±âÀÇ ¹è¿­¿¡ ÀÇÇØ Ç¥ÇöµÇ´Â °ÍÀÌ´Ù. ÇϳªÀÇ À¯ÀüÀÚ À§Ä¡¿¡ °üÇÑ À¯ÀüÀÚÀÇ Á¶ÇÕÀ» À¯ÀüÀÚÇü(genotype)À̶ó°í ÇÑ´Ù. ¶ÇÇÑ ¾î´À ÇüÁúÀÌ ¾î¶² À¯ÀüÀÚ¿¡ ÀÇÇؼ­ ´ë°³ °áÁ¤µÉ ¶§, ±× ÇüÁúÀ» À¯ÀüÀÚÀÇ Ç¥ÇöÇü(phenotype)À̶ó°í ÇÑ´Ù. Ç¥ÇöÇüÀº ½ÇÁ¦·Î´Â ´Ù¸¥ À¯ÀüÀÚ³ª ȯ°æ µî¿¡¼­ ¾î´À Á¤µµ º¯ÇÏ´Â °Íµµ ÀÖ´Ù. À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡¼­´Â ¿°»öü¸¦ 1Â÷¿øÀ¸·Î °£´ÜÈ­ÇÑ´Ù. °á±¹ ±âÈ£(symbol)³ª ¼öÄ¡¸¦ 1Â÷¿øÀ¸·Î ³ª¿­ÇÏ°í, ±×°ÍÀ» ¿°»öü·Î Ãë±ÞÇÑ´Ù. ±×¸®°í 1Â÷¿ø »ó¿¡¼­ÀÇ À§Ä¡¸¦ À¯ÀüÀÚÀÇ ÀÚ¸®·Î¼­ Ãë±ÞÇÑ´Ù. Ç¥ÇöÇüÀ» À¯ÀüÇüÀ¸·Î ¹Ù²Ù´Â °ÍÀº ÄÚµåÈ­(coding), ±× ¿ªÀ» µðÄÚµåÈ­(decoding)¶ó°í ÇÑ´Ù.

ÃÖ±Ù À¯ÀüÀÚ °øÇÐÀÇ Áøº¸¿¡ ÀÇÇØ Àΰ£ÀÇ ¿°»öüÀÇ ÇظíÀÌ ÀÌ·ç¾îÁö°í´Â ÀÖÁö¸¸, ¿°»öü°¡ °¡Áö´Â Á¤º¸·®Àº ¸Å¿ì ¸¹±â ¶§¹®¿¡ Àüü·Î º¸¸é ¾ÆÁ÷ ¸¹Àº ¹ßÀüÀÌ ÀÖ¾î¾ß ÇÒ °ÍÀÌ´Ù.

 [Ç¥ 3] »ý¹°Çаú À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¿ë¾î ºñ±³

»ý  ¹° ÇÐ

À¯ÀüÀÚ ¾Ë°í¸®Áò

¿°»öü(chromosome)

¹®ÀÚ¿­(string)

À¯ÀüÀÚ(gene)

Ư¼º(feature), ÇüÁú(character)

´ë¸³ À¯ÀüÀÚ(allele)

Ư¼ºÄ¡(feature value)

À¯ÀüÀÚ ÀÚ¸®(locus)

¹®ÀÚ¿­ÀÇ À§Ä¡(string position)

À¯ÀüÇü(genotype)

±¸Á¶Ã¼(structure)

Ç¥ÇöÇü(phenotype)

ÆĶó¸ÞÅÍ ÁýÇÕ(parameter set)

 

´ëüÇØ(alternative solution)
µðÄÚµåÈ­¸¦ À§ÇÑ ±¸Á¶Ã¼(a decoded structure)

 

Àΰ£ÀÇ 3°¡Áö ±â¾ï ½Ã½ºÅÛ

Áö±¸»ó¿¡¼­ °¡Àå °íµµ·Î ÁøÈ­ÇÑ »ý¹°ÀÎ Àΰ£Àº ´ÙÀ½ÀÇ 3°¡Áö ±â¾ï ½Ã½ºÅÛÀ» °¡Áø´Ù°í ¸» ÇÒ ¼ö ÀÖ´Ù.

¨ç À¯Àü¿¡ ÀÇÇÑ ±â¾ï
¨è ³ú¿¡ ÀÇÇÑ ±â¾ï
¨é ¿ÜºÎ ±â¾ï¿¡ ÀÇÇÑ ±â¾ï(¹®ÀÚÀÇ ÀÌ¿ë)

À̵é Áß¿¡¼­ ¹®ÀÚ¸¦ ÀÌ¿ëÇÑ ±â¾ïÀº À¯ÀüÀ̳ª ³ú¿¡ ÀÇÇÑ ±â¾ï°ú´Â ´Ù¸£°í, Àΰ£ÀÇ °³Ã¼¿Ü¿¡ Á¸ÀçÇÏ´Â Àηù ƯÀ¯ÀÇ ±â¾ï ¹æ¹ýÀÌ´Ù. ¹®ÀÚ´Â Àηù ÃÖ´ëÀÇ ¹ß¸íÀÌ°í, ÀÌ°Í¿¡ ÀÇÇØ ¹®È­³ª ±â¼úÀ» ³ÐÈ÷°í, Èļ¼¿¡ ³²±â´Â °ÍÀÌ ¿ëÀÌÇÏ°Ô µÇ¾ú´Ù. °á±¹ °ø°£Àû, ½Ã°£ÀûÀ¸·Î ½±°Ô ³ÐÈú ¼ö ÀÖ°Ô µÇ¾ú´Ù. ÀÌ¿Í°°ÀÌ Àηù´Â ¹®ÀÚ¿¡ ÀÇÇØ °úÇаú ÀÇÇÐ, »çȸ ½Ã½ºÅÛ, ´Ù¾çÇÑ ±â¼ú µîÀ» ¹ß´Þ ½Ãų ¼ö°¡ ÀÖ°í, ȯ°æÀ¸·ÎÀÇ ÀûÀÀµµ¸¦ ³ôÀÎ´Ù°í ¸»ÇÒ ¼ö ÀÖ´Ù. ÃÖ±Ù¿¡´Â ¸ÖƼ¹Ìµð¾îÀÇ º¸±Þ¿¡ ÀÇÇØ È­»óÁ¤º¸³ª À½¼ºÁ¤º¸µµ ¸¶Âù°¡Áö ¿ªÇÒÀ» ´ã´çÇÏ°í ÀÖ´Ù.

 

À¯Àü¿¡ ÀÇÇÑ ±â¾ï°ú ³ú¿¡ ÀÇÇÑ ±â¾ï

À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº À¯ÀüÀÚ °øÇаú´Â ´Þ¸® ½ÇÁ¦ »ý¹°À» Ãë±ÞÇÏ´Â °ÍÀÌ ¾Æ´Ï¸ç À¯ÀüÀÚ¿¡ ¾î¶² Á¶ÀÛÀ» ÷°¡ÇÏ¿©µµ À§ÇèÇÏÁö ¾Ê´Ù. ¿¹¸¦µé¸é ³»·ÂÀÌ ÁÁÁö ¾ÊÀº °³Ã¼¸¦ ¹Ù·Î µµÅ½ÃÅ°°Å³ª µ¹¿¬º¯À̸¦ ¸¹ÀÌ ÇàÇصµ °ü°è´Â ¾ø´Ù.

±×·±µ¥ ½ÇÁ¦ ÀÚ¿¬°è¿¡¼­ °ú°ÝÇÑ µ¹¿¬º¯À̸¦ ¼öÇàÇÏ´Â °ÍÀº ¸Å¿ì À§ÇèÇÏ´Ù. ¸ðó·³ ¿ì¼öÇÑ Á¾ÀÌ »ý°Üµµ ¸ÓÁö ¾Ê¾Æ ¸êÁ¾µÇ°í ¸¸´Ù. »ç¶÷ÀÇ °æ¿ì¿¡µµ µ¹¿¬º¯ÀÌ¿¡¼­ ¿ì¼öÇÑ °³Ã¼°¡ ¹ß»ýÇÏ´Â °Í º¸´Ùµµ ¿°»öü ÀÌ»ó¿¡ ÀÇÇÑ º´¿¡ ¾àÇÑ °³Ã¼°¡ µÉ ¼ö ÀÖ´Â °¡´É¼ºÀÌ ³ô´Ù. µû¶ó¼­ ÀÚ¿¬°è¿¡¼­ À¯ÀüÀÚÀÇ µ¹¿¬º¯ÀÌÀÇ ºñÀ²Àº ÀÛ¾ÆÁø´Ù.

±×·¯³ª µ¹¿¬º¯ÀÌÀÇ ºñÀ²ÀÌ ÀÛ¾ÆÁ®µµ À¯ÀüÀÚ ÀüüÀÇ ¾çÀÌ ¸¹¾ÆÁø´Ù¸é ¾î¶»°Ô µÉ±î? µ¹¿¬º¯À̸¦ ÇÏ´Â À¯ÀüÀÚÀÇ ¼ö´Â ¸¹°Ô µÇ°í, ±× Á¾·ùÀÇ Á¸¼ÓÀÌ À§ÇèÇÏ°Ô µÈ´Ù.

»ç¶÷ÀÇ ³ú´Â ¼ºÀå°ú ÇÔ²² ½Å°æ¼¼Æ÷(´º·±)³¢¸®ÀÇ °áÇÕÀÌ Áõ°¡ÇØ °¡°í, ¸¹Àº °ÍÀº ÇϳªÀÇ ½Å°æ ¼¼Æ÷°¡ 20¸¸°³ÀÇ °áÇÕÀ» °¡Áö°í ÀÖ´Ù°í ÇÑ´Ù. ÀÌ·¯ÇÑ °áÇÕ Á¤º¸¸¦ ¸ðµÎ À¯ÀüÀڷμ­ ÀüÇϵµ·Ï ÇÏ¸é ¾î¶»°Ô µÉ±î? À¯ÀüÀÚ ÀüüÀÇ Á¤º¸·®Àº ¸Å¿ì ¸¹°Ô µÇ°í, µ¹¿¬º¯À̸¦ ÇÏ´Â À¯ÀüÀÚÀÇ ¼öµµ ±×°Í¿¡ µû¶ó¼­ ¸Å¿ì ¸¹¾ÆÁö°í ¸¸´Ù. ±× °á°ú ½Å°æ ¼¼Æ÷ÀÇ °áÇÕºÎÀÇ ¸¹Àº ¿À·ù°¡ »ý°Ü ¹ö¸®°í ȸº¹ ºÒ°¡´ÉÇÏ°Ô µÈ´Ù. ÀÌ°Í¿¡ ÀÇÇØ ¸¹Àº °³Ã¼´Â ¸êÁ¾ÇÏ°Ô µÈ´Ù. ½Å°æ¼¼Æ÷³¢¸®ÀÇ °áÇÕÀº ÈÄõÀûÀÎ ÇнÀ¿¡ ÀÇÇØ ÇàÇØÁöµµ·Ï µÈ °ÍÀÌ´Ù. ÀÌ°ÍÀ» "³úÀÇ °¡¼Ò¼º"À̶ó ÇÑ´Ù.

À¯ÀüÀÚ ¾Ë°í¸®Áò ÀÇ ÇÁ·Î¼¼½º

À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» óÀ½ °øºÎÇÏ´Â »ç¶÷À» À§ÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ ´ëÇÏ¿© °£´ÜÈ÷ Á¤¸®ÇÏ¸é ´ÙÀ½°ú °°´Ù. À¯ÀüÀÚ ¾Ë°í¸®Áò Àº ¾î¶² ¹üÀ§ ³»¿¡¼­ Á¤ÀǵǾî ÀÖ´Â º¯¼ö x¿¡ ´ëÇÑ ÇÔ¼ö f(x)ÀÇ ÃÖ´ëÄ¡ ȤÀº ÃÖ¼ÒÄ¡¸¦ ÁØ xÀÇ °ªÀ» °í¼ÓÀ¸·Î ±¸Çϱâ À§ÇÑ ÃÖÀûÈ­ Ž»ö ¾Ë°í¸®ÁòÀÇ ÀÏÁ¾ÀÌ´Ù. GA´Â »ý¹°ÀÇ ÁøÈ­°úÁ¤¿¡ ÈùÆ®¸¦ ¾òÀº ºñ±³Àû ´Ü¼øÇÑ ±âº» ¿ø¸®¸¦ ±âÃÊ·Î ÇÏ¿© °ÅÀÇ ´ëºÎºÐÀÇ ÃÖÀûÈ­ Ž»ö ¹®Á¦¿¡ Àû¿ë °¡´ÉÇÑ ¾Ë°í¸®ÁòÀÌ´Ù.

GA´Â À¯ÀüÀÚ¸¦ °®´Â °¡»óÀûÀÎ »ý¹°ÀÇ Áý´ÜÀ» ÄÄÇ»ÅÍ ³»¿¡ ¼³Á¤ÇÏ¿© ¹Ì¸® Á¤ÇØÁø ȯ°æ¿¡ ÀûÀÀÇÏ°í ÀÖ´Â °³Ã¼°¡ ÀÚ¼ÕÀ» ³²±æ È®·üÀÌ ³ô°Ô µÇµµ·Ï ¼¼´ë±³Ã¼ ½Ã¹Ä·¹À̼ÇÀ» ½Ç½ÃÇÏ¿© À¯ÀüÀÚ ¹× »ý¹°Áý´ÜÀ» "ÁøÈ­" ½ÃŲ´Ù. À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ±âº»ÀûÀÎ Á¶ÀÛ¿¡´Â ´ÙÀ½ÀÇ 3°¡Áö°¡ ÀÖ´Ù. À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ̶õ ÁøÈ­¿Í ±×°ÍÀ» ±¸¼ºÇÏ°í ÀÖ´Â À¯ÀüÁ¶Á÷ÀÇ Á¤º¸Ã³¸® ¸ðµ¨ÀÌ´Ù.

  ½ÇÁ¦·Î´Â [±×¸² 2]¿Í °°Àº È帧À¸·Î 󸮰¡ ¼öÇàµÈ´Ù.

[±×¸² 2] À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ È帧µµ

´Ü°è 1

 

 

 

 

À¯ÀüÀÚÇüÀÇ °áÁ¤

À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡¼­ À¯ÀüÀÚ ¿ä¼Ò´Â DNA°¡ ¾Æ´Ï¶ó ±âÈ£¿­ÀÌ´Ù. µû¶ó¼­ ¿ì¼±´ë»óÀ¸·Î ÇÏ´Â ¹®Á¦¸¦ À¯ÀüÀÚÇüÀ¸·Î Ç¥ÇöÇؾ߸¸ ÇÑ´Ù. À¯ÀüÀÚÀÇ ¾îµð¿¡ ¾î¶² ¼öÄ¡, ¹®ÀÚ¸¦ ¹è´çÇÏ¿© °¡´Â°¡¸¦ °áÁ¤ÇÏ´Â °ÍÀÌ´Ù. ¿ª½Ã "´ë»óÀ¸·Î ÇÏ´Â ¹®Á¦"·ÎºÎÅÍ "±âÈ£¿­"À̶ó°í ÇÏ´Â º¯È¯À» ¼öÇàÇÏ´Â °ÍÀÌ´Ù. ÀÌ°ÍÀ» ÄÚµùÀ̶ó°í ÇÑ´Ù. À¯°¨½º·´°Ôµµ ÀÌ ÀϹÝÀû ¹æ¹ýÀº ¾ÆÁ÷ È®¸³µÇ¾î ÀÖÁö ¾Ê°í, ¼³°èÀÚÀÇ ¼÷´ÞÀ̳ª °æÇè¿¡ ´Þ·ÁÀÖ´Ù.(GAÀÇ °úÁ¦·Î µÇ´Â »ç»óÀÇ ¸ðµ¨È­)

 

´Ü°è 2

 

 

 

 

 

Ãʱâ À¯ÀüÀÚ Áý´ÜÀÇ °áÁ¤

À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ Å« Ư¡À¸·Î ¸¹Àº °³Ã¼¿¡ ÀÇÇÑ »óÈ£ÀûÀΠ󸮸¦ µé ¼ö ÀÖ´Ù. ¿ì¼± ´Ü°è 1¿¡¼­ °áÁ¤µÈ À¯ÀüÀÚÇü¿¡¼­ ¿ä¼Ò°¡ ´Ù¸¥ ´Ù¾çÇÑ °³Ã¼¸¦ ¹ß»ý ½ÃŲ´Ù. °³Ã¼ÀÇ ¼ö´Â ¹®Á¦ÀÇ ³­À̵µ³ª ¼ºÁú¿¡ ÀÇÁ¸ÇÏÁö¸¸ ÀϹÝÀûÀ¸·Î ¼ö½Ê°³ ÀÌ»ó ¹ß»ý½ÃŲ´Ù. ³Ê¹« ÀûÀ¸¸é º´·ÄÀû 󸮸¦ Ư¡À¸·Î ÇÏ´Â À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÀåÁ¡ÀÌ ¹ßÈÖµÇÁö ¾Ê´Â´Ù. ¹Ý´ë·Î ³Ê¹« ¸¹À¸¸é ÇѼ¼´ë ´ç ¿¬»ê·®ÀÌ ¸¹¾ÆÁö±â ¶§¹®¿¡ ³¶ºñ°¡ ¸¹¾ÆÁø´Ù. À̰͵µ ¼³°èÀÚÀÇ ¼÷´Þ°ú °æÇè¿¡ ´Þ·ÁÀÖ´Ù.(°áÁ¤ÇÑ À¯ÀüÀÚÇüÀ» Áß½ÉÀ¸·ÎÇÑ ÀÏÁ¤¹üÀ§³»¿¡¼­ÀÇ º¯È­¸¦ ÀÎÁ¤ÇÑ º¹¼öÀÇ »ý¹°°³Ã¼ÀÇ »ý¼ºÃ³¸®)

 

´Ü°è 3

 

 

 

°¢ °³Ã¼ÀÇ ÀûÀÀµµÀÇ Æò°¡

Áö±ÝºÎÅÍ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÇÙ½ÉÀûÀÎ ³»¿ë¿¡ °üÇÏ¿© ¼³¸íÇÑ´Ù. À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡¼­´Â "ÀûÀÀµµ"°¡ ¸Å¿ì Áß¿äÇÑ ¿ä¼Ò°¡ µÈ´Ù. ¿©±â¼­´Â °¢ °³Ã¼ÀÇ ÀûÀÀµµ¸¦ ¹Ì¸® °áÁ¤ÇÑ ¹æ¹ýÀ¸·Î ¿¬»êÇÑ´Ù. Áý´ÜÁß¿¡ ¹Ì¸® °áÁ¤ÇÑ ±âÁØÀ» ¸¸Á·ÇÏ´Â °³Ã¼ÀÇ À¯¹«¸¦ üũÇÏ°í ÀÖÀ¸¸é Á¾·áÇÏ°í, ±×·¸Áö ¾ÊÀ¸¸é ´ÙÀ½ ´Ü°è·Î °£´Ù.(ÀûÀÀȯ°æ¿¡ °üÇÑ ÀûÀÀµµÀÇ »êÁ¤Ã³¸®)

 

´Ü°è 4

 

 

 

 

¼±   ÅÃ

´Ü°è 3¿¡¼­ °áÁ¤ÇÑ ÀûÀÀµµ¿¡ ±âÃÊÇÏ¿© ´ÙÀ½ ´Ü°è¿¡¼­ ±³¹è¸¦ ¼öÇàÇÏ´Â °³Ã¼ÀÇ »ýÁ¸ ºÐÆ÷¸¦ °áÁ¤ÇÑ´Ù. ´Ü°è 4´Â "µµÅÂó¸®"¿Í "Áß½Äó¸®" ´Ü°è·Î »ý°¢ÇÒ ¼ö ÀÖ´Ù.
? µµÅÂó¸® : °¢ °³Ã¼ÀÇ Æò°¡¿¡ ±âÃÊÇÏ¿© °¢ °³Ã¼¸¶´ÙÀÇ »èÁ¦Ã³¸®
? Áõ½Äó¸® : µµÅÂ󸮿¡ ÀÇÇØ °¨¼ÒÇÑ Áý´Ü¼ö¸¦ ·£´ý»ùÇ®¸µ¿¡ ÀÇÇØ °³Ã¼¸¦ Áõ½Ä½ÃÄÑ Áý´Ü ¼ö¸¦ Áõ°¡Çϴ ó¸®

 

´Ü°è 5

 

 

±³¹èó¸®

2°³ÀÇ ¿°»öü »çÀÌ¿¡¼­ À¯ÀüÀÚ¸¦ ¹Ù²Ù¾î ³Ö¾î »õ·Î¿î °³Ã¼¸¦ ¹ß»ý½ÃŲ´Ù.(À¯ÀüÀÚÇüÀ¸·Î¼­ Á¤ÀǵǾî ÀÖ´Â Á¤º¸¸¦ °³Ã¼»çÀÌ¿¡ ¹Ù²Ù¾î ³Ö´Â ó¸®)

 

´Ü°è 6

 

 

 

 

µ¹¿¬º¯ÀÌ Ã³¸®

À¯ÀüÀÚÀÇ ¾î¶² ºÎºÐÀÇ °ªÀ» °­Á¦ÀûÀ¸·Î ¹Ù²Ù°í, À¯ÀüÀÚ Áý´ÜÀ¸·Î¼­ÀÇ ´Ù¾ç¼º, °á±¹ Èð¾îÁüÀ» Å©°Ô ÇÑ´Ù. ÀÌ·¸°Ô ÇÔÀ¸·Î½á º¸´Ù ÁÁÀº Çظ¦ °¡Áö´Â °³Ã¼ÀÇ ¹ß»ýÀ» ±â´ëÇÏ´Â °ÍÀÌ´Ù. ¹°·Ð ÀÌ µ¹¿¬º¯ÀÌÀÇ ºñÀ²À» ³Ê¹« Å©°Ô ÇÏ¸é ³ª»Û ¹æÇâÀ¸·Î º¯ÀÌÀÇ È®·üµµ Å©°Ô µÇ°í, Çظ¦ Á»Ã³·³ ±¸ÇÒ ¼ö ¾ø°Ô µÈ´Ù.(À¯ÀüÀÚÇüÀ¸·Î¼­ Á¤ÀǵǾî ÀÖ´Â À¯ÀüÀÚÁ¤º¸ÀÇ ±âÈ£¿­À» ƯÁ¤ÀÇ È®·ü(º¯ÀÌÀ²)·Î º¯È­½ÃÅ°´Â ó¸®)

 

´Ü°è 7

 

¹Ý   º¹

´Ü°è 3À¸·Î µÇµ¹¾Æ °¡°í, °¢ °³Ã¼ÀÇ ÀûÀÀµµ¸¦ Æò°¡ÇÑ´Ù.

 

¿©·¯°¡Áö ¼±Åùý

  1.4¿¡¼­ ¼­¼úÇßµíÀÌ À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡´Â ¼±ÅÃ, ±³¹è, µ¹¿¬º¯ÀÌ 3°¡ÁöÀÇ ±âº»ÀûÀÎ Á¶ÀÛÀÌ ÀÖ´Ù. ¿©±â¿¡¼­´Â ¼±Åÿ¡ ´ëÇØ ÀÚ¼¼È÷ ¼³¸íÇÑ´Ù. ¼±ÅÃÀº Áý´Ü Áß¿¡¼­ ÀûÀÀµµÀÇ ºÐÆ÷¿¡ µû¶ó ´ÙÀ½ ´Ü°è·Î ±³¹è¸¦ ¼öÇàÇÏ´Â °³Ã¼ÀÇ »ýÁ¸ ºÐÆ÷¸¦ °áÁ¤ÇÏ´Â °ÍÀÌ´Ù. ±âº»ÀûÀÎ ¼±Åà ¹æ¹ýÀº ´ÙÀ½°ú °°À¸¸ç, À̵éÀÌ Á¶ÇÕµÇ¾î »ç¿ëµÇ´Â °Íµµ ÀÖ´Ù.

  (1) ÀûÀÀµµ ºñ·Ê ¹æ½Ä
  ¼±Åà Áß¿¡¼­µµ °¡Àå ±âº»ÀûÀÎ ¹æ½ÄÀ¸·Î, °¢ °³Ã¼ÀÇ ÀÚ¼ÕÀº ±× ÀûÀÀµµ¿¡ ºñ·ÊÇÑ È®·ü·Î ¼±ÅÃµÉ ¼ö ÀÖ´Ù. µû¶ó¼­ ÀûÀÀµµ°¡ Å« °³Ã¼Àϼö·Ï ¼±ÅõDZ⠽±°í, ´ÙÀ½ ´Ü°èÀÇ ±³¹è¿¡ Âü°¡ÇÒ ¼ö ÀÖ´Â °¡´É¼ºÀÌ ³ô¾ÆÁø´Ù.

  (2) ¿¡¸®Æ® º¸Á¸ ¹æ½Ä (elitism)
  ¿¡¸®Æ® º¸Á¸ ¹æ½ÄÀº °³Ã¼ Áß¿¡¼­ °¡Àå ÀûÀÀµµ°¡ ³ôÀº °³Ã¼´Â ±×´ë·Î ´ÙÀ½ ¼¼´ë¿¡ ³²´Â ¹æ¹ýÀÌ´Ù. ¾î¶² ¼¼´ë¿¡¼­ÀÇ °³Ã¼´Â ±³¹è³ª µ¹¿¬º¯ÀÌ¿¡ ÀÇÇÑ º¯ÇüÀ» ¹ÞÁö ¾Ê°í ´ÙÀ½ ¼¼´ë¿¡ Àü´ÞµÈ´Ù. ±×·¯³ª °æ¿ì¿¡ µû¶ó¼­ ¿ø·¡´Â ¾ÆÁÖ ÁúÀÌ ÁÁÁö ¾ÊÀº À¯ÀüÀÚ°¡ Áý´Ü Áß¿¡ ³Î¸® ÆÛÁ® ¹ö¸± À§Ç輺ÀÌ ÀÖ´Ù. ±× ¶§¹®¿¡ ´Ù¸¥ ¹æ½Ä, ¿¹¸¦ µé¸é ´ÙÀ½¿¡ ¼³¸íÇÏ´Â ±â´ëÄ¡ ¹æ½Ä µî°ú Á¶ÇÕÇÏ¿© »ç¿ëÇÒ ¼ö ÀÖ´Ù.

  (3) ±â´ëÄ¡ ¹æ½Ä
  (1)ÀÇ ÀûÀÀµµ ºñ·Ê ¹æ½ÄÀº ÀûÀÀµµ·Î ºÎÅÍ ±¸ÇØÁø È®·ü¿¡ ±âÃÊÇÏ´Â ¼±Åà ¹æ½ÄÀ̾ú´Ù. ÀÌ °æ¿ì ¸¸ÀÏ °³Ã¼¼ö°¡ ÀûÀ¸¸é ¼±ÅÃµÈ °³Ã¼ ºÐÆ÷°¡ ¿øÇÏ´Â ºÐÆ÷·ÎºÎÅÍ Å©°Ô ¸Ö¾îÁ® ¹ö¸± °¡´É¼ºÀÌ ÀÖ´Ù. ¿¹¸¦ µé¸é ÁÖ»çÀ§¸¦ 6ȸ ´øÁ® º¸´Ùµµ 1ºÎÅÍ 6±îÁöÀÇ ´«±ÝÀÌ ¸ðµÎ 1ȸ¾¿ ³ª¿Â´Ù´Â °ÍÀº Á»Ã³·³ ¹ß»ýÇÏÁö ¾ÊÀ» °ÍÀÌ´Ù. ±â´ëÄ¡ ¹æ½Ä¿¡¼­´Â ÀûÀÀµµÀÇ ºÐÆ÷¿¡ ±âÃÊÇÏ¿© °¢ °³Ã¼°¡ ¼±ÅÃµÉ ±â´ëÄ¡(°³¼ö)¸¦ °è»êÇÑ´Ù. ±×¸®°í ¾î¶² °³Ã¼°¡ ¼±ÅÃµÉ ¶§¿¡ ±× °³Ã¼ÀÇ ±â´ëÄ¡¸¦ ÀÛ°ÔÇÏ¿© °¡´Â °ÍÀÌ´Ù. ÀÌ·¸°Ô ÇÏ´Â °Í¿¡ ÀÇÇØ ¼±ÅÃµÈ °³Ã¼´Â ¼±ÅõDZ⠾î·Æ°í, ÀûÀÀµµ ºñ·Ê ¹æ½Ä¿¡¼­ÀÇ È®·ü¿¡ ÀÇÇÑ ¿ÀÂ÷¸¦ °¡´ÉÇÑÇÑ ÀÛ°Ô ÇÒ ¼ö ÀÖ´Ù.

  (4) ¼øÀ§(Rank) ¹æ½Ä
  ¼øÀ§ ¹æ½Ä¿¡¼­´Â ¹Ì¸® ¼øÀ§¿Í ¼±ÅÃÇÒ °³Ã¼¼ö¿ÍÀÇ °ü°è¸¦ °áÁ¤ÇØ µÐ´Ù. ±×¸®°í °¢ °³Ã¼¸¦ ÀûÀÀµµ ¼øÀ¸·Î ³ª¿­ÇÏ°í, ¼±ÅÃÇÒ °³Ã¼¸¦ °áÁ¤ÇØ °¡´Â °ÍÀÌ´Ù. ÀûÀÀµµÀÇ ´ë¼Ò°ü°è¸¸ÀÌ °í·ÁµÇ±â ¶§¹®¿¡ ÀûÀÀµµ ±× ÀÚüÀÇ °ªÀº ¹«½ÃµÈ´Ù.

  (5) Åä³Ê¸ÕÆ® ¹æ½Ä
  Åä³Ê¸ÕÆ® ¹æ½ÄÀº Áý´Ü Áß¿¡ °áÁ¤µÈ ¼ö(½ÇÁ¦·Î´Â 2°³ÀÎ °æ¿ì°¡ ¸¹´Ù)ÀÇ °³Ã¼¸¦ ¹«ÀÛÀ§·Î ¼±ÅÃÇÑ´Ù. ±×µé Áß¿¡¼­ °¡Àå ÀûÀÀµµ°¡ ³ôÀº °³Ã¼¸¦ ¼±ÅÃÇÏ´Â °ÍÀ¸·Î ÀÌ·¯ÇÑ Á¶ÀÛÀ» ÇÊ¿äÇÑ È½¼ö¸¸Å­ ¹Ýº¹ÇÑ´Ù.
 

 

½ºÄÉÀϸµ

¾ÕÀý¿¡¼­ ¼³¸íÇÑ ¼±ÅÃÀº ±³¹è¸¦ ÇàÇÒ ¶§ÀÇ »ýÁ¸ ºÐÆ÷¸¦ Áý´Ü Áß¿¡¼­ ÀûÀÀµµÀÇ ºÐÆ÷¿¡ µû¶ó °áÁ¤ÇÏ´Â °ÍÀ̾ú´Ù. ±×·±µ¥ ƯÈ÷ Ãʱ⠼¼´ë¿¡ À־ ÇØ¿¡ ¾î´À Á¤µµ °¡±õ´Ù¸é Çطμ­´Â ¾ÆÁ÷ ºÒÃæºÐÇÑ ÀûÀÀµµ¸¦ °¡Áö´Â À¯ÀüÀÚ°¡ Áý´ÜÁß¿¡ ÆÛÁ® ¹ö¸®°Ô µÇ´Â °æ¿ì°¡ ÀÖ´Ù. ¸¶Ä¡ "¿ì¹°¾ÈÀÇ °³±¸¸®"¿Í °°Àº °ÍÀÌ Áý´Ü Áß¿¡¼­ ÀϾ°í ÀÖ´Â »óÅÂÀÌ´Ù. ÀÌ·¸°Ô µÇ¸é º¸´Ù ÀûÀÀµµ°¡ ³ôÀº À¯ÀüÀÚ¸¦ Ž»öÇÏ´Â °ÍÀÌ ¾î·Á¿öÁ® °£´Ù. ÀÌ·¯ÇÑ Çö»óÀ» ¹æÁöÇϱâ À§Çؼ­ °í¾ÈµÈ °ÍÀÌ ½ºÄÉÀϸµ(Scaling)ÀÌ´Ù. ½ºÄÉÀϸµÀº ÀûÀÀµµÀÇ °ªÀ» ¼±Åÿ¡ Á÷Á¢ ¹Ý¿µ½ÃÅ°´Â °ÍÀÌ ¾Æ´Ï¶ó ÇÔ¼ö¸¦ ÀÌ¿ëÇÏ¿© º¯È¯ÇÑ ÈÄ¿¡ ¼±Åÿ¡ ¹Ý¿µ½ÃÅ°·Á°í ÇÏ´Â °ÍÀÌ´Ù. µû¶ó¼­ ÀûÀÀµµÀÇ Â÷ÀÌ°¡ È®´ë ȤÀº Ãà¼ÒµÇ°Ô µÈ´Ù.

½ºÄÉÀϸµ¿¡ ÀÌ¿ëµÇ´Â ÇÔ¼ö·Î¼­ [Ç¥ 3]°ú °°Àº ÇÔ¼ö°¡ Áö±Ý±îÁö Á¦¾ÈµÇ¾ú´Ù. [Ç¥ 3]¿¡¼­ f´Â ½ºÄÉÀϸµ Àü¿¡ ÀûÀÀµµÀÇ °ªÀ», f'´Â ½ºÄÉÀϸµ ÈÄÀÇ ÀûÀÀµµÀÇ °ªÀ» º¸¿©ÁÖ°í ÀÖ´Ù. ½Ã±×¸¶ Àý´Ü¿¡¼­ ÀÌ¿ëµÇ´Â ´Â Áý´ÜÀÇ Ç¥ÁØ ÆíÂ÷ÀÌ´Ù. ¼±Çü ½ºÄÉÀϸµÀº 1Â÷ ÇÔ¼ö°¡ »ç¿ëµÇ°í ¸è½Â ½ºÄÉÀϸµ¿¡¼­´Â Áö¼ö ÇÔ¼ö°¡ »ç¿ëµÇ°í ÀÖ´Ù.

 [Ç¥ 3] ½ºÄÉÀϸµ¿¡ ÀÌ¿ëµÇ´Â ÇÔ¼ö

½ºÄÉÀϸµ

ÇÔ            ¼ö

¼±Çü ½ºÄÉÀϸµ

f' = af + b

¸è½Â ½ºÄÉÀϸµ

f' = fk

½Ã±×¸¶ Àý´Ü

f' = f-(f' - c × )

¼±Çü ½ºÄÉÀϸµÀ» »ç¿ëÇÒ °æ¿ì ½ºÄÉÀϸµ ÈÄÀÇ ÀûÀÀµµÀÇ °ªÀÌ À½¼ö°¡ µÇÁö ¾Êµµ·Ï ÁÖÀÇ ÇؾßÇÑ´Ù. ¸è½Â ½ºÄÉÀϸµÀÇ °æ¿ì´Â ÀûÀÀµµ °ªÀÌ À½¼ö°¡ µÉ ¼ö ¾ø´Ù´Â °ÍÀº ¼öÇÐÀûÀ¸·Îµµ Áõ¸íµÇ¾î ÀÖ´Ù. ½Ã±×¸¶ Àý´ÜÀ¸·Î ½ºÄÉÀϸµ ÈÄÀÇ ÀûÀÀµµÀÇ °ªÀÌ À½¼ö°¡ µÉ °æ¿ì´Â °­Á¦ÀûÀ¸·Î 0À¸·Î ÇÑ´Ù.

 

À¯Àü ¿¬»êÀÚ(genetic operator)

±âº»ÀûÀÎ ¿¬»êÀÚ·Î ±³¹è(crossover)¿Í µ¹¿¬º¯ÀÌ(mutation)°¡ ÀÖÀ¸¸ç ¹®Á¦¿¡ µû¶ó ¿ªÀ§(inversion), ġȯ(displacement), Áߺ¹(duplication), Ãß°¡(addition), Á¦°Å(deletion) µîÀÇ ¿¬»êÀÚ¸¦ »ç¿ëÇÏ´Â °æ¿ìµµ ÀÖ´Ù.

 ±³  ¹è

±³¹è(crossover)´Â 2°³ÀÇ ¿°»öü »çÀÌ¿¡¼­ À¯ÀüÀÚ¸¦ ¹Ù²Ù¾î ³Ö¾î »õ·Î¿î °³Ã¼¸¦ ¹ß»ý½ÃÅ°´Â °ÍÀÌ´Ù. ¿©±â¼­ ±³¹è¿¡ ´ëÇØ Á» ´õ ÀÚ¼¼È÷ ¼³¸íÇÑ´Ù.

¾ÕÀÇ ¿¹Á¦¿¡¼­´Â °¡Àå °£´ÜÇÑ ±³¹è¹ýÀ» ÀÌ¿ëÇß´Ù. ±³¹èÇÏ´Â À§Ä¡¸¦ ÀÓÀÇ·Î °áÁ¤ÇÏ¿© ±×µéÀÇ À§Ä¡¸¦ °æ°è·Î 2°³ÀÇ ¿°»öü »çÀÌ¿¡¼­ À¯ÀüÀÚ¸¦ ±³È¯ÇÏ¿´´Ù. ±× ¿Ü¿¡´Â ´ÙÀ½°ú °°Àº ±³¹è¹ýÀÌ ÀÖ´Ù.

  (1) ´Ü¼ø±³¹è(simple crossover)
  ´ÙÀ½°ú °°ÀÌ ºÎ¸ð 1, 2°¡ ÀÖ°í ±³¹èÁ¡(crossover site)À» 3À¸·Î ÇßÀ» ¶§ »ý¼ºµÇ´Â ÀÚ½ÄÀº ÀÚ½Ä 1, 2¿Í °°ÀÌ µÈ´Ù.

[±×¸² 3] ´Ü¼ø±³¹è

   (2) º¹¼öÁ¡ ±³¹è
  Áö±Ý±îÁöÀÇ ±³¹è¹ý¿¡¼­´Â ±³¹è À§Ä¡´Â Çѱºµ¥¿´Áö¸¸ º¹¼öÁ¡ ±³¹è¿¡¼­´Â [±×¸² 4]°ú °°ÀÌ ±³¹è À§Ä¡°¡ º¹¼ö°³ÀÌ°í, ±×µéÀÇ À§Ä¡¸¦ °æ°è·Î À¯ÀüÀÚÀÇ ±³È¯ÀÌ ÇàÇØÁø´Ù. 

±³¹èÁ¡ÀÌ º¹¼ö °³(ÀÌ °æ¿ì´Â 2±ºµ¥)°¡ ÀÖ°í ±×µéÀÇ À§Ä¡¸¦ °æ°è·Î À¯ÀüÀÚ¸¦ ±³È¯ÇÑ´Ù.

[±×¸² 4] º¹¼öÁ¡ ±³¹è

  (3) ÀÏ¾ç ±³¹è(uniform crossover)
  ÀÏ¾ç ±³¹è´Â º¹¼öÁ¡ ±³¹èÀÇ ÀÏÁ¾À¸·Î »ý°¢ÇÒ ¼ö ÀÖ´Ù. ¿ì¼± [±×¸² 5]¿Í °°Àº ¸¶½ºÅ©(±³¹è À§Ä¡¸¦ Á¤ÇÑ Ç¥)¸¦ ÁغñÇØ µÐ´Ù. ±×¸®°í ÀÚ½Ä 1¿¡ ´ëÇØ ¸¶½ºÅ©ÀÇ °ªÀÌ 0ÀÎ ºÎºÐ¿¡´Â ºÎ¸ð 1ÀÇ °ªÀ» º¹»çÇÏ°í, ¸¶½ºÅ©ÀÇ °ªÀÌ 1ÀÎ ºÎºÐ¿¡´Â ºÎ¸ð 2ÀÇ °ªÀ» º¹»çÇÑ´Ù. ±×¸®°í ÀÚ½Ä 2¿¡ ´ëÇؼ­´Â ±× ¹Ý´ëÀÌ´Ù. Áï ¸¶½ºÅ©ÀÇ °ªÀÌ 0ÀÎ ºÎºÐ¿¡´Â ºÎ¸ð 2ÀÇ °ªÀ» º¹»çÇÏ°í, ¸¶½ºÅ©ÀÇ °ªÀÌ 1ÀÎ ºÎºÐ¿¡´Â ºÎ¸ð 1ÀÇ °ªÀ» º¹»çÇÏ´Â °ÍÀÌ´Ù.

ÀÚ½Ä 1¿¡ À־´Â ¸¶½ºÅ©°¡ 0ÀÎ ºÎºÐÀº ºÎ¸ð 1À», ¸¶½ºÅ©°¡ 1ÀÎ ºÎºÐÀº ºÎ¸ð 2ÀÇ À¯ÀüÀÚ¸¦ º¹»çÇÑ´Ù. ÀÚ½Ä 2¿¡ À־´Â ¿ªÀ¸·Î ÇÑ´Ù.

[±×¸² 5] ÀÏ¾ç ±³¹è

  (4) ºÎºÐÀÏÄ¡ ±³¹è(partially matched crossover)
  º¸Åë TSP ¹®Á¦¿¡¼­ ¾Æ·¡¿Í °°ÀÌ A¿Í BÀÇ µÎ °³ÀÇ ¿°»öü(Áï, µµ½ÃÀÇ ¹æ¹®¼ø¼­)¸¦ ±³¹èÇÒ °æ¿ì 2°³ÀÇ ±³¹èÁ¡À» Àâ°í ±× »çÀÌÀÇ Áß°£ºÎºÐÀ» ÀÏÄ¡½ÃÄÑ ±³È¯ÇÑ ÈÄ ³ª¸ÓÁö ºÎºÐÀÇ ±× °á°ú¿¡ µû¶ó Áߺ¹µÇ´Â ºÎºÐÀ» ÇÇÇÏ¿© Á¶Á¤ÇÑ´Ù.

A = 9 8 4 | 5 6 7 | 1 3 2 10 ¡æ A' = 9 8 4 | 2 3 1 0 | 1 6 5 7
B = 8 7 1 | 2 3 10 | 9 5 4 6 ¡æ B' = 8 10 1 | 5 6 7 | 9 2 4 3

  (5) ¼ø¼­ ±³¹è(ordered crossover : OX)
  TSP ¹®Á¦¿¡¼­ ¼ø¼­ ±³¹èÀÇ ¿¹´Â ´ÙÀ½°ú °°´Ù.

A = 9 8 4 | 5 6 7 | 1 3 2 10
B - 8 7 1 | 2 3 10 | 9 5 4 6
¡æ B = 8 H 1 | 2 3 10 | 9 H 4 H
¡æ B = 2 3 10 | H H H | 9 4 8 1
A' = 5 6 7 | 2 3 10 | 1 9 8 4
B' = 2 3 10 | 5 6 7 | 9 4 8 1

±âŸ ¿¬»êÀÚ

  ±³¹è ¿¬»êÀÚ ÀÌ¿ÜÀÇ ±âŸ ¿¬»êÀÚ´Â ´ÙÀ½°ú °°´Ù.

  (1) µ¹¿¬º¯ÀÌ(mutation)
  °³Ã¼ÀÇ °¢ À¯ÀüÀÚÁÂÀÇ À¯ÀüÀÚ¿¡ ´ëÇÏ¿© ÀÏÁ¤ÇÑ µ¹¿¬º¯ÀÌ È®·ü(
pm)À» Àû¿ëÇÏ¿© ´ë¸³ À¯ÀüÀÚÀÇ °ªÀ¸·Î ¹Ù²Ù´Â °ÍÀÌ´Ù. °³Ã¼¿¡ ±ÙÁ¢ÇÑ »õ·Î¿î °³Ã¼¸¦ »ý¼ºÇÏ´Â ±¹¼ÒÀûÀÎ ·£´ý Ž»öÀÇ ÀÏÁ¾ÀÌ´Ù. ¶ÇÇÑ Áý´Ü¿¡¼­ ÀÒ¾î ¹ö¸° À¯ÀüÇüÁúÀ» º¹±¸ÇÏ¿© ´Ù¾ç¼ºÀ» À¯ÁöÇϱâ À§ÇÑ ¼ö´ÜÀ¸·Îµµ »ç¿ëµÈ´Ù. À̶§ ÀüÇüÀûÀÎ µ¹¿¬º¯ÀÌ È®·üÀº 0.05 ÀÌÇÏÀÌ´Ù.
´ÙÀ½Àº µ¹¿¬º¯ÀÌÀÇ Àû¿ë¿¹ÀÌ´Ù. ¼¼ ¹ø° ºñÆ®ÀÎ
a3°¡ A3·Î ¹Ù²î¾ú´Ù.

ºÎ¸ð a1 a2 a3 a4 a5 a6 a7 a8      ÀÚ½Ä a1 a2 a4 a5 a6 a7 a8      

  (2) Ä¡  È¯(displacement)
  ¿°»öüÀÇ ÀϺκÐÀ» ´Ù¸¥ ¿°»öüÀÇ ÀϺκÐÀ¸·Î ´ëÄ¡ÇÏ´Â ¹æ¹ý

  (3) ¿ª  À§(inversion)
  ºÎ¸ð  1 0 0  1  0  0  1  0        ÀÚ½Ä 1 0  0  0  1  0  1  0
             ¡è                 ¡è

  (4) Áß  º¹(duplication)
  ¿°»öü»óÀÇ ÄÚµåÀÇ ÀϺκÐÀ» Áߺ¹½ÃŲ´Ù.

  (5) Ãß  °¡(addition)
  ¿°»öü»ó¿¡ ¾î¶² ±æÀÌÀÇ ºÎºÐ ¹®ÀÚ¿­À» »ðÀÔ½ÃŲ´Ù. ÀÌ °á°ú ¿°»öüÀÇ ±æÀÌ°¡ ±æ¾îÁö°Ô µÈ´Ù.

  (6) Á¦  °Å(deletion)
  ¿°»öü»ó¿¡ ¾î¶² ±æÀÌÀÇ ºÎºÐ ¹®ÀÚ¿­À» Á¦°Å½ÃŲ´Ù. ÀÌ °á°ú ¿°»öüÀÇ ±æÀÌ°¡ ª¾ÆÁö°Ô µÈ´Ù.

À¯ÀüÀÚ ¾Ë°í¸®Áò À» ÀÌÇØÇϱâ À§ÇÑ ÀÀ¿ë ¿¹

°£´ÜÇÑ ¿¹Á¦¸¦ ÀÌ¿ëÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¿ø¸®¸¦ ÀÌÇØÇϵµ·Ï ÇÑ´Ù. ¿°»öüÀÇ ±æÀÌ´Â 10ºñÆ®·Î ÇÑ´Ù. ÀûÀÀµµ¸¦ ¾ÕÀÇ 5ºñÆ®¿¡ ´ëÇؼ­´Â 0ÀÇ ¿ä¼Ò ¼ö, ³ª¸ÓÁö 5ºñÆ®¿¡ ´ëÇؼ­´Â 1ÀÇ ¿ä¼Ò ¼öÀÇ ÇÕÀ¸·Î ÇÑ´Ù. ¿¹¸¦ µé¸é 10101 11011ÀÎ À¯ÀüÀÚ¿¡¼­´Â Àü¹Ý 5ºñÆ®¿¡ 0ÀÌ 2°³, ³ª¸ÓÁö 5ºñÆ®¿¡´Â 1ÀÌ 4°³À̱⠶§¹®¿¡ ÀûÀÀµµ´Â 2+4·Î 6ÀÌ µÈ´Ù. ¹®Á¦´Â °¡´ÉÇÑÇÑ ÀûÀÀµµ°¡ Å« ¿°»öü¸¦ ¹ß°ßÇÏ´Â °ÍÀÌ´Ù. ÀÌ ¿¹´Â ¸Å¿ì °£´ÜÇϱ⠶§¹®¿¡ ÀûÀÀµµÀÇ ¿¬»ê¹ýÀ¸·ÎºÎÅÍ Çظ¦ Áï½Ã ±¸ÇÒ ¼ö ÀÖ´Ù. À¯ÀüÀÚ°¡ 0000011111À̸é ÀûÀÀµµ°¡ 10À¸·Î ÃÖ´ë°¡ µÈ´Ù. ±×·¯³ª ¸ÕÀú ÇØ´Â ¹ÌÁö¼ö·Î ÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ ÀÇÇØ Çظ¦ ¹ß°ßÇÏ°Ô µÈ´Ù. ÀÌ°ÍÀ¸·Î ÀÏ´Ü À¯ÀüÀÚÇüÀÌ °áÁ¤µÇ°í, (´Ü°è 1)ÀÌ ³¡³­´Ù.

´ÙÀ½¿¡ Ãʱâ À¯ÀüÀÚ Áý´ÜÀÇ °áÁ¤(´Ü°è 2)ÀÌ´Ù. ¿©±â¼­´Â À¯ÀüÀÚ Áý´Ü ¼ö¸¦ 6À¸·Î ÇÑ´Ù. °¢ À¯ÀüÀÚÀÇ °¢ ¿ä¼Ò´Â ÀÓÀÇ·Î °áÁ¤µÈ´Ù.

  (´Ü°è 3)¿¡¼­´Â °¢ °³Ã¼ÀÇ ÀûÀÀµµ¸¦ ±¸ÇÑ´Ù. [±×¸² 6(a)]¿¡ ÀûÀÀµµ°¡ ³ôÀº ¼ø¼­·Î ³ª¿­ÇÑ À¯ÀüÀÚ¸¦ ³ªÅ¸³½´Ù. ÇÑÆí ¼øÀ§´Â ÀûÀÀµµ°¡ °°Àº °æ¿ì¿¡ À§ÂÊÀ» ³ôÀº ¼ø¼­·Î¼­ ¹øÈ£¸¦ ºÙÀδÙ.

  (´Ü°è 4)´Â ¼±Åà ´Ü°èÀÌ´Ù. ¿©±â¼­´Â °£´ÜÇϱ⠶§¹®¿¡ ¿¡¸®Æ® º¸Á¸ ¼±ÅùýÀ» ´Ü¼øÈ­½ÃŲ °ÍÀ» ÀÌ¿ëÇϱâ·Î ÇÑ´Ù. ¿¡¸®Æ® º¸Á¸ ¼±ÅùýÀ̶õ ÀûÀÀµµ°¡ Á¦ÀÏ ³·Àº °³Ã¼¸¦ ÀûÀÀµµ°¡ Á¦ÀÏ ³ôÀº °³Ã¼·Î ġȯÇÏ´Â °ÍÀÌ´Ù. ÀÌ Á¶ÀÛÀ» ¼öÇàÇÏ¿© ÀûÀÀµµ°¡ Å« ¼ø¼­·Î ³ª¿­Çϸé [±×¸² 6(b)]¿Í °°ÀÌ µÈ´Ù.

   (´Ü°è 5)ÀÇ ±³¹è¿¡¼­´Â 2°³ÀÇ À¯ÀüÀÚ¸¦ ÇÑ Á¶·Î ÇÏ¿© [±×¸² 6(c)]¿¡ ³ªÅ¸³½ ¹Ù¿Í°°ÀÌ ±³¹èÀ§Ä¡¸¦ ÀÓÀÇ·Î °áÁ¤ÇÑ´Ù. ±×°ÍÀ» °æ°è·Î À¯ÀüÀÚÀÇ ¿ä¼Ò¸¦ »óÈ£ ±³È¯ÇÏ´Â °ÍÀÌ´Ù. ¿©±â¼­ ¼øÀ§ 1ÀÇ À¯ÀüÀÚ¿Í ¼øÀ§ 6ÀÇ À¯ÀüÀÚ, ¼øÀ§ 2ÀÇ À¯ÀüÀÚ¿Í ¼øÀ§ 5ÀÇ À¯ÀüÀÚ, ¼øÀ§ 3ÀÇ À¯ÀüÀÚ¿Í ¼øÀ§ 4ÀÇ À¯ÀüÀÚ¸¦ °¢°¢ ÇÑ Á¶·Î ÇÏ¿© ±³¹è¸¦ ÇàÇϱâ·Î ÇÑ´Ù.

  (´Ü°è 6)ÀÇ µ¹¿¬º¯ÀÌ¿¡ ´ëÇؼ­ ¿ì¼± ¿©±â¿¡¼­´Â »ý·«ÇÑ´Ù.

±×·±µ¥ ¿©±â¿¡¼­ [±×¸² 6(d)]¿¡ º¸¿©ÁÖ´Â °Í°ú °°Àº Á¦ 2¼¼´ë À¯ÀüÀÚ°¡ 6°³ °®Ãß¾îÁ® ÀÖ´Ù. Á¦ 1¼¼´ë À¯ÀüÀÚ Áý´ÜÀº [±×¸² 6(a)]¿¡ º¸¿©ÁÖ´Â °Í°ú °°ÀÌ Æò±Õ ÀûÀÀµµ°¡ 5.0À¸·Î ÃÖ´ë°ªÀÌ 6ÀÌ µÇ´Âµ¥ ºñÇØ Á¦ 2¼¼´ë¿¡¼­´Â [±×¸² 6(d)]¿¡ ÀÇÇØ Æò±Õ ÀûÀÀµµ°¡ 5.3À¸·Î ÃÖ´ë°ªÀº 7·Î °¢°¢ Çâ»óµÇ´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù.

À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ÀÌ·¯ÇÑ ¼¼´ë ±³´ëÀÇ Á¶ÀÛÀ» ¹Ýº¹ÇØ °£´Ù. [±×¸² 7]¿¡ ´ÙÀ½ ¼¼´ë¿¡¼­ÀÇ ¹Ýº¹À» ³ªÅ¸³½´Ù. ±³¹èÀ§Ä¡´Â ¸Åȸ ÀÓÀÇ·Î ¼±ÅÃÇϱ⠶§¹®¿¡ [±×¸² 6]ÀÇ °æ¿ì¿Í ´Ù¸£´Ù.

               (a) µµÅÂ(Á¦1¼¼´ë) Æò±Õ ÀûÀÀµµ 5.0                      (b) Áõ½Ä(Á¦1¼¼´ë) Æò±Õ ÀûÀÀµµ 5.3

                            (c) ±³¹è(Á¦1¼¼´ë)                        (d) À¯ÀüÀÚ Áý´Ü(Á¦2¼¼´ë) Æò±Õ ÀûÀÀµµ 5.3

[±×¸² 6] À¯ÀüÀÚ ¾Ë°í¸®Áò ¿¹

  [±×¸² 6(d)]¿¡ ÀÇÇØ Á¦ 3¼¼´ë À¯ÀüÀÚ Áý´Ü¿¡¼­´Â ÃÖ´ë°ªÀº 7·Î½á Á¦ 2¼¼´ë¿Í °°Áö¸¸, Æò±Õ ÀûÀÀµµ´Â 5.8·Î Çâ»óµÈ °ÍÀ» ¾Ë ¼ö ÀÖ´Ù.
  ÀÌ·¯ÇÑ Á¶ÀÛÀ» ¹Ýº¹Çϸé ÀûÀÀµµ´Â Çâ»óµÇ¾î °¡°í, ÃÖ´ë°ªÀ» ¾òÀ» ¼ö ÀÖ´Ù(ºÒ°¡´ÉÇÑ °æ¿ìµµ ÀÖ´Ù)

              (a) µµÅÂ(Á¦2¼¼´ë) Æò±Õ ÀûÀÀµµ 5.3                            (b) Áõ½Ä(Á¦2¼¼´ë) Æò±Õ ÀûÀÀµµ 5.8

                       (c) ±³¹è(Á¦2¼¼´ë)                                     (d) À¯ÀüÀÚ Áý´Ü(Á¦3¼¼´ë) Æò±Õ ÀûÀÀµµ 5.8

[±×¸² 7] À¯ÀüÀÚ ¾Ë°í¸®Áò ¿¹([±×¸² 5.6]ÀÇ °è¼Ó)

À¯ÀüÀÚ ¾Ë°í¸®Áò ÀÇ ÀåÁ¡°ú ´ÜÁ¡

¿©±â¼­´Â À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÀåÁ¡°ú ´ÜÁ¡À» Á¤¸®ÇØ º¸±â·Î ÇÏÀÚ. ¿ì¼± À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÀåÁ¡À¸·Î¼­ ´ÙÀ½°ú °°Àº Á¡À» µé ¼ö ÀÖ´Ù.

¡á º¹¼ö °³ÀÇ °³Ã¼ »çÀÌÀÇ »óÈ£ Çù·Â¿¡ ÀÇÇÑ ÇØÀÇ Å½»ö
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº º¹¼öÀÇ °³Ã¼ »çÀÌ¿¡¼­ ¼±ÅÃÀ̳ª ±³¹è µîÀÇ À¯ÀüÀû Á¶ÀÛ¿¡ ÀÇÇؼ­ »óÈ£ Çù·ÂÀûÀ¸·Î ÇØÀÇ Å½»öÀ» ¼öÇàÇÏ°í ÀÖ´Ù. µû¶ó¼­, ´Ü¼øÇÑ º´·ÄÀû ÇØÀÇ Å½»ö°ú ºñ±³ÇÏ¿© º¸´Ù ÁÁÀº Çظ¦ ¹ß°ßÇϱ⠽±´Ù.

¡á ¹ø°Å·Î¿î ¹ÌºÐ ¿¬»ê µîÀÌ ºÒÇÊ¿ä
´º·² ³×Æ®¿öÅ©, ƯÈ÷ ¹éÇÁ·ÎÆÄ°ÔÀÌ¼Ç ¾Ë°í¸®Áò µî¿¡¼­´Â Æò°¡ ÇÔ¼öÀÇ ¹ÌºÐ°ªÀ» ÇÊ¿ä·Î ÇÏ¿´´Ù. À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡¼­´Â ÇöÀç ÀûÀÀµµ¸¦ ºÐº°ÇÒ ¼ö ÀÖÀ¸¸é µÇ±â ¶§¹®¿¡ ¾Ë°í¸®ÁòÀÌ ´Ü¼øÇÏ°í, Æò°¡ ÇÔ¼ö°¡ ºÒ¿¬¼ÓÀÎ °æ¿ì¿¡µµ Àû¿ëÀÌ °¡´ÉÇÏ´Ù.

ÇÑÆí ´ÙÀ½°ú °°Àº ¹®Á¦Á¡ÀÌ ÀÖ´Ù.

¡á ´ë»óÀ¸·Î ÇÏ´Â ¹®Á¦¸¦ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ¸·Î ÇØ°áÇϱâ À§ÇÑ ÀϹÝÀûÀÎ ¹æ¹ýÀÌ ¾ø´Ù. ƯÈ÷¹®Á¦ÀÇ À¯ÀüÀÚÇüÀ¸·ÎÀÇ Ç¥Çö(ÄÚµù)Àº ¼³°èÀÚÀÇ ¼÷´Þ·Î µÇ¾î ÀÖ´Ù.

¡á °³Ã¼¼ö, ¼±Åà ¹æ¹ýÀ̳ª ±³¹è¹ýÀÇ °áÁ¤, µ¹¿¬º¯ÀÌÀÇ ºñÀ² µî ÆĶó¹ÌÅÍÀÇ ¼ö°¡ ¸¹´Ù.