Colin's Blog
파이썬을 사용하여 유전 알고리즘으로 최적화된 경로 탐색하기

유전 알고리즘은 최적화 문제를 풀기 위한 다목적 최적화 알고리즘 중 하나입니다. 이 알고리즘은 생물의 진화 원리를 모방하여 문제의 해를 찾아냅니다. 이번 글에서는 파이썬을 사용하여 유전 알고리즘을 구현하고, 최적화된 경로 탐색 문제를 해결하는 방법에 대해 알아보겠습니다.

문제 설명

우리는 N개의 도시가 있는 지도에서 최적의 경로를 찾고자 합니다. 각 도시 사이의 거리는 미리 주어지며, 모든 도시를 한번씩 방문한 후 다시 시작 도시로 돌아와야 합니다. 이를 TSP (Traveling Salesman Problem) 문제라고 합니다. 유전 알고리즘을 사용하여 TSP 문제를 푸는 방법을 알아보겠습니다.

알고리즘 구현

먼저, 유전 알고리즘을 구현하기 위해 필요한 요소들을 정의합니다.

  1. 개체 (Individual): 경로의 후보를 나타내는 개체입니다. 각 도시를 방문하는 순서가 개체의 유전자로 표현됩니다.
  2. 유전자 (Genes): 개체를 구성하는 유전자로, 도시의 순서를 나타냅니다.
  3. 적합도 함수 (Fitness Function): 개체의 적합도를 측정하는 함수로, 경로의 길이를 측정할 수 있습니다.
  4. 선택 연산자 (Selection Operator): 개체들 중에서 다음 세대를 형성할 개체들을 선택하는 연산자입니다.
  5. 교차 연산자 (Crossover Operator): 선택된 개체들을 바탕으로 새로운 개체를 생성하는 연산자입니다.
  6. 돌연변이 연산자 (Mutation Operator): 개체의 유전자를 변이시키는 연산자입니다.

다음은 파이썬으로 유전 알고리즘을 구현한 예시 코드입니다.

import random

# 도시 사이의 거리 정보
distances = {
    "A": {"B": 10, "C": 15, "D": 20},
    "B": {"A": 10, "C": 25, "D": 35},
    "C": {"A": 15, "B": 25, "D": 30},
    "D": {"A": 20, "B": 35, "C": 30},
}

# 개체 클래스 정의
class Individual:
    def __init__(self, genes):
        self.genes = genes
        
    def fitness(self):
        # 경로의 길이 계산
        total_distance = 0
        for i in range(len(self.genes) - 1):
            total_distance += distances[self.genes[i]][self.genes[i+1]]
        return total_distance

# 초기 개체 집합 생성
population_size = 50
initial_genes = ['A', 'B', 'C', 'D']
population = [Individual(random.sample(initial_genes, len(initial_genes))) for _ in range(population_size)]

# 진화하는 과정 반복
iterations = 100
for _ in range(iterations):
    # 개체 선택 및 교차 연산
    selected = random.sample(population, 10)
    offspring = []
    for i in range(0, len(selected), 2):
        parent1 = selected[i]
        parent2 = selected[i+1]
        # 교차 연산 수행
        child = Individual(parent1.genes[:2] + parent2.genes[2:])
        offspring.append(child)
    
    # 돌연변이 연산
    for child in offspring:
        if random.random() < 0.2:
            child.genes[random.randint(0, len(child.genes)-1)] = random.choice(initial_genes)
    
    # 다음 세대 생성
    population = offspring

# 최적 해 출력
best_individual = min(population, key=lambda x: x.fitness())
print("Best path:", best_individual.genes)
print("Distance:", best_individual.fitness())

위 코드는 초기 개체 집합을 생성한 후, 지정된 횟수만큼 개체 선택, 교차, 돌연변이를 반복하여 최적의 경로를 찾습니다. 마지막으로, 최적 해의 경로와 거리를 출력합니다.

이제 유전 알고리즘을 사용하여 최적화된 경로 탐색 문제를 해결하는 방법을 알게 되었습니다. 파이썬을 사용하면 쉽게 구현할 수 있으며, 다양한 최적화 문제에 유용하게 활용할 수 있습니다.

#AI #유전알고리즘

© 2018 Colin. All rights reserved.