📝 5. 돌연변이

✨ 돌연변이(Mutation) 연산이란 ?

• 자식해에 무작위 변화를 가하는 과정
• 탐색 공간의 다양성을 확보하고 지역 최적해 탈출을 유도

---

✨ 돌연변이 연산의 특징

• 낮은 확률로 무작위 변화 발생

  ▸ 일반적으로 작은 확률(예: 0.001 ~ 0.01)로 유전자 변화
  ▸ 변화는 비선택적이고 예측 불가한 방식으로 적용됨

• 탐색 공간의 다양성 확보에 기여

  ▸ 교차로 생성된 자식해에 변화를 주어 새로운 해 탐색
  ▸ 기존에 존재하지 않던 해를 만들 수 있어 전역 최적해 탐색 가능성 증가
  ▸ 일정 수준의 돌연변이는 조기 수렴 방지에 효과적

• 과도한 돌연변이의 한계

  ▸ 돌연변이 확률이 너무 높으면, 알고리즘이 무작위 탐색에 가까워져 수렴 속도 저하
  ▸ 반대로 너무 낮으면, 다양성 부족으로 인해 국소 최적해에 머무를 위험 존재

---

중요

• 돌연변이 연산은 다양성 유지와 전역 탐색 능력 확보에 필수
• 따라서 적절한 돌연변이 확률 설정과 문제 특성에 맞는 변이 방식 선택이 중요함

---

✨ 유전자 표현 방식에 따른 변이 연산 설계

• 이산(discrete) 표현 vs 연속(continuous) 표현

  ▸ 이산 표현 : 유전자는 보통 이진수(0,1) 또는 정수형 값으로 구성됨
  ▸ 연속 표현 : 유전자는 실수형 값으로 구성되어 연속적인 값 조정 가능

• 표현 방식에 따라 적합한 변이 연산이 달라짐

  ▸ 이산 표현 예시

  • Bit flip mutation : 이진 유전자를 0 ↔ 1로 반전 ([1, 0, 1] → [1, 1, 1])
  • Exchange mutation : 두 유전자 위치를 교환 ([A, B, C] → [C, B, A])
  • Shift mutation : 유전자를 한 칸씩 이동 ([A, B, C, D] → [D, A, B, C])
  • Inversion mutation : 일부 구간을 뒤집음 ([1, 2, 3, 4] → [1, 4, 3, 2])
  • Shuffle mutation : 유전자의 특정 구간을 무작위로 섞음

  ▸ 연속 표현 예시

  • Random deviation mutation : 유전자에 정규분포 기반 무작위 수치를 더함 (x = 3.2 → x = 3.2 + N(0, 1))
  • Fitness-driven mutation : 현재 적합도에 따라 변이 강도를 조절해 실수 값을 조정

• 각 표현 방식과 변이 방식의 연결

  ▸ 이산 표현은 순서, 조합, 구조 변경에 초점 - TSP(외판원 문제), 작업 순서 최적화 문제 등
  ▸ 연속 표현은 수치 조절, 정밀 탐색에 강점을 가짐 - 함수 최적화, 하이퍼파라미터 튜닝 등
  ▸ 변이 연산 선택은 문제 유형(조합/수치 최적화) 과 밀접하게 연결됨

---

✨ Random Deviation Mutation : 무작위 편차 변이

• 유전자에 평균이 0인 무작위 값을 더하여 새로운 해를 생성하는 방식의 변이

  💡 왜 평균이 0인 무작위 값일까?
  ㅤ 방향성이 없는 “순수한 무작위성(randomness)“을 주기 위해서
  ㅤ 편향되지 않은, 중립적인 변이가 생기도록 만들기 위한 선택

• 주로 실수(real number)로 표현된 유전자에 적용
• 무작위성(Randomness) 을 포함하여, 해의 다양성을 확보함

• 연산 과정

  1. 유전자에 대해 일정 확률로 변이를 적용할지 결정

     각 유전자 위치마다 확률 $p$에 따라 변이 적용 여부를 무작위로 결정

  2. 선택된 유전자에 무작위 값을 더함

     평균이 $0$, 표준편차가 $\sigma$인 정규분포에서 생성된 난수를 더함 이로 인해 유전자의 값이 연속적으로 미세하게 변화

• 특징
  • 연속적인 해 공간을 탐색하는 데 효과적
  • 작은 변화로 새로운 해를 생성하므로, 미세한 조정에 유리
  • 무작위성으로 인해 해의 다양성 유지 가능
  • 적절한 $\sigma$ 값과 확률 $p$ 조절이 중요
    → 너무 크면 해가 튀고, 너무 작으면 변화가 거의 없음

