유전 알고리즘

자연 선택과 유전자 변형 같은 진화생물학의 원리를 컴퓨터 알고리즘으로 모방한 최적화 기법.
복잡한 문제에서 최적해 또는 근사해를 찾기 위해 사용.

핵심 아이디어

유전 알고리즘은 자연 선택을 모방합니다. 다음 과정을 통해 더 좋은 해답을 점진적으로 생성합니다.
1. 초기 집단 생성 : 문제를 해결할 후보들을 초기화
2. 적합도 평가 : 각 후보 해의 품질을 측정
3. 유전자 연산 : 교배와 돌연변이를 통해 새로운 후보 생성
4. 선택 : 더 나은 해를 생존시키고, 나쁜 해를 도태

유전 알고리즘의 구성 요소

1. 염색체

• 해를 표현하는 데이터 구조(ex. 배열, 문재열, 비트 등)
• 문제의 특성에 따라 염색체를 설계(ex. TSP(여행자 문제)에서는 도시 방문 순서를 염색체로 표현)

2. 적합도 함수

• 각 해의 품질을 평가하는 함수
• 값이 높을수록 더 좋은 해를 나타냄

3. 초기화

• 초기 집단을 생성
• 일반적으로 무작위의 초기 해를 생성하며, 집단 크기는 알고리즘 성능에 영향을 미침

4. 선택

• 다음 세대의 부모를 선택하는 단계
• 적합도가 높은 개체를 우선적으로 선택
• 선택 방법
  1. 룰렛 휠 선택 : 적합도에 비례하여 선택 확률을 부여
  2. 토너먼트 선택 : 임의의 개체 그룹에서 최고 적합도를 가진 개체 선택
  

5. 교차

• 부모 염색체를 결합하여 자식 염색체를 생성
• 두 개의 부모에서 유전 정보를 조합
• 방법
  1. 단일 점 교차 : 한 지점을 기준으로 부모 염색체를 나누어 결합
  2. 다중 점 교차 : 여러 지점에서 염색체를 나눔
  

6. 돌연변이

• 염색체 일부를 무작위로 변경하여 다양성을 추가
• 탐색 공간을 더 넓게 탐험할 수 있도록 돕는 역할
• 돌연변이율은 일반적으로 낮게 설정(1~5%)

7. 종료 조건

• 알고리즘을 멈출 기준
  1. 일정 세대 수 이후
  2. 적합도 함수 값이 목표치에 도달
  3. 세대 간 적합도 변화가 거의 없을 경우
  

작동 원리

1. 초기화 : 무작위로 초기 집단 생성
2. 적합도 평가 : 적합도 함수로 각 염색체 평가
3. 선택 : 적합도가 높은 염색체를 부모로 선택
4. 교차 : 부모의 일부 유전 정보를 교환하여 자식 새엇ㅇ
5. 돌연변이 : 새로운 염색체 일부를 변경
6. 세대 교체 : 새로 생성된 염색체로 집단을 갱신
7. 종료 조건 확인 : 종료 조건 만족 시 최적 해 반환 or 반복

장점

1. 글로벌 최적화 가능성 : 지역 최적해에 빠지지 않고 더 나은 해를 찾을 가능성이 높음
2. 탐색 공간에 제약 없음 : 함수의 형태에 관계없이 사용 가능
3. 병렬성 : 여러 해를 동시에 탐색하므로 병렬 처리가 가능

단점

1. 계산 비용 : 집단 크기와 반복 횟수가 클수록 계산 자원이 많이 필요
2. 파라미터 설정 : 돌연변이율, 교차율 등 초기값 설정이 결과에 큰 영향을 미침
3. 수렴 속도 : 수렴이 느릴 수 있고, 최적해에 도달하지 못할 수도 있음

적용 사례

1. 최적화 문제
   • 물류 및 경로 최적화(TSP)
   • 자원 할당(스케쥴링 문제)
2. 머신러닝
   • 하이퍼파라미터 튜닝
   • 신경망의 구조 설계
3. 게임이론
   • 전략 최적화
4. 공학 설계
   • 로봇의 동작 경로 최적화
   • 항공기 부품 설계

실습

import numpy as np

# 적합도 함수
def fitness_function(x):
    return -x**2 + 10 * x + 5  # 예제: 간단한 2차 함수

# 초기화
def initialize_population(size, lower_bound, upper_bound):
    return np.random.uniform(lower_bound, upper_bound, size)

# 선택
def selection(population, fitness):
    probabilities = fitness / fitness.sum()
    return population[np.random.choice(range(len(population)), p=probabilities)]

# 교차
def crossover(parent1, parent2):
    alpha = np.random.rand()
    return alpha * parent1 + (1 - alpha) * parent2

# 돌연변이
def mutate(individual, mutation_rate, lower_bound, upper_bound):
    if np.random.rand() < mutation_rate:
        return np.random.uniform(lower_bound, upper_bound)
    return individual

# 유전 알고리즘
def genetic_algorithm(iterations, population_size, lower_bound, upper_bound, mutation_rate):
    population = initialize_population(population_size, lower_bound, upper_bound)
    for _ in range(iterations):
        fitness = np.array([fitness_function(ind) for ind in population])
        new_population = []
        for _ in range(len(population)):
            parent1 = selection(population, fitness)
            parent2 = selection(population, fitness)
            child = crossover(parent1, parent2)
            child = mutate(child, mutation_rate, lower_bound, upper_bound)
            new_population.append(child)
        population = np.array(new_population)
    return population[np.argmax([fitness_function(ind) for ind in population])]

# 실행
best_solution = genetic_algorithm(100, 20, 0, 10, 0.1)
print("최적해:", best_solution)```