[지능형 시스템] Chapter 11. Genetics Algorithm (유전 알고리즘)

---

본 < 지능형 시스템 > 시리즈는 부산대 정보컴퓨터공학과 차의영 교수님의 '지능형 시스템' 강의에서 배운 내용을 바탕으로 작성합니다.

---

🧬 배경 및 정의

존 홀랜드가 유전학 개념을 컴퓨터로 가져오면서 유전 알고리즘이 나왔다.
유전 알고리즘은 환경으로부터의 영향을 받은 유전자(gene)와 염색체(chromosome)의 생물학적인 행위에 기반한 확률적인 탐색 기술이다.
모방한 모집단의 생성은 "평가, 선택, 재생산"의 단계를 따른다.
이진 숫자들의 문자열들이 생존을 하기 위해 경쟁하고 재생산의 과정을 거치는 것이다.

🧬 유전 용어

• Organism (유기체)
  모집단(population)이라 부르는 집합으로 집단화된 것이다.
• Generation (세대)
  평가, 선택, 재생산의 주기로 연속되는 염색체로 된 모집단이다.
• Cell (세포)
  동물의 몸에서 함께 일하는 작은 공장의 집합체이다.
• Cell nucleus (세포 핵)
  cell의 중앙부로 이 안에 유전자 정보가 있다.
• Chromosome(염색체)
  유전자로 된 생물학적인 집합을 연속된 문자열로 추상화한 것이다.
  각각은 종(species)의 특성을 가지는 문자열의 집합으로 구성된다.
• Gene(유전자)
  특정한 속성(attribute)에 일치하는 염색체의 요소다.
• Allele(대립 유전자)
  하나의 유전자를 위한 가능한 값들이다.
  유한하거나 연속된 값이다.
• Crossover(교차)
  재생산 동안 인접한 염색체가 분할될 때, 두 개의 다른 근원으로부터의 유전자를 가지는 새로운 염색체를 형성하기 위해서 인접한 염색체로부터 유전적 물질을 비틀어 재조합하는 것이다.
• Mutation(돌연변이)
  특정한 유전자를 다른 값으로 바꾸어 돌연변이 시키는 것이다.
• Elitism(엘리트주의)
  교차나 돌연변이를 하기전에 새로운 자손 모집단에 가장 좋은 염색체를 복사하는 방법이다.
  엘리트주의가 수행능력을 상당히 개선시킨다.
• Fitness Function(적합성 함수)
  특정한 solution이 다른 모든 solution들 보다 상위에 있도록 한 solution(=chromosome)의 최적성을 양자화한 것이다.
  fitness 값은 각 solution이 실제로 그 문제를 푸는데 얼마나 가까운가에 따라 각 solution에 할당된다.
  이상적인 fitness function은 목표+계산속도와 밀접하게 상관되어 있다.
  예를 들면, TSP에서는 f(x)가 solution에서의 도시들 사이의 거리의 합이며, 값이 작을수록, solution에 더 적합하다.
• Recombination(재결합)
  어떤 solution들이 보전되고, 재생산을 허용할 것이며, 어느 것이 죽어나갈 것인지 결정하는 과정이다.
  recombination operator의 첫번째 목표는 모집단에서 좋은 solution들을 강조하고, 나쁜 solution들을 제거하면서 모집단의 크기를 일정하게 유지하는 것이다.
  (1) 모집단에서 좋은 solution들을 찾는다.
  (2) 좋은 solution들의 다중 복사를 만든다.
  (3) 모집단 크기를 일정하게 유지하기 위해 나쁜 solution들을 제거한다.

• Offspring(자손)

즉, 유기체는 "유기체 ⊃ 세대 ⊃ 세포 ⊃ 세포 핵 ⊃ 염색체 ⊃ 유전자 ⊃ 대립유전자" 순으로 구성이 된다. 이때 재생산을 할 때 유전자가 교차되거나 돌연변이가 됨으로써 새로운 자손이 생긴다.

✔️ 교차

교차에 대해 조금 더 상세하게 다루어보겠다.
교차는 Single-point crossover과 Multi-point crossover이 있다.

• 📌 Single-point crossover
  º before
  1011|011101
  1001|001010
  º after
  1001|011101
  1011|001010
  ➡️ 이렇게 둘중 하나를 바꿔치기 한다.
