파이썬을 사용하여 유전 알고리즘으로 탐색 알고리즘 개발하기

01 Oct 2023

python

#인공지능 #유전알고리즘

유전 알고리즘은 자연의 진화 원리를 모방하여 최적화 문제를 해결하는 탐색 알고리즘입니다. 이 기법은 유전자의 변이, 교배, 선택 등의 단계를 통해 합리적인 솔루션을 생성하고 발전시키는 방법입니다.

1. 유전 알고리즘의 기본 개념 이해

유전 알고리즘은 세 가지 주요 단계로 구성됩니다.

a. 초기 집단 생성 - 탐색 공간에서 초기 해를 랜덤하게 생성합니다.

b. 유전 연산 - 유전적 원리를 통해 현재 해 집단을 발전시킵니다. 이 단계는 돌연변이, 교차 등의 연산을 수행합니다.

c. 선택 - 발전된 해들 중 가장 적합한 해를 선택합니다. 보통는 적합도 함수에 따라 선택됩니다.

2. 파이썬을 사용한 유전 알고리즘 구현

유전 알고리즘을 파이썬으로 구현하려면 다음 패키지를 사용할 수 있습니다.

a. NumPy - 배열 연산을 위해 사용됩니다.

b. matplotlib - 결과를 시각화하기 위해 사용됩니다.

다음은 간단한 유전 알고리즘 예제 코드입니다.

import numpy as np
import matplotlib.pyplot as plt

# 초기 집단 생성
def create_initial_population(population_size, chromosome_size):
    population = []
    for _ in range(population_size):
        chromosome = np.random.randint(2, size=chromosome_size)
        population.append(chromosome)
    return population

# 돌연변이 연산
def mutation(chromosome, mutation_rate):
    for gene_idx in range(len(chromosome)):
        if np.random.rand() < mutation_rate:
            chromosome[gene_idx] = 1 - chromosome[gene_idx]
    return chromosome

# 교차 연산
def crossover(parent1, parent2):
    crossover_point = np.random.randint(1, len(parent1) - 1)
    child1 = np.concatenate((parent1[:crossover_point], parent2[crossover_point:]))
    child2 = np.concatenate((parent2[:crossover_point], parent1[crossover_point:]))
    return child1, child2

# 선택 연산
def selection(population, fitness_values):
    parents_idx = np.random.choice(len(population), size=2, replace=False, p=fitness_values/np.sum(fitness_values))
    return population[parents_idx[0]], population[parents_idx[1]]

# 유전 알고리즘 실행
def genetic_algorithm(population_size, chromosome_size, mutation_rate, generations):
    population = create_initial_population(population_size, chromosome_size)
    best_fitness_history = []
    for _ in range(generations):
        fitness_values = np.random.rand(population_size)
        best_fitness = np.max(fitness_values)
        best_fitness_history.append(best_fitness)
        new_population = []
        for _ in range(population_size // 2):
            parent1, parent2 = selection(population, fitness_values)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutation(child1, mutation_rate)
            child2 = mutation(child2, mutation_rate)
            new_population.extend([child1, child2])
        population = new_population
    return population, best_fitness_history

# 유전 알고리즘 실행 예시
population_size = 100
chromosome_size = 10
mutation_rate = 0.05
generations = 100

population, best_fitness_history = genetic_algorithm(population_size, chromosome_size, mutation_rate, generations)

plt.plot(best_fitness_history)
plt.xlabel("Generation")
plt.ylabel("Best Fitness")
plt.title("Genetic Algorithm")
plt.show()

3. 결과 시각화

위의 코드를 실행하면 최적화 문제를 해결하기 위한 유전 알고리즘의 성능 변화를 확인할 수 있습니다. 세대에 따른 최적의 적합도를 시각적으로 나타내는 그래프를 볼 수 있습니다.

이렇게 파이썬을 사용하여 유전 알고리즘을 구현하고 최적화 문제를 해결할 수 있습니다. 유전 알고리즘은 다양한 영역에서 사용되며, 특히 복잡한 문제에 대한 근사적인 최적 솔루션을 찾는 데 유용합니다.