[공간 최적화] P-centdian을 유전자 알고리즘으로 구현하기

파이썬으로 Genetic Algorithm을 이용해 P-centdian을 구현한 코드

 

 

import pandas as pd


# 엑셀 파일 로드 (예: 'data.xlsx')
df = pd.read_csv('나의경로.csv', encoding = 'cp949')

# 거리 데이터 예상
# - 'origin'과 'destination' 열에는 경위도 좌표가 있어야 함
# - 'distance_fin' 열에는 두 위치 사이의 거리가 있어야 함
print(df.head())

import pandas as pd
import random
import numpy as np

def initialize_population(df, p, population_size):
    Dids = df['Did'].unique().tolist()
    population = [random.sample(Dids, p) for _ in range(population_size)]
    return population

def fitness(df, chromosome, w):
    subset_df = df[df['Did'].isin(chromosome)].copy()
    subset_df = subset_df.loc[subset_df.groupby('Oid')['distance'].idxmin()]
    Zmedian = (subset_df['distance'] * subset_df['demand']).sum()
    weighted_distances = subset_df['distance'] * subset_df['demand']
    Zcenter = weighted_distances.max()
    return w * Zmedian + (1 - w) * Zcenter

def crossover(parent1, parent2):
    common = set(parent1) & set(parent2)
    diff1 = set(parent1) - common
    diff2 = set(parent2) - common

    child1 = list(common.union(set(random.sample(list(diff1.union(diff2)), len(diff1)))))
    child2 = list(common.union(set(random.sample(list(diff1.union(diff2)), len(diff2)))))


    return child1, child2

def mutate(chromosome, mutation_rate, Dids):
    for i in range(len(chromosome)):
        if random.random() < mutation_rate:
            chromosome[i] = random.choice(list(Dids - set(chromosome)))
    return chromosome





def genetic_algorithm(df, p, w, population_size=100, generations=100, mutation_rate=0.01):
    # w의 범위 검증
    if not (0 <= w <= 1):
        raise ValueError("w should be in the range [0, 1]")
    Dids = set(df['Did'].unique())
    population = initialize_population(df, p, population_size)

    for generation in range(generations):
        scores = [(chromosome, fitness(df, chromosome, w)) for chromosome in population]
        scores.sort(key=lambda x: x[1])

        # Elite selection: keep the top 10% of the population
        new_population = [chromosome for chromosome, _ in scores[:population_size // 10]]

        # Crossover and mutation to create new population
        while len(new_population) < population_size:
            parent1, parent2 = random.sample(population, 2)
            child1, child2 = crossover(parent1, parent2)
            new_population.append(mutate(child1, mutation_rate, Dids))
            if len(new_population) < population_size:
                new_population.append(mutate(child2, mutation_rate, Dids))

        population = new_population

    best_chromosome, best_score = scores[0]

    # 각 Oid에 대한 최적의 Did 할당 찾기
    assignment = {}
    best_subset_df = df[df['Did'].isin(best_chromosome)].copy()
    idx_min_distance = best_subset_df.groupby('Oid')['distance'].idxmin()
    optimal_dids = best_subset_df.loc[idx_min_distance]

    for _, row in optimal_dids.iterrows():
        assignment[row['Oid']] = row['Did']

    return {'combination': best_chromosome, 'final_obj': best_score, 'assignment': assignment}


# 사용 예
# p는 시설의 개수, w는 가중치입니다.
# df는 사용자가 지정한 데이터 프레임입니다.
p = 15
w = 0.6
result = genetic_algorithm(df, p, w)
print(result)

 

이와 같이 할당된 결과도 알려준다.

 

 

 

 

 

 

네, 이 코드는 유전 알고리즘을 사용하여 특정 문제의 최적해를 찾는 코드입니다. 주어진 문제는 일종의 시설 위치 결정 문제로 추정되며, 데이터 프레임(df)에는 고려해야 할 위치(Did)와 이러한 위치 간의 거리와 수요(demand)에 관한 정보가 포함되어 있습니다.

코드의 주요 부분들에 대한 설명은 다음과 같습니다.

1. **initialize_population 함수**
   - 초기 인구(population)를 설정합니다.
   - `Did`의 고유한 값들 중에서 `p` 개의 위치를 무작위로 선택하여 개체(chromosome)를 만듭니다.
   - 이를 `population_size` 만큼 반복하여 초기 인구를 생성합니다.

2. **fitness 함수**
   - 주어진 chromosome의 적합도를 평가합니다.
   - `Zmedian`은 선택된 위치들의 거리에 수요를 곱한 값들의 합계입니다.
   - `Zcenter`는 선택된 위치들의 거리와 수요의 곱 중 최대 값입니다.
   - 적합도는 `w * Zmedian`과 `(1 - w) * Zcenter`의 합계로 계산됩니다.

3. **crossover 함수**
   - 두 부모 개체에서 자식 개체를 생성하는 교차(crossover) 연산을 수행합니다.
   - 두 부모 개체에서 공통으로 가지고 있는 위치와 각각만 가지고 있는 위치를 구분합니다.
   - 자식 개체는 공통 위치와 두 부모가 각각만 가지고 있는 위치 중 일부를 무작위로 선택하여 생성됩니다.

4. **mutate 함수**
   - 개체의 위치를 무작위로 변형하는 돌연변이(mutate) 연산을 수행합니다.
   - 각 위치는 `mutation_rate`의 확률로 다른 위치로 대체됩니다.

5. **genetic_algorithm 함수**
   - 주어진 매개변수와 데이터 프레임을 사용하여 유전 알고리즘을 수행합니다.
   - 각 세대에서는 적합도를 평가하고, 가장 적합한 상위 10%의 개체를 다음 세대에 그대로 전달합니다.
   - 나머지 90%의 개체는 교차와 돌연변이 연산을 통해 생성됩니다.
   - 이 과정을 지정된 세대 수만큼 반복합니다.
   - 마지막으로 가장 적합한 개체와 그 적합도를 반환합니다.

6. **사용 예**
   - 예제에서는 `p`, `w`, 그리고 사용자가 지정한 데이터 프레임 `df`를 사용하여 유전 알고리즘을 실행하고 결과를 출력합니다.

이 코드를 통해 주어진 데이터 프레임의 위치들 중에서 `p` 개의 위치를 선택하여 최적의 시설 위치를 결정하려는 것으로 보입니다.