유전 알고리즘

9.1 유전 알고리즘 소개.

유전 알고리즘 (GA)은 자연 선택 과정을 본떠 만든 최적화 및 탐색 방법이야. 생물학적 진화 과정을 모방한 거지.

유전 알고리즘은 전통적인 방법이 비효율적일 수 있는 복잡한 문제를 해결하는 데 사용돼. 이 알고리즘은 선택, 교차(crossover), 변이(mutation) 메커니즘을 사용해서 해결책을 진화시켜.

작동 원리:

1. 초기화:

가능한 해결책(염색체)의 초기 집단이 생성돼. 각 해결책은 문자열 (비트 문자열, 문자 문자열 또는 기타 구조)로 인코딩돼.

2 적합도 함수 (fitness function):

집단 내 각 해결책의 품질을 평가해.

3. 평가:

각 해결책(개체)은 fitness function을 사용해서 평가돼, 이 함수는 해결책이 문제를 얼마나 잘 해결하는지 결정해.

4. 선택:

적합도가 높은 해결책일수록 번식에 선택될 가능성이 커. 자주 사용하는 방법은 룰렛 휠 선택, 토너먼트 선택, 랭크 선택이 있어.

5. 교차 (crossover):

선택된 해결책(부모들)이 결합되어 새로운 해결책(자손들)을 만들어. 교차는 하나의 점, 두 개의 점 또는 여러 개의 점에서 일어날 수 있어.

6. 변이:

새롭게 생성된 해결책에 무작위 변화를 주어 다양성을 도입해. 이렇게 하면 알고리즘이 지역 최소값에 빠지지 않도록 도와줘.

7. 교체:

새 집단이 옛 집단을 대체하고, 이 과정은 멈춤 조건이 충족될 때까지 (예를 들어, 특정 세대 수에 도달하거나 특정 적합도에 도달할 때까지) 반복돼.

장점과 단점

장점:

• 광범위한 적용: 다양한 문제를 해결할 수 있어, 특히 분석적 방법이 작동하지 않을 때 좋아.
• 글로벌 최적화: 다차원 및 복잡한 공간에서 글로벌 최적점을 찾을 수 있어.
• 유연성: 어느 fitness function과도 사용할 수 있어.

단점:

• 높은 계산 비용: 큰 집단과 복잡한 문제에서 상당한 계산 자원이 필요해.
• 매개변수 설정의 어려움: 집단 크기, 변이 및 교차 확률과 같은 매개변수의 설정이 복잡하고 성능에 크게 영향을 줄 수 있어.
• 최적 해결책 보장의 부재: 찾은 해결책이 전역 최적임을 보장할 수 없어.

사실 유전 알고리즘은 매우 효율성이 높은 휴리스틱이야. 심지어 모든 데이터 접근이 가능해도 최고의 해결책을 보장하지는 않아. 하지만 복잡한 상황과 대량의 데이터에서 이상적인 해결책에 근접한 결과를 빠르게 제시해.

9.2 적용 예시

유전 알고리즘을 사용한 함수 최적화 예시를 살펴보자.

import random

# 유전 알고리즘 파라미터
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# 적합도 함수 정의
def fitness_function(x):
    return -x**2 + 10*x
            
# 집단 초기화
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# 선택 (토너먼트 선택)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# 교차 (하나의 교차점)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# 변이
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# 유전 알고리즘의 메인 루프
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# 최적의 해법 출력
best_individual = max(population, key=fitness_function)
print("최고의 해결책:", best_individual)
print("함수 값:", fitness_function(best_individual))
            
        

장점과 단점

9.3 다차원 함수의 최적화

문제:

다차원 함수의 최소값을 찾아라.

해결책:

이전 템플릿을 사용하자

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# 사용 예시:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"최고의 해결책: {best_solution}")