집단 지성으로 순회 판매원 문제를 풀 수 있을까?

글 : 인지심리 매니아

누군가 당신에게 “콜럼버스가 신대륙을 발견한 해가 언제입니까?”라는 질문을 했다고 가정하자. 당신은 정답이 1592년이라고 확신한다. 그런데 질문자가 100사람을 대상으로 한 설문조사 결과를 보여준다. 100사람의 응답을 평균한 값은 1500년이다. 당신은 1592년과 1500년 중 어떤 것이 정답이라고 생각하는가? (정답은 1492년이다)

대체적으로 자신의 생각보다 다수의 생각이 정답에 가깝다.  항상 그렇지는 않지만, 다수의 생각은 통계적으로 정답에 근접하는 경향이 있기 때문이다. 우리는 이것을 ‘집단 지성'이라고도 부른다. 위키피디아 정의에 의하면 집단 지성은 “다수의 개체들이 서로 협력 혹은 경쟁을 통하여 얻게 되는 지적 능력에 의한 결과로 얻어진 집단적 능력”을 말한다. 앞에서 든 사례도 사람들의 응답이 축적되는 과정에서 ‘집단적'으로 정답이 도출된 경우라고 할 수 있다.

집단 지성 효과는 위의 경우처럼 수치를 예측하는 과제 뿐만 아니라 일반 지식 문제에서도  입증이 되었다(SBS에서 방영 중인 ‘1억 퀴즈쇼'를 잘 살펴봤다면, 패널들의 다수가 고른 답이 정답인 경우가 많다는 사실을 눈치 챘을 것이다. 패널의 대부분이 정답을 모름에도 불구하고 다수의 선택이 정답이 되는 것을 보면 신기하다). 하지만, 우리는 그보다 더 중요한 문제에서도 집단 지성이 효력을 발휘하는지 궁금하다. 집단 지성은 복잡한 수학 문제를 풀 수 있을까? 또는 복잡한 정치 현안을 해결할 수 있을까? 

Yi(2012) 등^[각주:1]은 집단 지성이 보다 복잡한 문제를 해결할 수 있는지 연구했다. 그들은 특히 집단 지성이 순회 판매원 문제(TSP, Travelling Salesman Problem)와 최소 신장 트리 문제(MSTP, Minimum spanning tree problem)를 해결할 수 있는지에 관심을 가지고 있었다. 순회 판매원 문제는 N개의 점을 이동하는 가장 짧은 거리를 찾는 문제를 말한다. 최소 신장 트리 문제는 순회 판매원 문제와 유사하지만 점과 점 사이에 고유의 가중치가 있으며, 이 가중치의 합이 최소가 되는 경로를 찾는 게 목적이다.

순회 판매원 문제 : 각 도시를 한번씩 거치는 최단 경로는? - 출처 : http://www.aistudy.com

최소 신장 트리 문제 : 가중치의 합이 최소가 되는 최적 경로는? - 출처 : 위키피디아

일반적으로 이런 문제들을 해결할 땐 인공지능을 활용한 최적화 기법들을 사용한다. 인공 신경망, 마르코프 체인, 유전 알고리즘이 대표적이다. 그런데, 컴퓨터의 힘을 빌리지 않고 사람의 힘만으로 이 문제들을 해결할 수 있을까? 더 정확히 말해서, ‘여러 사람'의 힘을 합치면 이 문제들을 풀 수 있을까? 연구자들은 독특한 연구 방법을 통해 이 궁금증을 해결하고자 했다.

연구자들은 여러 사람의 정답을 합치기 위해 Local decomposition과 Global similarity라는 방법을 사용했다. Local decomposition은 사람들이 가장 많이 선택한 경로를 정답으로 채택하는 방법이다. 아래 그림에서 A는 각 참가자들이 내놓은 정답이다. 연구자들은 이를 토대로 참가자들이 가장 많이 선택한 경로(B의 진한 선)를 정답으로 채택했다. 반면 Global similarity는 가장 전형적인 참가자의 응답을 정답으로 채택한다. 즉, 참가자들의 정답을 가장 잘 대표하는 응답을 하나 골라서 그것을 정답으로 채택한다. 

Local decomposition

실험 결과, Local decomposition은 각 참가자의 응답보다 훨씬 정답에 가까웠다. 또, Local decomposition 방식은 Global similarity 방식보다 우수한 것으로 드러났다. 이 결과는 순회 판매원 문제와 최소 신장 트리 문제에서 모두 관찰되었다. 

MSTP 문제에서 참가자들의 응답을 정답과 가까운 순으로 나열한 그래프. 하얀 막대는 각 참가자를 의미한다. Local decomposition은 정답과 가장 가까웠고, Global Similarity는 정답과 4번째로 가까웠다.

Conclusion

집단 지성은 단순 사실을 추측하는 데만 쓰이지 않는다. 우리는 이 논문을 통해 집단 지성이 훨씬 복잡한 문제를 해결할 수 있음을 알았다. 어쩌면, 연구가 진행됨에 따라서 집단 지성이 해결할 수 있는 문제가 훨씬 다양하다는 사실이 밝혀질 지 모른다. 

개인적으로는, 집단 지성의 유용성을 확인하는 데 그치지 않고 이를 어떻게 활용할 지에도 관심을 가져야 한다고 생각한다. 우리는 과거와 달리 인터넷과 SNS을 통해 수많은 사람들의 의견을 결집할 수 있는 수단을 가졌다. 이런 도구들을 통해 집단 지성을 적절히 활용하는 방법을 찾는 것도 가치 있는 일이라고 할 수 있다.

1. Yi, S. K. M., Steyvers, M., Lee, M. D. and Dry, M. J. (2012), The Wisdom of the Crowd in Combinatorial Problems. Cognitive Science, 36: 452–470. doi: 10.1111/j.1551-6709.2011.01223.x [본문으로]