💻 1.4 Your first genetic algorithm

✨ 원본 코드

import random
from typing import List
import numpy as np
import matplotlib.pyplot as plt
 
 
def constraints(g, min_=-10, max_=10):
    if max_ and g > max_:
        g = max_
    if min_ and g < min_:
        g = min_
    return g
 
 
def crossover_blend(g1, g2, alpha):
    shift = (1 + 2 * alpha) * random.random() - alpha
    new_g1 = (1 - shift) * g1 + shift * g2
    new_g2 = shift * g1 + (1 - shift) * g2
 
    return constraints(new_g1), constraints(new_g2)
 
 
def mutate_gaussian(g, mu, sigma):
    mutated_gene = g + random.gauss(mu, sigma)
    return constraints(mutated_gene)
 
 
def select_tournament(population, size):
    new_offspring = []
    for _ in range(len(population)):
        candidates = [random.choice(population) for _ in range(size)]
        new_offspring.append(max(candidates, key=lambda ind: ind.fitness))
    return new_offspring
 
 
def func(x):
    return np.sin(x) - .2 * abs(x)
 
 
def get_best(population):
    best = population[0]
    for ind in population:
        if ind.fitness > best.fitness:
            best = ind
    return best
 
 
def plot_population(population, number_of_population):
    best = get_best(population)
    x = np.linspace(-10, 10)
    plt.plot(x, func(x), '--', color='blue')
    plt.plot(
        [ind.get_gene() for ind in population],
        [ind.fitness for ind in population],
        'o', color='orange'
    )
    plt.plot([best.get_gene()], [best.fitness], 's', color='green')
    plt.title(f"Generation number {number_of_population}")
    plt.show()
    plt.close()
 
 
class Individual:
 
    def __init__(self, gene_list: List[float]) -> None:
        self.gene_list = gene_list
        self.fitness = func(self.gene_list[0])
 
    def get_gene(self):
        return self.gene_list[0]
 
 
def crossover(parent1, parent2):
    child1_gene, child2_gene = crossover_blend(parent1.get_gene(), parent2.get_gene(), 1)
    return Individual([child1_gene]), Individual([child2_gene])
 
 
def mutate(ind):
    mutated_gene = mutate_gaussian(ind.get_gene(), 0, 1)
    return Individual([mutated_gene])
 
 
def select(population):
    return select_tournament(population, size=3)
 
 
def create_random():
    return Individual([random.uniform(-10, 10)])
 
 
random.seed(52)
# random.seed(16)  # local maximum
POPULATION_SIZE = 10
CROSSOVER_PROBABILITY = .8
MUTATION_PROBABILITY = .1
MAX_GENERATIONS = 10
 
first_population = [create_random() for _ in range(POPULATION_SIZE)]
plot_population(first_population, 0)
 
generation_number = 0
 
population = first_population.copy()
 
while generation_number < MAX_GENERATIONS:
 
    generation_number += 1
 
    # SELECTION
    offspring = select(population)
 
    # CROSSOVER
    crossed_offspring = []
    for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < CROSSOVER_PROBABILITY:
            kid1, kid2 = crossover(ind1, ind2)
            crossed_offspring.append(kid1)
            crossed_offspring.append(kid2)
        else:
            crossed_offspring.append(ind1)
            crossed_offspring.append(ind2)
 
    # MUTATION
    mutated_offspring = []
    for mutant in crossed_offspring:
        if random.random() < MUTATION_PROBABILITY:
            new_mutant = mutate(mutant)
            mutated_offspring.append(new_mutant)
        else:
            mutated_offspring.append(mutant)
 
    population = mutated_offspring.copy()
 
    plot_population(population, generation_number)

---

✨ 메인함수 1회독

random.seed(52)
# random.seed(16)  # local maximum
 
POPULATION_SIZE = 10
CROSSOVER_PROBABILITY = .8
MUTATION_PROBABILITY = .1
MAX_GENERATIONS = 10

