📝 2. 유전알고리즘의 기초

✨ 용어 정리

  🧬 개체(Individual)

• 유전알고리즘에서의 의미 : 하나의 후보 해(Candidate solution)
• 예시

  ▸ 이진수 표현 : 101101
  ▸ 실수 표현 : (3.4, 2.1, -1.7)
  ▸ 순열 표현(여행자 문제) : (2 → 5 → 3 → 1 → 4)
  ▸ 경로 표현(최단 경로 문제) : A → B → C → D → E

  🧬 염색체(Chromosome)

• 생물학적 의미 : 유전 물질을 담고 있는 하나의 집합

• 유전알고리즘에서의 의미 : 하나의 후보 해를 표현하는 구조 (변수들의 조합)

• 예시

  ▸ 이진수 표현 : [1,0,1,1,0,1]
  ▸ 실수 표현 : [3.4, 2.1, -1.7]
  ▸ 순열 표현(여행자 문제) : [2, 5, 3, 1, 4]
  ▸ 경로 표현(최단 경로 문제) : [A, B, C, D, E]

• 💡 염색체를 주로 리스트로 표현하는 이유

  1. 연산이 용이함 → 리스트는 인덱싱이 가능하여 교차(crossover), 돌연변이(mutation) 연산이 쉬움
  2. 유전자 조작이 편리함 → 리스트 내 개별 요소(유전자)를 수정하거나 교체하기 좋다
  3. 일관된 표현 가능 → 이진수, 실수, 순열 등 다양한 형태의 표현을 동일한 방식으로 다룰 수 있다

  🧬 유전자 (Gene)

• 염색체를 구성하는 요소 (개별 변수 값)
• 염색체 내에서 특정한 위치(Locus)를 차지하며, 문제를 구성하는 변수(Parameter)와 연관됨.
• 예시

  ▸ 염색체 [A, B, C]에서 개별 요소 A, B, C가 유전자
  ▸ 이진수 염색체 [1,0,1,1,0,1]에서 개별 숫자(0 또는 1)가 유전자
  ▸ 좌표를 표현하는 실수 염색체 [3.4, 2.1, -1.7]에서 개별 값이 유전자

  🧬 자손 (Offspring)

• 특정 세대(time t)에 존재했던 염색체(부모)로부터 생성된 새로운 염색체
• 교차(Crossover) 및 돌연변이(Mutation) 과정을 통해 부모와 유사한 유전 정보를 가짐
• 새로운 세대를 구성하는 염색체들이며, 적합도가 높은 해를 만들기 위한 탐색 과정의 일부

  🧬 적합도 (fitness)

• 개별 염색체(해)가 문제를 해결하는 데 얼마나 적합한지를 평가하는 값
• 적합도 함수(Fitness Function)에 의해 계산되며, 함수는 일반적으로 최대화 또는 최소화 문제로 표현됨
• 적합도가 높을수록 더 좋은 해이며, 선택 시 중요한 기준이 됨.

  🧬 유전 (Inheritance)

• 부모의 형질이 자녀에게 전달되는 현상.
• 유전 알고리즘에서는 교차(Crossover) 를 통해 부모의 유전자가 자손에게 전달됨.
• 돌연변이(Mutation)가 함께 작용하여, 일부 유전자는 변화할 수도 있음.

---

✨ 개체, 염색체, 유전자 간의 관계

• 예제 : 변수 개수가 2개인 최적화 문제
• 문제 : Minimize $f(x,y)=x^2+y^2$
• 변수 : $x,y$ (두 개의 연속형 변수)
• 목표 : $f(x,y)$를 최소화하는 $(x,y)$ 조합을 찾기

• 개체(Individual) = 하나의 후보 해(Candidate Solution)

  ▸ 개체 하나는 $(x,y)$ 값의 조합을 가짐
  ▸ 즉, “하나의 개체 = 하나의 $(x,y)$ 값”

  개체(Individual)	$(x,y)$ 값
  A	$(3.2,-8.5)$
  B	$(-6.1,2.9)$
  C	$(9.7,-1.3)$
  D	$(-2.4,5.6)$

