🔠 4. Crossover

✨ 4 - Crossover 교차

Crossover is the process of forming new individuals from existing individuals while maintaining traits.
교차(Crossover)는 기존 개체들로부터 특성을 유지한 채 새로운 개체를 생성하는 과정입니다.

The main purpose of crossing is the exchange of experience.
교차의 주요 목적은 경험의 교환입니다.

This approach greatly speeds up finding an acceptable solution.
이 방식은 수용 가능한 해를 더 빠르게 찾는 데 크게 기여합니다.

Crossover is the next logical action that occurs after selection.
교차는 선택 이후에 일어나는 다음 단계의 논리적 절차입니다.

---

🔡 주요 단어

영어 단어	한글 뜻
trait	특성
exchange	교환
experience	경험
acceptable	수용
solution	해
logical	논리
occur	발생

---

✨ 4 - Structure 구조

In this chapter, we will look at the following crossover methods:
이 장에서는 다음과 같은 교차 방법들을 살펴볼 것입니다.

One-point crossover
원포인트 교차

N-point crossover
N포인트 교차

Uniform crossover
균일 교차

Linear combination crossover
선형 결합 교차

Blend crossover
블렌드 교차

Order crossover
순서 기반 교차

Fitness driven crossover
적합도 기반 교차

---

✨ 4 - Objectives 학습 목표

Understand what crossover is
교차가 무엇인지 이해합니다.

Introduce main crossover methods
주요 교차 방법들을 소개합니다.

Get visualization and implementation of each method
각 방법의 시각화와 구현을 확인합니다.

---

✨ 4.1 One-point crossover 단일 지점 교차

In one-point crossover, a point in a gene sequence is randomly selected by dividing the gene sequence into two parts.
단일 지점 교차는 유전자 서열에서 한 지점을 무작위로 선택해, 이를 두 부분으로 나누는 방식입니다.

New individuals are created by crossing these two parts.
이 두 부분을 서로 교환하여 새로운 개체를 생성합니다.

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

One-point crossover can be applied to ordered gene and binary bin sets.
단일 지점 교차는 순서가 있는 유전자나 이진 집합에도 적용할 수 있습니다.

If the gene sequence consists of one element, then a simple exchange of genes between the parents happens, and each of the children is a clone of one of the parents.
유전자 서열이 하나의 요소만으로 이루어져 있다면 부모 간의 단순한 유전자 교환이 일어나며, 자식은 부모 중 한 쪽의 복제본이 됩니다.

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

If the gene sequence consists of two elements, then the genes are exchanged in a crisscross way.
유전자 서열이 두 개의 요소로 이루어져 있다면, 유전자는 엇갈리는 방식으로 교환됩니다.

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

Here we will show an implementation of one-point crossover to an ordered gene set.
여기서는 순서가 있는 유전자 집합에 단일 지점 교차를 적용한 구현을 보여줍니다.

---

Import part

import copy
import random

---

One-point crossover

def crossover_one_point(p1, p2):
    point = random.randint(1, len(p1) - 1)
    c1, c2 = copy.deepcopy(p1), copy.deepcopy(p2)
    c1[point:], c2[point:] = p2[point:], p1[point:]
    return [c1, c2]

---

Example

random.seed(2)
p1 = [random.randint(0, 9) for _ in range(5)]
p2 = [random.randint(0, 9) for _ in range(5)]
 
offspring = crossover_one_point(p1, p2)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: [1, 1, 0, 4, 3]  
Parent 2: [3, 3, 2, 1, 8]  
Child 1:  [1, 1, 2, 1, 8]  
Child 2:  [3, 3, 0, 4, 3]

---

🔡 주요 단어

영어 단어	한글 뜻
one-point	단일
randomly	무작위로
divide	나누다
exchange	교환
clone	복제본
element	요소
crisscross	엇갈림
implementation	구현
ordered	순서가 있는

---

✨ 4.2 N-point crossover 다중 지점 교차

N-point crossover is a logical continuation of one-point crossover,
다중 지점 교차는 단일 지점 교차의 논리적인 연장선입니다.

but instead of choosing only one point in a gene sequence, N points are selected,
하나의 지점을 선택하는 대신, 유전자 서열에서 N개의 지점을 선택합니다.

