추석 훈수를 무시해도 되는
수학적 이유 |
2020.09.29. 04:517,331 읽음 비밀글
추석이 다가왔습니다.
오래간만에 가족들을 보는 것은 좋지만,
뻔한 조언과 지나친 참견으로
우리는 때로 불편해집니다.
그러나 뻔한 훈수는 들을 필요가 없습니다. 이것은 수학적으로 증명 가능합니다.
이번 포스팅에서는
'유전 알고리즘'의 개념으로
왜 뻔한 훈수를 들을 필요가 없는지
이야기해보겠습니다.
해당 포스팅의 내용은
애니메이션을 이용한 설명이 많아
영상으로 보시면 더 좋습니다.
영상으로 보기
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
유전 알고리즘 | 훈수를 무시해도 되는 수학적 이유 | 외판원 문제
설날과 추석과 같은 명절, 그리고 연말에 가족과 친구를 보는 것은 좋은 일입니다. 하지만 뻔한 조언과 참견, 지나친 훈수는 때로 불편해집니다. 사실 뻔한 훈수는 들을 필요가 없습니다. 그리고 이것은 수학적으로 증명 가능합니다. 이 영상에서는 유전 알고리즘과 외판원 문제를 통해 왜 ...
youtu.be
설날과 추석 등의 명절과 연말 모임에서
우리는 인생을 어떻게 살아야 한다는
온갖 훈수를 듣습니다.
추석, 설날 등의 명절과 연말 모임에서, 우리는 나이를 막론하고 온갖 훈수를 듣습니다.
그저 따라하기만 하면 되는
해결책이 있다면 좋겠지만,
대부분의 훈수는 쓸모가 없습니다.
그리고 이것은
수학적으로 증명된 사실입니다.
해답은 존재할까?
우리의 삶에는 정답이 없는 것처럼
느껴질 때가 있습니다.
너무 많은 변수들이 있어
그렇게 느끼는지도 모르겠습니다.
그러나 매우 단순해 보이는 문제조차,
완벽한 정답을 제시할 수 없는
경우가 있습니다.
대표적인 사례가 바로 TSP
(Traveling Salesman Problem),
다시 말하자면, 외판원 문제입니다.
매우 단순하고 직관적인 문제조차, 완벽하게 풀 수 없는 상황이 존재합니다. 대표적으로 외판원 문제(TSP)가 그렇습니다.
외판원 문제가 훈수와 무슨 관련이 있을까요?
이 문제를 해결하는 수학적 과정에서,
우리는 훈수와 관련된
깊은 통찰을 얻을 수 있습니다.
Traveling Salesman Problem
외판원 문제의 상황은 매우 단순합니다.
여기 물건을 판매하는 영업사원은
한 도시를 출발해서, 모든 도시를
한 번씩 거쳐 다시 돌아와야 합니다.
영업사원은 서울을 출발해서 모든 도시를 한 번씩 거친 후에 다시 서울로 돌아와야 합니다. 영업사원은 가장 짧은 여행 경로를 찾을 수 있을까요?
당연히 영업사원은 기름값을 아껴야 하므로,
최단 거리가 되도록 도시를 방문하길 원합니다.
이 문제는 어렵지 않은 것처럼 느껴집니다.
만약 서울을 출발해서
세 군데의 도시를 거쳐
다시 서울에 도착해야 한다면,
단순히 도시의 순서를 조합해본 후
거리를 더하면 됩니다.
그 조합은 3!이며
계산해보면
6가지밖에 되지 않습니다.
영업사원이 영국, 런던, 리우의 세 도시를 거쳐 다시 서울로 돌아와야 한다면, 경우의 수는 6가지입니다.
여기서 영업사원은
거리가 가장 짧은 경로인
런던-리우-뉴욕의 순서대로 방문하거나,
이를 뒤집어 뉴욕-리우-런던의 순서대로
방문하면 됩니다.
영업사원은 6가지의 선택지 중, 가장 짧은 경로를 선택하면 됩니다.
하지만 방문해야 하는 도시가 백 군데라면
가능한 조합은 100!이 됩니다.
이 값은 숫자 9 뒤에 0이 157개가 붙는
매우 큰 수입니다.
외판원 문제의 핵심은, 방문해야 하는 도시가 늘어날수록 도시 방문의 조합이 급격히 커진다는 것입니다.
이 숫자가 얼마나 큰지는
잘 짐작이 되지 않습니다.
따라서 우주 전체에 존재하는
원자의 개수와 비교해 보겠습니다.
관측 가능한 우주 전체의 양성자 개수는
에딩턴 수라고 불리며,
이 값은 대략 10⁸⁰입니다.
관측 가능한 우주의 양성자 개수는 에딩턴 수라고 불립니다. 에딩턴 수의 정확한 값에는 이견이 있지만, 여기서는 10⁸⁰으로 가정했습니다.
영업사원이 계산해야 하는
조합의 개수에 비하면,
우주의 양성자 개수는
매우 초라한 숫자입니다.
만약 슈퍼컴퓨터가 있다고 해도,
이 경우의 수를 모두 계산하려면
매우 많은 시간이 필요할 것 같습니다.
그렇다면 이 문제는
영영 풀 수 없는 것일까요?
그렇지는 않습니다.
다만 모든 조합을 고려한 최고의 해답이 아닌,
최선의 해답을 찾아내는 선에서
만족해야 합니다.
완벽한 단 하나의 답이 아닌, 다른 방식을 선택해야 합니다.
그리고 이러한 최선의 해답을 찾아내기 위해
유전 알고리즘이 사용됩니다.
최선의 해답을 찾아내기 위한 방법 : 유전 알고리즘
유전 알고리즘은
어떻게 이 문제를 해결할 수 있을까요?
유전 알고리즘
(Genetic Algorithm)
유전 알고리즘은 그 이름에서도 알 수 있듯이,
유전적 진화 과정을 모방해 개발된
최적화 기법 중 하나입니다.
유전 알고리즘의 '유전'은 우리 몸 속의 정보 전달 시스템인 '유전자'를 지칭합니다.
이 유전적 진화 알고리즘은
레고를 조립하는 놀이로 비유할 수도 있습니다.
우리는 레고 조각을 끼워서,
원하는 형태의 디자인을 여러 개 만들 수 있고,
그중 가장 좋아 보이는
두 개의 디자인을 선정해서
새로운 변종을 시도할 수도 있습니다.
또는 완전히 다른 새로운 조각을 가져와
붙여볼 수도 있죠.
레고 유전 알고리즘 1단계 : 여러 개의 디자인 중 마음에 드는 것을 고릅니다.
레고 유전 알고리즘 2단계 : 마음에 드는 디자인 2개를 섞습니다.
레고 유전 알고리즘 3단계 : 다른 부품을 가져와 추가하거나, 기존의 부품을 변형해봅니다.
이렇게 만든 변종의 디자인이 더 좋아 보일 때,
우리는 그 디자인에 질리지 않고
오랫동안 가지고 놀 수 있을 것입니다.
약간의 용어를 사용해 말한다면,
이런 레고는
'디자인 적합도'가 높은 제품입니다.
만들어진 레고 제품이 '우리'의 마음에 든다면, 이 제품은 '적합도'가 높은 제품입니다.
이러한 레고 이야기는 자연계에서 일어나는
생물의 진화 알고리즘과 일치합니다.
생명체를 결정하는 빌딩 블록은 유전자입니다.
그리고 유전자간의 교차로 정보를 교환하고,
아주 가끔 뜬금없이
돌연변이가 일어나기도 합니다.
하지만, 전체적으로 보았을 때는,
안정성을 유지하는 편이죠.
레고 제품을 검열하는 주체가 '우리'였다면, 진화 알고리즘에서 유전자의 검열 주체는 '자연'입니다.
이렇게 만들어진 유전자는
생물체가 속해있는 환경,
다시 말해 '적합도 지형'에 잘 들어맞는
높은 '디자인 적합도'를 가질 수도 있고,
아닐 수도 있습니다.
유전자와 환경 사이의 적합도를 함수로 나타낼 수 있다면, 우리는 해당 유전자의 '적합도 지형'을 그릴 수 있습니다.
완성된 레고를 보는 사람이 누구냐에 따라,
그 레고가 맘에 들기도 하고
맘에 들지 않기도 하는 것처럼 말이죠.
이러한 문제 해결 과정을 수학적으로
모방한 것이 유전 알고리즘입니다.
유전 알고리즘으로
디자인 적합도가 높은 것들만을 선별하여
선택적으로 변형을 일으키면,
우리가 원하는 결과를
빠른 시간 내에 얻을 수 있습니다.
어느 정도 적합한 것들을 골라서 조금씩 변형을 가하면, 원하는 결과값을 구할 수 있습니다. TSP의 경우, 도시의 배열 중 어느 정도 거리가 짧은 것들을 먼저 선별해서, 이 배열을 아주 조금씩 변형하는 알고리즘을 구성하면 됩니다.
그러나 앞서 이야기했듯,
이렇게 얻은 결괏값은 최선일 뿐
최고의 결과는 아닐 수도 있습니다.
요소들을 다 고려하지 못하면
'지역적 최적해'에 갇혀 버리기 때문입니다.
최고라고 생각했던 결과가,
전체적인 적합도 지형에서는
매우 평범한 수준의 결과일 수도 있습니다.
유전 알고리즘은 변수들을 충분히 고려하지 못하면, 결과가 매우 평범한 수준이 될 수 있다는 것을 보여줍니다.
이러한 수학적 사실은
우리에게 일종의 통찰을 줍니다.
우리의 삶은 불확실성으로 가득 차 있으며,
개인의 능력은 사람마다 매우 다릅니다.
즉, 삶이라는 적합도 지형은
개인마다 차이가 있습니다.
삶의 적합도 지형이 개인마다 다를 것임은 명백합니다.
일방적인 조언은 개인이 가진
복잡한 변수들을 포괄할 수 없기 때문에,
우리를 국소적인 최적해에 가둬버리는
덫으로 기능합니다.
물론 오랜 시간 동안 적합도 지형을 탐색해 본
경험자의 훈수는 맞을 수도 있습니다.
다만 '그 사람의 과거'에
맞았던 조언일 뿐입니다.
따라서 우리는 '현재의 내가' 서 있는
적합도 지형의 가장 높은 정점을
탐색해야 합니다.
다수의 사람들이 옳다고 하는 것조차 '국소 최적해'일 가능성이 큽니다. 적합도 지형은 시간에 따라서도 변하기 때문입니다.
적합도 지형의 가장 높은 지점을 찾으려면,
현재의 지형을 직접 돌아보고
조금씩 전진해 나가야 합니다.
혹은 유전자에 일어나는 돌연변이처럼
급진적인 점프를 시도하는 방법도 있습니다.
내 적합도 지형의 가장 높은 정점을 찾으려면, 직접 발로 걸어보는 수밖에 없습니다.
그러나 적합도 지형이
산맥과 같은 형태라면,
단 한 번의 점프만으로
죽음의 계곡에 굴러떨어질 수도 있습니다.
힘을 모아 단번에 적합도 지형을 크게 옮겨갈 수도 있겠지만, 위험이 매우 큰 도박입니다.
따라서 여러 군데에 배팅하는 것이
옳을지도 모릅니다.
'계란을 한 바구니에 담지 말라'는
투자의 금언과 동일한 맥락입니다.
심지어 적합도 지형은 칠흑처럼 어두워서,
현재 당신이 높은 곳에 있는지
낮은 곳에 있는지 알기 어렵습니다.
하지만, 적합도 지형의 정점을 찾는
가장 효과적인 방법은 존재합니다.
직접 부딪히면서
새로운 무언가를
계속 시도하는 것입니다.
준비한 내용은 여기까지입니다.
내용이 유익했다면 구독과 좋아요로
응원해주세요 :)
Weniverse Original Soundtrack
'Genetic Algorithm'
Soundcloud에서 들어보실 수 있습니다.
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
Genetic Algorithm
Weniverse Original Soundtrack.
soundcloud.com
참고자료
Origin of Wealth
저자 에릭 바인하커
출판 HarvardBusinessSchoolPress
발매 2007.09.10.
수학이 일상에서 이렇게 쓸모 있을 줄이야
저자 클라라 그리마
출판 하이픈
발매 2018.12.24.
위니버스의 인기콘텐츠
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
테넷의 과학 | 테넷 해석 - 엔트로피, 양전자, 할아버지 역설 해설
테넷은 그냥 보기에도 재밌는 영화지만, 과학 지식이 없는 상태에서 영화를 보면 온전히 테넷을 즐기기 어려울 가능성이 큽니다. 이 동영상에서는 테넷을 재밌게 보기 위해 필요한 과학 지식들을 제대로 이야기합니다. 즉, 테넷의 과학과 테넷 분석을 위해 제작한 동영상입니다. 주요 주제는 ...
youtu.be
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
당신이 회사에서 능력을 펼치지 못하는 이유 | 혁신의 방정식, 룬샷
당신은 특별합니다. 하지만 회사가 문제입니다. '룬샷'의 저자인 사피 바칼은 '던바 수'에 영감을 받아, 직장 내 정치질을 없애고 여러분이 창의적으로 일하기 위한 회사의 최대 인원수를 구하는 '혁신의 방정식'을 제시합니다. 이 콘텐츠는 사피 바칼이 수학적, 인지심리학적 접근으로 제...
youtu.be
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
디즈니가 넷플릭스를 넘기 어려운 이유 | 인공지능과 알고리즘, 나이브 베이즈 분류
OTT 서비스 시장의 선두인 넷플릭스가 디즈니+, HBO, 애플 TV+ 등과 본격적으로 경쟁을 시작했습니다. 그럼에도, 넷플릭스는 대외적으로는 태연한 모습을 보여주고 있습니다. 오랜 기간 갈고닦았던 넷플릭스의 추천 알고리즘에 자신이 있어서일까요? 이번 영상에서는 나이브 베이즈 분류...
youtu.be
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
베이즈 정리를 이해하는 가장 쉬운 방법
조건부 확률과 베이즈 정리를 이용하여, 발렌타인데이 초콜릿을 준 사람이 날 좋아할 확률을 구해봅니다. ------------ 베이즈 정리는 총 네 시리즈로 연재될 예정입니다. 이 영상은 베이즈 정리의 기본 개념을 익히는 첫 번째 파트입니다 :) 다음 영상은 베이즈 정리가 인공지능에...
youtu.be
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
내가 코로나에 걸릴 확률은? | 장소에 따른 코로나 바이러스 감염 확률
한 달 사이에 당신이 코로나 바이러스에 걸릴 확률을 추정할 수 있을까요? 사실을 알고 난 후에는 외출하기 싫어질지도 모릅니다. 이 영상에서는 미국의 연구진이 발표한 내용을 근거로, 장소에 따른 코로나 감염 확률에 관해 이야기합니다. 특히 연구진은 코로나 바이러스의 에어로졸(공기) ...
youtu.be
동영상
버튼을 누르면 현재 화면에서 재생됩니다.
당신이 매일 쓰는 마스크의 모든 것 | 코로나 시대와 마스크의 과학
#위니버스 #weniverse #마스크 #마스크의 과학 코로나 19 사태 이후로 모두가 마스크를 착용하고 있습니다. 이 영상에서는 마스크와 관련된 수학적, 과학적 사실들에 관해 이야기합니다. 소재별 마스크의 효율, 마스크의 성능, 비말 크기와 브라운 운동, 마스크를 빨지 말아야 하...
youtu.be
이 콘텐츠는 2020년도 정부(과학기술진흥기금복권기금)의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.
위니버스(Weniverse)
Understanding We & Universe
© 2020 Weniverse. All Rights Reserved
'현대 창조론 연구 자료실 > 창조론 연구를 위한 과학 뉴스' 카테고리의 다른 글
| 머스크의 뉴럴링크 프로젝트, 구속 신앙 무너뜨릴 것인가 (0) | 2020.10.02 |
|---|---|
| 뇌에 칩 이식 ‘일론 머스크의 돼지’가 보여주는 인류의 미래 (0) | 2020.10.02 |
| 다윈의 항해 (0) | 2020.10.01 |
| 온난화와 팬데믹의 악순환…잠들었던 바이러스가 부활한다 (0) | 2020.10.01 |
| 백신 나와도 마스크 못벗는다···인류 위협하는 ‘신데믹 쇼크’ (0) | 2020.10.01 |