파이썬으로 멀티쓰레딩을 활용한 유전 알고리즘 구현하기

01 Oct 2023

python

유전 알고리즘(Genetic Algorithm)은 최적화 문제를 해결하는 데에 사용되는 휴리스틱 알고리즘입니다. 이 알고리즘은 유전자의 개념을 통해 해의 후보들을 표현하고, 적합도 함수를 통해 각 후보들을 평가하며, 교차와 돌연변이 연산을 통해 후보들을 섞고 개선합니다. 이러한 과정들을 반복해서 최적의 해를 찾습니다.

이번에는 파이썬을 이용해서 멀티쓰레딩을 활용한 유전 알고리즘을 구현해보겠습니다.

단계 1: 초기화

먼저, 해의 후보들을 초기화하는 단계입니다. 각 후보는 유전자로 표현되고, 이는 보통 이진수나 실수로 표현됩니다. 초기 해의 후보들은 랜덤하게 생성됩니다.

import random

# 초기 해의 후보 생성
def generate_candidate():
    # 후보의 유전자 표현 생성
    candidate = [random.randint(0, 1) for _ in range(10)]
    return candidate

candidates = [generate_candidate() for _ in range(100)]

단계 2: 적합도 평가

각 후보의 적합도를 평가하는 단계입니다. 적합도 평가 함수는 최적화하고자 하는 문제에 따라 다르게 정의됩니다. 여기서는 각 후보의 적합도를 간단히 합으로 계산해보겠습니다.

# 적합도 평가
def evaluate_fitness(candidate):
    fitness = sum(candidate)
    return fitness

fitness_scores = [evaluate_fitness(candidate) for candidate in candidates]

단계 3: 선택

선택 연산은 각 후보의 적합도에 기반하여 다음 세대의 후보들을 선택하는 단계입니다. 일반적으로 선택은 룰렛 휠 선택이나 토너먼트 선택 등으로 구현됩니다.

# 선택 연산
def selection(candidates, fitness_scores):
    total_fitness = sum(fitness_scores)
    probabilities = [fitness / total_fitness for fitness in fitness_scores]
    
    selected_candidates = random.choices(candidates, probabilities, k=len(candidates))
    return selected_candidates

selected_candidates = selection(candidates, fitness_scores)

단계 4: 교차와 돌연변이

이제 선택된 후보들을 교차와 돌연변이 연산을 통해 다음 세대의 후보들로 재구성해봅시다.

# 교차 연산
def crossover(candidate1, candidate2):
    crossover_point = random.randint(0, len(candidate1) - 1)
    child1 = candidate1[:crossover_point] + candidate2[crossover_point:]
    child2 = candidate2[:crossover_point] + candidate1[crossover_point:]
    return child1, child2

# 돌연변이 연산
def mutation(candidate):
    mutation_point = random.randint(0, len(candidate) - 1)
    mutated_candidate = candidate[:]
    mutated_candidate[mutation_point] = 1 - mutated_candidate[mutation_point]
    return mutated_candidate

# 교차와 돌연변이 연산 적용
next_generation = []
for i in range(0, len(selected_candidates), 2):
    candidate1 = selected_candidates[i]
    candidate2 = selected_candidates[i+1]
    
    child1, child2 = crossover(candidate1, candidate2)
    
    mutated_child1 = mutation(child1)
    mutated_child2 = mutation(child2)
    
    next_generation.extend([mutated_child1, mutated_child2])

위의 과정은 유전 알고리즘의 한 단계를 나타내는 것이며, 이를 반복함으로써 다음 세대의 후보들을 생성하고 최적의 해를 찾게됩니다.

#python #유전알고리즘 #멀티쓰레딩