and genes are being exchanged in a crisscross way.
그리고 유전자는 엇갈리는 방식으로 교환됩니다.

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

Let’s see an implementation of N-point crossover that is applied to an ordered gene set. 순서가 있는 유전자 집합에 다중 지점 교차를 적용한 구현을 살펴보겠습니다.

---

Import part

import copy
import random

---

N-point crossover

def crossover_n_point(p1, p2, n):
    ps = random.sample(range(1, len(p1) - 1), n)
    ps.append(0)
    ps.append(len(p1))
    ps = sorted(ps)
    c1, c2 = copy.deepcopy(p1), copy.deepcopy(p2)
    for i in range(0, n + 1):
        if i % 2 == 0:
            continue
        c1[ps[i]:ps[i + 1]] = p2[ps[i]:ps[i + 1]]
        c2[ps[i]:ps[i + 1]] = p1[ps[i]:ps[i + 1]]
    return [c1, c2]

---

Example

random.seed(3)
p1 = [random.randint(0, 9) for _ in range(6)]
p2 = [random.randint(10, 19) for _ in range(6)]
offspring = crossover_n_point(p1, p2, 3)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: [3, 8, 9, 3, 8, 5]  
Parent 2: [11, 13, 11, 11, 13, 13]  
Child 1:  [3, 13, 11, 3, 13, 5]  
Child 2:  [11, 8, 9, 11, 8, 13]

---

🔡 주요 단어

영어 단어	한글 뜻
continuation	연장선, 확장
crisscross	엇갈림

---

✨ 4.3 Uniform crossover 균등 교차

Uniform crossover randomly selects some points in the parent’s gene chain, and swaps the genes at these points.
균등 교차는 부모의 유전자 서열에서 몇몇 지점을 무작위로 선택하고, 해당 지점의 유전자를 서로 교환합니다.

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

---

Import part

import copy
import random

---

Uniform crossover

def crossover_uniform(p1, p2, prop):
    c1 = copy.deepcopy(p1)
    c2 = copy.deepcopy(p2)
    for i in range(len(p1)):
        if random.random() < prop:
            c1[i], c2[i] = p2[i], p1[i]
    return [c1, c2]

---

Example

random.seed(3)
p1 = [random.randint(0, 9) for _ in range(6)]
p2 = [random.randint(10, 19) for _ in range(6)]
offspring = crossover_uniform(p1, p2, 0.5)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: [3, 8, 9, 3, 8, 5]  
Parent 2: [19, 17, 11, 12, 15, 17]  
Child 1:  [3, 17, 9, 12, 8, 17]  
Child 2:  [19, 8, 11, 3, 15, 5]

---

🔡 주요 단어

영어 단어	한글 뜻
uniform	동일한, 균등한
chain	사슬
swap	교환
point	지점
probability	확률

---

✨ 4.4 Linear combination crossover 선형 결합 교차

Linear combination crossover is the example of a crossover without any randomness.
선형 결합 교차는 무작위성이 없는 교차 방식의 예시입니다.

Child genes is a simple linear combination of parent genes:
자식의 유전자는 부모 유전자의 단순한 선형 결합으로 구성됩니다:

(x₁ + α |x₂ − x₁|, x₂ − α |x₂ − x₁|), where α is the parameter of linear combination in range [0, 1].
(x₁ + α |x₂ − x₁|, x₂ − α |x₂ − x₁|), 여기서 α는 [0, 1] 범위의 선형 결합 계수입니다.

NOTE : If α equals 0 or 1, then children are the same as parents.
참고 : α가 0 또는 1이면 자식은 부모와 동일합니다.

If α equals 0.5, then we have twins in offspring (both children are the same).
α가 0.5이면 두 자식이 동일한 쌍둥이 개체가 생성됩니다.

If we want only new individuals to be created, then we can restrict α to this range (0, 0.5).
항상 새로운 개체만 생성되기를 원한다면 α의 범위를 (0, 0.5)로 제한할 수 있습니다.

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

Implementation of linear crossover is just arithmetic operation applied to real gene set.
선형 결합 교차의 구현은 실수형 유전자 집합에 산술 연산을 적용하는 것일 뿐입니다.

