유전 알고리즘을 활용한 주문 최적화 시스템 구현하기

안녕하세요! 오늘은 제가 직접 구현한 유전 알고리즘(Genetic Algorithm)을 통해 주문 최적화 문제를 해결하는 과정을 공유하려 합니다. 이 글에서는 코틀린(Kotlin)으로 작성된 유전 알고리즘의 구현 방법과 그 응용에 대해 알아보겠습니다.

유전 알고리즘이란?

유전 알고리즘은 자연 선택과 유전학의 원리에서 영감을 받은 최적화 알고리즘입니다. 복잡한 문제에 대한 해결책을 찾기 위해 유전적 진화의 과정을 시뮬레이션합니다. 간단히 말해, 여러 해결책(개체)들이 세대를 거듭하며 더 좋은 해결책으로 진화해가는 과정입니다.

문제 정의: 주문 최적화

이번 프로젝트에서는 주문(Order)과 상품(SKU)으로 구성된 시스템에서, 최소한의 다양한 상품을 포함하는 주문 조합을 찾는 문제를 해결하고자 했습니다. 적합도(fitness)는 주문 그룹에 포함된 고유 상품 ID의 개수로 정의했으며, 이 값이 낮을수록 더 좋은 해결책입니다. 즉, 더 적은 종류의 SKU로 주문을 처리하는 것이 목표입니다.

코드 구현

1. 주요 클래스 정의

먼저 필요한 데이터 모델을 정의했습니다:

class Order(
    val orderId: String = uuid(),
    val skus: MutableList<OrderSku>,
)

class OrderSku(
    val skuId: String,
    val quantity: Long,
)

class Individual(
    val orders: MutableList<Order>,
) {
    val fitness: Long = calculateFitness()

    fun calculateFitness(): Long = orders
        .flatMap { it.skus }
        .map { it.skuId }
        .toSet().size.toLong()
}

여기서 Individual은 유전 알고리즘의 개체를 나타내며, Order 리스트를 포함합니다. 각 Order는 OrderSku 리스트로 구성됩니다. 개체의 적합도는 모든 주문에 포함된 고유 상품 ID의 개수이며, 이 값이 낮을수록 더 좋은 해결책입니다.

2. 유전 알고리즘 구현

순서도는 아래와 같습니다.

1. 시작

2. 초기 개체군 생성

3. 신규 세대 개체군 생성

4. 앨리트 개체 필터링

5. 교배 확률에 확인

   1. 교배 확률이 높은 경우, 교배

   2. 교배 확률이 낮은 경우, 돌연변이

6. 최대 세대가 확인 및 2번 반복

7. 종료

알고리즘의 핵심은 GenerationAlgorithm 클래스에 구현했습니다:

class GenerationAlgorithm(
    private val config: Config = Config(),
) {
    data class Config(
        val maxGenerationCount: Int = 100,
        val eliteRatio: Double = 0.3,
        val crossRatio: Double = 0.5,
        val initSkuKindCount: Int = 1000,
        val initOrderCount: Int = 1000,
    )

    fun cross(i1: Individual, i2: Individual): MutableList<Individual> {
        val mixedOrders = (i1.orders + i2.orders).toMutableList()
        mixedOrders.shuffle()
        return mutableListOf(
            Individual(mixedOrders.take(mixedOrders.size / 2).toMutableList()),
            Individual(mixedOrders.takeLast(mixedOrders.size / 2).toMutableList()),
        )
    }

    fun mutation(i1: Individual, i2: Individual): MutableList<Individual> {
        val u = i1.orders.random()
        val v = i2.orders.random()

        i1.orders.remove(u)
        i2.orders.remove(v)

        i1.orders.add(v)
        i2.orders.add(u)

        return mutableListOf(i1, i2)
    }

    fun calculate() {
        // 초기 데이터 설정 및 알고리즘 실행
        // ...
    }
}

이 구현에는 다음과 같은 주요 매개변수가 있습니다:

• maxGenerationCount: 최대 세대 수 (100)

• eliteRatio: 엘리트 비율 (30%)

• crossRatio: 교차 연산 확률 (50%)

• initSkuKindCount: 초기 SKU 종류 수 (1000)

• initOrderCount: 초기 주문 수 (1000)

3. 유전 연산자: 교차와 돌연변이

이번 구현에서는 두 가지 주요 유전 연산자를 사용했습니다:

교차(Crossover) 연산

fun cross(i1: Individual, i2: Individual): MutableList<Individual> {
    val mixedOrders = (i1.orders + i2.orders).toMutableList()
    mixedOrders.shuffle()
    return mutableListOf(
        Individual(mixedOrders.take(mixedOrders.size / 2).toMutableList()),
        Individual(mixedOrders.takeLast(mixedOrders.size / 2).toMutableList()),
    )
}

두 부모 개체의 주문들을 합치고 무작위로 섞은 후, 절반씩 나누어 두 개의 자식 개체를 생성합니다.

돌연변이(Mutation) 연산

fun mutation(i1: Individual, i2: Individual): MutableList<Individual> {
    val u = i1.orders.random()
    val v = i2.orders.random()

    i1.orders.remove(u)
    i2.orders.remove(v)

    i1.orders.add(v)
    i2.orders.add(u)

    return mutableListOf(i1, i2)
}

