💻 0. Code Flow

✨ 유전알고리즘 순서도

0️⃣ Define : 정의

• 📌 Type of Variables/Encoding : 변수 유형 및 인코딩

  유전 알고리즘에서 변수(유전자) 는 문제의 해(solution) 를 표현하는 요소

  인코딩(Encoding) 은 이러한 변수들을 GA에서 처리할 수 있는 형식(유전자형)으로 변환하는 방법을 의미

  대표적인 인코딩 방법
  ▸ 이진 인코딩(Binary Encoding) : 0과 1로 표현 (예 : 101101)
  ▸ 실수 인코딩(Real-valued Encoding) : 실수 값으로 표현 (예 : 3.25, -1.78, 5.94)
  ▸ 순열 인코딩(Permutation Encoding) : 순열로 표현 (예 : 3, 1, 4, 2)
  ▸ 문자열 인코딩(String Encoding) : 문자열 또는 기호로 표현 (예: “ABCD”,“x+y*z”)

• 📌 Fitness Function : 적합도 함수

  GA에서 적합도 함수는 각 개체(해)의 품질을 평가하는 함수

  목표는 높은 적합도를 가진 개체를 선택하여 점진적으로 더 나은 해를 찾는 것

  예시
  ▸ 회귀 문제에서는 MSE(Mean Squared Error)를 적합도 함수로 사용 가능
  ▸ 최적화 문제에서는 목적 함수(objective function)를 적합도 함수로 활용 가능

• 📌 GA Parameters : 유전 알고리즘의 주요 매개변수

  ▸ 집단 크기(Population Size)
      - 한 세대에서 유지하는 개체(해)의 수
      - 일반적으로 너무 작으면 탐색이 부족하고, 너무 크면 연산 비용이 증가함

  ▸ 변이 확률(Mutation Rate, $P_m$)
      - 유전자 돌연변이가 발생할 확률
      - 낮으면 탐색이 부족하고, 너무 높으면 무작위 탐색에 가까워질 수 있음

  ▸ 교차 확률(Crossover Rate, $P_c$)
      - 두 개체가 교차하여 새로운 개체를 생성할 확률
      - 일반적으로 높은 값(0.7~0.9)이 사용됨

  ▸ 세대 수 (Number of Generations)
      - GA가 실행될 총 세대(반복 횟수)
      - 충분한 세대가 필요하지만 너무 많으면 계산 비용이 증가할 수 있음

• 📌 Convergence Criteria : 수렴 기준

  ▸ 알고리즘을 종료할 시점을 결정하는 조건
  ▸ 일반적인 수렴 기준
      - 세대 수가 특정 값에 도달할 때
      - 적합도 값이 특정 임계값을 초과할 때
      - 개체군의 다양성이 너무 낮아질 때
      - 최근 몇 세대 동안 개선이 없을 때

---

0️⃣ Generate Initial Population : 초기 모집단(개체군) 생성

• 유전 알고리즘(GA)에서 초기 모집단(Initial Population) 은 탐색을 시작하는 첫 번째 세대를 의미
• 초기 개체군을 어떻게 생성하느냐에 따라 탐색 성능과 최적해 발견 속도가 영향을 받을 수 있음