---

✨ Exchange Mutation : 교환 변이

• 두 유전자의 위치를 서로 맞바꾸는 방식의 변이
• 주로 이진(binary) 또는 순서가 중요한 유전자 표현에 적용
• 간단한 연산이지만, 큰 해 탐색 효과를 낼 수 있음

  💡 왜 단순한 교환이 효과적일까?
  ㅤ 유전자의 구성은 그대로 유지하면서 순서만 바꿔 새로운 해를 만들 수 있기 때문
  ㅤ 특히 순서 기반 문제(예 : TSP, 정렬 문제)에서 유용

• 연산 과정

  1. 두 유전자 위치를 무작위로 선택

     전체 유전자 중 두 개의 서로 다른 위치를 무작위로 고름

  2. 선택된 두 유전자의 값을 교환

     위치만 바꾸고, 값 자체는 변형하지 않음
     유전자의 총 구성은 그대로지만, 순서 변경을 통해 새로운 해 생성

• 특징
  • 간단하면서도 효과적인 탐색 기법
  • 유전자 값의 총합이나 분포가 유지되므로, 안정적인 탐색 가능
  • 순서 기반 문제에 특히 적합
  • 다른 연산(교차 등)과 함께 쓰일 때 시너지 효과

---

✨ Shift Mutation : 이동 변이

• 하나의 유전자를 선택하여, 해당 유전자를 좌우로 이동시키는 방식의 변이
• 주로 이진(binary) 또는 순서가 중요한 유전자 표현에 적용
• 하나의 유전자만 이동시키면서 나머지 유전자들의 상대 순서를 유지

• 연산 과정

  1. 무작위로 하나의 유전자 위치 선택

     전체 유전자 중 하나의 위치를 선택

  2. 무작위로 이동 방향과 거리 결정

     좌측 또는 우측으로 몇 칸 이동할지 무작위로 정함

  3. 선택된 유전자를 지정된 위치로 이동

     이동된 경로의 중간 유전자들은 한 칸씩 밀림

  
  

  • Bounded shifting (경계 제한 이동)

    유전자가 리스트의 끝을 넘어 이동하지 않도록 제한
    예: [1, 2, 3, 4, 5]에서 3을 0번 위치로 이동 → [3, 1, 2, 4, 5]

  • Unbounded shifting (경계 없는 이동) : 자료찾는중

    유전자가 리스트의 끝을 넘어 반대편으로 회전 이동 가능
    예: [1, 2, 3, 4, 5]에서 3을 0번 위치로 이동하면서 끝값이 뒤로 → [3, 2, 4, 5, 1]

• 특징
  • 단일 유전자의 위치만 바꿔, 구조를 크게 해치지 않음
  • 연결성과 순서를 유지한 채 새로운 해를 생성 가능
  • 탐색 공간을 부드럽게 이동하며 지역 최적화 탐색에 유리
  • Bounded / Unbounded 방식에 따라 다양한 탐색 가능성 확보

---

✨ Bit Flip Mutation : 비트 반전 변이

• 이진(binary) 유전자에 적용되는 가장 기본적인 변이 방식
• 무작위로 선택된 유전자의 비트를 반전(0 ↔ 1) 시킴

• 연산 과정

  1. 무작위로 하나의 유전자 위치 선택

     전체 이진 유전자 중 하나의 비트 위치를 선택

  2. 선택된 비트 반전 (0 ↔ 1)

     0이면 1로, 1이면 0으로 변경
     수학적으로는 비트 + 1 mod 2 연산으로 구현

  
  
  • 예: [1, 0, 1, 1, 0]에서 두 번째 비트(0)를 선택 → [1, 1, 1, 1, 0]

• 특징
  • 구현이 매우 간단하고 효율적
  • 탐색 공간 전체를 고르게 탐색 가능
  • 이진 표현에 특화되어 있음
  • 빠르게 새로운 해를 생성해 초기 다양성 확보에 유리

---

✨ Inversion Mutation : 구간 반전 변이

• 무작위로 선택한 연속된 구간(subrange)을 반전(reverse) 시키는 변이 방식
• 주로 이진(binary) 또는 순서가 중요한 유전자 표현에 적용