---

Import part

import copy
import random

---

Linear crossover

def crossover_linear(p1, p2, alpha):
    c1 = copy.deepcopy(p1)
    c2 = copy.deepcopy(p2)
    for i in range(len(p1)):
        c1[i] = round(p1[i] + alpha * (p2[i] - p1[i]), 2)
        c2[i] = round(p2[i] - alpha * (p2[i] - p1[i]), 2)
    return [c1, c2]

---

Example

random.seed(3)
p1 = [round(random.uniform(0, 10), 2) for _ in range(6)]
p2 = [round(random.uniform(0, 10), 2) for _ in range(6)]
offspring = crossover_linear(p1, p2, 0.3)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: [4.16, 6.6, 1.62, 8.14, 9.58, 4.64]  
Parent 2: [3.26, 0.2, 1.82, 2.91, 0.91, 7.12]  
Child 1:  [3.89, 4.57, 1.68, 6.51, 6.89, 5.39]  
Child 2:  [3.53, 2.22, 1.76, 4.54, 3.6, 6.37]

---

🔡 주요 단어

영어 단어	한글 뜻
linear	선형의
combination	결합
randomness	무작위성
parameter	매개변수
range	범위
equal	같다
twin	쌍둥이
restrict	제한하다
offspring	자손

---

✨ 4.5 Blend crossover 혼합 교차

Blend crossover method chooses random genes in the range defined by parent genes.
혼합 교차는 부모 유전자에 의해 정의된 범위 내에서 무작위로 자식 유전자를 선택하는 방식입니다.

The range for children genes is defined as follows:
자식 유전자의 범위는 다음과 같이 정의됩니다:

[x₁ − α(x₂ − x₁), x₂ + α(x₂ − x₁)], where α is the parameter that expands the parent genes range.
[x₁ − α(x₂ − x₁), x₂ + α(x₂ − x₁)], 여기서 α는 부모 유전자 범위를 확장하는 계수입니다.

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

Usually, α = 0.5.
일반적으로 α는 0.5로 설정됩니다.

Please take a look at the following figure 4.8:
그림 4.8을 참고해 주세요.

Like linear crossover, blend crossover is applied to a real gene set; let’s study an implementation.
선형 결합 교차처럼, 혼합 교차도 실수형 유전자 집합에 적용됩니다. 구현을 살펴보겠습니다.

---

Import part

import copy
import random

---

Blend crossover

def crossover_blend(p1, p2, alpha):
    c1 = copy.deepcopy(p1)
    c2 = copy.deepcopy(p2)
    for i in range(len(p1)):
        l = min(c1[i], c2[i]) - alpha * abs(c2[i] - c1[i])
        u = max(c1[i], c2[i]) + alpha * abs(c2[i] - c1[i])
        c1[i] = round(l + random.random() * (u - l), 2)
        c2[i] = round(l + random.random() * (u - l), 2)
    return [c1, c2]

---

Example

random.seed(3)
p1 = [round(random.uniform(0, 10), 2) for _ in range(6)]
p2 = [round(random.uniform(0, 10), 2) for _ in range(6)]
offspring = crossover_blend(p1, p2, 0.5)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: [4.16, 6.6, 1.62, 8.14, 9.58, 4.64]  
Parent 2: [3.26, 0.2, 1.82, 2.91, 0.91, 7.12]  
Child 1:  [3.95, 5.64, 1.72, 7.96, 8.41, 5.6]  
Child 2:  [3.84, 1.55, 1.77, 4.49, 5.29, 6.63]

---

🔡 주요 단어

영어 단어	한글 뜻
blend	혼합
range	범위
define	정의하다
expand	확장하다
real	실수
uniform	균일한
random	무작위

---

✨ 4.6 Order crossover 순서 기반 교차

Order crossover is used for ordered genes; the main principle in this approach is to preserve the order of parent genes.
순서 기반 교차는 순서가 중요한 유전자에 사용되며, 이 방식의 핵심 원리는 부모 유전자의 순서를 유지하는 것입니다.

We will show how this method works with an example:
이 방법이 어떻게 작동하는지 예제를 통해 살펴보겠습니다.

Say, we have two individuals with ordered genes:
다음과 같이 순서가 있는 유전자를 가진 두 개체가 있다고 가정합시다:

