유전 알고리즘(Genetic Algorithm)

■ 유전 알고리즘이란?
- 다윈의 유전법칙에 기반
- 자연 선택 또는 적자 생존의 원칙에 입각한 알고리즘
- 진화의 결과 : 염색체형태로 저장(DNA:C.G.A.T)
- 개체군(population)중에서 환경에 대한 적합도(fitness)가 높은 개체일수록 재생산할 수 있게 되며,
  개체군은 환경에 적응을 할 수 있게 됨


■ 유전 알고리즘의 연산자?
- 재생산(Reproduction)(재생,번식)
  -- 새로운 세대 생성시 부모 염색체의 일부를 임의로 선택하여 재조합
  -- 적합도가 높은 개체일수록 다음 세대에 자식 개체들이 번식할 가능성이 높아짐
- 돌연변이(Mutation)(변화,돌연변이,변종)
  -- 유전자의 일부를 임의로 변화
- 교배(Crossover)(염색체의 교차형)
  -- 염색체상에서 임의의 위치를 저장하여 나뉜 부분의 위치를 서로 바꿈

각각의 예를 들자면
- Reproduction
  A[■■■■■■□□]와 B[□□□□□□■■]에서 A의 앞부분과 B의 뒷부분을
  임의로(정해진 규칙에 따라) 나눠 재조합
  A[■■■■■■] + B[■■] => C[■■■■■■■■]
- Mutation
  A[■■■■■■□□]의 일부를 변화하여 D를 생성함
  A[■■■■■■□□]의 오른쪽 부분[□□]을 [■■]로 변경하여 => D[■■■■■■■■]
- Crossover
  A[■■■■■■□□]의 임의의 위치(정해진 규칙에 따라)를 저장하여 나뉘는 부분의 위치를 서로 교환함
  A[■■■■■■□□]의 앞 4자리[■■■■]과 뒤 4자리[■■□□]를 교환하여 => E[■■□□■■■■]


■ 유전 알고리즘의 예 (상대방의 숫자 알아내기)
- 문제 : 0과 1로 이루어진 6자리 수 알아내기 (결과:101001)
  -- 2^6 = 64번, 평균 32번의 추측 필요함
- 1. 임의의 답을 제시
   a) 010111
   b) 110101
   c) 100101
   d) 011011
- 2. 주어진 답이 정답인지 확인하고 아니라면 각각에 대해 적합도(fitness)가 높은 것을
  선택하고 낮은 것을 도태시킴
  -- 적합도 평가를 위해 임의의 답과 정해진 결과의 각 자리가 동일한지 검사하여 동일한 개수로 적합도를 평가함
   a) 010111 (적합도 = 1)
   b) 110101 (적합도 = 2)
   c) 100101 (적합도 = 4)
   d) 011011 (적합도 = 3)
  -- 위 결과에서 임의의 기준에 따라 적합도가 낮은 a, b는 도태시키고 적합도가 우수한 c, d가 생존함
- 3. 유전 연산자 적용
  - 적용은 임의로(혹은 정해진 규칙에 따라) 진행되나 여기서는 결과를 얻기 위한 최소 단계만을 보여줌
  - Reproduction
    c[1001][01]과 d[0110][11]을 reproduction하여 => e[1001][11]를 구함
  - Crossover
    e[1001111]를 e[1001]과 e[11]로 나누어 Crossover하여 => f[11][1001]를 구함
  - Mutation
    f[ 1 1 1 0 0 1 ]의 왼쪽에서 2번째를 변화시켜 => g[101001]
- 4. 주어진 답이 정답인 경우 멈추고 아니라면 유전 연산자를 적용함(3번 과정)


■ 유전 알고리즘 수행 절차



■ 해결 절차와 의사 코드
- 답 표현 방식, 유전연산자(재생산, 돌연변이, 교배)와 적합성 평가함수 필요함
  -- 답 표현 방식 : 적용하려는 문제를 어떻게 염색체 처럼 표기하여 처리할 수 있는가?
  -- 유전연산자 : 각 연산자를 어떻게 구현할 것인가? 혹은 다른 연산자를 추가로 구성하는가?
  -- 적합성 평가함수 : 초기에 주어진 답 혹은 유전 연산자를 적용한 답이 정답인지 어떻게 평가하는가?
- 학습효과(성능) : 문제의 표현(염색체의 구성), 사용 염색체 군의 수, 연산의 종류, 연산의 빈도수 등에 의해 결정
  -- 문제의 표현(염색체의 구성) : 위의 예에서는 0과 1로 염색체를 구성함
  -- 사용 염색체 군의 수 : 위 예에서는 6자리로 구성함
- 응용분야 : 네트워크의 최적화, 칩 설계, 게임, 시간표 작성 등
- 의사코드

procedure genetic algorithm; begin     set time t := 0;     initialize the population P(t);     while the termination condition is not met do     begin         evaluate fitness of each member of the population P(t);         select most fit members from the population P(t);         produce the offspring of these pairs using genetic operators;         replace the weakest candidates of P(t) with these offspring;         set time t := t + 1            end end

<End>

블로그 내의 관련 글

2010/09/30 - [Study/Artificial Intelligence] - Genetic Algorithm (GA; 유전 알고리즘)

2010/09/30 - [Study/Artificial Intelligence] - CSP vs BFS vs GA for N-Queen