• 📌 초기 모집단 생성 방법

  ▸ 일반적으로 무작위(random initialization) 또는 문제에 맞춘 초기화(domain-specific initialization) 방법이 사용됨

  무작위 초기화 (Random Initialization)
  ▸ 가장 일반적인 방법으로, 변수의 범위 내에서 개체를 무작위로 생성
  ▸ 다양한 해를 탐색할 수 있도록 보장하지만, 초기 해가 문제와 너무 동떨어질 수도 있음

  균등 분포 초기화 (Uniform Initialization)
  ▸ 가장 일반적인 방법으로, 변수의 범위 내에서 개체를 무작위로 생성
  ▸ 예시 : (실수 인코딩, 범위 [-5, 5]) → [4.2, -3.1, 0.8] / [-2.5, 1.9, 3.6] 와 같은 결과 생성

  문제 기반 초기화 (Heuristic or Domain-Specific Initialization)
  ▸ 문제의 특성을 고려하여 초기 해를 생성
  ▸ 예를 들어, 여행하는 외판원 문제(TSP)에서는 가능한 경로를 일부 랜덤하게 조정하여 초기 해로 사용 가능
  ▸ 최적해에 더 빨리 수렴할 수 있지만, 초기 해가 너무 유사하면 다양성이 부족해질 위험이 있음

  기존 솔루션 기반 초기화 (Seeded Initialization)
  ▸ 이미 존재하는 좋은 해(solution)를 일부 포함하여 초기 개체군을 구성
  ▸ 예를 들어, 기계 학습에서 기존 모델의 가중치를 일부 활용하여 새로운 GA를 시작할 수 있음

• 📌 초기 개체군 크기 (Population Size)

  ▸ 너무 작으면 탐색 범위가 제한되며 최적해를 찾기 어려울 수 있음
  ▸ 너무 크면 계산 비용이 증가하지만 더 다양한 해를 탐색할 수 있음
  ▸ 일반적으로 경험적으로 설정하며, 문제의 복잡성에 따라 20~1000개 정도의 개체를 사용

• 📌 초기 모집단의 역할

  ▸ GA는 집단 기반 탐색이므로 초기 모집단의 다양성이 중요함
  ▸ 초기 모집단이 특정 영역에 집중되면 지역 최적해(Local Optimum)에 빠질 위험이 커짐
  ▸ 따라서, 일반적으로 무작위 초기화 + 문제 기반 초기화를 혼합하여 사용하는 것이 효과적

---

1️⃣ Fitness Evaluation : 적합도 평가

• 각 개체(해)가 문제를 얼마나 잘 해결하는지 평가
• 유전 알고리즘은 적합도(Fitness)를 기준으로 더 좋은 해를 선택하여 진화하기 때문에, 적합도 평가가 없으면 어떤 개체가 좋은지 판단할 수 없음

1️⃣ Convergence Check : 수렴 검사

• GA는 특정 조건에서 조기에 종료될 수도 있음
• 초기 모집단이 이미 최적해를 포함하고 있다면 불필요한 반복을 줄이기 위해 종료하는 것이 효율적

2️⃣ Selection : 선택 연산

• 유전 알고리즘(GA)에서 다음 세대를 생성할 부모 개체를 결정하는 과정
• 적합도가 높은 개체를 더 많이 선택하여 진화의 방향을 최적해로 유도
• 탐색 공간의 다양성을 유지하여 국소 최적해(Local Optimum)에 빠지는 것을 방지
• 개체군이 점진적으로 발전하도록 유전 알고리즘의 흐름을 조절
• 다양한 선택 연산 방법

3️⃣ Crossover : 교차 연산

• 선택된 부모 개체들의 유전 정보를 조합하여 새로운 자식 개체를 생성하는 과정
• 기존 개체들의 특성을 물려받으면서도 새로운 해를 탐색할 수 있도록 함
• 다양한 교차 방식(단일 지점 교차, 다중 지점 교차, 균등 교차 등)을 적용할 수 있음
• 적절한 교차 연산을 사용하면 탐색 능력을 향상시키고 해의 질을 높일 수 있음

4️⃣ Mutation : 돌연변이 연산

• 개체의 일부 유전자를 확률적으로 변경하여 다양성을 유지하는 과정
• 새로운 탐색 공간을 열어 국소 최적해(Local Optimum)에서 탈출할 가능성을 높임
• 돌연변이 확률이 너무 높으면 무작위 탐색에 가까워지고, 너무 낮으면 다양성이 부족해질 수 있음
• 다양한 돌연변이 기법(비트 플립, 스왑 변이, 역순 변이 등)을 활용 가능

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

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

🔁 1~5 과정 반복

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