다른 형태의 탐색과 그 응용

(Alternative Search Formulations and Applications)

 

인공지능-지능형 에이전트를 중심으로 : Nils J.Nilsson 저서, 최중민. 김준태. 심광섭. 장병탁 공역, 사이텍미디어, 2000  (원서 : Artificial Intelligence : A New Synthesis 1998), Page 191~199 

 

할당 문제 (Assignment Problems)        

단계적인 방법 (Constructive Method)        

휴리스틱 교정 (Heuristic Repair)        

함수 최적화 (Function Optimization) 

 

 

에이전트가 행동을 선택하는 문제 외에도 탐색 기법의 응용 분야는 다양하다. 제약조건이 있는 변수들에 값을 할당하는 문제나 최적화 문제 등이 여기에 해당한다. 이러한 문제들에 대해서는 특수한 방법들이 개발되었으며, 에이전트를 설계하는 것과 직접 관련이 있지는 않지만, 이들도 중요한 AI 기법들이다. 이런 기법들 중 일부를 이 장에서 소개한다.

할당 문제

그래프 탐색 문제에서 목표 노드의 조건은 특정한 자료 구조나 그 노드에 대한 상태 표현을 지정하여 정의할 수도 있고, 그 노드의 자료 구조에 대한 제약조건 (constraints) 에 의해 암시적으로 정의될 수도 있다. 어느 경우에나 주어진 문제가 에이전트가 실행할 행동의 순서를 찾는 것일 때는 목표 노드의 자료 구조 자체에 주된 관심이 있는 것은 아니다. 관심 있는 것은 목표에 도달할 수 있는 행동의 순서인 것이다. 하지만 목표 노드가 특정한 자료 구조로 정의되지 않고 제약조건에 의해 정의되어 있는 경우에는 그러한 조건을 만족시키는 자료 구조를 보이는 것이 문제일 수도 있다. 이 경우 그래프 탐색 방법은 적절하지 않을 수도 있다. 이와 같은 종류의 문제들을 제약조건 만족 (constraint-satisfaction) 문제라고 한다. 이 범주에 들어가는 유명한 문제 중 하나는 제약조건이 있는 변수들에 값을 할당하는 것이다. 이런 문제를 할당 문제 (assignment problem) 라고 하며, 이제부터 이 문제에 대하여 이야기할 것이다.
제약조건 만족 문제도 그래프 탐색 방법으로 풀 수 있다. 목표 노드는 제약조건을 만족하는 자료 구조나 상태 표현으로 나타나는 노드이다. 연산자는 한 자료 구조를 다른 자료 구조로 변경시킨다. 시작 노드는 어떤 초기 자료 구조이다. 할당 문제에 대한 좋은 예는 8 퀸 (queen) 문제이다. 이 문제는 체스판 위에 8 개의 퀸을 어느 행, 열, 또는 대각선에도 반드시 하나의 퀸만이 있어야 한다는 제약조건하에서 행과 열에 하나씩 배치하는 문제이다 (즉, 체스의 규칙에 따르면 어느 퀸도 서로 잡지 못하도록 배치하는 것이다). 이 문제에 대한 한 가지 답이 그림 1 에 나타나 있다. 이 문제는 (열 1 에 있는 퀸의 위치, 열 2 에 있는 퀸의 위치, ..., 열 8 에 있는 퀸의 위치) 라는 변수들에 행 1, 행 2, ..., 행 8 에 있는 값 중 하나씩을 할당하는 것과 같으므로 이것도 할당 문제라고 할 수 있다.

 

그림 1  8 퀸 문제의 한 가지 답

이 문제를 그래프 탐색 문제로 설정한다면, 간단한 자료 구조는 각 칸에 퀸 (1) 또는 공백 (0) 을 나타내는 두 가지 기호 중 하나가 있는 8×8 배열일 것이다. 목표 상태는 모두 서로 잡히지 않도록 배치된 8 개의 퀸이 있어야 한다는 조건에 의해 암시적으로 정의된다. 상태들을 서로 연결하는 연산자는 아직 8 개의 퀸을 갖고 있지 않은 배열에 하나의 퀸을 추가하는 것일 수도 있고, 하나의 퀸을 다른 칸으로 이동하는 것일 수도 있다. 할당 문제에서는 목표까지의 경로는 중요한 것이 아니므로, 시작 상태와 연산자를 무엇으로 할 것인가에 여러 가지 선택이 가능한 경우가 많다.
아주 방대한 상태 공간을 가진 할당 문제의 또 다른 예로, 단어 맞추기 (crossword) 퍼즐을 생각해 보자.