• 0️⃣ GA Parameters 정의

---

first_population = [create_random() for _ in range(POPULATION_SIZE)]

• 0️⃣ 초기 모집단(개체군) 생성

• 1️⃣ 적합도 평가는 어디있을까? : 우선 pass

---

plot_population(first_population, 0)
 
generation_number = 0
 
population = first_population.copy()

while generation_number < MAX_GENERATIONS:
    generation_number += 1

• 🔁 반복문
• 종료조건은 generation_number가 MAX_GENERATIONS에 도달할 때까지 (generation_number= MAX_GENERATIONS가 되면 종료)

---

    # SELECTION
    offspring = select(population)

• 2️⃣ 선택 연산

---

    # CROSSOVER
    crossed_offspring = []
    for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < CROSSOVER_PROBABILITY:
            kid1, kid2 = crossover(ind1, ind2)
            crossed_offspring.append(kid1)
            crossed_offspring.append(kid2)
        else:
            crossed_offspring.append(ind1)
            crossed_offspring.append(ind2)

• 3️⃣ 교차 연산

---

    # MUTATION
    mutated_offspring = []
    for mutant in crossed_offspring:
        if random.random() < MUTATION_PROBABILITY:
            new_mutant = mutate(mutant)
            mutated_offspring.append(new_mutant)
        else:
            mutated_offspring.append(mutant)

• 4️⃣ 돌연변이 연산

---

    population = mutated_offspring.copy()

• 5️⃣ 새로운 모집단 업데이트

---

    plot_population(population, generation_number)

---

✨ 메인함수 2회독

random.seed(52)
# random.seed(16)  # local maximum
 
POPULATION_SIZE = 10
CROSSOVER_PROBABILITY = .8
MUTATION_PROBABILITY = .1
MAX_GENERATIONS = 10

• 0️⃣ GA Parameters 정의

  ▸ POPULATION_SIZE : 개체군 크기
  ▸ CROSSOVER_PROBABILITY : 교차 확률
  ▸ MUTATION_PROBABILITY : 변이 확률
  ▸ MAX_GENERATIONS : 최대 세대 번호 (알고리즘 반복 횟수이자 종료 조건)

---

first_population = [create_random() for _ in range(POPULATION_SIZE)]

• 0️⃣ 초기 모집단(개체군) 생성
  1. POPULATION_SIZE 만큼 반복문을 실행
  2. 각 반복에서 create_random() 함수를 호출하여 새로운 개체(Individual 객체)를 생성
  3. 생성된 개체들을 리스트에 저장하여 first_population으로 반환

---

• 1️⃣ 적합도 평가는 어디있을까? : 우선 pass

---

plot_population(first_population, 0)

• 초기 모집단 시각화

generation_number = 0

• 현재 세대 번호(Generation Number)를 저장하는 역할을 할 변수 generation_number 선언 및 초기화

population = first_population.copy()

• 초기 모집단을 복사하여 population 변수에 저장

💡 왜 .copy()를 사용할까?

• 유전 알고리즘의 올바른 실행을 보장하고, 실험의 재현성을 유지하기 위해서
• 초기 세대와 이후 세대 간의 비교를 통한 알고리즘의 동작 확인을 위해서
• 단순히 population = first_population을 하면, 두 변수가 같은 리스트를 참조하기 때문에 population이 바뀌면 first_population도 영향을 받음
• .copy()를 사용하면 새로운 리스트가 생성되어 first_population과 독립적인 개체군으로 작동

💡 .copy() vs .deepcopy()

