📝 3. 선택 연산

✨ 선택(Selection) 연산이란 ?

• 현재 세대에서 다음 세대를 만들 부모해를 결정하는 과정
• 적자생존(Survival of the Fittest) 원리를 반영하여 우수한 개체가 선택될 확률을 높임

---

✨ 선택 연산의 특징

• 적합도(Fitness)에 기반한 생존 확률 분포

  ▸ 적합도가 높을수록 부모로 선택될 확률 ↑
  ▸ 반대로 적합도가 낮으면 선택되지 않을 가능성도 있음

• 우수한 개체를 선별해 다음 세대로 전달

  ▸ 선택된 개체들은 교차(Crossover)를 통해 새로운 자식해를 생성
  ▸ 하나의 개체가 여러 번 선택될 수 있음 (중복 선택 가능)
  ▸ 선택된 개체 수는 모집단 크기(n) 와 동일하게 유지됨

• 적합도만 고려한 선택의 한계

  ▸ 최고 적합도 개체만 반복 선택 시, 다양성 저하 → 전역 최적해 탐색 어려움
  ▸ 일부 개체가 과도하게 선택되면, 탐색이 국소 최적해에 수렴할 위험 증가

---

중요

• 선택 연산은 우수한 개체를 다음 세대로 전달하면서도 다양성을 유지하는 것이 핵심
• 따라서 여러 가지 선택 방식을 활용하여 적합도 기반 + 다양성 보장을 함께 고려해야 함

---

✨ 토너먼트 선택 (Tournament Selection)

• 무작위로 선택한 개체들 중에서 적합도가 가장 높은 개체를 부모로 선택하는 방식
• 무작위성(Randomness) 이 포함되어 있어, 항상 최적 개체가 선택되는 것은 아님

• 연산 과정

  1. 토너먼트에 참가할 개체를 무작위로 선택

     모집단에서 크기가 $k$인 개체 그룹을 무작위로 선정

  2. 선택된 개체들 중에서 가장 적합도가 높은 개체를 부모로 선택

     선택된 $k$개의 개체 중에서 가장 높은 적합도($f_i$) 를 가진 개체를 선택 동일한 과정으로 필요한 수의 부모 개체를 선택

• 특징
  • $k$ 값이 작으면 → 무작위성이 커져 다양한 해를 실험할 수 있음 → 탐색(Exploration)에 유리
  • $k$ 값이 크면 → 우수한 개체가 선택될 가능성이 커짐 → 활용(Exploitation)에 유리
  • 완전 무작위 선택보다는 우수한 개체를 선택할 확률이 높음
  • 항상 최상의 개체가 선택되는 것은 아니므로, 특정 개체가 여러 번 선택되지 않을 수도 있음

---

✨ 비례 선택 (Proportional selection)

• 각 개체의 적합도(Fitness)에 비례하여 선택 확률을 부여하는 방식
• 적합도가 높은 개체일수록 선택될 확률이 높아지는 구조
• 무작위성(Randomness) 이 포함되어 있어, 항상 최적 개체가 선택되는 것은 아님

• 룰렛 휠(Roulette Wheel) 방식을 통한 설명

• 연산 과정

  1. 모든 개체의 적합도(Fitness) 합을 계산

     모집단 크기가 $n$개이고, 각 개체의 적합도가 $f_i$라고 하면

     $$F_{\text{total}}=\sum _{i=1}^n{f}_i$$

     이 값이 전체 룰렛휠의 크기가 됨

  2. 각 개체의 선택 확률을 계산

     각 개체가 선택될 확률은 다음과 같이 계산됨

     $$P_i=\frac{f_i}{F_{\text{total}}}$$

     적합도가 높은 개체일수록 확률이 커짐

  3. 룰렛휠을 돌려 부모해를 선택

     $[0,F_{\text{total}}]$ 범위에서 무작위 값을 선택
     이 값이 속한 구간의 개체가 부모로 선택됨
     이 과정을 반복하여 필요한 수의 부모해를 선택

• 특징
  • 적합도가 높은 개체가 선택될 확률이 높음 → 우수한 개체가 자연스럽게 유지됨
  • 적합도가 낮은 개체도 선택될 가능성이 있음 → 탐색 다양성(Exploration) 유지 가능
  • 적합도 차이가 너무 크면 → 일부 개체가 지나치게 많이 선택됨 → 조기 수렴 위험 증가
  • 선택 연산이 확률 기반이므로 계산량이 적음 → 빠른 연산이 가능하지만, 수렴 속도 조절이 어려울 수 있음
  • 무작위성이 포함되어 있어 특정 개체가 덜 선택될 수도 있음

---

✨ 확률적 보편 샘플링 선택 (Stochastic Universal Sampling, SUS)

• 룰렛 휠 선택의 변형 방법
• 룰렛휠을 균등한 간격으로 나누어 여러 개의 부모를 동시에 선택하는 방식
• 우수한 개체가 여러 번, 평균적인 개체도 일정 비율로 선택되도록 보장

• 연산 과정

  1. 모든 개체의 적합도(Fitness) 합을 계산

     모집단 크기가 $n$개이고, 각 개체의 적합도가 $f_i$라고 하면

     $$F_{\text{total}}=\sum _{i=1}^n{f}_i$$

     이 값을 기준으로 룰렛휠을 나눔

  2. 룰렛휠을 균등한 간격으로 나누고, 무작위 시작점을 설정

     전체 룰렛휠을 모집단 크기($n$)만큼의 간격으로 나누어 $N$개의 지점을 동시에 선택
     $d=\frac{F_{\text{total}}}{n}$
     $\text{Shift}=\text{random.uniform}(0,d)$
     선택 지점 = $\text{Shift}+i\cdot d$ $(i=0,1,...,n-1)$

  3. 각 선택 지점에 해당하는 개체를 부모로 선정

     선택된 지점이 속한 개체를 부모로 선택
     적합도가 높은 개체는 여러 번 선택될 가능성이 높음