• 염색체(Chromosome) = 개체를 표현하는 유전 정보의 집합

  ▸ 염색체는 개체의 유전 정보를 담고 있는 구조
  ▸ $x$와 $y$ 값을 저장하는 실수형 리스트(벡터) 로 표현 가능
  ▸ 개체를 표현하는 정보(즉, 변수 값들의 조합)임

  개체(Individual)	염색체(Chromosome)
  A	[3.2, -8.5]
  B	[-6.1, 2.9]
  C	[9.7, -1.3]
  D	[-2.4, 5.6]

• 유전자(Gene) = 개별 변수 값

  ▸ 유전자는 염색체를 구성하는 개별 요소
  ▸ 즉, 유전자는 변수 하나에 해당함
  ▸ $x$와 $y$가 각각 하나의 유전자 역할을 함
  ▸ 염색체 [x, y]의 각 요소 = 하나의 유전자(Gene)
  ▸ 유전자의 개수는 변수의 개수와 동일

  개체(Individual)	염색체(Chromosome)	유전자(Gene) - $x$	유전자(Gene) - $y$
  A	[3.2, -8.5]	3.2	-8.5
  B	[-6.1, 2.9]	-6.1	2.9
  C	[9.7, -1.3]	9.7	-1.3
  D	[-2.4, 5.6]	-2.4	5.6

• ✅ 최종 정리

  ✔ 개체(Individual) = 하나의 해 (하나의 $(x,y)$ 값 조합)
  ✔ 염색체(Chromosome) = 개체를 표현하는 데이터 (즉, $[x,y]$ 리스트)
  ✔ 유전자(Gene) = 염색체를 구성하는 개별 요소 (즉, 변수 값 $x$와 $y$)

---

✨ 유전 알고리즘의 Flow

  0️⃣ 초기 모집단(Initial Population) 생성

• 랜덤 또는 특정 규칙을 기반으로 초기 개체군 생성.

  1️⃣ 적합도 평가 (Fitness Evaluation) 및 종료 조건 확인

• 각 개체의 성능을 평가하여 적합도를 계산.
• 종료 조건(세대 수, 목표 적합도 도달 여부 등)을 확인.

  2️⃣ 부모해 선택 (Selection)

• 적합도가 높은 개체를 중심으로 다음 세대를 위한 부모 개체를 선택.

  3️⃣ 교차 (Crossover)

• 선택된 부모 해를 조합하여 새로운 개체 생성.

  4️⃣ 돌연변이 (Mutation)

• 일정 확률로 유전자 일부를 변형하여 다양성 유지.

  5️⃣ 새로운 모집단 구성 (Next Generation Population)

• 생성된 자식 해들로 새로운 개체군을 형성.

  🔁 1~5 과정 반복

• 종료 조건을 달성할 때까지 반복하여 최적해 탐색.

더 자세한 정리 : 💻 0. Code Flow

---

✨ 탐색과 활용

1. 탐색 (Exploration)

   • 정의 : 다양한 해(해결책)를 폭넓게 탐색하여, 전역 최적해(global optimum)에 도달할 가능성을 높이는 성질
   • 목적 : 지역 최적해(local optimum)에 갇히지 않기 위해 검색 공간 전체를 넓게 탐색
   • 새로운 가능성을 계속 시도하여 더 나은 해를 찾을 수 있지만, 탐색만 하면 수렴이 느려지고 좋은 해 근처로 모이지 않을 수 있음

2. 활용 (Exploitation)

   • 정의 : 현재까지 찾은 좋은 해의 정보를 집중적으로 활용하여 더 나은 해를 찾는 성질
   • 목적 : 이미 좋은 해가 있는 위치 주변을 집중적으로 탐색하여 빠르게 수렴
   • 좋은 해를 빠르게 찾을 수 있고 성능이 안정적이나, 지역 최적해에 갇힐 위험이 있음

3. 탐색과 활용의 균형

   • 유전 알고리즘에서 중요한 건 탐색과 활용의 균형 조절
   • 탐색은 멀리, 넓게 본다의 개념이고, 활용은 가까이, 깊게 본다의 개념
   • 두 요소를 잘 조절해야 유전 알고리즘이 효율적으로 전역 최적해에 수렴할 수 있음