두 개체 사이에서 무작위로 선택된 주문을 교환합니다. 각 개체에서 하나의 주문을 제거한 후, 서로의 주문을 추가합니다. 이 방식은 지역 최적해에서 벗어나 더 넓은 해 공간을 탐색할 수 있게 해줍니다.

4. 알고리즘 동작 과정

calculate() 메서드에서 알고리즘의 주요 로직이 실행됩니다:

1. 초기 데이터 생성:

   • 지정된 수의 SKU ID를 생성합니다.

   • 각 주문은 1~5개의 랜덤한 SKU를 포함하도록 합니다.

   • 주문들을 10개씩 묶어 초기 개체군을 생성합니다.

2. 진화 과정:

   • 최대 100세대까지 반복합니다.

   • 각 세대마다:

     • 적합도에 따라 개체군을 정렬합니다. 적합도가 낮은(고유 SKU 개수가 적은) 개체가 더 우수합니다.

     • 상위 30%(엘리트)는 직접 다음 세대로 전달합니다.

     • 나머지 70%는 교차 또는 돌연변이 연산을 통해 새로운 개체를 생성합니다.

     • 교차와 돌연변이 중 어떤 연산을 적용할지는 crossRatio 매개변수에 따라 결정됩니다(기본값 50%).

     • 각 세대의 최고 적합도를 출력합니다.

결과 분석

알고리즘을 실행하면 세대가 지남에 따라 적합도(고유 SKU ID의 개수)가 점차 감소하는 것을 확인할 수 있습니다. 이는 더 적은 종류의 SKU로 주문을 처리할 수 있게 되었다는 것을 의미합니다. 다음은 각 세대별 최고 적합도의 변화를 보여주는 출력 예시입니다:

Maximum individual: 42
[Generation 0]  Maximum individual: 39
[Generation 1]  Maximum individual: 36
[Generation 2]  Maximum individual: 32
...
[Generation 99]  Maximum individual: 15

이 최적화의 실제 의미

이러한 최적화가 실제로 의미하는 바는 무엇일까요? 실제 비즈니스 환경에서 적은 종류의 SKU로 주문을 처리하면 다음과 같은 이점이 있습니다:

1. 재고 관리 단순화: 더 적은 종류의 SKU를 관리하므로 재고 관리가 쉬워집니다.

2. 보관 비용 절감: 다양한 SKU를 보관하는 데 필요한 공간과 비용을 줄일 수 있습니다.

3. 주문 처리 효율성 증가: 적은 종류의 SKU를 처리하므로 피킹, 패킹 과정이 단순해집니다.

4. 공급망 최적화: 더 적은 공급업체와 거래할 수 있어 공급망 관리가 쉬워집니다.

돌연변이 연산의 중요성

이번 구현에서는 교차 연산과 함께 돌연변이 연산을 추가했습니다. 이는 매우 중요한 개선 사항입니다. 돌연변이 연산은 다음과 같은 이점을 제공합니다:

1. 지역 최적해 탈출: 돌연변이는 현재 해 공간에서 벗어나 새로운 영역을 탐색할 수 있게 해줍니다.

2. 다양성 유지: 개체군의 다양성을 유지하여 조기 수렴을 방지합니다.

3. 더 넓은 탐색: 교차 연산만으로는 발견하기 어려운 해결책을 발견할 수 있습니다.

우리의 구현에서는 두 개체 간에 주문을 교환하는 방식의 돌연변이를 사용했습니다. 이는 단순하지만 효과적인 방법으로, 각 세대마다 50%의 확률로 적용됩니다.

개선 가능성

현재 구현에도 여전히 다음과 같은 개선 가능성이 있습니다:

1. 다양한 돌연변이 전략:

   • 현재는 주문 교환만 구현되어 있지만, SKU 수준의 돌연변이도 고려해볼 수 있습니다.

   • 예를 들어, 주문 내의 특정 SKU를 다른 SKU로 대체하는 방식 등이 있습니다.

2. 적합도 함수 개선:

   • 현재는 단순히 고유 SKU 개수만 고려합니다.

   • 각 SKU별 재고 비용, 처리 시간 등 추가 요소들도 고려하도록 확장할 수 있습니다.

3. 선택 방법 다양화:

   • 루울렛 휠 선택, 토너먼트 선택 등 다른 선택 방법을 시도해볼 수 있습니다.

4. 매개변수 튜닝:

   • 엘리트 비율, 교차 확률 등의 매개변수를 다양하게 시도하여 최적의 조합을 찾을 수 있습니다.

결론

이 프로젝트를 통해 유전 알고리즘을 활용하여 주문 최적화 문제를 해결하는 방법에 대해 알아보았습니다. 코틀린의 간결한 문법과 함수형 프로그래밍 기능을 활용하여 복잡한 알고리즘을 비교적 쉽게 구현할 수 있었습니다.

특히 교차 연산과 돌연변이 연산을 적절히 조합하여 더 효과적인 탐색을 가능하게 했습니다. 이 두 연산자는 유전 알고리즘의 핵심 요소로, 함께 사용할 때 더 강력한 결과를 얻을 수 있습니다.

Github : 유전 알고리즘 구현 코드

참고 자료

• 마켓 컬리 : 컬리는 물류 최적화 문제를 어떻게 풀고 있을까? - 1부

• [수리적 최적화] 유전 알고리즘 (Genetic Algorithm)과 전역 최적화