유전 알고리즘으로 블랙박스 최적화 문제 다루기

해 공간을 세대 단위로 탐색하는 방식

유전 알고리즘(Genetic Algorithm, GA)은 생물의 선택·교차·돌연변이 원리를 빌려 해 공간에서 더 나은 해를 점진적으로 찾는 메타휴리스틱 최적화 기법이다. 전역 탐색이 필요한 비선형·비미분·블랙박스 목적함수, 이산 또는 혼합 변수, 제약이 있는 문제와 다봉형(multi-modal) 지형에 사용할 수 있다.

각 후보 해의 품질은 적합도(Fitness)로 평가한다. 적합도가 높은 개체의 유전정보는 선택을 통해 다음 세대로 전달되고, 교차 과정에서 서로 다른 해의 부분 구조가 결합한다. 돌연변이는 집단이 한 영역에 갇히지 않도록 탐색 범위를 넓힌다.

다음 세대를 만드는 연산

적합도에 따른 선택

선택(Selection)은 높은 적합도를 가진 개체의 유전정보를 보존하고 확산하는 단계다. 룰렛휠, 토너먼트, 순위 선택 등을 사용할 수 있으며, 이때 선택 압력(selection pressure)이 수렴 속도와 조기수렴 사이의 균형을 좌우한다.

고적합도 개체에 지나치게 편향되면 집단의 다양성이 무너질 수 있다. 엘리티즘과 다중 샘플 토너먼트는 이 균형을 조절하는 수단이다.

서브구조를 조합하는 교차

교차(Crossover)는 부모 해의 유용한 서브구조(schema)를 결합해 탐색을 진행한다. 이산 표현에는 단일 포인트, 이중 포인트, 균등 교차를 쓸 수 있고, 실수 표현에는 SBX, BLX-α, 아리서메틱 교차가 사용된다.

교차율(pc)은 0.6~0.9 범위에서 시작할 수 있다. 다만 순열 문제인지 연속 변수 문제인지에 따라 적절한 연산자가 달라진다.

탐색 폭을 남겨 두는 돌연변이

돌연변이(Mutation)는 국소 최적에 머무는 일을 줄이고 전역 탐색을 돕는다. 비트플립, 가우시안/코시 노이즈, 순열을 위한 교환·삽입 변이가 여기에 해당한다.

돌연변이율(pm)이 너무 낮으면 조기수렴으로 이어지고, 너무 높으면 탐색이 랜덤워크처럼 변한다. 적응형 또는 자가적응형 스케줄을 활용할 수 있다.

목적함수와 제약을 담는 적합도

적합도 함수는 해의 품질을 수치로 표현한다. 단일 목적뿐 아니라 다목적(MOEA) 문제에도 구성할 수 있다. 제약은 정적·동적 패널티, 수리(Repair), 불가능해 제거, 랭킹 우선 규칙으로 처리한다.

적합도 스케일링과 정규화는 선택 편향을 제어하는 데 쓰이며, 캐싱과 병렬화는 평가 비용을 낮추는 방법이다.

교체와 중단 시점

세대 교체는 전세대 교체(generational), (μ+λ), 엘리트 보존 방식으로 설계할 수 있다. 종료 조건은 세대 또는 평가 횟수 예산, 개선 정체(stagnation), 목표 적합도 도달 여부로 둔다.

초기 집단에서 최적 해까지

입력으로는 초기 집단 크기 N, 변수 범위와 암호화 방식, pc/pm, 제약 조건, 평가 예산이 필요하다. 적합도를 평가한 뒤 선택·교차·돌연변이를 수행하고, 수리(Repair) 또는 경계 클리핑을 거쳐 자식 개체를 다시 평가한다. 이후 교체 전략에 따라 다음 세대를 구성한다.

출력은 최적 해의 추정치, 최적 적합도, 그리고 기록된 진행 히스토리다.

⤢✕

비정상 적합도(NaN/Inf)가 발생하면 수리 후 재평가하거나 큰 패널티를 부여한다. 제약 위반은 패널티, 수리 휴리스틱, 불가능해 필터링 가운데 한 가지 방식을 일관되게 적용한다. 엔트로피 또는 분산 임계치 하락으로 다양성 붕괴가 감지되면 pm을 올리거나 리스타트를 적용할 수 있다.