Parent 1: (1, 7, 4, 5, 9, 2, 8, 3, 6)
부모 1: (1, 7, 4, 5, 9, 2, 8, 3, 6)

Parent 2: (3, 1, 5, 4, 9, 8, 6, 2, 7)
부모 2: (3, 1, 5, 4, 9, 8, 6, 2, 7)

We choose a random range in genes chain and swap it.
유전자 서열에서 무작위로 일정 범위를 선택하고, 해당 구간을 교환합니다.

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

Now, we will try to find the next number in Parent which wasn’t mentioned in Child 1 yet:
이제 부모의 유전자 중 자식 1에 아직 포함되지 않은 다음 숫자를 찾아보겠습니다.

Parent 1: (1, 7, 4, 5, 9, 2, 8 → 3, 6) – the next number is 3.
부모 1: (1, 7, 4, 5, 9, 2, 8 → 3, 6) – 다음 숫자는 3입니다.

Child 1: (X, X, 5, 4, 9, 8, 6, X, X) – doesn’t contain 3 yet.
자식 1: (X, X, 5, 4, 9, 8, 6, X, X) – 아직 3은 포함되어 있지 않습니다.

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

The same happens for Child in Parent 2 – the next number is 2, but it is already mentioned in Child 2 – then we take the next one:
Parent 2에서도 마찬가지로 자식 2에 대해 다음 숫자가 2이지만, 이미 자식 2에 포함되어 있으므로 다음 숫자를 확인합니다.

Parent 2: (3, 1, 5, 4, 9, 8, 6 → 2, 7) – the next number is 2.
부모 2: (3, 1, 5, 4, 9, 8, 6 → 2, 7) – 다음 숫자는 2입니다.

Child 2: (X, X, 4, 5, 9, 2, 8, X, X) – already contains 2.
자식 2: (X, X, 4, 5, 9, 2, 8, X, X) – 이미 2를 포함하고 있습니다.

Checking the next number:
다음 숫자를 확인합니다:

Parent 2: (3, 1, 5, 4, 9, 8, 6, 2 → 7) – the next number is 7.
부모 2: (3, 1, 5, 4, 9, 8, 6, 2 → 7) – 다음 숫자는 7입니다.

Child 2: (X, X, 4, 5, 9, 2, 8, X, X) – doesn’t contain 7 yet.
자식 2: (X, X, 4, 5, 9, 2, 8, X, X) – 아직 7은 포함되어 있지 않습니다.

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

Keep going for Child 1; the next Parent 1 number is 6 and this number is mentioned in Child 1 too, so we’re taking the next one:
자식 1에 대해 계속 진행합니다. 다음 부모 1의 숫자는 6인데, 자식 1에 이미 포함되어 있으므로 다음 숫자를 확인합니다.

Parent 1: (1, 7, 4, 5, 9, 2, 8, 3 → 6) – the next number is 6.
부모 1: (1, 7, 4, 5, 9, 2, 8, 3 → 6) – 다음 숫자는 6입니다.

Child 1: (X, X, 5, 4, 9, 8, 6, 3, X) – already contains 6.
자식 1: (X, X, 5, 4, 9, 8, 6, 3, X) – 이미 6을 포함하고 있습니다.

Checking the next number:
다음 숫자를 확인합니다:

Parent 1: (→ 1, 7, 4, 5, 9, 2, 8, 3, 6) – the next number is 1.
부모 1: (→ 1, 7, 4, 5, 9, 2, 8, 3, 6) – 다음 숫자는 1입니다.

Child 1: (X, X, 5, 4, 9, 8, 6, 3, X) – doesn’t contain 1 yet.
자식 1: (X, X, 5, 4, 9, 8, 6, 3, X) – 아직 1은 포함되어 있지 않습니다.

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

We hope you have got the principle.
이제 원리를 이해하셨기를 바랍니다.

As a result, we will have the following offspring.
그 결과로 우리는 다음과 같은 자식 개체들을 얻게 됩니다.

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

In very high dimension tasks with a large number of variables, an execution of order crossover can be rather time-consuming;
변수가 많은 고차원 문제에서는 순서 기반 교차의 실행이 상당한 시간을 소모할 수 있습니다.

