Algorithm and World-정대명

안녕하세요! 이번 주 관점공유를 맡게 된 정대명 Eyes입니다. 저의 관점공유 주제는 ‘Algorithm and World'입니다. 처음에는 ’여행‘이라는 가벼운 주제로 하려고 하였으나 생소할 수 있는 저의 전공적인 지식의 일부를 재미나게 풀 수 있다고 생각하여 ’Algorithm'을 이번 관점공유의 주제로 택하였습니다. 

알고리즘에 대하여 생소하신 분들을 위하여 알고리즘에 대한 소개를 간단히 한 뒤, 대표적인 알고리즘에 대하여 알아보도록 하겠습니다. 먼저, '알고리즘'이란 어떤 문제를 해결하기 위하여 명확히 정의된 한정된 개수의 규제나 명령의 집합을 말합니다.

위와 같은 그림은 특정 알고리즘을 가시화 한 순서도입니다. 

알고리즘들의 쓰임은 일상생활 거의 모든 곳에 분포하고 있습니다. Facebook에서는 현재 포스터에 머무른 시간이 많을수록 더 가중치를 두는 빅 데이터 분야의 알고리즘을 사용하고 있으며, 암호학, 통신, 인공지능, 심지어 컴퓨터의 압축과정 하나하나에 조차 모두 각자의 알고리즘이 사용되고 있습니다. 대표적인 알고리즘을 이용한 성공적인 사례는 구글의 우수한 searching algorithm이 있습니다.

 

하나의 작업을 수행하는 과정에 사용될 수 있는 알고리즘은 어떠한 사람이 어떠한 알고리즘을 디자인 하느냐에 따라 다양한 종류의 알고리즘이 나올 수 있습니다. 예를 들어 숫자를 크기순으로 분류하는 Sorting 의 경우 Bubble sort, insert sort, bucket sort 등등 많은 종류의 알고리즘을 사용할 수 있습니다. 그렇다면 같은 작업을 수행하더라도 좀 더 질이 좋은 알고리즘을 사용하면 작업의 효율성이 좋아져 더 짧은 시간 안에 많은 일을 수행하고, 에러를 줄여 완성도가 더 높은 결과물을 얻을 수 있습니다.

 

그렇다면 지금부터는 누구나 이해할 수 있는 재미있고 또한 아주 중요하고 훌륭한 알고리즘을 알아보겠습니다.

 

첫 번째로는 Gale Shaply의 Stable Marriage Algorithm입니다. 실제로 이 알고리즘에 관한 논문을 낸 Gale shaply가 노벨 경제학상을 받았을 정도로 완성도가 높은 알고리즘입니다. 게다가 누구나 이해할 수 있을 정도로 알고리즘이 복잡하지 않다는 장점도 있습니다.

 

이 알고리즘을 이해하기 위해서는 다음과 같은 정의가 필요합니다. 우선 Unstable한 상황을 여기서 어떻게 정의하였는지 보겠습니다.

위의 그림을 보겠습니다. 현재 Man1은 Woman1과 결혼한 상태이고 Man2와 Woman2는 결혼한 상태입니다. 그런데 현재 Man1은 Woman1보다 Woman2를 선호하고 있고 Woman2또한 Man2보다 Man1을 선호하고 있습니다. 다음과 같은 상태라면 Man1과 Woman2는 불륜이 일어날 수 있는 상태라고 말할 수 있습니다. 다음과 같은 상황이 발생할 경우를 Unstable 이라고 부릅니다.

그런데 정말 놀랍게도, 이러한 Unstable한 상황을 단 하나도 발생시키지 않는 알고리즘이 존재합니다. 바로 Stable Marriage Algorithm을 사용하여 서로 간에 매칭을 시켜 결혼을 할 경우 Unstable한 상황은 절대적으로 0%가 됩니다. 그렇다면 Stable Marriage Algorithm이 무엇인지 알아보겠습니다.

위의 설명이 Stable Marriage Algorithm에 관한 내용입니다. 우선 N명의 여성과 N명이 남성이 있다고 가정합니다. N명의 여성과 N명의 남성은 각각 상대 집단에 대하여 선호도를 가지고 있습니다.

1. 한명의 남성을 선택한다