그림 2 단어 맞추기 퍼즐의 배열

단어 맞추기 퍼즐의 한 예를 그림 2 에 나타내었다. 문제는 일반적인 단어 맞추기 퍼즐에서처럼 모든 행과 열이 영어 단어가 되도록 배열의 모든 빈칸을 글자로 채우는 것이다 (여기서는 퍼즐을 푸는 사람에게 주어지는 힌트를 만드는 부분은 고려하지 않는다). 이 문제에서 상태 표현은 글자와 공백 (그리고 검은 칸들) 의 배열이다. 목표 상태는 단어 맞추기 퍼즐의 정당한 답이 되는 임의의 배열이다. 상태들을 연결하는 연산자는 임의의 글자와 공백 배열에서 임의의 다른 글자와 공백 배열을 만들어내는 모든 조작이 될 수 있다. 예를 들어, 어떤 연산자는 빈 행이나 열에 하나의 단어를 추가하는 것일 수도 있고, 하나의 글자를 다른 글자로 바꾸는 것일 수도 있다.

단계적인 방법

그림 3 단계적인 형태의 상태 공간

할당 문제를 풀기 위해 지난 장에서 다룬 탐색 방법들을 사용할 수 있다. 가장 간단한 방법은 할당의 순서에는 관심이 없긴 하지만, 필요한 할당을 한 단계씩 만들어가는 것이다. 우선 전혀 할당을 하지 않은 시작 노드에서 출발한다. 8 퀸 문제의 경우, 여기에 해당하는 자료 구조는 모든 칸이 0 인 배열이다. 각 연산자는 퀸들 사이의 제약조건을 만족하는 배열이 되도록 하나의 퀸을 추가한다. 모든 열에 하나의 퀸이 있어야 하므로, 보편성을 잃지 않고서도 깊이 0 인 노드에 적용되는 연산자는 첫 번째 열에 퀸을 넣고, 깊이 1 인 노드에 적용되는 연산자는 두 번째 열에 퀸을 넣는 식으로 연산자의 적용을 규정할 수 있다. 답이 한 단계씩 만들어져 가기 때문에 이러한 방법을 단계적인 방법 (constructive method) 이라고 한다 (나중에 이와 대조적인 방법을 소개할 것이다).
그림 3 에 8 퀸 문제와 단어 맞추기 퍼즐에 대하여 단계적인 방법을 사용했을 때 만들어지는 탐색트리의 예를 나타내었다 (알아보기 쉽게 하기 위해 1 과 0 의 배열 대신 퀸의 자리에 X 를 표시하였다). 특히 이전의 노드에서 새 노드를 만들어내기 위해 사용된 연산자들을 주목하라. 단어 맞추기 퍼즐의 탐색 공간은 매우 크므로 각 노드에 적용할 수 있는 수천 개의 다른 연산자들이 있다.
제약조건 전파 (constraint propagation) 라는 계산 기법을 사용하면 탐색 공간을 현저히 줄일 수 있다. 이 방법은 각 변수에 차례로 값을 할당하는 단계적인 기법과 결합하여 사용된다. 8 퀸 문제의 축소판에 이것이 어떻게 적용되는지를 보임으로써 이 기법에 대해 설명하겠다. 4 × 4 체스판에 4 개의 퀸을 서로 잡을 수 없도록 배치하는 문제를 생각해 보자. 퀸이 놓여질 수 있는 1 에서 4 까지의 4 개 열을 나타내는 4 개의 변수 가 있다. 각 변수는 행 번호에 따라 1, 2, 3, 4 4 개의 값 중 하나를 가질 수 있다. 즉, 예를 들어 q3 가 2 라면 세 번째 열의 두 번째 행에 하나의 퀸이 있다는 것을 의미한다. 4 퀸 문제는 이 변수들의 값에 제약조건을 가지고 있다. 예를 들면 이 1 이라면 는 1 이나 2 가 될 수 없다.
제약조건은 제약조건 그래프 (constraint graph) 라는 방향성 그래프로 표현된다. 이 그래프의 노드는 변수의 이름과 그 변수에 가능한 값들의 집합으로 나타낸다. 노드 와 노드 사이를 연결하는 제약조건 아크 (constraint arc) 는 변수 의 값이 변수 의 값에 의해 제한된다는 것을 의미한다. 그림 4 에 4 퀸 문제에 대한 이런 그래프의 예를 보였다. 이 문제에서 각 변수는 모든 다른 변수를 제한하므로 모든 노드들이 다른 모든 노드들로 아크를 가지고 있다. 만일 아크의 끝에 있는 변수의 가능한 각 값에 대하여 아크의 시작에 있는 변수에 제약조건을 위배하지 않는 하나 이상의 값이 있다면 방향성 아크 를 일관되다 (consistent) 고 한다. 그림 4 의 아크 들은 모두 각 값에 대하여 제약조건을 위배하지 않는 값이 존재하므로 일관된 것들이다.