you have to pay attention to this fact by applying this method.
이 방법을 적용할 때는 이러한 점에 유의해야 합니다.

---

Implementation of order crossover
순서 기반 교차의 구현입니다.

---

Import part

import random
from math import nan

---

Order crossover

def crossover_order(p1, p2):
    zero_shift = min(p1)
    length = len(p1)
    start, end = sorted([random.randrange(length) for _ in range(2)])
    c1, c2 = [nan] * length, [nan] * length
    t1, t2 = [x - zero_shift for x in p1], [x - zero_shift for x in p2]
    spaces1, spaces2 = [True] * length, [True] * length
 
    for i in range(length):
        if i < start or i > end:
            spaces1[t2[i]] = False
            spaces2[t1[i]] = False
 
    j1, j2 = end + 1, end + 1
    for i in range(length):
        if not spaces1[t1[(end + i + 1) % length]]:
            c1[j1 % length] = t1[(end + i + 1) % length]
            j1 += 1
        if not spaces2[t2[(i + end + 1) % length]]:
            c2[j2 % length] = t2[(i + end + 1) % length]
            j2 += 1
 
    for i in range(start, end + 1):
        c1[i], c2[i] = t2[i], t1[i]
 
    return [[x + zero_shift for x in c1], [x + zero_shift for x in c2]]

---

Example

random.seed(10)
p1 = random.sample(range(1, 10), 9)
p2 = random.sample(range(1, 10), 9)
offspring = crossover_order(p1, p2)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: [7, 4, 6, 1, 9, 3, 2, 5, 8]  
Parent 2: [3, 2, 6, 1, 7, 5, 4, 8, 9]  
Child 1:  [7, 4, 6, 1, 9, 5, 8, 3, 2]  
Child 2:  [3, 2, 6, 1, 7, 3, 9, 4, 8]

---

🔡 주요 단어

영어 단어	한글 뜻
order	순서
preserve	유지
mention	언급
contain	포함
execution	수행
time-consuming	소모적
pay attention	유의
variable	변수
high dimension	고차원
space	자리

---

✨ 4.7 Fitness driven crossover

Fitness driven crossover is an approach that compares the child to the parent and selects the best one.
적합도 기반 교차는 자식과 부모를 비교하여 더 나은 개체를 선택하는 방식입니다.

The main principle of this approach is that children should be better than their parents or not at all.
이 방식의 핵심 원리는 자식이 부모보다 더 나아야 하며, 그렇지 않으면 아예 선택되지 않는다는 것입니다.

In some tasks, the crossing operation is very unpredictable, and carries a high risk of destroying the accumulated positive experience.
일부 문제에서는 교차 연산이 매우 예측 불가능하며, 축적된 긍정적인 경험을 망가뜨릴 위험이 큽니다.

Then, as soon as the individuals appear to begin to adapt well to the environment, their genotype can be destroyed after crossing,
이러한 경우, 개체가 환경에 잘 적응하기 시작한 순간 교차로 인해 유전형이 파괴될 수 있습니다.

and as a result, their unique genetic adaptation will be destroyed.
그 결과, 개체의 고유한 유전적 적응력이 사라질 수 있습니다.

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

NOTE: You can notice that fitness driven crossover shares the same principle as elite selection which we covered in Chapter 3: Selection – not to lose valuable individuals.
참고: 적합도 기반 교차는 3장에서 다룬 엘리트 선택과 동일한 원리를 공유합니다 — 중요한 개체를 잃지 않도록 하는 것입니다.

And a reasonable question could be: Why not always do this? Why don’t we protect the best ones all the time?
이때 자연스럽게 생기는 질문은 이것입니다: 왜 항상 이렇게 하지 않을까? 왜 최적 개체를 매번 보호하지 않을까?

Sometimes it makes sense, but evolution is very tricky and unpredictable thing; sometimes it can make one step back and two steps forward.
때때로 그렇게 하는 것이 타당하지만, 진화는 매우 복잡하고 예측 불가능하여, 때론 한 걸음 뒤로 갔다가 두 걸음 앞으로 나아가기도 합니다.

