Tabu search는 simulated annealing, genetic algorithm 등과 같이 최적화 문제의 형태에 상관없이 주어진 최적화 문제를 풀기 위한 메타휴리스틱 (metaheuristic) 알고리즘이다. 기존의 simulated annealing, genetic algorithm과 같은 최적화 알고리즘들은 기본적으로 neighbor search를 기반으로 동작하기 때문에 current solution이 개선되는 방향으로만 진행하려는 성질이 있다. 이러한 성질로 인해 simulated annealing 및 genetic algorithm은 빈번하게 [그림 1]과 같은 지역 최적점 (local optimum)에 수렴한다. Tabu search는 빈번하게 지역 최적점에 수렴하는 문제를 해결하기 위해 지역 최적점에 대한 정보를 저장하여 이 정보를 기반으로 지역 최적점을 회피한다. 이때 지역 최적점에 대한 정보를 tabu라고 한다.
[그림 1] 지역최적해 수렴 문제
Tabu search에 대해 서술하기 위해 아래와 같은 용어를 정의한다.
feasible solution: current solution과 같은 의미이며, 이 글에서는 $s$로 표기한다.
trial solutions: feasible solution에 대한 neighbor search를 통해 생성된 solution이다. Tabu search는 시간이 $t$인 시점에서 생성된 trial solution들 중에서 시간 $t+1$의 feasible solution을 선택한다.
tabu queue: tabu에 해당하는 사항들이 저장되는 자료구조로써, 일반적인 queue와 같이 먼저 입력된 데이터가 먼저 출력되는 구조를 갖는다.
Tabu search는 feasible solution으로부터 trial solution들을 생성하고, tabu queue에 지역 최적점에 대한 정보를 저장하는 과정을 반복하면서 최적해를 찾는다. 아래의 [알고리즘 1]은 tabu search의 동작을 나타낸다. [알고리즘 1]에서 neighbor search method $f$는 feasible solution에 대한 trial solution을 생성하는 함수이다. 또한, $isContainTabu$는 trial solution에 tabu의 존재 하는지를 검사하고, $addTabu$는 feasible solution과 trial solution을 비교하여 새로운 tabu를 결정한다. 세 함수는 특정한 형태가 있는 것이 아니라, 문제를 정의할 때 알고리즘 설계자가 직접 설정해야한다.
기존의 simulated annealing, genetic algorithm과는 다르게 tabu search에서는 알고리즘 수행 중에 tabu queue라는 별도의 memory를 유지한다. Tabu search에서 tabu queue의 역할은 시간 $t$에서 선택된 trial solution의 특성을 저장하여 시간 $t+1$의 trial solution들이 $t$에서 선택된 trial solution의 특성을 갖지 않도록 하는 것이다. 이를 통해 tabu search는 다양한 trial solution을 탐색할 수 있으며, 지역 최적점으로 수렴하는 현상을 방지한다. 아래의 [그림 2]는 그래프에서 edge들을 선택하는 문제에 대한 tabu의 예시를 보여준다.
[그림 2] 시간 $t$에서의 feasible solution과 선택된 trial solution
[그림 2-a]는 시간 $t$에서의 feasible solution을 나타내고, [그림 2-b]는 시간 $t$에서 선택된 trial solution을 나타낸다. 시간 $t$에서 선택된 trial solution은 feasible solution에서 edge ${e}_{CD}$가 제거되고, edge ${e}_{BE}$가 추가된 조합이다. 따라서, tabu queue에는 edge ${e}_{BE}$가 추가된다. Tabu queue의 크기는 알고리즘의 parameter중 하나이며, queue가 모두 찼을 경우에는 일반적인 queue의 동작처럼 가장 먼저 입력된 데이터가 제거된다.
Tabu search는 특정한 알고리즘이 아니라, 문제를 해결하는 방법론에 가깝기 때문에 어떠한 문제를 해결하기 위해 tabu search를 구현할 때는 아래와 같은 4가지 연산을 알고리즘 설계자가 직접 정의해야 한다.
- 초기 feasible solution 생성 연산
- Neighbor search
- Tabu 검사 연산
- Tabu 추가 연산
각각의 연산에 대한 자세한 설명과 예시는 다음과 같다.
Tabu search에서는 새로운 feasible solution을 생성하기 위해 현재 feasible solution의 주변을 탐색한다. 그러나 알고리즘의 초기에는 feasible solution이 존재하지 않기 때문에 초기 feasible solution을 생성하는 연산을 별도로 정의해야 한다. 일반적으로 가장 많이 이용되는 초기 feasible solution 생성 연산은 feasible solution의 각 원소를 임의의 값으로 설정하는 것이다. 이러한 방법은 개념이 간단하고, 구현이 쉽기 때문에 메타휴리스틱, 머신러닝 등의 분야에서 많이 이용된다. 물론, 최적해의 특성을 예측하여 초기 feasible solution을 생성하는 것도 가능하며, 예측에 의해 초기 feasible solution을 생성하는 방법이 더 좋은 성능을 보여주는 경우도 있다 [1, 2].
Neighbor search는 feasible solution으로부터 trial solution을 생성하는 연산이다. 문제의 특성에 따라 다양한 방법들이 neighbor search를 위해 사용될 수 있다. 아래의 [그릠 3]은 [그림 2]의 edge 선택 문제에 대한 neighbor search의 한 예시를 보여준다.
[그림 3] Neighbor search의 예시
[그림 3]에서는 feasible solution에서 하나의 edge를 제거 (drop)하고, feasible solution에 존재하지 않았던 새로운 edge를 하나 추가 (add)함으로써 trial solution을 생성하고 있다. Feasible solution의 특성을 어느정도 보존하는 탐색 방법이라면, neighbor search로써 이용될 수 있다. 그러나 [그림 2]와 같은 edge 선택 문제에서는 feasible solution의 각 요소의 순서를 임의로 뒤섞는 등의 방법은 neighbor search로써 적절하지 않기 때문에 풀고자 하는 문제에 맞는 neighbor search를 정의하는 것이 중요하다.
주어진 solution에 대해 solution에 tabu queue에 포함된 요소가 존재하는지를 검사한다. [그림 2]의 예시에서 tabu 검사 연산은 tabu queue에 포함된 edge가 존재하는지를 검사하는 것과 같다.
Feasible solution과 선택된 trial solution의 차이점을 결정하여 이를 tabu queue에 추가하는 역할을 한다. [그림 2]의 예시에서는 feasible solution에 edge $e_{BE}$가 추가되어 trial solution이 생성되었기 때문에 tabu 추가 연산은 tabu queue에 $e_{BE}$를 추가한다.
이 예제는 tabu search의 동작을 간단하게 설명하기 위한 것이다. 이 글의 예제와 같이 단순한 문제에 tabu search를 적용하는 것은 매우 비효율적인 판단이지만, tabu search의 동작을 명확하게 서술하기 위해 이와 같은 문제를 선택하였다.
아래의 [그림 4]의 좌측과 같은 8개의 물건 $\{x_{1}, x_{2}, ..., x_{8}\}$이 있으며, [그림 4]의 우측은 물건의 중요도와 무게를 고려한 최종 cost라고 가정한다 (중요한 물건이라면, 무게가 많이 나가도 cost가 적게 계산될 것이다). 이 예제에서 tabu search를 이용하여 풀고자 하는 문제는 정확히 4개의 물건만 가져갈 수 있을 때, cost의 합을 최소화하는 물건의 조합을 찾는 것이다.
[그림 4] 예제의 입력 데이터
만약 어떠한 제약도 없다면, $x_2, x_5, x_6, x_7$을 가져가면 문제는 해결되겠지만, 이 예제에서는 물건을 가져갈 때 다음과 같은 제약 조건을 따라야 한다고 가정한다.
$x_2$와 $x_7$은 같이 가져갈 수 없다.
$x_5$는 $x_6$을 가져가려고 선택했을 때만 가져갈 수 있다.
물건이 선택되었다면 ${x}_{i}$의 값이 1이고, 그렇지 않으면 0이라고 가정할 경우, 위의 제약 조건을 아래의 [식 1, 2]와 같이 정의할 수 있다.
이 예제에 대해 tabu search를 적용하여 최적해를 구하는 과정은 다음과 같다.
1) 임의로 초기 feasible solution을 생성
문제에서 4개의 물건만 가져갈 수 있다고 했으므로, 최적해의 크기는 4이다. 또한, 총 8개의 물건이 있으므로 1~8까지의 난수를 4번 생성하여 초기 feasible solution으로 설정한다. 만약, 4번의 난수 생성에서 2, 1, 6, 7이 생성되었을 경우에 초기 feasible solution은 [2 1 6 7]이 된다.
2) 초기 feasible solution의 cost를 계산하고, 그 값을 best cost로 설정
위의 [그림 4]를 참조하여 초기 feasible solution의 cost를 계산하면, 초기 feasible solution [2 1 6 7]의 cost는 31이 된다. 그러나 제약 조건인 [식 1]에 의하면 2번째와 7번째 물건은 같이 선택될 수 없으므로, 초기 feasible solution의 cost에는 패널티가 부여된다. 패널티의 값은 문제를 정의할 때 설정하는 값으로써, 이 예제에서는 100이라고 가정한다. 따라서, 초기 feasible solution [2 1 6 7]의 최종 cost는 131이 된다. 그 다음, 초기 feasible solution의 cost를 best cost로 설정한다.
3) 현재 feasible solution으로부터 trial solution들을 생성
Neighbor search를 이용하여 feasible solution으로부터 trial solution들을 생성한다. Tabu search에서 trial solution을 생성하는 연산은 다양한 방법이 있을 수 있다. 이 예제에서는 위의 [그림 3]과 같이 현재 feasible solution의 한 요소를 임의로 제거하고, feasible solution에 존재하지 않는 임의의 요소를 추가하는 방법을 neighbor search로써 이용한다. Feasible solution [2 1 6 7]로부터 아래와 같은 4가지 trial solution들이 임의로 생성되었다고 생각한다.
[2 3 6 7]
[2 5 6 7]
[8 1 6 7]
[2 1 5 7]
앞의 과정에서 생성된 trial solution들의 cost를 계산한다. 계산된 cost는 아래와 같다.
$cost$([2 3 6 7]) = 7 + 11 + 9 + 5 + 100 = 132
$cost$([2 5 6 7]) = 7 + 8 + 9 + 5 + 100 = 129
$cost$([8 1 6 7]) = 12 + 10 + 9 + 5 = 36
$cost$([2 1 5 7]) = 7 + 10 + 8 + 5 + 100 + 100 = 230
각 trial solution의 cost를 계산하는 과정에서 1, 2번째 trial solution은 [식 1]의 제약 조건을 위반하였기 때문에 100의 패널티가 부여되었다. 또한, 4번째 trial solution은 [식 1]과 [식 2]의 두 제약 조건을 모두 위반하였기 때문에 200의 패널티가 부여되었다. 모든 trial solution의 cost를 계산한 다음에는 cost가 가장 낮은 trial solution을 선택한다. 만약, trial solution의 cost가 위와 같이 계산되었다면, 3번째 trial solution [8 1 6 7]이 선택된다.
5) 선택된 trial solution을 feasible solution으로 설정
현재의 실행은 tabu search의 첫 번째 반복이기 때문에 현재 tabu queue는 당연히 비어있다. 따라서, 선택된 3번째 trial solution [8 1 6 7]은 당연히 어떠한 tabu도 포함하고 있지 않기 때문에 즉시 feasible solution으로 선택된다.
6) 현재 feasible solution이 생성될 때 반영된 사항을 tabu queue에 입력
현재의 feasible solution [8 1 6 7]은 이전의 feasible solution [2 1 6 7]에서 첫 번째 요소에 2가 제거되고, 새로운 요소 8이 추가되어 생성되었다. 따라서, [그림 5]와 같이 현재 feasible solution이 생성될 때 반영된 사항에 해당하는 8이라는 요소를 tabu queue에 저장한다.
[그림 5] Tabu queue에 저장된 데이터
Tabu queue에 8이 저장되었다는 것의 의미는 다음의 trial solution 생성 과정에서 어떠한 trial solution이 8이라는 요소를 포함할 경우에 이 trial solution은 tabu를 포함하고 있는 것으로 간주된다는 것이다. Tabu search에서는 tabu queue를 이용하여 현재 feasible solution과 다른 특성을 갖는 solution을 탐색하도록 강제한다.
7) 현재 feasible solution의 cost가 best cost보다 작으면, 현재 feasible solution을 best solution으로 설정
현재 feasible solution [8 1 6 7]의 cost는 36이므로, 이전의 best cost인 131보다 작다. 따라서, best solution은 [8 1 6 7]이 되며, best cost는 36으로 변경된다.
'지능형시스템 > 최적화' 카테고리의 다른 글
| [최적화] 입자 군집 최적화 (Particle Swarm Optimization, PSO)의 개념과 구현 (6) | 2021.07.25 |
|---|---|
| [수리적 최적화] 유전 알고리즘 (Genetic Algorithm)과 전역 최적화 (8) | 2016.09.16 |
| 라그랑주 승수법 (Lagrange Multiplier Method) (9) | 2016.09.01 |