그림 4  4 퀸 문제의 제약조건 그래프

한 개 이상의 변수에 값을 할당하고 나면, 아크의 일관성 개념을 이용하여 다른 변수들의 가능한 값 중 일부를 제외시킨다. 제약조건 전파 과정은 그래프의 아크를 따라 반복되면서 아크의 일관성을 유지하기 위해 아크의 끝에 있는 변수들의 값을 삭제해 나간다. 이 과정은 더 이상 삭제할 값이 없을 때 종료한다. 예를 들어 보자. 변수 에 1 을 할당하면서 깊이우선 탐색이 출발한다고 하자 (즉, 1 열 1 행에 퀸을 놓은 것이다) 이 할당에 대해 제약조건 전파를 적용하면 다음과 같이 진행된다.

 

그림 5   일 때 제약조건 그래프

이 단계가 되면 그림 5 에 있는 그래프가 남게 된다. 제약조건 전파를 계속하면 그림에 있는 것과 같이 q3 의 모든 값이 삭제되고, 따라서 인 경우에는 답이 없다는 것을 알 수 있다. 그러므로 탐색 그래프에서 인 노드 아래로는 더 이상 탐색을 진행할 필요가 없고, 되추적 (backtrack) 하여 인 노드를 생성한다.
이번에는 라고 하고 제약조건 전파를 수행한다. 처음 몇 단계는 다음과 같이 진행된다.

 

그림 6   일 때 제약조건 그래프

이렇게 하고 나면 그림 6 의 그래프가 만들어진다. 제약조건 전파를 계속하면 각 노드에 하나의 변수값만 남기고 모두 삭제하게 되어 모든 아크가 일관되게 된다. 따라서 탐색을 완료하기 전에 이미 하나의 답만이 존재한다는 것을 알 수 있으며, 제약조건 전파가 그러한 답을 구한 것이다.
이 예처럼, 어떤 경우에는 제약조건 전파에 의해 어떤 변수의 모든 값이 삭제되어, 변수들에 대한 이전까지의 할당값을 가지고는 탐색 문제에 답이 없다는 것을 보이기도 한다. 이 경우에는 제약조건 전파의 기본적인 개념은 일관성에 대한 보다 복잡한 검사를 수행하는 데까지 확장되었으나, 아마 가장 경제적인 응용은 방금 보인 것과 같이 아크의 일관성을 검사하는 일일 것이다. 제약조건 전파는 영상 분석 (visual scene analysis) 에서 라인에 +, -, 또는 → 를 지정하는 문제나 이 책의 뒷부분에서 다루는 명제 만족성 (propositional satisfiability) 문제와 같은 다양한 흥미 있는 문제들에 적용되어 왔다. 이 방법에 대한 전체적인 개관과, 이 방법의 확장, 그리고 응용에 대해서는 [Kumar 1992] 를 참조하라.

휴리스틱 교정

그래프 탐색 방법으로 풀 수 있도록 문제를 설정하는 또 다른 방법이 있다. 이 방법은 제약조건을 확실히 만족시키지 못할 것 같은 답을 제시하면서 시작하여, 만족이 될 때까지 그것을 교정하는 방식으로 수행되기 때문에 교정 방법 (repair approach) 이라고 한다. 따라서 시작 노드는 일반적으로 모든 제약조건을 만족시키지 못하는 자료구조가 된다. 연산자는 다른 해에 해당하는 새로운 자료 구조를 만들어내는 것이다.

 

그림 7  8 퀸 문제의 교정 과정