Tiny mammals from the Jurassic period lived on the brink of survival, but after millions of years, this species led to the appearance of human.
쥐라기 시대의 작은 포유류는 생존의 벼랑 끝에 있었지만, 수백만 년 후 인류의 탄생으로 이어졌습니다.

We will get back to this question in further chapters.
이 질문은 이후 장에서 다시 다루겠습니다.

Fitness driven crossover can be based on any other crossover method.
적합도 기반 교차는 어떤 교차 방식 위에서도 구현할 수 있습니다.

For example, let’s examine the implementation of fitness driven crossover based on blend crossover.
예를 들어, 혼합 교차를 기반으로 한 적합도 기반 교차 구현을 살펴보겠습니다.

---

Import part

import copy
import random
from math import sin, cos

---

Individual

def fitness_function(x, y):
    return sin(x) * cos(y)
 
class Individual:
    def __init__(self, x, y) -> None:
        self.gene_set = [x, y]
        self.fitness = fitness_function(x, y)
 
    def __str__(self):
        return f'x: {self.gene_set[0]}, ' \
               f'y: {self.gene_set[1]}, ' \
               f'fitness: {round(self.fitness, 4)}'
 
def generate_random():
    return Individual(round(random.random(), 2),
                      round(random.random(), 2))

---

Fitness driven blend crossover

def crossover_fitness_driven_blend(ind1, ind2, alpha):
    c1 = copy.deepcopy(ind1.gene_set)
    c2 = copy.deepcopy(ind2.gene_set)
    for i in range(len(c1)):
        l = min(c1[i], c2[i]) - alpha * abs(c2[i] - c1[i])
        u = max(c1[i], c2[i]) + alpha * abs(c2[i] - c1[i])
        c1[i] = round(l + random.random() * (u - l), 2)
        c2[i] = round(l + random.random() * (u - l), 2)
    child1 = Individual(c1[0], c1[1])
    child2 = Individual(c2[0], c2[1]) # 교재에는 (c1[0], c1[1])로 나와있는데 수정해야 함
    candidates = [ind1, ind2, child1, child2]
    best = sorted(candidates, key=lambda ind: ind.fitness, reverse=True)
    return best[0:2]

---

Example

random.seed(3)
p1, p2 = generate_random(), generate_random()
offspring = crossover_fitness_driven_blend(p1, p2, 0.5)
 
print(f'Parent 1: {p1}')
print(f'Parent 2: {p2}')
print(f'Child 1: {offspring[0]}')
print(f'Child 2: {offspring[1]}')

---

Result

Parent 1: x: 0.24, y: 0.13, fitness: 0.2345  
Parent 2: x: 0.1, y: 0.84, fitness: 0.0672  
Child 1:  x: 0.24, y: 0.13, fitness: 0.2345  
Child 2:  x: 0.23, y: 0.24, fitness: 0.2245

---

We see that Child 1 is the copy of Parent. 자식 1은 부모의 복제본임을 확인할 수 있습니다.

---

🔡 주요 단어

영어 단어	한글 뜻
driven	기반
destroy	파괴
accumulate	축적
adaptation	적응
unpredictable	예측불가
survival	생존
brink	직전
species	종
appearance	출현

---

✨ 4 - Conclusion 결론

Crossover is a very specific evolutionary method.
교차는 매우 독특한 진화 방식입니다.

While the selection is an objective factor that is determined by nature and environment,
선택은 자연과 환경에 의해 결정되는 객관적인 요소인 반면,

the crossover mechanisms for each species can be very different.
교차 메커니즘은 종마다 매우 다를 수 있습니다.

There are insect species that may not use crossbreeding as such!
어떤 곤충 종은 교배 자체를 사용하지 않기도 합니다!

So, in genetic algorithms, crossover methods are chosen only as the source of the problem to be solved,
따라서 유전 알고리즘에서는 문제의 성격에 맞게 교차 방식을 선택합니다.

and it is impossible to decide in advance which method is better.
어떤 방식이 더 나은지는 사전에 결정할 수 없습니다.

An incorrectly chosen crossover method can stop the evolutionary improvement of a population,
잘못 선택된 교차 방식은 개체군의 진화적 발전을 멈추게 할 수 있으며,