선택 방식은 집단의 성질에 맞춰 고른다

선택 방법	성능(수렴 속도)	확장성(대규모 N)	일관성(분산)	안정성(조기수렴)	운영 편의(튜닝)
룰렛휠(비례)	중	중	중하	중하	상
토너먼트(k=2~5)	중상	상	중상	중	중상
순위 기반	중	상	상	상	중

초기 탐색기에는 토너먼트(k=3)를 권장하며, 고노이즈 환경이나 고편향 적합도에서는 순위 기반 선택을 사용할 수 있다. 엘리트는 1~5% 보존해 수렴 안정성을 확보할 수 있지만, 과도한 보존은 다양성을 낮춘다.

표현 방식이 달라지면 연산자도 달라진다

AutoML과 하이퍼파라미터 최적화에서는 모델·파라미터 공간과 검증 스코어 함수를 입력으로 두고, 교차검증 기반 적합도 평가와 토너먼트 선택, SBX 또는 가우시안 변이를 조합할 수 있다. 결과는 최고 성능 조합과 성능-복잡도 파레토 전선(선택)이다.

생산 스케줄링이나 라우팅처럼 순열 표현이 필요한 문제에서는 작업-기계 매핑과 마감·용량 제약을 다룬다. PMX·오더 교차, 교환·삽입 변이, 지연 패널티를 적용해 지연 최소 스케줄과 로드 밸런스 개선 지표를 얻는다.

네트워크 설계와 플로우 최적화에서는 토폴로지 후보, 링크 비용, 신뢰도를 입력으로 받고 지연·가용성을 포함한 다목적 적합도와 제약 기반 수리를 사용한다. 비용-신뢰도 균형 해와 경로 집합이 결과가 된다.

특징 선택은 이진 표현에 맞는다. 피처 집합과 평가 모델을 입력으로 두고 비트플립 변이, 엘리트 보존, 과적합 패널티를 적용해 성능을 유지하거나 향상시키는 최소 피처 세트를 찾는다.

실수 벡터를 이용한 Python 구현

이 예제는 Python 3.9+, numpy 1.24+ 환경에서 라스트리진 함수의 단일 목적 최소화를 수행한다. 실수 벡터 표현, 경계 클리핑, 토너먼트 선택, 아리서메틱 교차, 가우시안 변이, 엘리트 보존을 사용한다.

# Genetic Algorithm for Rastrigin minimization (real-coded)
# Python 3.9+, numpy 1.24+
import numpy as np

rng = np.random.default_rng(42)

def rastrigin(x):
    A = 10.0
    return A * x.shape[-1] + np.sum(x**2 - A * np.cos(2 * np.pi * x), axis=-1)

def fitness(x):
    # GA는 기본적으로 최대화 프레임. 최소화 목적을 음수 적합도로 변환
    val = rastrigin(x)
    # NaN/Inf 방어
    if np.any(~np.isfinite(val)):
        return -1e30
    return -val

def init_pop(pop_size, dim, low, high):
    return rng.uniform(low, high, size=(pop_size, dim))

def tournament_select(fit, k=3):
    n = len(fit)
    idx = rng.integers(0, n, size=(n, k))
    best = idx[np.arange(n), np.argmax(fit[idx], axis=1)]
    return best

def arithmetic_crossover(p1, p2, pc=0.9):
    if rng.random() > pc:
        return p1.copy(), p2.copy()
    alpha = rng.random(p1.shape)
    c1 = alpha * p1 + (1 - alpha) * p2
    c2 = alpha * p2 + (1 - alpha) * p1
    return c1, c2

def gaussian_mutation(x, pm=0.1, sigma=0.1, low=-5.12, high=5.12):
    mask = rng.random(x.shape) < pm
    x_mut = x + mask * rng.normal(0, sigma, size=x.shape)
    return np.clip(x_mut, low, high)