2. 한명의 남자는 그동안 프로포즈 하지 않았던 여성 중 가장 선호도가 높은 여성에게 프로포즈한다.

3. 만약에 여성이 이전에 약혼하지 않았다면 그 여성은 프로포즈한 남자와 약혼한다.

4. 만약에 여성이 약혼을 이미 하였다면 예전에 약혼한 사람과 비교를 하여 더 선호도가 높은 사람과 다시 약혼을 합니다

5. 선택받지 못한 남자는 다시 약혼하지 않은 사람으로 돌아갑니다.

6. 모든 커플이 약혼을 하게 되면 동시에 모두 결혼합니다.

 

이러한 과정을 거쳐서 N*N매칭이 이루어질 경우 단 하나의 Unstable한 상황조차 생기지 않는다는 점에서 이 알고리즘의 우수성이 증명됩니다. Gale Shapley는 이 알고리즘을 증명하고 또한 이 알고리즘이 발전하여 다수 대 다수 매칭 시스템인 School commission algorithm을 증명하였고 여러 분야에 우수한 활용성을 인정받아 노벨상을 받았습니다.

  

그 다음으로 소개하고자 하는 알고리즘은 Gene algorithm입니다. 이 Gene algorithm은 하나의 알고리즘을 뜻하는 것은 아니고 특정 알고리즘들의 속성을 대표한다고 볼 수 있습니다.

 

Gene algorithm의 키포인트는 스스로 진화하는 알고리즘 이라는 것에 있습니다.

현재 인류를 포함에서 살아남은 종 들은 수백만년에 걸쳐서 환경에 적응한 가장 최적의 생물들입니다. 그 동안 맘모스를 비롯하여 환경에 적응하지 못한 수많은 종들은 멸종되었습니다. 즉 최적의 생물만이 자연적으로 선택되고, 이에 해당이 되지 않는 다른 생물들은 멸종한다는 적자생존의 원리가 적용된 것입니다. 이러한 원리를 알고리즘에 적용시킨 것이 Gene Algorithm의 기본적인 원리입니다.

즉, 수없이 많은 케이스를 만든 뒤 그 중 최적의 상태들만 남기고 다른 도태되는 상태들은 제거한다는 것이 Gene algorithm의 기본 원리입니다.

 

그에 관한 예로 최단 강하 곡선 찾기 문제에 대하여 알아보겠습니다.

다음 그림은 공을 같은 위치에서 낙하 시켰을 때 어떠한 공이 가장 빨리 낙하하는가에 대한 문제입니다. 실제로 이 문제의 해답은 Cycloid에서 가장 빠르게 공이 낙하 한다고 뉴턴이 이미 증명 한 바 있습니다. 하지만 Gene algorithm을 이용하면 이러한 복잡한 수식적 증명이 없이도 최단 거리 곡선이 Cycloid라는 것을 손쉽게 유추할 수 있습니다.

다음과 같이 임의의 곡선에서 여러 가지 종류의 자손들이 뻗어 나옵니다. 한 세대를 거칠 때 마다 최단 강하 곡선과 거리가 먼 곡선들은 적자생존의 원리가 적용되어 자동으로 제거 됩니다. 이러한 방식으로 수만 또는 수십만 세대를 거듭하다 보면 저절로 가장 빠르게 공을 낙하시키는 자손만이 살아남습니다. 아래의 움직이는 그림은 그에 대한 내용을 담은 것입니다. 여기서 n이 뜻하는 것은 자손 수입니다.

보시는 바와 같이 세대를 거듭할수록 퇴화되는 곡선은 버려지고 우수한 새끼곡선만이 살아남게 됩니다. 즉 공이 최단 시간에 낙하할 수 있는 곡선만이 계속해서 살아남게 되고 결국에는 Cycloid 곡면 형태의 모양에 계속해서 가까워집니다.

즉 Gene algorithm은 이러한 방식으로 스스로 진화해서 최적의 답을 찾도록 설계 됩니다.

실제로 자연현상에서도 이와 같은 원리를 볼 수가 있는데 독수리는 물고기를 잡기위하여 낙하할 때 Cycloid 곡선 모양을 따라 낙하하도록 세대를 거쳐 진화하였다고 합니다.

 

이상으로 Algorithm and world에 대한 관점공유를 진행한 정대명 Eyes였습니다. 감사합니다.