[알고리즘] 마켓 컬리 물류 최적화 문제로 본 최적화 문제와 이를 해결하기 위한 알고리즘

커리어리의 변성윤 머신러닝 엔지니어의 글을 보고 궁금해서 관련 내용 찾아보고 개인 학습용으로 정리한 내용임.

변성윤 / 컬리는 물류 최적화 문제를 어떻게 풀고 있을까1 | 커리어리

 

---

최적화(optimization) 문제란

정해진 제약조건(constraint) 아래 목적함수(object function)를 최소화 또는 최대화하는 문제

가능한 해들 중에서 가장 좋은(최대 or 최소) 해를 찾는 문제

해당 문제에 대한 목표를 어떻게 잡느냐에 따라 최적화하고자 하는 목적함수가 달라지게 됨

ex) 물류 데이터에서 '운송 최적화'가 목표일 경우 해당 문제는 운송 비용을 최소화하는 문제로, '생산 계획 최적화'가 목표일 경우 해당 문제는 이익을 최대화하는 문제로 정의내려지게 됨.

cf) 최적화 문제를 해결하는데 주로 쓰이는 알고리즘들

: 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등

최적화 문제를 푸는 방법

변수의 값이나 조합을 바꿔가면서 목적함수를 최소화 또는 최대화시키는 지점을 찾는 것

경사하강법(gredient descent)과 유사!

1차 출처: IBM, 2차 출처: 참고 블로그1

이때, 목적함수를 최소화 또는 최대화시키는 지점 = 최적해(optimal solution)

위 최적해 값을 가질 때의 목적함수의 값 = 최적값(optimal value)

ex) 경사하강법을 예시로 들 때,

loss function을 최소화하는 지점 = 미분 시 0이 되는 지점 = 최적해

위 최적해를 가질 때 loss function의 값? = weight(가중치) = 최적값

 

최적화 문제를 푸는 알고리즘

1. Greedy Algorithm(탐욕 알고리즘)

: 입력 데이터 간의 관계를 고려하지 않고 수행 과정에서 최솟값 또는 최댓값을 가진 데이터를 선택하는 기법. 근시안적인 선택으로 부분적인 최적해를 먼저 찾은 뒤, 각각의 최적해들을 모두 모아서 그 중 문제를 해결할 수 있는 결론적인 최적해를 얻음.[참고 블로그5]

2. Dynamic Programming(동적 계획법)

: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법[1차 출처: 위키피디아, 2차 출처: 참고 블로그6]

주어진 숫자의 범위가 크고 경우의 수가 엄청난 값의 문제들을 푸는 데 주로 사용

 

DP를 적용하기 위한 조건

1. 부분 반복 문제(Overlapping Subproblem)
2. 최적 부분 구조(Optimal Substructure)

cf) 1,2번의 알고리즘 둘 다 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가까움.

3. Genetic Algorithm(유전 알고리즘)

: 생물의 진화과정에서 일어나는 자연선택과 같은 유전법칙을 모방한 확률적 탐색기법[참고3]으로, 최적화 문제를 해결하는 기법 중 하나. 병렬적이고 전역적인 탐색 알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 함[참고 블로그4].

출처: 참고 블로그2(마켓 컬리)

1) 목적함수를 최소화 또는 최대화하는 최적해에 해당하는 유전자와 그러한 유전자들의 집합인 세대 존재

2) 각 세대에 대해서 (임의의 함수로 계산된) 적합도 평가를 거쳐 상위 50%에 해당하는 우수한 유전자들만 걸러냄

3) 좋은 유전자들을 교배 및 증식시키고 변형함으로써 좋은 유전자의 합으로 만들어진 더 좋은 해를 얻을 수 있도록 함

4) 결론적으로, 세대를 거듭할수록 보다 더 나은 유전자(최적해)를 얻게 되는 것

→ 임의의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위한, 진화를 모방한(simulated evolution) 탐색 알고리즘

특정한 문제를 풀기 위한 알고리즘이라기 보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다고 함.[참고 블로그4]

---

<reference>

참고 블로그1

최적화 문제란? (python optimization) / 파이썬 데이터 분석 실무 테크닉 100

참고 블로그2(마켓 컬리 물류 최적화 문제 블로그)

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

참고3(논문)

참고블로그4

유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기

참고블로그5

최적화 문제 - 탐욕(greedy) 알고리즘과 한계점(백준 알고리즘 11047번)

참고 블로그6

동적 계획법(Dynamic Programming)