• .copy() : 얕은 복사 (리스트는 새로 생성되지만, 내부 개체들은 기존 개체를 참조)
• copy.deepcopy() : 깊은 복사 (리스트뿐만 아니라 내부 개체도 새로 생성되어 완전히 독립적)
• 코드에서 .copy()(얕은 복사)만 사용한 이유는 개체군 리스트를 독립적으로 유지할 필요는 있지만, 개체(Individual) 자체는 새로 만들 필요가 없기 때문
• 유전 알고리즘에서 매 세대마다 개체군을 완전히 새로운 개체들로 교체하는 것이 아니라, 기존 개체들을 변형(선택, 교차, 돌연변이)하여 업데이트하기 때문

---

while generation_number < MAX_GENERATIONS:

• 유전 알고리즘의 세대 진행을 제어하는 🔁 반복문
• generation_number : 현재 진행 중인 세대 번호 (0부터 시작)
• MAX_GENERATIONS : 최대 세대 수 (10)
• while문 : 현재 세대 번호가 MAX_GENERATIONS보다 작으면 반복 실행 (= 유전 알고리즘을 최대 MAX_GENERATIONS 세대까지 실행)

    generation_number += 1

• 반복문이 실행될 때마다 세대 번호를 1 증가시킴

---

    # SELECTION
    offspring = select(population)

• 2️⃣ 선택 연산 수행
• select(population) 함수 : 현재 개체군(population)에서 다음 세대로 전달할 개체들을 선택
• offspring : 선택된 개체들의 리스트 → 교차(Crossover)와 돌연변이(Mutation)에 사용됨

💡 offspring 변수에 대하여

• 제 개인적인 생각이지만 선택 연산은 부모(Parent)를 선택하는 과정인데, offspring(자손) 이라는 이름을 사용하고 있기 때문에 어색하다고 느꼈습니다.
• 코드 작성자는 다음 세대로 전달될 개체 라는 의미로 사용한 것으로 보이나, 엄밀히 말하면 select()에서 반환된 개체들은 아직 부모(Parent)이며, 자손(offspring)이 아님에 유의하셔야 합니다.

---

    # CROSSOVER
    crossed_offspring = []
    for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < CROSSOVER_PROBABILITY:
            kid1, kid2 = crossover(ind1, ind2)
            crossed_offspring.append(kid1)
            crossed_offspring.append(kid2)
        else:
            crossed_offspring.append(ind1)
            crossed_offspring.append(ind2)

• 3️⃣ 교차 연산 수행

  1. crossed_offspring = [] : 새로운 개체군(교차 후 자손들)을 저장할 빈 리스트 생성
  2. for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
     • offspring[::2]: 짝수 번째 인덱스의 개체 → 첫 번째 부모(ind1) 그룹
     • offspring[1::2]: 홀수 번째 인덱스의 개체 → 두 번째 부모(ind2) 그룹
     • zip()을 사용하여 부모 쌍 생성
     • for 루프는 모든 부모 쌍에 대해 반복 실행
  3. if random.random() < CROSSOVER_PROBABILITY:
     • random.random() → 0~1 사이의 난수 생성
     • CROSSOVER_PROBABILITY → 교차 확률 (예 : 0.8 → 80% 확률로 교배 수행)
     • 난수 값이 CROSSOVER_PROBABILITY보다 작으면 교차 수행, 크면 교차 없이 부모를 그대로 유지
  4. kid1, kid2 = crossover(ind1, ind2)
     • crossover() 함수를 사용해 부모 개체 두 개(ind1, ind2)를 교차하여 새로운 두 개의 자손(kid1, kid2) 생성
  5. crossed_offspring.append(kid1) crossed_offspring.append(kid2)
     • 생성된 두 개의 자손(kid1, kid2)을 리스트에 추가
     • 새로운 개체군(crossed_offspring)에 저장
  6. else: crossed_offspring.append(ind1) crossed_offspring.append(ind2)

     • 교차가 발생하지 않은 경우 (80% 확률을 넘긴 경우)

     • 부모 개체(ind1, ind2)를 그대로 다음 세대에 전달

  💡 리스트 슬라이싱 : [start:stop:step]

  💡 zip()

  • 여러 개의 iterable(리스트, 튜플 등)을 동시에 묶어주는 함수
  • 여러 리스트에서 각각 같은 인덱스에 있는 요소들을 튜플로 묶어서 반환

  list1 = [1, 2, 3]
  list2 = ['a', 'b', 'c']
   
  zipped = zip(list1, list2)
  print(list(zipped))  
  # [(1, 'a'), (2, 'b'), (3, 'c')]

