Silverback9

오늘은 Genetic Algorithm을 “unicorn” 찾기(만들기) 과정을 통해 이해해 보겠습니다~^^*

다윈의 자연선택설 Dawinian Natural Selection의 3가지 원칙을 먼저 살펴 볼까요, 우리~^^*

(1) Heredity 유전 : 프로그램의 한 개체의 정보는 그 개체의 다음 세대에도 전달됩니다.

(2) Variation 변화 변이: 세대를 거듭하면서 개체의 특성들 중에 어떤 다양성이 생겨납니다.

(3) Selection 선택: 군집 내 어떤 개체는 다음 세대를 통해 자신의 정보를 전달할 기회를 가집니다.

Darwinian Natural Selection

- Heredity : There must be a process in place by which children receive the properties of their parents.

- Variation : There must be a variety of traits present in the population or a means with which to introduce variation.

- Selection : There must be a mechanism by which some members of a population have the opportunity to be parents and pass down their genetic information and some do not. This is typically referred to as "survival of the fittest."

자 그럼, 이 세가지 원칙에 따라 “unicorn”이라는 단어를 생성해 보겠습니다~^^*

(1) Create a population of N elements with random genetic material : 무작위적인 유전 물질을 가지고 N개의 요소를 가진 군집을 만들어 봅시다. <<Variation 변이>>

function setup(){
       
      무작위적인 알파벳 조합을 통해 다양한 단어를 만들어 냅니다. 

      unijorn, pancake, aaaaaah, popcorn ,etc
}

(2) (A) Caculate the finess of N elements: 요소들의 적합성을 계산합니다. <<Selection 선택>>

function draw() {
     for () {

     우리의 목표 unicorn과의 적합도를 계산합니다. 
     unicorn과 같은 철자의 갯수를 계산해 보겠습니다.
     
     unijorn : u, n, i, o, r, n => 5
     pancake : n, c => 2
     aaaaaah : 0
     popcorn : c, o, r, n => 4
     }
}

(2) (B) Reproduction/Selection (i) Pick 2 parents: 두 요소를 짝지어 부모를 만듭니다. <<Selection 선택>>

(2)(B) Reproduction/Selection (ii) Make a new element (a) Crossover 교차를 통해 새로운 요소가 만들어 집니다. <<Heredity 유전>>

(2)(B) Reproduction/Selection (ii) Make a new element (b) Mutation 돌연변이 생성을 통해 새로운 요소가 만들어 집니다. <<Variation 변이>>

function draw() {
     .      
     .
     .
   for () {
      요소들의 적합도 수치를 부모가 될 확률로 사용합니다. 
      unijorn 50%  pancake 20%  aaaaaah 0%  popcorn  40%
      부모로 짝지어 주기 활동에 참여할 수 있는 확률입니다.
      unijorn과 popcorn이 부모가 되어 후세를 만들 경우가 많겠네요.

      새로운 요소들을 만들어 봅시다.

      부모들의 구성체를 서로 교차합니다. 
      <CrossOver> 
      uni + cake
      uni + corn 
      pan + jorn
      pan + corn    
      pop + jorn  
      pop + cake
      jorn + pan
      jorn + pop
      cake + uni
      cake + pop
      corn + uni
      corn + pan
           .
           .  
           .
     약간의 돌연변이도 더해 봅니다. 
     <<mutation>>
     1% 정도의 무작위 철자 변이성을 가미하여 새로운 요소를 살짝쿵 바꾸어 더 다양한 새로운 요소를 만들어 냅니다. 
     unicoke  enicake umicake unocake unikake unicape unicaka . . . 
     penjorn   
     joonpan  
     cakipop
         .
         .
         .  

    새로운 요소들이 탄생되었습니다. 

   }
   생성된 새로운 요소를 다시 부모로 하여 이 과정들을 반복합니다. 
   우리의 목표 "unicorn"을 찾을 때 까지~~~^^* 
}     

오늘 저와 함께 unicorn을 만들어 가는 과정을 함께 살펴봐 주셔서 감사합니다~^^*

알고리즘 정리는 오후에 덧붙여 놓도록 하겠습니다~^^*

음…생명체 한 종 한 종의 고유한 특성을 우리의 일상용품의 고유한 특성과 crossover mutation할 수 있을까요?

오늘도

점심 맛있게 드시고요!

멋진 하루 보내시고요!

내일 우리 본격 코딩을 슬슬 시작해 볼까요~~^^*

네~~^^* 꿈은 이루어 집니다~~^^*

Genetic Algorithm

SETUP

  Step 1: Initialize: Create a population of N elements, each with randomly generated DNA.

DRAW

  Step 2: Selection: Evaluate the fitness of each element of the population and build a mating pool.

  Step 3: Reproduction: Repeat N times:
       a. Pick two parents with probability accoridng to relative fitness
       b. Crossover - create a "child" by combining the DNA of these two parents
       c. Mutation - mutate the child;s DNA based on a given probability
       d. Add the new child to a new population

  Step 4: Replace the old population with the new populatio and return to Step 2.