유전 알고리즘을 활용한 버티포트 선정 예제

chat GPT를 이용하여 랜덤한 도시들에 랜덤한 fitness score을 매겨 유전 알고리즘으로 최적의 버티포트 지역을 선정하는 알고리즘을 가져와봤다.

 

 

import numpy as np
import random

# 서울의 10개 주요 지점 예제
possible_locations = ['강남', '시청', '판교', '신림', '화곡', '한강', '종로', '동대문', '목동', '여의도']

# 개체 생성 (5개의 버티포트 선택)
def create_individual():
    return random.sample(possible_locations, 5)

# 초기 개체군 생성
def initialize_population(size=10):
    return [create_individual() for _ in range(size)]


# 적합도 평가 함수 (수요 - 비용 기준)
def fitness(individual):
    demand_score = np.random.uniform(0, 100)  # 가상의 수요 점수
    cost_penalty = len(set(individual)) * 5    # 버티포트 개수에 따른 비용 패널티
    # Ensure fitness is non-negative by taking the maximum with 0
    return max(0, demand_score - cost_penalty)

# 선택 과정 (룰렛 휠 선택)
def selection(population):
    scores = [fitness(ind) for ind in population]
    # Avoid division by zero if all scores are 0
    total_score = sum(scores)
    if total_score == 0:
        probs = [1/len(population)] * len(population)  # Assign equal probabilities if total score is 0
    else:
        probs = [s / total_score for s in scores]
    return population[np.random.choice(len(population), p=probs)]


# 교차 과정 (2점 교차)
def crossover(parent1, parent2):
    idx = sorted(random.sample(range(5), 2))
    child = parent1[:idx[0]] + parent2[idx[0]:idx[1]] + parent1[idx[1]:]
    # Ensure child always has 5 elements
    child = list(set(child))
    while len(child) < 5:
        child.append(random.choice(possible_locations)) # Add random locations if needed
    return child[:5]

# 돌연변이 과정 (5% 확률)
def mutation(individual, mutation_rate=0.05):
    if random.random() < mutation_rate:
        # Check if the individual has at least one element before mutating
        if individual: 
            individual[random.randint(0, len(individual) - 1)] = random.choice(possible_locations)
    return individual

# GA 실행
def genetic_algorithm(iterations=50, pop_size=10):
    population = initialize_population(pop_size)
    for _ in range(iterations):
        new_population = []
        for _ in range(pop_size // 2):
            parent1, parent2 = selection(population), selection(population)
            child1, child2 = crossover(parent1, parent2), crossover(parent2, parent1)
            new_population += [mutation(child1), mutation(child2)]
        population = sorted(new_population, key=fitness, reverse=True)[:pop_size]  # 적합도 기준 상위 개체 유지
    return population[0]  # 최적 해 반환


# 실행
optimal_solution = genetic_algorithm()
print("최적 버티포트 위치:", optimal_solution)
# 최적 버티포트 위치: ['목동', '신림', '여의도', '동대문', '종로']  => 때에 따라 다름