🔠 5. Mutation

✨ 5 - Mutation 돌연변이

A mutation is a random change in genes with the aim of improving an individual’s ability to survive.
돌연변이(Mutation)는 개체의 생존 능력을 향상시키기 위한 목적을 가진 유전자의 무작위적인 변화입니다.

A mutation has no direction; it is a simple attempt at introducing a new feature that will give the future individual additional advantages.
돌연변이는 특정한 방향성이 없으며, 단지 미래의 개체에게 추가적인 이점을 줄 수 있는 새로운 특성을 도입하려는 시도일 뿐입니다.

If you look at the history of evolution, it might seem that all mutations of species were strictly directed, and were extremely successful. But this is not right.
진화의 역사를 보면 모든 돌연변이가 마치 명확한 방향성을 가지고 있었고, 매우 성공적이었던 것처럼 보일 수 있지만, 이는 사실이 아닙니다.

An unsuccessful mutation makes an individual less viable due to which it cannot leave offspring, and therefore pass on its genes.
성공하지 못한 돌연변이는 개체의 생존 가능성을 낮추어 후손을 남기지 못하게 하며, 따라서 자신의 유전자를 전달하지 못합니다.

Consequently, individuals and species with unsuccessful mutations do not exist for a long time, which means they do not leave a significant trace in the evolutionary chain.
결과적으로, 실패한 돌연변이를 가진 개체나 종은 오래 존재하지 못하고, 이는 곧 진화의 흐름에 눈에 띄는 흔적을 남기지 않는다는 것을 의미합니다.

The mechanism of mutations is the driving force of evolution; it helps species to improve, as well as to adapt to environmental conditions.
돌연변이의 메커니즘은 진화의 원동력이며, 종이 향상되고 환경 조건에 적응할 수 있도록 돕습니다.

---

✨ 5 - Structure 구조

The mechanisms of mutation are simpler than the mechanisms of selection and crossing.
돌연변이의 메커니즘은 선택과 교차의 메커니즘보다 더 단순합니다.

In this chapter, we will look at the following main ones:
이번 장에서는 다음과 같은 주요 돌연변이 방식들을 살펴봅니다:

• Random deviation mutation
  임의 편차 돌연변이
• Exchange mutation
  교환 돌연변이
• Shift mutation
  이동 돌연변이
• Bit flip mutation
  비트 반전 돌연변이
• Inversion mutation
  구간 반전 돌연변이
• Shuffle mutation
  셔플 돌연변이
• Fitness driven mutation
  적합도 기반 돌연변이

---

✨ 5 - Objectives 목표

Understand basic principles of mutation
돌연변이의 기본 원리를 이해합니다.

Introduce main mutation methods
주요 돌연변이 방법들을 소개합니다.

---

✨ 5.1 Random deviation mutation 무작위 편차 변이

Random deviation mutation is mainly applied to a real set of genes.
무작위 편차 변이는 주로 실수(real number) 집합으로 이루어진 유전자에 적용됩니다.

A random variable is added to the gene with a certain probability, usually with an average of 0. Refer to the following figure.
유전자에 일정 확률로 평균이 0인 무작위 변수를 더하는 방식입니다. 다음 그림을 참고해 주세요.

Random deviation mutation can be implemented by adding the random variable with normal distribution (average = 0 and sigma = 1).
무작위 편차 변이는 평균이 0이고 표준편차가 1인 정규분포를 따르는 난수를 더하는 방식으로 구현할 수 있습니다.

---

Import part

import copy
import random

---

Random deviation mutation

def mutation_random_deviation(ind, mu, sigma, p):
    mut = copy.deepcopy(ind)
    for i in range(len(mut)):
        if random.random() < p:
            mut[i] = mut[i] + random.gauss(mu, sigma)
    return mut

---

Example

random.seed(0)
ind = [random.uniform(0, 10) for _ in range(2)]
mut = mutation_random_deviation(ind, 0, 1, 0.3)
 
print(f'Original: {ind}')
print(f'Mutated: {mut}')

---

Result

Original: [8.444218515250482, 7.579544029403024]  
Mutated:  [8.444218515250482, 7.579544029403024]

---

✨ 5.2 Exchange mutation 교환 변이