---

    # MUTATION
    mutated_offspring = []
    for mutant in crossed_offspring:
        if random.random() < MUTATION_PROBABILITY:
            new_mutant = mutate(mutant)
            mutated_offspring.append(new_mutant)
        else:
            mutated_offspring.append(mutant)

• 4️⃣ 돌연변이 연산 수행
  1. mutated_offspring = [] : 돌연변이가 적용된 개체들을 저장할 빈 리스트 생성
  2. for mutant in crossed_offspring: : 교차(Crossover) 이후 생성된 개체군(crossed_offspring)의 모든 개체를 하나씩 순회
  3. if random.random() < MUTATION_PROBABILITY:
     • 확률(MUTATION_PROBABILITY)에 따라 돌연변이 수행 여부 결정
     • random.random() → 0~1 사이의 난수를 생성
     • MUTATION_PROBABILITY보다 작으면 돌연변이 발생
  4. new_mutant = mutate(mutant)
     • mutate() 함수를 호출하여 선택된 개체(mutant)에 돌연변이를 적용
     • 돌연변이가 발생한 경우, 새로운 변이된 개체(new_mutant) 생성
  5. mutated_offspring.append(new_mutant)
     • 돌연변이가 적용된 개체를 새로운 리스트(mutated_offspring)에 추가
  6. else: mutated_offspring.append(mutant)
     • 돌연변이가 발생하지 않은 경우, 기존 개체(mutant)를 그대로 유지하여 리스트에 추가

---

    population = mutated_offspring.copy()

• 5️⃣ 새로운 모집단 구성
• 교차(Crossover)와 돌연변이(Mutation)을 거친 개체군(mutated_offspring)을 새로운 개체군(population)으로 업데이트

    plot_population(population, generation_number)

• 새로 생성된 모집단 시각화

---

• 🔁 반복문으로 돌아가 종료 조건을 만족할 때 까지 위 과정 반복

---

✨ 함수 살펴보기

# Import part
 
import random                    # 난수 생성 라이브러리
from typing import List          # 리스트 타입 힌트를 제공하는 라이브러리
import numpy as np               # 행렬 및 수학 연산을 지원하는 라이브러리
import matplotlib.pyplot as plt  # 데이터 시각화를 위한 라이브러리

💡 typing 모듈

• 타입 힌팅을 위해 사용되는 모듈
• 타입 힌팅이란 파이썬 코드를 작성할 때 타입에 대한 메타 정보를 제공하는 것
• Python은 동적 타입 언어라서 변수의 타입을 명시하지 않아도 되지만, 타입 힌팅을 하면 여러 가지 실용적인 장점이 있음
  ▸ 코드 가독성 향상
  ▸ 오류 방지 및 정적 분석 가능
  ▸ 팀 협업 & 코드 유지보수에 도움
  ▸ 개발 도구 지원 (IDE 자동완성, 코드 분석 등)
• Python 3.9부터는 타입 어노테이션의 사용성이 대폭 개선되어 이제 typing 모듈에서 List, Dict, Tuple, Set를 불러오지 않고, list, dict, tuple, set 내장 타입을 통해 바로 원소의 타입까지 명시해줄 수 있습니다.

---

def func(x):                          # 입력 값 `x`를 기반으로 함수를 계산하여 반환
    return np.sin(x) - .2 * abs(x)    # 적합도 함수(Fitness Function)
 

---