• 📌 Multi-point crossover
  º before
  1011|011|101
  1001|001|010
  º after
  1011|001|101
  1001|011|010
  ➡️ 가운데에 있는 것을 바꿔치기 한다.

➡️ 2개의 좋은 solution의 교차가 항상 더 좋은 자손을 낳는 것은 아니다.
그러나, 부모가 좋으면 자식이 좋을 확률이 높다.

🧬 Roulette Wheel Selection (룰렛 휠 선택)

모집단에 있는 각각의 string에 대해서 그것의 fitness에 비례하게 slot을 할당하고 회전한 후 정지되었을 때 선택되는 string을 생성한다.

• solution의 수가 n이면 roulette wheel도 n번 회전시킨다.
• string의 적합도가 클수록 slot을 넓게 할당 받으며, 새로운 모집단에 나타날 기회가 더 좋아진다.

✔️ 예제

Fitness: f(x) = (-1/4)∙x^2 + 2∙x + 5

No.	Chromosome	Value	x	f(x)	%
1	0001101011	107	?	?	?
2	1111011000	984	?	?	?
3	0100000101	261	?	?	?
4	1110100000	928	?	?	?
5	1110001011	907	?	?	?

? 들을 차례대로 구해보겠다.

📌 x 구하기
Chromosome은 10자리로 이루어져있으므로 총 2의 10승개 (0부터 1023까지) 가 있다.
따라서 마지막 수 1023으로 각각의 value들을 나눈 후 곱하기 10을 한다.
1 ➡️ 107/1023 = 0.105 ➡️ 1.05
2 ➡️ 984/1023 = 0.962 ➡️ 9.62
3 ➡️ 261/1023 = 0.255 ➡️ 2.55
4 ➡️ 928/1023 = 0.907 ➡️ 9.07
5 ➡️ 907/1023 = 0.887 ➡️ 8.87

📌 f(x) 구하기
f(x) 값은 위에서 구한 x 값을 함수에 대입했을 때 나온 결과이다.
1 ➡️ 6.82
2 ➡️ 1.11
3 ➡️ 8.48
4 ➡️ 2.57
5 ➡️ 3.08

📌 % 구하기
앞서 구한 f(x)값들을 모두 더하면 22.06 이 나온다.
각각의 f(x) 값에 대해 총 f(x)값을 나누면 각각에 대한 % 값이 나온다.
1 ➡️ 31
2 ➡️ 5
3 ➡️ 38
4 ➡️ 12
5 ➡️ 14

이 퍼센트를 가지고, 룰렛 휠을 만들면 아래와 같다.

• 

🧬 유전 알고리즘

1. 첫번째 세대 G(0)을 생성한다.
2. G(0) 을 평가한다.
   내가 원하는 솔루션이 발견될 때까지 누가 좋은 유전자를 가졌는지 계속해서 다음세대를 생성하고 평가하면서 반복한다.

✔️ 임의의 적합성 (arbitrary fitness)

• odd - even + 2
• odd는 문자열에서 홀수 위치의 모든 비트들의 합이다.
• even은 짝수 위치에 있는 모든 비트의 합이다.
  🌹 ex ) 이진수 string에 대한 fitness 값과 probability를 구해본다.
  11111 ➡️ 3-2+2 = 3 ➡️ 0.3
  10111 ➡️ 3-1+2 = 4 ➡️ 0.4
  11000 ➡️ 1-1+2 = 2 ➡️ 0.2
  01011 ➡️ 1-2+2 = 1 ➡️ 0.1
  5비트에서 가장 좋은 fitness는 10101 일 때가 되겠다!

✔️ 예제

•  
• 
• 📌 규칙
  1. (Selection) 모집단에서 fitness 값이 좋은 4개를 선택한 후 순서대로 나열.
  2. (Crossover) 2개씩 짝을 짓고, 3번째와 4번째 gene의 사이에서 교차한다.
  3. (Mutation) 생겨난 자손 중 조상 세대와 같은 것이나 fitness 값이 나쁜 것은 2번과 5번 gene을 돌연변이 시킨다.
  4. (New Generation) fitness 값이 좋은 것만 모으고, 지정된 횟수만큼 진화한다.
• 여기서 size가 6인 population을 무작위로 다음과 같이 선택되었다고 가정한다.
  ➡️ 12345, 14532, 13425, 15342, 15423, 14325

이렇게 세대를 생성해갈 수 있다.