def evolve(pop, low, high, pc=0.9, pm=0.05, sigma=0.1, elite_frac=0.05, max_gen=200, stagnation=50):
    pop_size, dim = pop.shape
    best_fit = -np.inf
    best = None
    gen_best_hist = []
    no_improve = 0

    for gen in range(max_gen):
        fit = fitness(pop)
        # 엘리트 보존
        elite_count = max(1, int(pop_size * elite_frac))
        elite_idx = np.argsort(fit)[-elite_count:]
        elites = pop[elite_idx]

        # 선택
        parent_idx = tournament_select(fit, k=3)
        parents = pop[parent_idx]

        # 교차/변이
        offsprings = []
        for i in range(0, pop_size - elite_count, 2):
            p1, p2 = parents[i], parents[min(i+1, pop_size-1)]
            c1, c2 = arithmetic_crossover(p1, p2, pc=pc)
            c1 = gaussian_mutation(c1, pm=pm, sigma=sigma, low=low, high=high)
            c2 = gaussian_mutation(c2, pm=pm, sigma=sigma, low=low, high=high)
            offsprings.append(c1); offsprings.append(c2)
        offspr = np.vstack(offsprings)[:pop_size - elite_count]

        # 합치기(세대교체 + 엘리트)
        pop = np.vstack([elites, offspr])

        # 진행 상황
        cur_fit = fitness(pop)
        cur_best_idx = np.argmax(cur_fit)
        cur_best_fit = cur_fit[cur_best_idx]
        gen_best_hist.append(cur_best_fit)
        if cur_best_fit > best_fit:
            best_fit = cur_best_fit
            best = pop[cur_best_idx].copy()
            no_improve = 0
        else:
            no_improve += 1

        if no_improve >= stagnation:
            break

    return best, -best_fit, np.array(gen_best_hist)

if __name__ == "__main__":
    dim = 10
    pop_size = 120
    low, high = -5.12, 5.12
    pop = init_pop(pop_size, dim, low, high)
    best_x, best_obj, hist = evolve(pop, low, high, pc=0.9, pm=0.08, sigma=0.15, elite_frac=0.05, max_gen=300, stagnation=60)
    print("Best objective (Rastrigin min):", best_obj)
    print("Best solution (first 5 dims):", np.round(best_x[:5], 4))

python main.py로 실행할 수 있다. 평가 비용을 줄여야 한다면 fitness 병렬화(multiprocessing)를 적용한다. 수십수백 세대 내 Rastrigin 목적값 수수십 단위까지 감소하며, 정확한 수렴 수준은 랜덤 시드와 파라미터에 의존한다.

수렴 속도와 다양성 사이의 운영 판단

선택 압력이 높으면 수렴은 빨라지지만 조기수렴 위험이 커진다. 낮은 압력은 다양성을 유지하는 대신 수렴을 지연시킨다. 적응형 pm/pc, 리스타트, 니칭/NBC(근접군) 전략, 크라우딩은 다양성 관리에 사용할 수 있다.

제약 처리에서는 문제 지식을 활용한 수리가 성능 면에서 우수할 수 있으나 구현 복잡도가 증가한다. 패널티 방식은 단순하지만 계수 튜닝에 민감하다. 적합도 평가는 캐싱, 서로게이트(보간/경사 없음 모델), 얼리 스톱 검증으로 최적화할 수 있다.

적합도 평가를 병렬화하면 워커 수에 비례한 가속과 벽시계 시간 단축을 기대할 수 있다. I/O 바운드 환경에서는 비동기 GA(steady-state)를 고려한다. 랜덤 시드 고정, 로그·히스토리 저장, 파라미터 스윕 자동화는 재현 가능성과 관측성을 위한 운영 항목이다.

블랙박스 문제에서의 적용 범위

경사나 해석이 제공되지 않는 블랙박스 문제에서는 그리드·랜덤 탐색 대비 동일 예산 내 우수 해 발견 확률 상승을 기대할 수 있다. 적합도 평가를 병렬화하면 벽시계 시간이 줄고, 워커 수에 비례한 가속을 기대할 수 있다.

다봉형·불연속·잡음 환경에서도 안정적으로 탐색할 수 있으며, 순열·이진·연속 표현에 맞는 연산자를 선택해 적용 범위를 넓힌다. 제약 반영 방식과 도메인 지식을 적합도 및 수리 과정에 넣기 쉬운 점도 유전 알고리즘의 장점이다.