class Individual:
    def __init__(self, gene_list: List[float]) -> None: # 초기화 메서드 / 매개변수는 gene_list / 타입 힌팅을 통한 인코딩 방법 정의
        self.gene_list = gene_list                      # 전달받은 유전 정보를 self.gene_list에 저장
        self.fitness = func(self.gene_list[0])          # 첫 번째 유전자를 기반으로 적합도(fitness)를 평가
 
    def get_gene(self):
        return self.gene_list[0]                        # 개체의 첫 번째 유전자를 반환하는 메서드

• Individual 클래스의 역할 : 유전 알고리즘에서 하나의 개체(Individual)를 표현 / 유전 정보(유전자)와 적합도(Fitness)를 저장하고 관리

💡파이썬 Class

• 클래스 Class : 객체를 만들기 위한 설계도
• 인스턴스 Instance : 클래스를 기반으로 생성된 실제 객체 / 같은 클래스를 사용하여 만든 여러 인스턴스들은 클래스는 동일하지만, 각 인스턴스는 메모리에서 독립적으로 존재함
• 메서드 Method : 클래스를 만들면서 그 안에 넣은 함수 / 사용하려면 객체.메서드()와 같은 형식으로 호출
• __init__ 메서드 : 초기화(Initialize)메서드로, 어떤 클래스의 객체가 만들어질 때 자동으로 호출되어 그 객체가 갖게 될 여러 성질을 정해줌 (생성자)
• self 키워드 : 클래스 내부에서 자기 자신(인스턴스)을 가리킴 / self를 사용하면 __init__ 메서드뿐만 아니라 같은 클래스 내 다른 메서드에서도 속성을 변경하거나 접근할 수 있음

---

def get_best(population):                # 주어진 개체 집단(population)에서 가장 높은 fitness 값을 가진 개체를 찾아 반환하는 함수 (시각화에 활)
    best = population[0]                 # 첫 번째 개체를 초기 최적 개체로 설정
    for ind in population:               # 모든 개체에 대해 반복
        if ind.fitness > best.fitness:   # 현재 best보다 fitness 값이 더 크다면
            best = ind                   # best를 현재 개체로 업데이트
    return best                          # 최종적으로 가장 fitness가 높은 개체 반환

---

def plot_population(population, number_of_population):   # 시각화 함수
    best = get_best(population)                          # get_best 함수를 사용해 주어진 개체군에서 가장 우수한 개체를 선택
    x = np.linspace(-10, 10)                             # -10에서 10까지의 값을 일정 간격으로 나눈 배열을 생성
    plt.plot(x, func(x), '--', color='blue')             # 배열을 적합도 함수에 대입해 그래프 그리기 / 파란색 점
    plt.plot(
        [ind.get_gene() for ind in population],          # X축 : 개체의 유전자 값(`get_gene` 메서드 활용)
        [ind.fitness for ind in population],             # Y축 : 개체의 적합도
        'o', color='orange'                              # 주황색 원으로 표시
    )
    plt.plot([best.get_gene()], [best.fitness], 's', color='green')   # 최적 개체(best)의 위치 시각화
    plt.title(f"Generation number {number_of_population}")            # 그래프 제목 설정
    plt.show()                                                        # 그래프를 화면에 출력
    plt.close()                                                       # 그래프를 닫아 메모리를 확보

• 매개변수

  ▸ population : 현재 세대의 개체군(리스트 형태)
  ▸ number_of_population: 현재 세대의 번호 (세대 수)

---

def create_random():                              # 초기 모집단 생성에 활용되는 함수
    return Individual([random.uniform(-10, 10)])         

• create_random 함수의 역할 : 새로운 개체(Individual)를 무작위로 생성하여 반환

• 동작

  1. random.uniform(-10, 10) : -10에서 10 사이의 무작위 실수를 생성
  2. Individual([random_value]) : 위에서 생성된 랜덤 값으로 Individual 객체를 생성 / 만들어진 개체는 유전자를 리스트 형태로 가짐
  3. 생성된 개체를 반환