Exchange mutation is mainly applied to a binary or ordered set of genes.
교환 변이는 주로 이진(binary) 또는 순서형(ordered) 유전자 집합에 적용됩니다.

A pair of genes are exchanged from randomly selected positions. Please refer to the following figure.
무작위로 선택된 두 위치의 유전자를 서로 교환하는 방식입니다. 다음 그림을 참고해 주세요.

In concrete implementation, we pick two random indices in the list of genes, and change their values.
구체적인 구현에서는 유전자 목록에서 두 개의 무작위 인덱스를 선택하고, 해당 위치의 값을 서로 바꿉니다.

---

Import part

import copy
import random

---

Exchange mutation

def mutation_exchange(ind):
    mut = copy.deepcopy(ind)
    pos = random.sample(range(0, len(mut)), 2)
    g1 = mut[pos[0]]
    g2 = mut[pos[1]]
    mut[pos[1]] = g1
    mut[pos[0]] = g2
    return mut

---

Example

random.seed(1)
ind = list(range(1, 7))
mut = mutation_exchange(ind)
 
print(f'Original: {ind}')
print(f'Mutated: {mut}')

---

Result

Original: [1, 2, 3, 4, 5, 6]  
Mutated:  [1, 5, 3, 4, 2, 6]

---

✨ 5.3 Shift mutation 이동 변이

Shift mutation is moving a gene from a randomly selected position by a random number of positions to the left or right.
이동 변이는 무작위로 선택된 유전자를 왼쪽 또는 오른쪽으로 무작위 개수만큼 이동시키는 방식입니다.

The content of all intermediate genes is shifted by one position.
이때 중간에 위치한 유전자들은 한 칸씩 밀려납니다.

This mutation method is applied to a binary or ordered set of genes. Refer to the following figure.
이 변이 방식은 이진 또는 순서형 유전자 집합에 적용됩니다. 다음 그림을 참고해 주세요.

There are three different approaches of shift mutation implementation:
이동 변이는 구현 방식에 따라 세 가지로 나뉩니다:

• 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]

---

Import part

import copy
import random
from math import copysign

---

Shift mutation (bounded shifting approach)

def mutation_shift(ind):
    mut = copy.deepcopy(ind)
    pos = random.sample(range(0, len(mut)), 2)
    g1 = mut[pos[0]]
    dir = int(copysign(1, pos[1] - pos[0]))
    for i in range(pos[0], pos[1], dir):
        mut[i] = mut[i + dir]
    mut[pos[1]] = g1
    return mut

---

Example

random.seed(21)
ind = list(range(1, 6))
mut = mutation_shift(ind)
 
print(f'Original: {ind}')
print(f'Mutated: {mut}')

---

Result

Original: [1, 2, 3, 4, 5]  
Mutated:  [1, 3, 4, 2, 5]

---

✨ 5.4 Bit flip mutation 비트 반전 변이

This type of mutation is applied to the binary gene set.
비트 반전 변이는 이진(binary) 유전자 집합에 적용됩니다.

Random gene is selected, and bit flipping is provoked, from 1 to 0 or from 0 to 1.
무작위로 선택된 유전자의 비트를 반전시켜 1을 0으로, 또는 0을 1로 바꾸는 방식입니다.

Let’s take a look at the following figure.
다음 그림을 참고해 주세요.

To realize this method, we pick a random gene and apply addition of 1 modulo 2.
이 방식은 무작위로 선택된 유전자에 1을 더한 후, mod 2 연산을 통해 구현됩니다.

---

Import part

import copy
import random

---

Bit flip mutation

def mutation_bit_flip(ind):
    mut = copy.deepcopy(ind)
    pos = random.randint(0, len(ind) - 1)
    g1 = mut[pos]
    mut[pos] = (g1 + 1) % 2
    return mut

---

Example

random.seed(21)
ind = [random.randint(0, 1) for _ in range(0, 5)]
mut = mutation_bit_flip(ind)
 
print(f'Original: {ind}')
print(f'Mutated: {mut}')

---

Result

Original: [1, 1, 1, 0, 0]  
Mutated:  [1, 1, 1, 1, 0]

---

✨ 5.5 Inversion mutation 역전 변이

Inversion mutation picks a random subrange and changes the order of the values in it.
역전 변이는 유전자에서 무작위로 하나의 구간을 선택하여, 해당 구간의 순서를 반전시키는 방식입니다.

