유전자 알고리즘: 선택·교차·돌연변이로 최적해를 찾는 법

다윈의 적자생존을 알고리즘으로 옮기면

유전자 알고리즘(GA)은 자연의 진화 메커니즘을 모방한 최적화 알고리즘이다. 1975년 John Holland에 의해 제안된 메타휴리스틱 탐색 방법으로, 복잡한 최적화 문제, 특히 전통적인 탐색 방법으로 해결하기 어려운 비선형 문제에 효과적이다. 생물학적 진화의 주요 개념인 선택(Selection), 교차(Crossover), 돌연변이(Mutation)를 컴퓨터 알고리즘으로 구현했으며, 병렬 처리가 가능하고 지역 최적해(Local Optima)에 빠질 가능성이 줄어든다.

다윈의 적자생존 이론 — "환경에 가장 적합한 개체가 생존하고 번식할 확률이 높다" — 에 기반해, 문제 해결을 위한 후보 해결책들을 개체(Individual)로 표현한다. 각 개체는 염색체(Chromosome)로 표현되며 이는 문제 변수들의 인코딩이고, 세대(Generation)를 거듭하며 진화를 통해 최적해에 접근한다.

이 탐색을 이루는 부품들

염색체 표현은 문제 특성에 따라 고른다. 0과 1로 구성된 이진 인코딩이 가장 기본적이고, 실수값으로 직접 표현하는 실수 인코딩, TSP(Traveling Salesman Problem)처럼 순서가 중요한 문제에 적합한 순열 인코딩, 유전 프로그래밍에서 프로그램 진화에 쓰는 트리 인코딩이 있다.

초기 집단은 무작위로 생성된 다양한 염색체들로 구성하며, 일반적으로 수십~수백 개의 개체로 이뤄진다. 집단의 다양성을 충분히 확보하는 것이 중요하다. 적합도 평가는 각 개체가 문제 해결에 얼마나 적합한지 측정하는 함수로, 문제의 특성에 따라 정의하며 최대화 문제인지 최소화 문제인지에 맞게 설계한다.

선택은 적합도에 비례해 선택 확률을 부여하는 룰렛 휠 선택, 무작위로 선택된 개체들 중 가장 적합도가 높은 개체를 고르는 토너먼트 선택, 상위 n개의 개체를 다음 세대로 무조건 전달하는 엘리트 선택 중에서 고른다. 교차는 한 지점을 기준으로 두 부모의 유전자를 교환하는 단일점 교차, 여러 지점을 기준으로 교환하는 다중점 교차, 각 위치마다 확률적으로 어느 부모의 유전자를 선택할지 정하는 균등 교차로 나뉜다. 돌연변이는 유전적 다양성을 유지하기 위해 낮은 확률로 유전자를 변형하는 연산으로, 이진 인코딩에서는 비트를 반전시키고 실수 인코딩에서는 가우시안 노이즈를 추가하는 식으로 구현한다. 종료 조건은 최대 세대 수 도달, 적합도 개선 없이 일정 세대 경과, 목표 적합도 달성 중 하나로 정한다.

루프 하나가 세대를 거듭하는 방식

⤢✕

초기 집단을 생성하고 적합도를 평가한 뒤, 종료 조건을 충족하지 않으면 선택 → 교차 → 돌연변이를 거쳐 새로운 세대를 만들고 다시 평가하는 루프를 반복한다.

의사 코드로 본 전체 흐름

function GeneticAlgorithm():
    population = generateInitialPopulation(populationSize)
    generation = 0

    while not terminationCriteriaMet():
        evaluateFitness(population)
        newPopulation = []

        // 엘리트 보존
        elites = selectElites(population, eliteCount)
        newPopulation.addAll(elites)

        while newPopulation.size < populationSize:
            parent1 = selectionMethod(population)
            parent2 = selectionMethod(population)

            if random() < crossoverRate:
                child1, child2 = crossover(parent1, parent2)
            else:
                child1, child2 = parent1, parent2

            mutate(child1, mutationRate)
            mutate(child2, mutationRate)

            newPopulation.add(child1)
            newPopulation.add(child2)

        population = newPopulation
        generation += 1

    return getBestIndividual(population)

