시험 공부를 하다가 쓸데없는 생각이 들었다. 이 수업에서 소개한 알고리즘을 가지고 내 삶을 결정하는 모든 행동과 선택을 설명해 볼 수 있지 않을까? 또는, 적어도 그런 시도는 해볼 수 있지 않을까.
아, 그전에 공부하고 있던 과목이 무엇인지에 대해서 설명하는 데에도 지면을 많이 할애해야 한다. 사실 시험 기간의 절반은 이것에 대해 고민하며 보냈다. 나는 대체 무엇을 배우고 있었던가?
마지막 학기에 내가 듣고 있는 유일한 전공 과목. 이 수업은 다양한 메타휴리스틱 기법을 소개하고, 이를 소프트웨어 엔지니어링 문제에 적용한 사례를 다룬다. 소프트웨어 엔지니어링의 범위를 프로그램 개발의 전체 생애 주기(Lifecycle)로 생각한다면, 요구사항 수집, 설계, 테스팅, 배포, 유지 보수 등에 이르는 과정 속에 발생하는 문제들에서 ‘메타휴리스틱’ 알고리즘으로 최적해를 찾아내는 것이라고 말할 수 있겠다. 여전히 알쏭달쏭하기는 하지만.
메타휴리스틱 알고리즘
메타몽은 아는데.. 메타휴리스틱은 잘…
알고리즘
알고리즘, 이라는 단어에서 연상되는 것은 잘 정의된 문제와 이 문제에서 요구하는 조건에 맞는 정답을 정해진 동작을 통해 찾아나가는 과정이다.
알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm 알고리듬, IPA: [ǽlɡərìðm])은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.
프로그래머스나 LeetCode와 같은 사이트에서 알고리즘 문제를 풀어 본 적이 있다면, 어떤 값을 최소화/최대화하거나 (ex. 거리가 최소인 경로 찾기) 특정 형태를 만족하도록 (ex. 특정 규칙에 따라 encoding된 문자열) 하는 ‘정답’을 output으로 출력하게 하는 프로그램을 상상할 수 있을 것이다. 얼마 전 있었던 카카오 코딩 테스트 문제를 예시로, 알고리즘 문제를 푸는 방법에 대해서 생각해 보자. 2번이나 5번 문제에서는 주어진 input을 가공하면 곧바로 조건에 맞는 output을 얻어낼 수도 있지만, 생각해보면 이렇게 시뮬레이션으로 깔끔하게 풀리는 경우는 잘 없다.
주어진 input과 제약 조건을 가지고 후보가 될 수 있는 답을 먼저 골라낸 후에, 정렬 등을 이용해서 목표가 되는 값이 최소가 되는 경우를 뽑아낸다. 또는 그렇게 최소가 되는 경로를 그래프나 트리 등 자료구조의 특성을 이용해서 바로 탐색하는 경우도 생각해 볼 수 있다. 예를 들어 문제 4번 같은 경우에는 trie 자료 구조를 사용하면 key에 해당하는 문자를 불필요한 탐색 없이 바로 찾아갈 수 있다.
데이터 구조를 사용해서든, 동적 계획법(Dynamic Programming)과 같은 기법을 사용해서든 우리는 연산량을 줄여서 최대한의 효율을 내는 알고리즘을 짜기 위해 자신의 머리를 쥐어짜곤 한다. 물론 효율성을 높인다고 해도 정확한 답을 도출해야 하는 것은 변함없다.
하지만 이렇게 우리의 프로그래밍 능력을 검증하기 위해 ‘정제된’ 문제가 아닌, 현실의 문제를 생각해본다면 조금 다른 형태의 ‘알고리즘’을 받아들일 수도 있게 된다.
- 최적해와 최적해의 근삿값이 큰 차이가 없을 수도 있다
- 결국은 NP-hard, NP-complete 문제로 귀결되는 경우가 있다 (N이 조금만 커져도 살아있는 동안 절대 안 풀린다)
바로 휴리스틱 알고리즘이다.
휴리스틱, 그리고 휴리스틱 알고리즘
요즘은 운영체제에 꽤 신뢰도 높은 Defender가 내장되어 있어서 그런지, 바이러스 백신에 대한 관심이 줄어든 것 같다. 하지만 2010년도 근처만 하더라도 각종 바이러스 백신 엔진에 대한 벤치마킹, 비교글이 많이 돌아다녔던 기억이 난다. 몇몇 해외 제품들에서 ‘휴리스틱 엔진’을 탑재해서 높은 바이러스 탐지율을 자랑했었고, 그런 백신들이 벤치마크 결과에서 높은 점수를 얻으면서 사람들 사이에서 인기가 많았더랬다. (내 동년배들 다 소싯적에 백신 좀 써 봤다)
아무튼, 이 휴리스틱 엔진의 치명적인 단점이 있었으니, 정상 파일마저 감염 파일로 종종 진단한다는 것이었다. 벤치마크 기록만 믿고 다운받았다가 무고한 파일을 감옥에 집어넣는 일이 많았던 기억이 난다. 원칙적으로 이미 알려진 바이러스 파일의 패턴을 바탕으로 검사를 하게 되는데, 휴리스틱 기술을 사용하면 아직 알려지지 않은 위협 요소로부터 ‘정상적이지 않은 패턴’을 감지해서 바이러스로 진단하게 된다.
휴리스틱은 ‘발견법’이라고도 불리며, 근본적으로는 심리학에서 나온 용어다. 심리학자들은 인간의 불완전하지만 빠르고 효과적인 직관, 또는 어림짐작을 휴리스틱이라고 일컫는다. 그리고 이러한 사고방식을 컴퓨터의 연산 과정에 적용한 것이 휴리스틱 알고리즘이다.
불충분한 시간이나 정보로 인하여 체계적이고 합리적인 판단이 힘들 때 휴리스틱은 합리적인 시간으로 문제의 최적해를 근사할 수 있다. 즉, 위의 바이러스 백신 예시에서처럼 ‘바이러스 패턴’에 대한 불충분한 정보를 가지고도 완벽하진 않지만 유의미한 탐지 결과를 낼 수 있다.
휴리스틱 알고리즘은 인간의 직관적 사고방식을 모방한다. 불완전한 인간의 사고방식을 모방하기 때문에 해답의 엄밀함은 보장할 수 없다. 하지만 컴퓨터의 이점은 인간에 비해 훨씬 더 많은 시도(Trial & Error)를 할 수 있다는 것이다. 또 저장 공간이 모자라지 않은 한 한번 기억한 것은 절대 잊어버리지 않는다. 그러니 그들이 대신 수많은 시행착오를 거치도록 한다면 인간의 직관이 가진 장점은 십분 활용하면서 더 정확하고 의미있는 결과를 도출할 수 있는 것이다.
다양한 분야에서 휴리스틱 방법으로 문제를 푸는 시도가 가능하다. 하지만 특정한 문제를 목표로 휴리스틱 알고리즘을 하나하나 고안하기보다는 좀더 보편적인 상위 수준의 알고리즘을 먼저 고안하고, 이를 문제의 특성에 맞춰 적응시키는 것이 더 효과적일 수 있다.
이러한 상위 수준의 발견적 기법이 메타휴리스틱이고, 대부분 자연 법칙으로부터 영감을 받아 형성되었다.
대표적으로,
- 유전 알고리즘 (생물의 진화 과정과 유전 법칙 모방)
- 담금질 기법 (금속의 표면처리 과정에서 냉각 과정)
- 타부 서치 (인간이 기억을 하는 과정)
등이 있다.
Search in Solution Space
공부를 하면서 잘 연결되지 않았던 것은 메타휴리스틱 알고리즘이 다양한 탐색(Search) 메소드로 귀결된다는 점이었다.
앞에서 제시한 유전 알고리즘 등의 기법들은 가능한 해(Solution)로 이루어진 공간(Solution Space)에서 좀더 좋은 해를 찾아가는(Search) 방법이라는 공통점을 가지고 있다. 인공면역체계(AIS)과 같이 학습을 기반으로 모델을 훈련하는 방식도 존재하지만, 기본적으로 초기해로부터 계속해서 더 나은 해를 탐색하는 과정이라는 것은 동일하다. 그런데 왜 휴리스틱 알고리즘은 Search Technique의 형태로 발전해왔을까? 사실 생각해보면 휴리스틱 자체가 직관적으로 빨리 찾아낼 수 있는 답을 먼저 찾고, 시행착오를 통해 점점 더 개선된 답으로 나아가는 과정이다. 이러한 과정을 수학적으로 모델링하려다 보니 ‘공간’과 ‘좌표’가 필요했고, 자연히 더 나은 해로 발전해나가는 과정을 탐색 알고리즘으로 구현하게 되었을 것이다.
물론 내가 알고리즘을 먼저 배우고 이후에 그 기원(?)에 끼워맞추다 보니 ‘자연스럽다’라고 느끼는 것일 수도 있겠지만, 처음 이 알고리즘을 고안했던 사람들도 비슷한 사고의 과정을 거치지 않았을까 싶다.
Representation of Life
휴리스틱 알고리즘이 기본적으로는 인간의 사고 방식으로부터 영감을 받아 고안된 것이기는 하지만, 기본적으로는 deterministic한 연산을 하는 컴퓨터를 이해시키기 위해 체계화되고 더 다양하게 수정된 부분이 많은 것 같다. 그렇기 때문에 우리의 생각, 그리고 매 순간의 선택을 다시 체계화된 휴리스틱 알고리즘에 대입해서 생각해 볼 수 있을 것도 같다. 그런 아이디어에서 사실 이 글을 쓰기 시작했다. 삶 속에서 우리가 하는 선택, 그런 선택을 통해 나는 나 스스로가 조금씩 더 나아지기를 바란다. 추상적이지만 그런 ‘나아짐’을 fitness function으로 정의할 수 있다고 가정하면 어떨까? 보통 우리는 우리가 영위하는 삶의 State \(S\) 가 최선이 아니라고 생각하고, 더 나은 State \(S'\)을 찾기를 바라지 않는가?
그런 State를 우리가 찾고자 하는 Solution이라고 가정한다면, 어떤 탐색 기법을 쓸 수 있을까?
Local Search, GA, and …
탐색 기법 중에서 Local Search를 먼저 생각해볼 수 있다. 현재 내가 선택한 답에서, 어떤 작은 변형을 거치면 더 나은 답으로 옮겨갈 수 있을까? 그렇게 계속해서 조금씩, 더 나은 답을 찾아가다 보면 언젠가 더이상 그런 변형을 통해서는 더 나아질 수 없는 지점에 도달할 것이다.
그게 내가 얻을 수 있는 최적의 답이라는 보장은 없지만, Local Search의 장점은 많은 것을 기억하지 않아도 된다는 것이다. 그저 현재의 점, 현재의 상태에서 가장 좋아 보이는 방향으로 발걸음을 떼면 된다.
하지만 그런 변형을 어떻게 정의하느냐에 따라, 그리고 내가 어떤 지점에서 탐색을 시작하느냐에 따라 결과는 많이 달라진다. 운이 좋으면 Local Optimum에 빨리 도달할 수도 있지만, 운이 나쁘면 한참 도달하기도 전에 유한한 삶을 마감해 버릴 수도 있다. 이런 질문을 던질 수도 있다. Local Search는 그저 하나의 최선을 생각하며 맹목적으로 달려가는 삶에 비유할 수 있다. 그 과정에서 똑같은 연산을 끝없이 반복하는, 자아를 가진 ‘우리’라는 점은 과연 행복할까?
그러면 ‘유전’을 닮은 Genetic Algorithm은 어떨까? 어쩌면 GA가 대안이 될 수도 있다. 내 생각에 이 알고리즘의 핵심은 ‘협동’에 있기 때문이다. 물론 진화는 자연 선택, 그리고 생존에 기반하기 때문에 단순히 협동이라고 말하는 것이 이상할 수도 있다. 좀더 협동에 집중한 particle swarm optimization이라는 알고리즘이 있기도 하다(새 군집의 먹이 찾기 모델링). 하지만 알고리즘의 결과적인 측면에서 볼 때 각자가 찾은 해답을 합쳐나감으로써 혼자서는 찾을 수 없는 답을 만들어낼 수 있다. ‘개인’을 나타내는 하나의 점만 고려하는 것이 아니라, ‘population’이라는 군집을 생각하고, 각자가 찾은 해답을 합쳐서 다음 세대의 해들을 생성한다. 이런 과정을 우리가 주변, 그리고 온라인의 사람들과 상호작용하는 과정에 대입해 생각할 수도 있을 것이다.
하지만 GA는 ‘개인’이 아니라 전체 그룹의 성장에 집중한다. 결과적으로 최적해는 그룹에 속한 일부만이 갖게 될 것이다. population을 이루는 각각의 개체에 우리 스스로를 대입한다면, 조금 비극적인 장면이 상상된다. 우리가 실제로 인식하는 fitness function은 상대적이기 때문이다.
100년 전의 삶과, 지금의 삶을 비교하면 어떤 점에서는 많은 진보를 이루었다고 생각할 수 있다. 어딘가로 이동하는 것도, 다양한 컨텐츠를 접하는 것도 훨씬 쉬워진 세상이다. 하지만 사람들이 느끼는 행복의 크기는 줄어든 것처럼만 보인다. 우리가 best individual이 아니라는 사실을 받아들여야 하기 때문이다.
이런, 이쯤에서 인정해야겠다. 사실 삶을 좌표 공간으로 완전히 모델링하는 것은 불가능하다. fitness function은 오직 목적을 반영할 뿐, 그걸 찾아가는 과정의 의미는 고려할 수 없기 때문이다. 함수의 값이 가장 높은 지점에 도달하는 것으로 삶의 의미를 정의하는 것은 천진난만한 생각이다. (메인 페이지에 naive writer라고 소개를 걸어놓아서 다행이다)
그래도 이런 생각의 시도 자체가 무의미한 것은 아니라고 생각한다.
시행착오를 지향하는 삶
삶 전체를 휴리스틱 알고리즘으로 풀어보려는 시도는 허무하게 좌절되었지만, 여전히 우리가 겪는 일상, 혹은 학문적인 문제들에 대해서 휴리스틱으로 생각하는 것이 필요하다는 생각이 들었다.
공부를 하고, 조금씩 아는 것이 생길수록 맞닥뜨리는 부작용은 지나치게 생각하고, 계산한다는 것이다. 알게 될수록 두려움이 많아진다, 아니, 사실은 어설프게, 안다고 생각할 뿐인데 그런 생각이 스스로에게 독이 되는 경우가 많다. 틀리는 것이 못내 두려운 것이다. 내가 이만큼 알고 있고, 다른 사람들도 내가 이걸 알 거라고 생각할 텐데, 이걸 틀리게 말하면 분명히 비웃음을 살 거야- 하는 생각이 든다. 완벽하다고 스스로 생각할 때까지 종종 입을 다물고, 침묵하는 습관이 생겼다. 스스로가 갖고 있는 ‘직관’이라는 무기를 논리적인 과정을 거쳐 나온 생각이 아니라는 이유로 억압하게 되기 쉬운 것 같다.
휴리스틱 알고리즘을 배우면서 다시 깨닫게 된 건 그런 것이다. 알고리즘의 핵심은 ‘탐색’, 그리고 여러 번의 시행착오에 있다. 특정한 문제에 대한 체계적인 해답을 암기하기보단, 올바른 방향으로 생각한 답을 발전시킬 수 있는, 그런 보편적인 도구(operator)를 갖게 되는 게 필요하다. 새로운 것을 쉽게 받아들이고 의미있는 질문을 던지는 사람들을 관찰하며 얻어낸 결론이다. 직관에 의존한 불완전한 답을 내놓는 것을 두려워하지 말자. 잘못된 것이 있다면 조금씩 고쳐나가면서, 그리고 주변에 있는 사람들의 생각을 하나씩 받아들여나가면서 좀더 괜찮은 답에 도달할 수 있다는 믿음을 갖자. 시행착오를 필연적인 것으로 받아들이고, 그런 시행착오 과정 자체를 발전시키기 위해 노력하는 삶. 불완전하지만, 삶이라는 landscape를 이런 관점에서 바라보고 싶다.