This mutation method is applied to a binary or ordered set of genes.
이 변이 방식은 이진 또는 순서형 유전자 집합에 적용됩니다.

Refer to the following figure.
다음 그림을 참고해 주세요.

There are two different approaches of implementation of inversion mutation:
역전 변이 구현 방식은 다음 두 가지가 있습니다:

• Unbounded subrange:
  리스트 끝을 넘어가는 구간 선택 허용. 예: [1,2,3,4,5]에서 [3:1]을 선택하면 결과는 [5,4,3,2,1].

• Bounded subrange:
  리스트 경계를 넘지 않으며, 항상 앞 인덱스 < 뒤 인덱스를 만족하는 구간만 선택.
  아래는 bounded 방식의 구현 예시입니다.

---

Import part

import copy
import random

---

Inversion mutation

def mutation_inversion(ind):
    mut = copy.deepcopy(ind)
    temp = copy.deepcopy(ind)
    pos = sorted(random.sample(range(0, len(mut)), 2))
    for i in range(0, (pos[1] - pos[0]) + 1):
        mut[pos[0] + i] = temp[pos[1] - i]
    return mut

---

Example

random.seed(5)
ind = list(range(1, 6))
mut = mutation_inversion(ind)
 
print(f'Original: {ind}')
print(f'Mutated: {mut}')

---

Result

Original: [1, 2, 3, 4, 5]  
Mutated:  [1, 4, 3, 2, 5]

---

✨ 5.6 Shuffle mutation 셔플 변이

Shuffle mutation, like inversion mutation, picks a random subrange, but instead of changing the order of the values in it, it just shuffles the values.
셔플 변이는 역전 변이와 유사하게 무작위 구간을 선택하지만, 순서를 역전하는 대신 해당 구간의 값들을 무작위로 섞는 방식입니다.

This mutation method is applied to a binary or ordered set of genes.
이 변이 방식은 이진 또는 순서형 유전자 집합에 적용됩니다.

Refer to the following figure.
다음 그림을 참고해 주세요.

Similar to the inversion mutation, there are two different approaches of shuffle mutation:

• Unbounded subrange:
  리스트 끝을 넘어가는 구간도 허용합니다.

• Bounded subrange:
  리스트 경계를 넘지 않고, 항상 앞 인덱스 < 뒤 인덱스인 구간만을 사용합니다.
  아래는 bounded 방식의 구현 예시입니다.

---

Import part

import copy
import random

---

Shuffle mutation

def mutation_shuffle(ind):
    mut = copy.deepcopy(ind)
    pos = sorted(random.sample(range(0, len(mut)), 2))
    subrange = mut[pos[0]:pos[1] + 1]
    random.shuffle(subrange)
    mut[pos[0]:pos[1] + 1] = subrange
    return mut

---

Example

random.seed(13)
ind = list(range(1, 6))
mut = mutation_shuffle(ind)
 
print(f'Original: {ind}')
print(f'Mutated: {mut}')

---

Result

Original: [1, 2, 3, 4, 5]  
Mutated:  [1, 2, 4, 3, 5]

---

✨ 5.7 Fitness driven mutation 적합도 기반 변이

Fitness driven mutation, like the fitness driven crossover, is an approach that tries to obtain only positive changes.
적합도 기반 변이는 적합도 기반 교차와 유사하게, 오직 긍정적인 변화를 얻기 위한 방식입니다.

We run several mutations and pick the best one; if all mutations are worse than the original individual, then we leave the original without a mutation.
여러 번 변이를 수행한 뒤 가장 좋은 결과를 선택하며, 모든 변이 결과가 원래 개체보다 나쁘면 변이를 적용하지 않습니다.

Refer to the following figure.
다음 그림을 참고해 주세요.

---

NOTE: You have to make only a finite number of mutation tries.
주의: 반드시 유한한 횟수의 변이 시도만 허용해야 합니다.

It is unacceptable to make an infinite loop trying to find any positive mutation.
긍정적인 변이를 찾기 위해 무한 루프를 도는 것은 바람직하지 않습니다.

Because there can be a situation when you’re trying to mutate the best individual, and each mutation makes it worse than it is now.
예를 들어 최고 적합도의 개체를 변이시키는 경우, 오히려 성능이 저하될 수 있기 때문입니다.

