현재 해(solution)에서 더 나은 해를 찾기 위해 주변을 탐색하는 방식
- 단순히 가장 좋은 해만 따라가는 '탐욕적(greedy)' 알고리즘의 단점을 보완하기 위해 '금기 목록(tabu list)'이라는 개념을 도입한 것이 특징
⭐ Tabu Search의 특징
✅ 1. 지역 최적해(Local Optimum) 탈출
- Greedy algorithm이 매 순간 가장 좋은 해를 따라가다 보면 더 이상 개선할 수 없는 지역 최적해에 갇히게 됨
✅ 2. 금기 목록(Tabu List) 사용
- 최근에 시도했던 이동이나 방문했던 해를 일정 기간 동안 '금지' 상태로 저장하는 메모리 구조
- 일반적으로 FIFO(선입선출) 구조를 가지며, 매 반복마다 가장 오래된 항목이 삭제되고 새로운 항목이 추가됨
✅ 3. 예외 조건(Aspiration Criteria)
- 타부 리스트에 금지된 이동이라도, 만약 그 이동이 지금까지 찾은 최적해보다 더 좋은 해로 이어진다면 예외적으로 허용
- 이러한 예외 조건을 통해 알고리즘의 유연성을 높여 탐색 효율을 개선
✅ 4. 집중화(Intensification)와 다양화(Diversification)
- 집중화: 현재까지 찾은 좋은 해 주변을 집중적으로 탐색하여 해의 품질을 높임
- 다양화: 탐색이 정체될 때, 아직 탐색하지 않은 새로운 영역을 탐색하여 더 나은 해를 찾을 기회를 만듦
📌 Tabu Search의 단계
✅ 1. 시작점 (Starting Point)
- 알고리즘은 일반적으로 무작위 또는 간단한 휴리스틱 기반윽로 초기 해를 선택하며 시작
✅ 2. 이웃 탐색 (Neighborhood Search)
- 각 단계에서 현재 해의 이웃(neighborhood)을 탐색
- neighborhood: 현재 해에서 작은 변화를 준 해들
✅ 3. 타부 리스트 (Tabu List)
- 리스트에 일시적으로 금지된 이동(move) 또는 해(solution)들이 저장됨
- 최근에 방문한 해를 다시 선택하는 것을 방지하여, 지역 최적해에서 벗어나도록 함
✅ 4. 예외 조건 (Aspiration Criteria)
- 때로는 Tabu list에 포함된 이동이 매우 좋은 해로 이어질 수 있음
--> 이 때 예외적으로 허용됨
✅ 5. 종료 조건 (Stopping Criteria)
- 알고리즘은 다음 조건 중 하나를 만족할 때까지 반복됨
- 정해진 반복 횟수 도달
- 시간 제한 초과
- 더 이상 개선되지 않음
✅ 6. 기억 구조 (Memory Structures)
- 탐색 과정의 정보를 저장하는 메모리 구조를 사용
- 단기 기억(short-term memeory): Tabu list (최근 이동 저장)
- 장기 기억(long-term memory): 과거에 찾은 좋은 해에 대한 정보 저장
✅ 7. 집중화와 다양화 (Intensification & Diversification)
- 좋은 해 주변을 집중적으로 탐색 (Intensification)
- 새로운 영역 탐색 (Diversification)
--> 해의 품질 향상
일반적으로 FIFO (first in first out) 구조로 매 반복마다 갱신됨
❗ Tabu Search의 구현
✅ 1. 단기 기억 (Short-Term Memory)을 이용한 구현
가장 기본적인 구현 방식으로, 금기 목록(Tabu List)이 여기에 해당함
- 목적: 최근해 방문한 해(solution)나 이동(move)을 일시적으로 금지하여 탐색이 같은 경로를 반복하는 순환(cycle) 현상을 막고, 지역 최적해에 갇히는 것을 방지함
- 구현: 일반적으로 큐(Queue) 또는 덱(Deque)과 같은 FIFO(First-In, First-Out) 자료 구조를 사용. 새로운 이동이 발생하면 리스트에 추가하고, 리스트의 크기가 정해진 금기 지속 기간(Tabu Tenure)을 초과하면 가장 오래된 항목을 삭제하는 방식
✅ 2. 장기 기억 (Long-Term Memory)을 이용한 구현
탐색의 효율성을 높이기 위해 더 복잡한 전략을 사용하는 고급 구현 방식
-
목적: 탐색이 너무 한 곳에만 치우치는 것을 방지하고, 새로운 탐색 영역으로 확장하여 전역 최적해를 찾을 가능성을 높임
-
구현
- 빈도 기억(Frequency Memory): 특정 이동이나 해가 너무 자주 선택되었을 경우, 다음에 선택될 가능성을 낮추는 방식으로 탐색의 다양성(Diversification)을 높임
- 집중화(Intensification): 반대로 좋은 해가 발견된 영역 주변을 더 집중적으로 탐색하여 해의 품질을 향상
- 재시작 전략: 탐색이 더 이상 진전되지 않을 때, 이전에 찾았던 좋은 해를 기반으로 다시 탐색을 시작하여 새로운 경로를 모색
⚠️ Tabu Search의 장단점
✅ 장점
- 지역 최적해 탈출: 타부 리스트를 통해 이미 방문했던 경로로 다시 돌아가지 않도록 금지함으로써, 지역 최적해(Local Optimum)에 갇히는 것을 방지하고 더 넓은 탐색 공간을 탐험할 수 있게 함.
- 효율적인 탐색: 그리디 알고리즘의 탐욕적인 접근 방식은 유지하면서도, 금기 목록과 예외 조건 등을 통해 무작위 탐색보다 더 체계적으로 최적해를 찾아감
❌ 단점
-
매개변수 튜닝: 타부 리스트의 크기(Tabu Tenure)와 같은 매개변수를 문제에 맞게 조절해야 함. 이 값이 너무 작으면 지역 최적해에 빠지기 쉽고, 너무 크면 비효율적인 탐색이 될 수 있음.
-
복잡성: 리디 알고리즘에 비해 구현이 복잡하고, 메모리 구조(단기/장기 기억)와 같은 추가적인 개념을 고려해야 함
📝예제
리스트 내 숫자 조합 중 합이 최소가 되는 해를 찾기
import random
from collections import deque
def objective(solution):
# 목적 함수: 합이 작을수록 좋음
return sum(solution)
def generate_neighbors(solution):
# 이웃 해 생성: 랜덤한 위치 2개를 바꾼다
neighbors = []
for _ in range(10):
new_solution = solution.copy()
i, j = random.sample(range(len(solution)), 2)
new_solution[i], new_solution[j] = new_solution[j], new_solution[i]
neighbors.append(new_solution)
return neighbors
def tabu_search(initial_solution, max_iter=100, tabu_size=10):
current_solution = initial_solution
best_solution = current_solution
best_score = objective(best_solution)
tabu_list = deque(maxlen=tabu_size)
for iteration in range(max_iter):
neighbors = generate_neighbors(current_solution)
neighbors = [n for n in neighbors if n not in tabu_list]
if not neighbors:
break
neighbor_scores = [(n, objective(n)) for n in neighbors]
next_solution, next_score = min(neighbor_scores, key=lambda x: x[1])
# Aspiration Criteria: 좋은 해면 Tabu여도 허용
if next_score < best_score:
best_solution = next_solution
best_score = next_score
tabu_list.append(next_solution)
current_solution = next_solution
print(f"Iter {iteration+1}: best_score = {best_score}")
return best_solution, best_score
# 초기 해: 1~10의 무작위 순열
initial = random.sample(range(1, 11), 10)
best_solution, best_score = tabu_search(initial, max_iter=50, tabu_size=5)
print("\nBest solution:", best_solution)
print("Best score:", best_score)
🔎 Tabu Search의 주요 활용 예시
✅ 1. 외판원 문제 (Traveling Salesman Problem, TSP)
여러 도시를 한 번씩 방문하고 시작점으로 돌아오는 가장 짧은 경로를 찾는 문제로, 이는 전형적인 NP-하드 문제로, 모든 경우의 수를 확인하기 어려움
-
동작 방식
- 현재 경로에서 두 도시의 순서를 바꾸는 것을 '이동'으로 간주.
- 과거에 시도했던 비효율적인 이동들을 금지 목록 (Tabu list)에 넣어 반복을 피하고, 더 넓은 탐색 공간을 효율적으로 탐색하여 최단 경로를 찾음.
-
ex) 100개의 도시를 방문하는 최단 경로를 찾을 때, 모든 경로를 계산하는 대신 Tabu Search를 사용하면 현실적인 시간 안에 좋은 근사 해 얻을 수 있음.
✅ 2. 스케줄링 문제
작업 할당, 생산 계획, 항공기 이착륙 시간 배정 등 복잡한 제약 조건이 있는 스케줄링에서 최적의 해를 찾는 문제
-
동작 방식
- Tabu Search는 현재 스케줄에서 작업을 재배치하는 것을 '이동'으로 봄
- 이미 시도했던 비효율적인 재배치들을 금지하여 더 나은 스케줄을 탐색
-
ex) 공장에서 여러 기계에 작업을 할당하여 전체 생산 시간을 최소화하는 문제를 해결할 때, 타부 서치를 사용해 최적의 작업 순서를 찾음
✅ 3. 네트워크 설계
통신망에서 가장 효율적인 연결망을 구축하거나, 물류 네트워크에서 운송 비용을 최소화하는 경로를 설계하는 문제
- 동작 방식
- 네트워크 구성 요소를 변경하는 것을 '이동'으로 간주하여 최적의 네트워크 구조를 찾음
- ex) 물류 회사가 배송 지점 간의 최단 경로를 찾거나, 통신 회사가 기지국을 설치할 최적의 위치를 결정할 때 사용할 수 있음
✅ 4. 포트폴리오 최적화
주어진 자산들로 수익은 최대화하면서 위험은 최소화하는 투자 포트폴리오를 구성하는 문제
- 동작 방식
- 포트폴리오의 자산 구성을 변경하는 것을 '이동'으로 보고, 과거의 비효율적인 자산 조합을 금지하여 더 나은 포트폴리오를 찾음
- ex) 주식, 채권, 부동산 등 다양한 자산에 투자할 때, 타부 서치를 이용해 투자 비율을 조정함으로써 기대 수익률을 높이고 위험을 관리하는 최적의 포트폴리오를 찾을 수 있음
📑 용어 설명
Tabu list
- 최근 수행한 이동들을 기록하는 단기 기억 장치
- Closed list, 이전에 방문한 해를 다시 탐색하지 않도록 함
Tabu Tenure (Tabu 지속 기간)
- 한 번 Tabu 리스트에 들어간 이동이 금지되는 횟수
- 이 기간이 지나기 전에는 같은 이동을 다시 시도할 수 없음
Frequency Memory (빈도 기억 장치)
- 너무 자주 선택되었지만 해결책에 도움이 되지 않은 이동은 다음에 선택될 가능성을 낮춤
- 탐색 다양성을 높이기 위한 전략
코딩 공부