• 특징
  • 룰렛 휠 선택(Roulette Wheel Selection)의 단점을 보완
  • 적합도가 높은 개체가 많이 선택됨 → 우수한 개체를 유지
  • 평균적인 개체도 일정 비율로 선택됨 → 다양성 유지
  • 무작위성이 줄어들어 특정 개체가 과도하게 선택되는 현상 방지
  • 최적의 개체가 항상 선택된다는 보장은 없음

---

✨ 순위 방식 (Rank-Based Selection)

• 개체의 적합도 크기에 따라 순위를 매긴 후, 순위에 기반하여 선택 확률을 부여하는 방식
• 적합도 차이가 커도 선택 확률의 편중을 완화할 수 있어, 다양성 유지와 조기 수렴 방지에 효과적
• 룰렛 휠 선택보다 특정 개체가 지나치게 많이 선택되는 문제를 완화

• 연산 과정

  1. 개체 순위 지정

     모집단의 개체들을 적합도에 따라 정렬
     가장 적합한 개체가 1위, 가장 적합하지 않은 개체가 $N$위
     여기서 $N$은 개체의 총 개수

  2. 순위 간의 간격 계산

     선택 확률의 균형을 위한 간격 값

     $$\text{rank\_step}=\frac{1}{N-1}$$

  3. 순위 가중치 계산

     각 개체의 순위 가중치 ($\text{rank\_weight}$)는 다음과 같이 계산됨

     $$\text{rank\_weight}=1-(\text{rank}-1)\times \text{rank\_step}$$

     순위가 높을수록 (1위에 가까울수록) 가중치가 큼

  4. 룰렛 휠 방식으로 개체 선택

     순위 가중치를 선택 확률처럼 활용
     무작위 값을 선택해 해당 위치의 개체를 부모로 선택

• 특징
  • 적합도 차이가 커도 균형 잡힌 선택 가능 → 다양성 유지에 유리, 조기 수렴 방지
  • 적합도가 낮은 개체도 선택될 기회가 있음 → **탐색 범위 확대(Exploration)**에 도움
  • 절대적 적합도 대신 순위 사용 → 적합도 정규화 불필요
  • 최적 개체가 항상 선택되는 것은 아님 → 엘리트 보존 방식과 병행 시 보완 가능
  • 정렬이 필요해 연산량 증가 가능성 있음

---

✨ 엘리트 보존 방식 (Elitism Selection)

• 적합도가 가장 높은 개체 일부를 다음 세대로 그대로 유지하는 방식
• 우수한 해가 유실되는 것을 방지하여 최적해를 안정적으로 유지
• 랭크 선택 또는 다른 선택 방식과 병행하여 사용 가능

• 연산 과정

  1. 현재 세대에서 가장 적합도가 높은 개체를 선택

     상위 $e$개의 개체(예: 적합도 상위 5%)를 보존하여 다음 세대에서도 유지

  2. 선택된 개체를 새로운 세대로 그대로 전달

     나머지 부모 개체는 다른 선택 방법(룰렛휠, 토너먼트, 랭크 선택 등)으로 선정
     엘리트 개체가 다음 세대에서도 살아남아 진화 과정에 영향을 줌

• 특징
  • 우수한 개체가 항상 유지됨 → 최적해를 안정적으로 보존
  • 진화 속도가 빨라짐 → 유용한 유전 정보가 빠르게 전달됨
  • 조기 수렴 위험 증가 → 다양성이 줄어들어 국소 최적해(Local Optimum)에 빠질 가능성 있음
  • 다른 선택 방법과 병행하여 사용됨

    랭크 선택과 결합 시, 엘리트 개체는 유지하면서도 나머지 개체는 균형 잡힌 확률로 선택 가능
    룰렛 휠 선택과 조합하면, 적합도가 높은 개체가 더 자주 선택되는 방식으로 조절 가능

---

✨ 선택 연산 방식 비교

구분	주요 원리	우수 개체 선택	다양성 유지	무작위성	장점	단점
토너먼트 선택 (Tournament Selection)	무작위로 $k$개 선택 후 최고 적합도 개체 선택	높음 (k↑ 시)	중간 (k↓ 시 다양성↑)	있음	구현 간단, 파라미터(k)로 조절 가능	k값 설정에 따라 성능 편차
비례 선택 (Proportional / Roulette Wheel)	적합도 비율에 따라 선택 확률 부여	높음 (적합도↑ 시)	있음	많음	연산 속도 빠름	적합도 편차 클 경우 조기 수렴 가능
확률적 보편 샘플링 (Stochastic Universal Sampling, SUS)	룰렛휠을 일정 간격으로 분할하여 선택	높음	좋음	적음	다양성 유지, 편향 방지	구현이 다소 복잡
순위 선택 (Rank-Based Selection)	적합도 순위 기반으로 선택 확률 부여	중간	높음	있음	적합도 편차 영향 ↓, 조기 수렴 방지	정렬 필요, 연산량 증가
엘리트 보존 (Elitism)	최고 적합도 개체 일부를 그대로 유지	매우 높음	낮음 (단독 사용 시)	없음	최적해 보존, 빠른 수렴	다양성 저하, 국소 최적 위험
혼합 방식 (예: 랭크 + 엘리트)	두 방식 이상을 조합	조절 가능	조절 가능	조절 가능	장점 보완, 균형 조절	설계 복잡성 증가