Thus, your genetic algorithm will get stuck, trying to improve something that is already perfect.
이로 인해 이미 완벽한 개체를 개선하려다 알고리즘이 멈춰버릴 수 있습니다.

---

Following are the two different approaches of fitness driven mutation:
다음은 적합도 기반 변이의 두 가지 구현 방식입니다.

• Pick first positive:
  처음으로 적합도가 증가한 변이를 찾으면 그 즉시 선택하는 방식입니다.

  This approach generates mutations one by one, and stops when first positive mutation is found.
  변이를 하나씩 생성하며 처음으로 성능이 향상된 경우에 멈춥니다.

  This approach is better in terms of the algorithm speed.
  이 방식은 알고리즘 속도 측면에서 더 효율적입니다.

• Pick best positive:
  모든 변이를 생성한 후, 그 중 가장 좋은 것을 선택하는 방식입니다.

  This approach generates all mutations, then picks the best one.
  여러 개의 변이를 생성한 뒤 가장 좋은 결과를 선택합니다.

  This approach can improve population better but is worse in terms of the algorithm speed.
  인구 개선 측면에서는 더 효과적이지만, 속도는 느립니다.

---

Fitness driven mutation can be based on any other mutation technique.
적합도 기반 변이는 다른 모든 변이 기법 위에 적용될 수 있습니다.

Here we have the implementation of random deviation picking the first positive fitness driven mutation.
여기서는 무작위 편차(random deviation)를 사용한 처음 긍정 선택 방식의 구현을 소개합니다.

---

Import part

import copy
import random
from math import sin
from typing import List

---

Fitness function

def func(x):
    return sin(x) - 0.2 * abs(x)

---

Individual

class Individual:
    def __init__(self, gene_list: List[float]) -> None:
        self.gene_list = gene_list
        self.fitness = func(self.gene_list[0])
 
    def __str__(self):
        return f'x: {self.gene_list[0]}, fitness: {self.fitness}'

---

Fitness driven random deviation mutation (pick first positive)

def mutation_fitness_driven_random_deviation(ind, mu, sigma, p, max_tries=3):
    for t in range(max_tries):
        mut_genes = copy.deepcopy(ind.gene_list)
        for i in range(len(mut_genes)):
            if random.random() < p:
                mut_genes[i] = mut_genes[i] + random.gauss(mu, sigma)
        mut = Individual(mut_genes)
        if ind.fitness < mut.fitness:
            return mut
    return ind

---

Example

random.seed(14)
ind = Individual([random.uniform(-10, 10)])
mut = mutation_fitness_driven_random_deviation(ind, 0, 1, 0.3)
 
print(f'Original: ({ind})')
print(f'Mutated: ({mut})')

---

Result

Original: (x: -6.228264870789683, fitness: -0.5436606638121143)
Mutated:  (x: -6.563361314086153, fitness: -0.5795202996943434)

---

✨ Conclusion 결론

Just as in nature, in computational problems, the mutation is usually more important than crossing.
자연에서 그렇듯, 계산 문제에서도 변이는 교차보다 더 중요한 역할을 합니다.

Yes, it is possible to construct successive GA algorithm architecture without crossing, but with a mutation.
실제로 변이만 사용하고 교차 없이도 유전 알고리즘 구조를 구성할 수 있습니다.

But architecture without mutation is impossible in principle.
하지만 변이 없이 구성된 구조는 원칙적으로 불가능합니다.

In the wild, some species reproduce themselves by simple cloning with mutation, and this approach ensures their development and survival.
자연계에서는 일부 종들이 단순 복제와 변이만으로 번식하며, 이는 진화와 생존을 가능하게 합니다.

And so, we ended up with the basic operations performed by the GA.
이로써 유전 알고리즘에서 수행되는 기본 연산들을 살펴보았습니다.

In the next chapter, we will look at how you can compare and evaluate different genetic operations with each other so that you can choose the best architecture of the GA for a specific problem.
다음 장에서는 다양한 유전 연산들을 어떻게 비교하고 평가할 수 있는지, 그리고 특정 문제에 가장 적합한 구조를 선택하는 방법에 대해 다룰 예정입니다.

---

✨ Points to remember 꼭 기억할 점