최적화 문제부터 로봇 보행까지, GA가 쓰이는 곳

최적화 문제에서는 복잡한 다변수 함수의 최대·최소값을 찾는 함수 최적화, TSP·스케줄링·리소스 할당 같은 조합 최적화, VLSI 설계·경로 배선 최적화 같은 회로 설계 최적화에 쓰인다. 기계 학습에서는 최적 특성 부분집합을 고르는 특성 선택(Feature Selection), 인공 신경망의 초기 가중치나 구조를 최적화하는 신경망 가중치 최적화, 분류 규칙이나 퍼지 규칙을 생성하는 규칙 기반 시스템에 활용된다. 이미지 및 신호 처리에서는 의료 영상에서 특정 구조를 식별하는 이미지 분할, 복잡한 패턴 인식 문제 해결, 신호 처리를 위한 디지털 필터 설계에 쓰이고, 게임 AI 및 로봇 공학에서는 체스·오델로 같은 게임 전략 개발, 로봇의 최적 경로 탐색, 이족 보행 로봇의 안정적 걸음걸이를 최적화하는 로봇 보행 패턴에 활용된다.

배낭 문제로 손에 잡아보는 진화 과정

n개의 아이템(각각 가치 vi와 무게 wi)에 대해 총 무게 제한 W 이내에서 최대 가치를 얻는 아이템 조합을 찾는 문제다. 각 아이템의 선택 여부를 이진수로 표현하고(1: 선택, 0: 미선택), 적합도 함수는 선택된 아이템의 총 가치로 정의하되 총 무게가 제한을 초과하면 페널티를 부여한다.

⤢✕

진화 과정을 예로 들면, 적합도 비례 선택으로 개체2(0101)와 개체1(1010)이 선택되고, 단일점 교차로 두 번째 위치 이후를 교환해 자식1(0110)과 자식2(1001)가 만들어진다. 자식1의 네 번째 비트가 변경되는 돌연변이를 거쳐 0111이 되고, 새로운 세대의 적합도를 계산하며 이 과정을 반복한다.

전역 탐색이 주는 것과 치르는 비용

지역 최적해에 빠질 가능성이 낮은 전역 최적화, 여러 해결책을 동시에 탐색하는 병렬성, 다양한 해결책을 탐색할 수 있는 다양성, 미분 불가능·불연속·노이즈가 있는 환경에서도 효과적인 복잡한 탐색 공간 대응력, 변화하는 환경에 적응하는 적응성이 장점이다. 반면 많은 평가가 필요해 계산 비용이 높고, 집단 크기·교차율·돌연변이율 같은 최적의 매개변수를 결정하기 어려우며, 적절한 적합도 함수를 설계하기 어렵고, 항상 최적해를 찾는다는 보장이 없으며, 계산 시간으로 인해 실시간 응용에 제약이 따른다는 단점이 있다.

하이브리드와 병렬화가 그리는 다음 단계

GA와 시뮬레이테드 어닐링처럼 다른 최적화 알고리즘과 결합하는 하이브리드 접근법, GPU와 분산 컴퓨팅을 활용해 성능을 높이는 병렬 유전자 알고리즘, 진화 중 매개변수를 동적으로 조정하는 적응적 매개변수 제어, NSGA-II·SPEA2 같은 다중 목표 최적화 알고리즘인 멀티 오브젝티브 GA, 양자 컴퓨팅 개념을 결합한 양자 유전자 알고리즘, 프로그램 자체를 진화시키는 유전자 프로그래밍이 연구 동향으로 꼽힌다.

매개변수 설정과 적합도 함수 설계가 성능에 큰 영향을 미치지만, 전통적인 방법으로 해결하기 어려운 복잡하고 대규모의 탐색 공간을 가진 문제에는 여전히 효과적이라는 점에서 유전자 알고리즘은 최적화 분야에서 계속 발전하고 있다.