예를 들어 8 퀸 문제에서는 각 열의 임의의 행 위치에 하나씩 8 개의 퀸을 놓고 시작한다. 그리고 나서 위배되는 제약조건이 줄어들도록 하나의 퀸을 이동함으로써 잘못된 답을 교정해 나간다. 최소 충돌 (min-conflict) [Gu 1989, Minton, et al. 1992] 이라고 하는 교정 방법에서는 각 열을 차례로 보면서 그 열이 각 칸에 그 칸을 공격할 수 있는 퀸의 수를 기록한다. 그리고 나서 그 열에 있는 퀸을 칸 중에서 공격하는 퀸의 수가 가장 적은 (충돌이 가장 적은) 칸으로 이동한다. 같은 값인 경우에는 임의로 선택한다. 이런 작업은 약간 더 교정된 답에 해당하는 자식 노드를 만들어내며, 이와 같은 작업을 열을 따라 계속해 나간다. 그림 7 에 최소 충돌 방법을 사용하여 8 퀸에 대한 깊이우선 탐색을 수행하는 과정을 나타내었다. 여기서도 퀸의 위치를 X 로 나타내었으며, 칸에 있는 숫자는 그 칸을 공격하는 퀸의 수를 나타낸다. 이와 비슷한 교정기반 방법 [Minton, et al. 1990] 이 백만 퀸 문제와 같은 훨씬 큰 문제를 푸는 데 사용된 바 있다.
단어 맞추기 퍼즐에 교정 방법을 적용하면, 시작 노드는 글자들이 꽉 찬 임의의 배열이 된다. 그리고 나서 하나의 글자를 행이나 열이 단어가 되도록 하는 방향으로 갈 가능성이 있는 다른 연산자들이 있으므로 단어 맞추기 퍼즐의 탐색 공간은 엄청나게 큰 것이다.
단계적인 방법을 사용하는가 혹은 교정 방법을 사용하는가에 따라, 그리고 어떤 상태와 연산자를 사용하는가에 따라 탐색의 난이도에 지대한 영향을 미치게 된다.

함수 최적화

어떤 문제는 명시적인 목표 조건 대신에 자료 구조에 대한 함수 가 있고, 이 함수가 최대 (혹은 최소) 가 되는 자료 구조를 찾고자 하는 경우가 있다. 하나의 자료 구조를 공간에 있는 하나의 점이라고 생각하면, 이 함수는 이 공간상의 지형 (land-scape) 이라고 할 수 있다. 이 지형을 돌아다니면서 고도가 높은 점을 찾는 일련의 방법들이 있다. 이 경우 전역 최대값 (global maximum) 을 모르기 때문에 고도가 최대인 점에 다달았는지 확실하게 알 수 없다.
공간을 돌아다니는 기법 가운데 언덕 오르기 (hill-climbing) 방법은 한 점에서 고도가 가장 높은 인접한 점으로 이동하면서 다니는 것이다. 언덕 오르기 방법은 보통 현재의 점보다 높은 고도를 가진 인접한 점이 없으면 종료된다. 따라서 지역 최대값 (local maxima) 에 걸릴 수 있다.
언덕 오르기를 하기 위해 그래프 탐색 방법을 사용할 수 있다. 노드는 일반적인 자료 구조로 표현한다. 연산자는 주어진 자료 구조를 인접한 노드의 자료 구조로 변환하는 것에 해당한다. 언덕 오르기는 단일한 경로를 쫓아가면서 되추적이 없는 깊이우선 탐색과 같이) 높이를 계산하고, 더 낮은 지점으로 내려가지는 않는다. (지역) 최소값을 갖는 노드를 찾는 문제에 대한 간단한 언덕 오르기 알고리즘은 다음과 같다.

 

그림 8  2 색 컬러링 문제를 푸는 과정