Mutation has to add light changes to individual genes.
변이는 개별 유전자에 가벼운 변화를 주어야 합니다.

The mutation which changes genes drastically is very dangerous, and can ruin all positive experience which was accumulated by an individual, and even the whole population.
유전자를 과도하게 변화시키는 변이는 매우 위험하며, 개체가 축적한 긍정적인 특성은 물론, 전체 개체군을 망칠 수 있습니다.

There is no predetermined list of mutation methods.
변이 방식은 미리 정해진 목록이 존재하지 않습니다.

You can implement your own mutation method for specific task.
특정 작업에 맞춰 자신만의 변이 방식을 구현할 수 있습니다.

Mutation is absolutely random process, and there is no guarantee that the mutation will improve an individual.
변이는 본질적으로 무작위적인 과정이며, 그것이 개체를 향상시킬 것이라는 보장은 없습니다.

---

✨ 5 - Multiple choice questions 객관식 문제

Question 1
In population, we have the best individual and this individual is very valuable to us.
개체군 내에 가장 뛰어난 개체가 있으며, 이 개체는 매우 소중합니다.

We want to save it or get an improved version in the next generation. What GA architecture should we choose?
우리는 이 개체를 다음 세대에도 유지하거나 더 나은 버전으로 발전시키고자 합니다. 어떤 유전 알고리즘 구조를 선택해야 할까요?

• Rank selection, uniform crossover, fitness driven mutation
  랭크 선택, 균등 교차, 적합도 기반 변이

• Elite selection, fitness driven crossover, fitness driven mutation
  엘리트 선택, 적합도 기반 교차, 적합도 기반 변이

• ✅ Elite selection, one-point crossover, fitness driven mutation
  ✅ 엘리트 선택, 단일 지점 교차, 적합도 기반 변이

Question 2
We have the following gene set (0,1,1,0) and fitness function (b₁,b₂,b₃,b₄) = b₁ + b₂ + b₃ + b₄, i.e., fitness(0,1,1,0) = 2.
유전자 집합 (0,1,1,0)과 적합도 함수 (b₁,b₂,b₃,b₄) = b₁ + b₂ + b₃ + b₄, 즉 fitness(0,1,1,0) = 2 가 주어졌습니다.

We apply bit flip mutation to individual (0,1,1,0). What fitness function of mutated individual can be?
개체 (0,1,1,0)에 비트 반전 변이를 적용할 때, 변이된 개체의 적합도는 어떻게 될 수 있을까요?

• ✅ 1 with 50% probability, 3 with 50% probability
  ✅ 1일 확률 50%, 3일 확률 50%

• 1 with 90% probability, 3 with 10% probability
  1일 확률 90%, 3일 확률 10%

• 1 with 25% probability, 2 with 50% probability, 3 with 25% probability
  1일 확률 25%, 2일 확률 50%, 3일 확률 25%

---

✨ 4 - Questions 질문

1. In random deviation mutation, we pick random variable with average = 0. Why is it unacceptable to pick random variable with average = 1?
랜덤 편차 변이에서 평균이 0인 확률 변수를 사용하는데, 왜 평균이 1인 확률 변수를 사용하는 것은 바람직하지 않을까요?

✔️ 평균이 1인 확률 변수를 사용하면, 변이 방향이 항상 한쪽(양의 방향)으로 치우치게 되어 탐색의 편향이 생기고, 전체 해 공간을 고르게 탐색하지 못하게 됩니다. 이는 지역 최적점에 빠질 가능성을 높이고 전역 최적점을 찾기 어렵게 만듭니다.

---

2. Say we are trying to find the maxima of the multivariable function f(x,y,z) with genetic algorithm. Will it be a successful approach to use the shuffle mutation in this case?
f(x, y, z)라는 다변수 함수의 최대값을 유전 알고리즘으로 찾고자 할 때, 셔플 변이를 사용하는 것이 효과적인 방법일까요?

✔️ 아니요. 셔플 변이는 순서형 유전자에 적합한 변이 방식으로, 실수형 유전자처럼 값 그 자체가 중요한 경우에는 적절하지 않습니다. f(x, y, z) 문제처럼 실수 최적화 문제에서는 보통 연속적인 변이(예: 랜덤 편차 변이)를 사용하는 것이 효과적입니다.