and therefore make the search for a solution ineffective.
그 결과, 해를 찾는 과정이 비효율적이 될 수 있습니다.

In the next chapter, we will study the last part of evolution called mutation.
다음 장에서는 진화의 마지막 단계인 돌연변이에 대해 학습하겠습니다.

---

✨ 4 - Points to remember 기억할 점

Each crossover method has the principle: Try to change the experience of individuals, but not to make soup of the genes, destroying the whole gene structure.
모든 교차 방식은 하나의 원칙을 따릅니다: 개체의 경험은 바꾸되, 유전자를 뒤섞어 전체 구조를 파괴하지는 말 것.

There is no predetermined list of crossover methods.
교차 방식에는 미리 정해진 목록이 있는 것이 아닙니다.

You can implement your own crossover method for specific task.
문제의 성격에 따라 자신만의 교차 방법을 구현할 수 있습니다.

---

✨ 4 - Multiple choice questions 객관식 문제

Question 1
We have a population of individuals with genes: where x and y lie in range (-10, 10).
x와 y가 (-10, 10) 범위에 있는 유전자를 가진 개체군이 있습니다.

We use blend crossover with α = 0 in our genetic algorithm flow (without mutation).
우리는 돌연변이 없이 α = 0인 블렌드 교차만을 사용하는 유전 알고리즘 흐름을 적용합니다.

What can we say about our population after 50 generations?
50세대가 지난 후 개체군에 대해 어떤 현상이 나타날까요?

• All individuals will be concentrated near one point because the best solution will be found.
  모든 개체가 하나의 점 근처로 모일 것입니다. 왜냐하면 최적 해가 발견되었기 때문입니다.

• All individuals will be uniformly distributed in square (-10,10) × (-10,10).
  모든 개체가 (-10,10) × (-10,10) 사각형 영역에 균등하게 분포될 것입니다.

• ✅ All individuals will be concentrated near one point because blend crossover with α = 0 doesn’t expand the range of genes and all children genes will be shrinking.
  ✅ 모든 개체는 하나의 점 근처에 집중될 것입니다. α = 0인 블렌드 교차는 유전자 범위를 확장하지 않으며, 모든 자식 유전자가 점점 수렴되기 때문입니다.

Question 2
We have a population of individuals with ordered genes: (1 2,…,9).
정렬된 유전자 (1, 2, …, 9)를 가진 개체군이 있습니다.

Our gene structure is very fragile and there is a high probability that after each crossover, new offspring will be worse than their parents.
우리의 유전자 구조는 매우 민감해서, 교차 이후 자식이 부모보다 못한 경우가 자주 발생합니다.

What approach can we use to solve that issue?
이 문제를 해결하기 위해 어떤 접근을 사용할 수 있을까요?

• Order Crossover
  순서 기반 교차

• ✅ Fitness Driven Crossover based on Order Crossover
  ✅ 순서 기반 교차를 바탕으로 한 적합도 기반 교차 : 순서 유지 + 성능 보장이라는 두 가지 조건을 만족

• One Point Crossover
  단일 지점 교차

• Fitness Driven Crossover based on Uniform Crossover
  균등 교차를 바탕으로 한 적합도 기반 교차

---

✨ 4 - Questions 질문

1. Why the usage of blend crossover with very high α can lead to poor results of genetic algorithm execution?
블렌드 교차에서 α 값이 너무 클 경우, 왜 유전 알고리즘의 성능이 떨어질 수 있을까요?

✔️ α가 너무 크면 자식 유전자가 부모 범위를 훨씬 넘어서게 되어, 무작위성이 과도하게 커지고 유용한 유전자 구조가 손상될 수 있기 때문입니다.

---

2, Say we have a real gene set for genetic algorithm finding maxima of multivariable function f(x, y, z). Can we get acceptable results with the usage of order crossover here?
f(x, y, z)라는 다변수 함수의 최대값을 찾는 유전 알고리즘에서 실수형 유전자 집합을 사용하는 경우, 순서 기반 교차를 적용해도 괜찮은 결과를 얻을 수 있을까요?

✔️ 아니요. 순서 기반 교차는 순열 기반 유전자(예: 외판원 문제)처럼 순서가 중요한 문제에 맞춰 설계된 방식이기 때문입니다.