이전 글: 최적화란 무엇인가? 친구들과 저녁 약속을 잡는 것도 최적화다
지난 글에서 우리는 친구들과 금요일 저녁을 먹을 식당을 고르고 있었습니다. 무엇을 결정할지, 무엇을 좋게 만들지, 어떤 조건을 지킬지까지 정했습니다.
그런데 아직 예약은 못 했습니다.
저렴하고, 가깝고, 맛있는 식당을 동시에 찾으려니 의견이 모이지 않았기 때문입니다. 누군가는 가격이 중요하고, 누군가는 퇴근하고 한 시간씩 이동하기 싫습니다. 누군가는 “그래도 먹으러 가는데 맛은 있어야지”라고 말합니다.
전부 맞는 말입니다. 그래서 더 곤란합니다.
가격, 이동시간, 맛을 동시에 가장 좋게 만들 수 없다면, 우리는 무엇을 ‘최적’이라고 불러야 할까요? 이번에는 이 질문에서 파레토 최적화(Pareto optimization)로 들어가 보겠습니다.
무엇이 가장 좋은 식당인가?
이번에는 비교를 위해 후보 네 곳에 구체적인 숫자를 붙여보겠습니다. 아래는 설명을 위한 새로운 가상 데이터입니다. 지난 글에서 상황마다 등장했던 A·B·C·D의 평점이나 위치를 그대로 이어받는 것은 아닙니다.
또 지난 글에서는 예산을 3만 원 이하로 두었습니다. 이번에는 예산 상한을 잠시 3만 5천 원으로 완화하고, 네 식당 모두 영업시간과 예약 조건을 만족한다고 가정하겠습니다. 그래야 D도 선택 가능한 후보로 두고 비교할 수 있습니다. 3만 원 상한을 유지했다면 D는 비교에 앞서 제약조건에서 탈락합니다.
| 식당 | 1인당 가격 ↓ | 평균 이동시간 ↓ | 맛 ↑ (5점 만점) |
|---|---|---|---|
| A | 20,000원 | 45분 | 4.8 |
| B | 25,000원 | 25분 | 4.5 |
| C | 30,000원 | 20분 | 4.2 |
| D | 32,000원 | 35분 | 4.0 |
가격은 낮을수록, 평균 이동시간은 짧을수록, 맛 점수는 높을수록 좋다고 하겠습니다. 평균 이동시간은 네 친구의 이동시간을 평균한 값입니다. 맛은 실제로 사람마다 다르겠지만, 여기서는 모두가 이 점수에 동의한다고 가정합니다.
가격만 보면 A입니다. 맛도 A가 가장 좋습니다. 그런데 평균 45분을 이동해야 합니다. 가까운 곳을 찾으면 C가 눈에 들어오지만, 가격은 3만 원이고 맛은 4.2점입니다. B는 그 사이에 있습니다.
“그래서 어디가 제일 좋은데?”
숫자를 표로 만들었다고 해서 친구들의 의견까지 자동으로 정리되지는 않습니다.
누가 봐도 탈락인 식당
그런데 한 곳은 조금 이상합니다. D입니다.
B와 D를 나란히 놓고 보면 이렇습니다.
- 가격: B는 25,000원, D는 32,000원. B가 더 저렴합니다.
- 평균 이동시간: B는 25분, D는 35분. B가 더 가깝습니다.
- 맛: B는 4.5점, D는 4.0점. B가 더 맛있습니다.
D로 가면 돈을 더 내고, 더 오래 이동하고, 맛 점수까지 낮아집니다.
“D식당은 누가 봐도 탈락 아닌가?”
적어도 우리가 정한 세 기준만 놓고 보면 그렇습니다. D에만 특별한 장점이 없다면 B 대신 D를 고를 이유가 없습니다. 물론 D에만 넓은 주차장이 있다면 이야기가 달라집니다. 하지만 그건 주차라는 기준을 새로 넣고 다시 비교할 문제입니다.
이런 선택을 밀리는 후보라고 부른다
이처럼 한 선택이 다른 선택보다 모든 기준에서 같거나 더 좋고, 적어도 하나에서는 확실히 더 좋을 때, 뒤의 선택은 밀리는 후보가 됩니다. 이를 앞의 선택이 뒤의 선택을 파레토 지배한다고 합니다.
우리 예시에서는 B가 D를 모든 기준에서 앞서므로, D는 밀리는 해입니다.
여기서 중요한 것은 “모든 기준에서 반드시 더 좋아야 한다”가 아니라는 점입니다. 가격과 맛이 같더라도 이동시간이 더 짧으면 다른 후보는 밀립니다. 반대로 어떤 기준은 좋아지고 다른 기준은 나빠진다면, 어느 쪽도 밀린다고 말할 수 없습니다.
그림으로 보려면 잠시 맛을 빼고 가격과 평균 이동시간 두 가지만 비교해봅시다. 가로축은 이동시간, 세로축은 가격입니다. 둘 다 낮을수록 좋으므로 왼쪽 아래가 더 좋은 방향입니다.
● A·B·C: 파레토 후보 □ D: 밀리는 후보
D는 B보다 오른쪽에 있고 위쪽에 있습니다. 더 멀고 더 비싸다는 뜻입니다. B로 옮기면 두 기준을 모두 개선할 수 있습니다. 그래서 이 두 기준만으로도 D는 탈락합니다.
D를 지우고 나면 무엇이 남는가?
이제 A, B, C가 남았습니다. 여기서부터는 쉽게 지울 수 없습니다.
A에서 B로 바꾸면 평균 이동시간은 45분에서 25분으로 줄어듭니다. 대신 가격이 2만 원에서 2만 5천 원으로 올라갑니다. B에서 C로 바꾸면 5분을 더 줄일 수 있지만, 다시 5천 원을 더 내야 합니다.
반대로 C에서 A로 바꾸면 만 원을 아낍니다. 대신 25분을 더 이동합니다.
어느 한쪽이 무조건 좋다고 말하기 어렵습니다. 좋아지는 기준이 있으면 포기해야 하는 기준도 있습니다. 이것이 절충 관계입니다.
누군가에게 5천 원은 20분보다 중요할 수 있고, 누군가에게는 그 반대일 수 있습니다. 계산이 틀린 것이 아니라 중요하게 생각하는 것이 다른 겁니다.
파레토 최적해는 하나가 아닐 수 있다
주어진 제약조건을 만족하는 선택들 가운데 다른 후보에 밀리지 않는 해를 파레토 최적해(Pareto-optimal solution)라고 부릅니다. 파레토 효율적인 해(Pareto-efficient solution)라는 표현도 같은 뜻으로 사용합니다.
다른 기준을 하나도 나쁘게 만들지 않으면서 적어도 한 기준을 더 좋게 만들 수는 없는 선택입니다.
지금의 가격·이동시간 문제에서는 A, B, C가 모두 파레토 최적해입니다. A와 B는 서로 밀리지 않고, B와 C도, C와 A도 마찬가지입니다.
최적해가 세 개라니 조금 이상하게 들릴 수도 있습니다. 하지만 여기서 ‘최적’은 모든 사람이 동의하는 최고의 식당이라는 뜻이 아닙니다. 우리가 정한 기준과 후보 안에서, 아무런 희생 없이 더 나은 곳으로 갈 수 없다는 뜻입니다.
새 식당이 후보에 추가되거나 평가 기준이 바뀌면 파레토 최적인 후보도 달라질 수 있습니다.
파레토 프런티어: 남은 후보들이 보여주는 경계
A, B, C를 목적함수 값, 즉 이동시간과 가격의 좌표로 표시해보겠습니다.
● A·B·C: 파레토 후보 □ D: 밀리는 후보 ⋯ 안내선
이렇게 목적함수 공간에서 파레토 효율적인 해들이 이루는 경계 또는 집합을 파레토 프런티어(Pareto frontier)라고 부릅니다.
‘프런티어’라는 이름 때문에 매끈한 곡선을 떠올리기 쉽습니다. 연속적인 양을 결정하는 문제에서는 실제로 곡선처럼 보일 수 있습니다. 하지만 오늘 우리는 A, B, C 중 하나를 통째로 선택합니다. 따라서 이 예시의 프런티어는 세 점의 집합입니다.
점선은 눈으로 따라가기 편하도록 연결한 안내선일 뿐입니다. A와 B 사이에 가격도 적당하고 위치도 적당한 새 식당이 생겼다는 뜻은 아닙니다. 지난 글에서 이야기했듯이, A식당 30%와 B식당 70%를 예약해서 한 식당으로 만들 수는 없습니다.
이 그림의 역할은 우승자를 표시하는 것이 아닙니다. 이동시간을 줄이려면 가격을 얼마나 더 감수해야 하는지를 보여주는 것입니다.
이제 맛을 다시 넣어보자
지금까지 두 차트에서는 이해를 위해 맛을 제외했습니다. 이제 처음 표의 세 기준으로 돌아가겠습니다.
가격 ↓ / 평균 이동시간 ↓ / 맛 ↑
A는 2만 원에 맛 4.8점이지만 평균 45분 거리입니다. B는 2만 5천 원에 맛 4.5점, 평균 25분 거리입니다. C는 3만 원에 맛 4.2점이지만 평균 20분으로 가장 가깝습니다.
이 데이터에서는 맛을 다시 넣어도 A, B, C가 남습니다. A는 저렴하고 맛있지만 멀고, C는 가장 가깝지만 더 비싸고 맛 점수는 낮습니다. B 역시 다른 후보에 의해 세 기준 모두에서 밀리지 않습니다. D는 맛까지 B보다 낮으므로 여전히 밀립니다.
다만 두 기준에서 탈락한 후보가 세 기준에서도 항상 탈락하는 것은 아닙니다. 새로 추가한 기준에서 그 후보가 더 좋다면 밀리는 관계가 사라질 수 있습니다. 이번 D는 실제로 맛도 더 낮기 때문에 탈락하는 것입니다.
목표가 세 개라고 꼭 3차원 그래프를 그려야 하는 것은 아닙니다. 표를 보면서 같은 질문을 하면 됩니다.
다른 기준을 나쁘게 만들지 않으면서, 적어도 한 기준을 더 좋게 만드는 대안이 있는가?
그냥 점수를 하나 만들면 안 되나?
여기까지 오면 자연스럽게 이런 생각이 듭니다.
“가격이랑 거리랑 맛을 점수 하나로 합치면 되는 거 아니야?”
물론 가능합니다. 개념적으로는 이런 형태입니다.
Score = Taste × w1 - Price × w2 - Travel Time × w3맛은 높을수록 좋으니 더하고, 가격과 이동시간은 낮을수록 좋으니 뺍니다. 그러면 점수가 가장 높은 식당을 고르면 됩니다.
그런데 질문이 하나 남습니다.
왜 맛의 가중치는 0.5이고, 가격의 가중치는 0.2여야 할까요?
이 숫자는 식당 표가 정해주지 않습니다. 우리가 무엇을 중요하게 생각하는지를 반영합니다. 원, 분, 5점 만점의 맛은 단위와 규모도 다르므로, 실제로 계산하려면 척도를 맞추거나 가중치가 그 차이를 어떻게 반영할지도 정해야 합니다. 위 식은 방법의 모양을 보여줄 뿐, 바로 계산하라는 뜻은 아닙니다.
점수 하나로 합치는 순간에도 선호는 사라지지 않습니다. 가중치 안으로 들어갈 뿐입니다. 가중합을 어떻게 사용할지는 다음 글에서 다루겠습니다. 이번에는 “점수를 만들기 전에 누구의 기준인지 물어봐야 한다”는 것만 기억하면 충분합니다.
직접 실험
가중치를 바꾸면 선택이 달라진다
위 표와 차트는 그대로입니다. 여기서는 같은 가상 데이터로 가중합이 파레토 후보 중 어디를 고르는지 볼 수 있습니다.
| 식당 | 가격 | 이동시간 | 맛 |
|---|---|---|---|
| A | |||
| B | |||
| C | |||
| D |
평균은 괜찮은데, 왜 나만 70분인가?
지난 글에서 친구들 사이의 묘한 공정성을 이야기했습니다.
친구만 가까우면 배가 아프고, 나만 너무 멀면 배알이 꼴립니다.
평균 이동시간만 줄인다고 이 문제가 해결될까요? 이번에는 공정성만 따로 살펴보기 위한 작은 예시입니다. X와 Y의 가격과 맛은 같고, 이동시간만 아래처럼 다르다고 하겠습니다. 앞의 A·B·C·D 표를 바꾸는 것은 아닙니다.
- X식당: 네 사람의 이동시간이 20분 / 20분 / 20분 / 70분. 평균은 32.5분, 최댓값은 70분입니다.
- Y식당: 네 사람 모두 35분 / 35분 / 35분 / 35분. 평균은 35분, 최댓값은 35분입니다.
평균만 보면 X가 더 좋습니다. 그런데 70분을 이동하는 사람이 저라면 이야기가 조금 달라집니다.
“너희 셋은 20분씩 오면서 나한테는 한 시간 넘게 오라는 거야?”
계산은 맞습니다. 다만 그 계산이 제가 느끼는 불공평함까지 담고 있지는 않습니다.
그래서 새로운 목적을 추가할 수 있습니다.
가장 멀리 이동하는 사람의 이동시간, 즉 개인별 이동시간의 최댓값을 줄이자.
이제 X는 평균에서, Y는 최댓값에서 더 좋습니다. 평균과 최댓값 두 기준으로 보면 서로 밀리지 않습니다. 이 두 후보만 있는 문제에서는 둘 다 파레토 최적입니다.
평균 이동시간으로 표현한 전체의 효율성과, 최장 이동시간을 줄이는 방식으로 표현한 공정성 사이에 상충 관계가 생긴 것입니다. 물론 공정성을 정의하는 방법이 이것 하나뿐인 것은 아닙니다. 중요한 것은 공정성이 중요하다면 그것도 평가 기준이나 제약조건에 담아야 한다는 점입니다.
파레토 최적이 곧 최종 결정은 아니다
파레토 최적이라고 해서 가장 공정하거나, 가장 싸거나, 모든 사람에게 가장 좋다는 뜻은 아닙니다. ‘파레토 효율적’이라는 말도 모든 종류의 효율성에서 1등이라는 뜻은 아닙니다.
A, B, C가 모두 파레토 최적이라는 것을 알았어도, 예약할 식당은 결국 하나입니다.
오늘은 다들 피곤해서 C를 고를 수도 있습니다. 이번 달에는 돈을 아끼기로 해서 A를 고를 수도 있고, 서로 조금씩 양보해 B를 고를 수도 있습니다. 이것이 최종 결정입니다.
파레토 최적화는 우리 대신 결정을 내려주지 않는다. 대신 명백하게 열등한 선택들을 제거하고, 실제로 고민할 가치가 있는 후보만 남겨준다.
물론 여기서 ‘열등하다’는 판단도 우리가 모델에 넣은 기준에 한정됩니다. 빠뜨린 조건이 없는지 확인하는 일과, 남은 후보 중 무엇을 고를지 합의하는 일은 여전히 필요합니다.
작은 구분: 파레토 집합과 파레토 프런티어
파레토 집합(Pareto set)은 의사결정 변수 공간에서 파레토 최적해들의 집합입니다. 여기서는 ‘A식당을 선택한다, B식당을 선택한다, C식당을 선택한다’가 그 원소입니다.
파레토 프런티어(Pareto frontier)는 목적함수 공간에서 그 해들이 만드는 값들의 집합 또는 상충 관계의 경계입니다. 두 차트에서는 ‘(45분, 20,000원), (25분, 25,000원), (20분, 30,000원)’입니다.
둘을 흔히 비슷하게 이야기하지만 엄밀히는 선택 자체를 보느냐, 그 선택의 평가값을 보느냐의 차이입니다. 맛까지 포함하면 프런티어의 각 점에도 맛 점수가 추가됩니다.
가장 좋은 식당 대신, 남겨둘 식당을 묻는다
처음 질문은 단순했습니다.
“가장 좋은 식당은 어디인가?”
그런데 여러 목표를 동시에 바라보니 질문이 조금 달라졌습니다.
“명백하게 열등하지 않은 식당은 무엇인가?”
D처럼 다른 후보로 바꾸면 모든 기준이 좋아지는 선택은 지울 수 있었습니다. 하지만 A, B, C 사이에서는 무언가를 얻으면 다른 무언가를 포기해야 했습니다. 그래서 마지막 질문이 남습니다.
“그 후보 중 결국 하나를 어떻게 선택할 것인가?”
이 세 질문을 구분하는 것이 이번 글의 핵심입니다. 밀리는 후보를 걸러내는 것, 남은 후보들의 상충 관계를 이해하는 것, 선호에 따라 최종 결정을 내리는 것은 서로 이어져 있지만 같은 일은 아닙니다.
여러 목표가 충돌하는 현실에서 ‘최적’은 항상 하나의 답을 뜻하지 않는다. 먼저 명백하게 열등한 선택을 제거하고, 남은 상충 관계를 이해하는 것이 좋은 의사결정의 시작일 수 있다.
적어도 이제 “왜 여기가 좋은데?”라는 친구의 질문에 “그냥” 말고 다른 대답을 할 수 있습니다. 예약까지 끝내려면 아직 합의가 필요하겠지만요.
다음 글: 다목적 최적화란 무엇인가? 현실의 의사결정에는 목적이 하나뿐이지 않다
식당을 고를 때는 목표가 세 가지 정도였습니다. 회사에서는 보통 더 많습니다. 값도 낮춰야 하고, 탄소도 줄여야 하고, 공급이 끊기면 안 됩니다.
다음 글에서는 제가 회사에서 직접 겪었던 조달 문제를 가져오겠습니다. 그때 어떤 조건이 겹쳤는지, 그걸 다목적 최적화(multi-objective optimization)로 어떻게 풀었는지를 이어서 쓰겠습니다.
다음 글은 준비 중입니다. 게시 후 이곳에서 연결하겠습니다.
관련 토픽: 최적화 · 파레토 최적화 · 다목적 최적화
시리즈: 최적화
Discussion
토론
질문, 정정, 반례, 다른 해석이 있다면 남겨 주세요.