파이썬을 이용한 유전 알고리즘의 개념과 구현 방법

01 Oct 2023

python

유전 알고리즘은 최적화 문제를 해결하기 위해 자연의 진화 원리에서 영감을 받은 알고리즘입니다. 이 알고리즘은 유전적인 연산자를 사용하여 초기 집단을 유전적으로 변이시키고 선택 과정을 통해 최적해를 찾아냅니다.

유전 알고리즘의 개념

유전 알고리즘은 아래의 단계로 이루어집니다.

초기 집단 생성: 문제에 대한 초기 해결책의 집단을 랜덤으로 생성합니다.
적합도 평가: 각 해결책의 적합도를 평가하여 선택에 사용될 확률을 계산합니다.
선택: 적합도에 기반하여 일부 해결책을 선택합니다.
교차: 선택된 해결책을 이용하여 새로운 자손을 생성합니다.
변이: 일부 자손을 랜덤으로 변이시킵니다.
교체: 변이된 자손을 이용하여 다음 세대의 집단을 형성합니다.

이러한 과정을 반복하여 최적해를 찾아냅니다.

유전 알고리즘의 구현 방법

아래는 파이썬을 이용하여 유전 알고리즘을 구현하는 간단한 예제 코드입니다.

import random

# 초기 해결책 생성
def initialize_population(population_size, chromosome_length):
    population = []
    for _ in range(population_size):
        chromosome = [random.randint(0, 1) for _ in range(chromosome_length)]
        population.append(chromosome)
    return population

# 적합도 평가
def evaluate_fitness(chromosome):
    return sum(chromosome)

# 선택
def selection(population, fitness):
    selected_population = []
    total_fitness = sum(fitness)
    probabilities = [fit / total_fitness for fit in fitness]
    for _ in range(len(population)):
        selected_population.append(random.choices(population, probabilities)[0])
    return selected_population

# 교차
def crossover(parent1, parent2):
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# 변이
def mutate(chromosome, mutation_rate):
    for i in range(len(chromosome)):
        if random.random() < mutation_rate:
            chromosome[i] = 1 - chromosome[i]
    return chromosome

# 유전 알고리즘 실행
def genetic_algorithm(population_size, chromosome_length, mutation_rate, max_generations):
    population = initialize_population(population_size, chromosome_length)

    for generation in range(max_generations):
        fitness = [evaluate_fitness(chromosome) for chromosome in population]
        selected_population = selection(population, fitness)

        new_population = []
        while len(new_population) < population_size:
            parent1, parent2 = random.sample(selected_population, 2)
            child1, child2 = crossover(parent1, parent2)
            new_population.extend([mutate(child1, mutation_rate), mutate(child2, mutation_rate)])

        population = new_population

        best_chromosome = max(population, key=lambda x: evaluate_fitness(x))
        best_fitness = evaluate_fitness(best_chromosome)
        
        print(f"Generation {generation+1}: Best Fitness = {best_fitness}")

# 유전 알고리즘 실행
genetic_algorithm(population_size=100, chromosome_length=10, mutation_rate=0.01, max_generations=50)

위 코드는 0과 1로 이루어진 이진문자열을 최대로 구성하는 유전 알고리즘의 예시입니다. 각 세대에서 최적해에 대한 정보를 출력합니다.

이처럼 파이썬을 이용하여 유전 알고리즘을 간단하게 구현할 수 있습니다. 유전 알고리즘은 다양한 최적화 문제에 적용될 수 있으며, 문제에 맞게 알고리즘을 수정하고 발전시킬 수 있습니다.

#GeneticAlgorithm #Python