이 알고리즘은 항상 가장 큰 값을 갖는 자식 노드를 (그리고 그 값이 부모 노드의 값보다 작지 않은 경우에만) 확장한다는 것과 되추적을 하지 않는다는 것을 제외하고는 깊이우선 탐색과 매우 유사하다. 언덕 오르기에서의 이동은 되돌릴 수 없다.
언덕 오르기 (여기서는 실제로 언덕 내려가기) 를 3 × 3 격자의 칸에 에 대하여  대한 컬러링 (coloring) 문제를 가지고 설명하도록 하자. 임의의 빨강과 파랑 칸 배치가 주어졌을 때, 같은 색을 가진 인접한 노드 쌍이 최소가 되는 색 배치를 찾고자 한다. 즉, = 노드 에서 같은 색을 가진 인접한 노드 쌍의 수라고 할 때, 모든 에 대하여 인 노드 를 찾는 것이다. 연산자는 어느 칸에서나 색이 빨강에서 파랑으로 혹은 그 반대로 변경되도록 하는 것이라고 하자. 그림 8 에 이 문제에 대한 그래프의 일부와 언덕 내려가기 (hill descending) 방법이 쫓아가는 경로를 나타내었다.
이동을 해도 의 값이 바뀌지 않는 경우에는 탐색 공간 안의 평원 (plateau) 위에서 이동한다고 말한다. 언덕 오르기 알고리즘은 평원 위에서 이전에 방문했던 노드들을 다시 방문하면서 더 높은 지대로 올라가지 못하고 무한히 방황할 수도 있다. 값이 바뀌지 않는 횟수를 기억하는 카운터를 추가하면 이러한 방황에 한계를 줄 수 있다. 추가적인 메모리를 사용하여 현재 노드와 같은 값을 갖고 있는 전에 방문했던 노드로는 이동하지 않게 함으로써 평원 문제를 개선할 수 있다.
또 다른 문제는 탐색 공간 안의 산등성이 (ridges) (또는 반대로 도랑) 때문에 발생한다. 언덕 오르기의 경우 모든 이동이 더 낮은 곳으로 가는 것이라도, 연속적인 두 번의 이동에 의해 더 높은 곳으로 갈 수 있는 것을 말한다. 이러한 문제를 그림 9 에 나타내었다. 어떤 이동을 선택해도 산등성이에서 벗어나 더 낮은 곳으로 가게 되지만, 연속적으로 두 번 이동하면 산등성이의 더 높은 곳으로 갈 수도 있다. 산등성이 문제는 하나 이상의 이동을 결합하여 "매크로 이동 (macro-move)" 을 만들거나 제한된 범위의 예견 (lookahead) 탐색을 할 수 있게 함으로써 해결되는 경우도 있다.

 

그림 9   산등성이 (ridge) 문제

지역 최대값에 걸리는 문제를 해결하는 방법으로 여러 개의 개별적인 언덕 오르기 탐색을 (동시에 혹은 순차적으로) 서로 다른 위치에서 시작할 수도 있다. 각 탐색이 서로 다른 지역 최대값에서 끝나게 되면, 이들 중 가장 큰 값을 선택하는 것이다. 기계 진화에서 다루었던 GP 방법은 여러 명의 등산가 (climber) 가 동시에 동작하며, 자식 등산가를 만들어냄으로써 이동을 수행하는, 확률론적 언덕 오르기의 한 종류라고 할 수 있다. 여기서는 적합도 함수 (fitness function) 가 최적화하려는 함수에 해당한다 GA 와 GP 방법의 효율성을 일반적인 언덕 오르기의 여러 형태와 비교할 수 있다 [Juels & Wattenberg 1996, O'Reilly & Oppacher 1994].
모의 담금질 (simulated annealing) [Kirkpatrick, Gelatt, and Vecchi 1983] 이라고 알려진 방법도 지역 최대값 문제를 다루는 유용한 방법이다. 이 방법에는 여러 가지 형태가 있다. 한 가지 형태는, 가능한 이동들에 대한 확률 분포에 따라 이동을 선택하는 것이다. 확률 분포는 낮은 고도를 가진 노드를 선호하도록 되어 있다 (언덕 내려가기의 경우). 노드를 선호하는 경향이 무시할 만큼 작은 분포를 가지고 시작하여, 점차 선호하는 경향을 증가시켜서, 나중에는 압도적인 확률로 고도가 낮은 노드 쪽으로 이동하게 하는 것이다. 이렇게 하면 시작 부분에서는 지형을 임의로 걸어다니게 된다. 하지만 이 과정이 계속되면 나중에는 계곡 중의 하나로 내려가기 시작한다. 만일 계곡이 아주 깊지 않다면, 일반적으로 아주 넓지도 않을 것이며, 이어서 임의의 이동을 하게 되면 계곡에서 빠져 나오게 된다. 넓은 (따라서 깊을 가능성이 큰) 계곡일수록 빠져 나올 가능성이 적어질 것이며, 따라서 마지막에는 (임의의 이동이 없는 상황에서) 가장 깊은 지점으로 내려가게 된다. 이 방법은 금속의 온도를 서서히 낮추어서 재료의 결정 구조가 최소의 에너지 상태가 되도록 하는 야금술에서의 담금질에 비유하여 이름을 붙인 것이다. 모의 담금질에서 확률 분포의 너비를 조정하는 매개변수를 온도라고 한다.