SKU Consolidation (4) - 몬테 카를로 알고리즘 이해하기

SKU Consolidation 4부를 이어 씁니다.

 

지난 글 소개

https://learn-and-run.tistory.com/216

https://learn-and-run.tistory.com/217

https://learn-and-run.tistory.com/219

SKU Consolidation (3) - 선정 된 박스 간 통합 최적화 방법론

 

 

이번 글 개요

몬테카를로 알고리즘이 왜 필요한가?

• 몬테카를로 알고리즘이 왜 필요한가?
• 몬테카를로 알고리즘은 무엇인가?

 

 

몬테카를로 알고리즘이 왜 필요한가?

SKU Consolidation 최적화를 위해서는 최적화된 로케이션 선정과 로케이션 간 최적화된 이동이 필수다. 가장 나은 선택임을 알기 위해서는 가지고 있는 모든 선택지를 알 수 있어야 한다. 하지만, 이전에 논의되었듯 로케이션이 4만개 중 100개의 로케이션을 선택할 때 발생 가능한 경우의 수는 1경을 19번 제곱과 상응하는 수였다. 따라서 시뮬레이션을 고려했으나 컴퓨팅 자원의 부족문제로 좌절하게 되었다. AI 엔지니어링을 알려주셨던 교수님과 이 문제에 대해 이야기를 하다가 알게된 것이 몬테 카를로 알고리즘이었다. 그래서 시뮬레이션을 적용하기 전 해당 방법론에 대해 공부하고 정리하고자 한다.

 

 

몬테카를로 알고리즘은 무엇인가?

복잡한 문제를 해결하기 위해 무작위 샘플링을 사용하는 확률적 시뮬레이션 방법

 

 

아래 예를 들어보자.

 

 

전구의 빛이 공 뒤에 도달할 확률을 구하기 위해서는 수치화하기 힘들만큼의 경우의 수가 존재할 것이다. 그리고 이 모든 경우의 수를 시뮬레이션하는 것은 불가능에 가깝다.

 

 

따라서 대표성을 가진 샘플을 무작위로 선정한다. 예를 들어 전구를 기준으로 1, 3, 5, 6, 7, 9, 11시 방향을 기준으로 그룹화 할 수 있을 것이다.

 

그리고 그룹 내 무작위의 각도를 샘플로 선정하고 샘플의 수를 계속 늘려가본다. 샘플의 수를 늘려가다보면 그룹별로 확률이 특정 수에 수렴하게 될 것이며 이를 통해 전구의 빛이 공 아래 뒷면에 도달할 확률의 근사값을 추측할 수 있을 것이다. 더 많은 샘플을 추가할 수록 이러한 결과값은 더욱 정확해질 것이다.

 

 

결국, 샘플 수를 늘리는 것을 반복함으로써 특정 사건의 확률 범위를 구할 수 있다. 모든 경우의 수를 고려하는 불가능한 일을 하지 않더라도 근사치를 얻을 수 있는 것이 장점이다. 하지만 이는 여전히 근사치이므로 정확하지 않은 경우도 발생할 수 있다.

 

참고자료

• Monte Carlo Method - Wikipedia
• Monte Carlo Simulation by MarbleSicence
• A Simple Solution for Really Hard Problems: Monte Carlo Simulation
• Monte Carlo Simulation: History, How it WOrks, and 4 Key Steps