할당제의 종결 조건(stopping criteria) 을 정의할 수 있을까

최적화와 종결조건

아주 특수한 몇 가지 경우를 제외하면 최적화 문제는 정확한 답을 구하기가 매우 어렵다. 어렵다는 것을 정확하게 정의하긴 힘들지만, 모든 가능한 답안을 적어서 내보고 하나씩 검사해봐야 최적해를 구할 수 있다면 그 문제는 매우 어려운 문제라고 할 수 있다.

예를 들어 숫자의 집합 {3,1,1,2,2,1}이 주어졌을 때, 이것을 합이 같은 두 개의 집합으로 나누는 문제의 답은 {3,1,1}{2,2,1}이 될 것이다. 이 문제는 직접 집합을 두개로 나눠보고 (답안을 적어서 내보고), 두 개의 합이 같은지를 확인 (검사)해야 내가 문제를 잘 풀었는지 알 수 있다.

이런 문제는 숫자가 더 많아지고 더러워질수록 난이도가 기하급수적으로 올라간다. 이를테면, {234,15412,5456,523,42,423,4423,51435,3245,215,4,2134,3124,16,15,4124,21} 를 합이 같은 두 개의 집합으로 나누는 문제를 보면 난이도가 훨씬 올라간 것을 알 수 있다. 사실 답이 있는지도 확인하기 어렵다.

 

이렇게 풀기 어려운 문제는 근사해를 찾는 수준에서 만족하곤 한다. 위의 문제로 따지자면 "합이 같은 두 개의 집합"에서 "합의 차이가 조금 차이나는 두 개의 집합"으로 나누는 문제로 바꾸고 그 차이를 최소한으로 줄이는 알고리즘을 개발하는 것이다. 

 

종결 조건은 적당한 근사해를 찾았다면 알고리즘을 멈추자는 신호이다. 주로 (1) 만족스런 근사해를 찾거나 (2) 계속 찾아봐도 더 좋은 해를 못찾을 것 같을 때를 정의하여 종결조건을 만든다. 위의 문제로 예시를 들자면 (1) 두 집합의 합의 차이가 3보다 작을 때 혹은 (2) 알고리즘을 10번 돌려봤는데 두 집합의 차이가 작아지지 않을 때 왜 같은 것이 종결 조건이라고 할 수 있겠다. 

 

알고리즘 멈춰!

 

할당제와 최적화 문제

나는 할당제라는 알고리즘은 사회 구성원의 행복을 최대화하기 위한 근사해 찾기 알고리즘이라고 생각한다. 정치를 예로 들자. 우리 사회에서 국민을 가장 행복하게 해주는 국회의원의 성비에 대한 최적해는 어딘 가에 있을 것이다. 예를 들면 남성 의원 비율이 전체의 48%, 여성 의원 비율이 52% 일 때 대한민국 국민의 행복이 최대화된다는 식으로. 그러나 이것을 찾는 것은 매우 어려운 문제이다. 그러니까 근사해를 찾기 위해 할당제를 하는 것이다. "지금보다 여성 의원이 많아지면 국민이 행복해질 테니 할당제를 통해 여성 의원 비율을 높이자!"가 될 수 있다.

 

나는 이런 접근법이 완전히 잘못되었다고는 생각하지 않는다. 최적화 방법에서도 해 찾기 시작 지점이 아주 극단의 지점이라면 최적해에 더 빠르게 수렴하게 하기 위해서 아주 높은 변화율로 근사해를 업데이트 하는 방법이 적용되기도 한다. 과거의 남성과 여성의 의원 성비를 보면 어느정도 극단의 지점에 있다고 볼 수 있다. 따라서 최적의 성비로 빠르게 수렴하게 하기 위해서 외부에서 변화율을 높게 해주는 할당제가 있다는 것에 대해서 공학적으로는 꽤나 합리적인 접근이라고 생각한다.

 

문제는 이러한 할당제에는 종결 조건이 없다는 것이다. 할당제를 주장하는 사람들은 얘기한다. 할당제는 단순하게 숫자를 맞추기 위한 정책이 아니라 질적인 평등을 이루기 위한 정책이라고. 그렇다면 질적인 평등이 이루어 졌을 때는 더이상 할당제라는 최적화 알고리즘은 작동할 필요가 없다. 오히려 적당히 구한 근사해 (50%:50%)에서 더 나은 해 (위의 예시에서 48%:52%)로 해가 자연스럽게 업데이트 될 수 있도록 근사해 찾기 알고리즘은 종결되어야 한다.

 

그러나 할당제에 대한 여러 토론 프로그램을 봤을 때, 그 누구도 이러한 할당제의 종결 조건에 대해서는 이야기하지 않았다. 질적인 평등이나 사회 구성원의 행복에 대해서 정의하고, 어느 수준에서 그것이 달성되었을 때 할당제를 폐지해야 하는가에 대한 논의는 여전히 부족한 상태이다. 법 체계는 매우 논리적이고, 정성적인 것을 정량화하기 위한 노력을 한다는 점에서 품질공학과 유사하다고 생각한다. 물론 법이 공학처럼 딱딱 나누어 떨어지는 분야는 아니겠지만, 적어도 이러한 종결 조건에 대해서 관심을 가지는 사람이 생겼으면 좋겠다.