Python을 이용한 유전 알고리즘: 개념과 구현 방법

유전 알고리즘은 생물학적 진화 과정에서 영감을 얻은 최적화 기법으로, 해결책을 진화시키는 방식으로 문제를 해결합니다. 이러한 알고리즘은 특히 복잡한 문제에 대한 효과적인 근사해를 찾는 데 사용됩니다. Python은 라이브러리 지원과 쉬운 구현 덕분에 유전 알고리즘을 실험하고 적용하기에 매우 적합합니다. 이 글에서는 유전 알고리즘의 기본 원리와 Python을 활용한 간단한 구현 예제를 소개하겠습니다.

 

 

유전 알고리즘의 기본 원리

• 인코딩: 문제의 해결책을 유전자로 표현합니다. 일반적으로 이진 문자열, 숫자 배열 등으로 해결책을 인코딩합니다.
• 초기 인구 생성: 해결책의 초기 집합(인구)을 무작위로 생성합니다.
• 적합도 평가: 각 해결책의 적합도를 평가하여 문제의 요구 사항을 얼마나 잘 만족하는지 평가합니다.
• 선택: 적합도에 따라 해결책을 선택합니다. 높은 적합도를 가진 해결책은 다음 세대로 전달될 확률이 높습니다.
• 교차: 선택된 해결책들 사이에서 일어나며, 두 해결책의 유전자를 조합하여 새로운 해결책을 생성합니다.
• 돌연변이: 임의로 해결책의 일부 유전자를 변형시켜 다양성을 유지합니다.
• 새로운 세대: 교차와 돌연변이를 통해 생성된 새로운 해결책들로 이전 세대를 대체합니다.

 

Python을 사용한 유전 알고리즘 구현 예제

• 아래의 예제는 간단한 최적화 문제를 해결하기 위한 유전 알고리즘의 구현입니다. 목표는 주어진 수식 x^2의 최소값을 찾는 것입니다.

 

import random

def generate_individual(size, min, max):
    return [random.randint(min, max) for _ in range(size)]

def compute_fitness(individual):
    return sum(x**2 for x in individual)

def select(population, fitnesses, num_parents):
    parents = sorted(zip(population, fitnesses), key=lambda x: x[1])
    return [x[0] for x in parents[:num_parents]]

def crossover(parent1, parent2):
    child = parent1[:len(parent1)//2] + parent2[len(parent2)//2:]
    return child

def mutate(individual, mutation_rate, min, max):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            individual[i] = random.randint(min, max)

def run_genetic_algorithm(generations, population_size, chromosome_length, mutation_rate):
    population = [generate_individual(chromosome_length, -10, 10) for _ in range(population_size)]
    
    for _ in range(generations):
        fitnesses = [compute_fitness(ind) for ind in population]
        parents = select(population, fitnesses, population_size//2)
        next_population = []

        while len(next_population) < population_size:
            parent1, parent2 = random.sample(parents, 2)
            child = crossover(parent1, parent2)
            mutate(child, mutation_rate, -10, 10)
            next_population.append(child)

        population = next_population

    best_individual = min(population, key=compute_fitness)
    return best_individual

best_solution = run_genetic_algorithm(100, 50, 3, 0.01)
print("Best solution:", best_solution)
print("Fitness:", compute_fitness(best_solution))

 

 

적용 분야

• 유전 알고리즘은 매우 유연하며, 공학 설계, 스케줄링, 자동차 경로 최적화, 기계 학습 등 다양한 분야에 적용됩니다.

Python과 유전 알고리즘을 사용하여 복잡한 최적화 문제를 해결하는 것은 효율적이고 효과적입니다. 이러한 접근 방식은 문제에 대한 새로운 해결책을 탐색하고, 가능한 최적의 해결책을 발견하는 데 도움을 줄 수 있습니다.