• 연산 과정

  1. 무작위로 두 개의 인덱스를 선택해 구간 설정

     하나는 시작 위치, 하나는 종료 위치

  2. 선택된 구간의 유전자 순서 반전

     해당 구간 내 유전자의 순서를 뒤집어 새로운 배열 생성

  
  
  • 예: [1, 2, 3, 4, 5]에서 인덱스 1~3 선택 → [1, 4, 3, 2, 5]
  
  

  • Bounded subrange (경계 제한 구간)

    선택된 구간이 리스트 내에서만 반전되도록 제한
    시작 인덱스 < 종료 인덱스 조건 유지
    예 : [1, 2, 3, 4, 5] → [1, 4, 3, 2, 5]

  • Unbounded subrange (경계 없는 구간)

    선택 구간이 리스트 끝을 넘어 회전 반전될 수 있음
    예: [1, 2, 3, 4, 5]에서 인덱스 3~1 선택 → [5, 4, 3, 2, 1]

• 특징
  • 순서를 보존하며 전체 구조를 변화시킴
  • 길이 제한 없는 유전자 탐색에 유리
  • 탐색 공간을 비선형적으로 이동 가능
  • Bounded / Unbounded 방식 선택에 따라 다양한 탐색 전략 구성 가능

---

✨ Shuffle Mutation : 구간 셔플 변이

• 무작위로 선택한 구간(subrange) 내의 유전자들을 섞는(셔플) 방식의 변이
• 이진(binary) 또는 순서가 중요한 유전자 표현에 적용

• 연산 과정

  1. 무작위로 두 개의 인덱스를 선택해 구간 설정

     하나는 시작 위치, 하나는 종료 위치

  2. 선택된 구간의 유전자들을 무작위로 섞음

     전체 순서를 뒤집는 것이 아닌, 구간 내에서 랜덤 순서로 재배열

  
  
  • 예: [1, 2, 3, 4, 5]에서 인덱스 1~3 선택 → [1, 4, 2, 3, 5] (섞인 결과는 무작위)
  
  

  • Bounded subrange (경계 제한 구간)

    구간이 리스트 내에서만 존재하도록 제한
    시작 인덱스 < 종료 인덱스 조건 유지

  • Unbounded subrange (경계 없는 구간)

    리스트 끝을 넘어 회전하며 구간을 설정하고 섞음
    예: [1, 2, 3, 4, 5]에서 인덱스 4~1 → [2, 1, 3, 5, 4] (섞인 결과는 무작위)

• 특징
  • 유전자의 조합을 무작위로 섞으며 다양성 증가
  • 순서를 부분적으로 변경해 탐색 공간 확장에 유리
  • 탐색 구조를 크게 해치지 않으면서 새로운 해 생성
  • Bounded / Unbounded 방식에 따라 다양한 탐색 패턴 가능

---

✨ Fitness Driven Mutation : 적합도 기반 변이

• **변이가 해를 더 좋게 만들었는지(적합도 향상 여부)**를 판단하여 적용 여부를 결정
• 여러 번의 변이를 시도한 후, 가장 좋은 결과 또는 첫 번째 긍정적 결과만 적용
• 모든 변이가 원래보다 나쁘면 변이를 적용하지 않고 원본 유지

• 연산 과정

  1. 원본 유전자에 여러 번 변이 시도

     임의의 변이 기법 사용 (예: 비트 반전, 셔플 등)

  2. 각 변이 결과의 적합도 평가

     적합도가 원본보다 높아야 적용 대상이 됨

  3. 적용 방식 선택

     • Pick first positive (첫 번째 긍정 변이 적용)

       변이들을 순차적으로 생성하고, 가장 먼저 적합도가 향상된 경우만 적용
       빠른 계산 속도 장점

     • Pick best positive (가장 적합한 변이 적용)

       모든 변이 결과 중 가장 적합도가 높은 것을 선택
       계산은 더 오래 걸리지만 개체 개선에 효과적

  
  
  • 주의 사항

    변이를 무한히 시도하는 것은 금지
    최적 개체의 경우, 모든 변이가 오히려 적합도를 떨어뜨릴 수 있음
    무한 루프에 빠지지 않도록 변이 시도 횟수는 제한해야 함

• 특징
  • 적합도 향상이 보장된 변이만 적용
  • 개체의 품질 저하를 방지하며 탐색
  • 탐색 공간의 효율적 활용 가능
  • 다양한 기존 변이 기법에 적용 가능 (ex. 비트 반전, 구간 반전 등)
  • 속도와 품질 사이의 균형을 설정할 수 있는 두 가지 전략 존재

---