---

def select_tournament(population, size):               # 토너먼트 방식으로 선택 연산을 진행하는 함수
    new_offspring = []                                 # 새로운 개체들을 저장할 리스트 초기화
    for _ in range(len(population)):                   # 기존 모집단의 크기를 만족할 때 까지 새로운 개체 생성
        candidates = [random.choice(population) for _ in range(size)] 
        new_offspring.append(max(candidates, key=lambda ind: ind.fitness))
    return new_offspring                               # 선택된 개체들로 구성된 새로운 개체군을 반환

• select_tournament 함수의 역할 : 토너먼트 선택 방식(Tournament Selection)을 사용하여 새로운 개체군을 선택

• 매개변수

  ▸ population : 현재 개체군(리스트 형태)
  ▸ size : 토너먼트에 참가할 후보 개체의 수

• 추가 주석

  ▸ candidates = [random.choice(population) for _ in range(size)]
      현재 개체군 population에서 size 개만큼 무작위로 후보를 선택하여 candidates 리스트를 생성

  ▸ new_offspring.append(max(candidates, key=lambda ind: ind.fitness))
      candidates 리스트에서 가장 높은 적합도를 가진 개체를 선택하여 new_offspring에 추가.

  💡 max(iterable, key=function)

  • 주어진 리스트(iterable)에서 가장 큰 값을 찾는 함수
  • key=function을 사용하면, 리스트의 각 요소에서 특정 속성이나 기준을 기반으로 비교할 수 있음

  💡 Lambda

  • 이름 없이 사용할 수 있는 익명 함수(Anonymous Function)
  • 일반적인 def 키워드를 사용한 함수와 달리, 한 줄로 간결하게 표현
  • lambda 매개변수: 반환값 형태로 선언
  • return 키워드는 사용하지 않으며, 한 줄만 작성할 수 있음

• 메인 함수에서 사용

def select(population):
    return select_tournament(population, size=3)

• select 함수를 실행하면 ‘select_tournament’의 실행 결과를 반환
• 후보는 3개

---

def constraints(g, min_ = -10, max_ = 10):   # 제약함수 / constraints = 제약
    if max_ and g > max_:                    # 만약 max_가 None이 아니고 g가 max_보다 크다면, g를 max_로 설정 (상한 제한)
        g = max_                          
    if min_ and g < min_:                    # 만약 min_이 None이 아니고 g가 min_보다 작다면, g를 min_으로 설정 (하한 제한)
        g = min_
     
    return g                                 # 제한이 적용된 g를 반환

• constraints 함수의 역할 : 주어진 값 g를 특정 범위 내로 제한

• 매개변수

  ▸ g : 제한을 적용할 값
  ▸ min_ : g 값의 하한 (최소값), 기본값 -10
  ▸ max_ : g 값의 상한 (최대값), 기본값 10

---

def crossover_blend(g1, g2, alpha):
    shift = (1 + 2 * alpha) * random.random() - alpha         # [-alpha, 1 + alpha] 범위에서 랜덤한 혼합 비율 생성  
 
    new_g1 = (1 - shift) * g1 + shi용
```python
def mutate(ind):
    mutated_gene = mutate_gaussian(ind.get_gene(), 0, 1) # 평균이 0이고 표준 편차가 1인 정규 분포에서 샘플을 추출하여 ind의 유전자 값에 더함
    return Individual([mutated_gene])                    # 변이가 적용된 새로운 유전자로 새로운 Individual 객체를 생성하여 반환

• mutate 함수를 실행하면 mutate_gaussian 함수를 사용하여 돌연변이를 적용하고 변이가 적용된 새로운 유전자를 반환

---

✨ 메인함수 3회독

• 2회독, 함수 이해하기를 읽고 메인 코드를 다시 읽어보기
• 예시 (미완)