Tìm kiếm tabu là gì? Các bài nghiên cứu khoa học liên quan

Định nghĩa và khái quát

Tabu Search (TS) là một phương pháp tối ưu hóa heuristic được thiết kế để giải quyết các bài toán tổ hợp phức tạp, nơi không gian tìm kiếm quá lớn để khám phá bằng thuật toán toàn cục. Ý tưởng chủ đạo của TS là kết hợp cơ chế ghi nhớ các bước di chuyển gần đây – gọi là danh sách cấm (tabu list) – để ngăn thuật toán lặp lại các biến đổi vừa thực hiện và thoát khỏi các cực trị cục bộ.

Bài toán mục tiêu tổng quát của TS có thể được diễn đạt dưới dạng $\min_{x \in S} f(x)$ trong đó $S$ là tập hợp các giải pháp khả dĩ và $f(x)$ là hàm mục tiêu cần tối ưu hóa. TS cho phép tạm thời chấp nhận một lời giải kém hơn để mở rộng khám phá không gian và tránh kẹt cục bộ.

• Cơ chế tabu: ngăn di chuyển ngược về vùng đã thăm gần đây.
• Aspiration criterion: cho phép vượt tabu nếu đạt được cải thiện đáng kể.
• Cho phép khai thác vùng cận kề ưu việt và khám phá vùng mới.

Lịch sử và phát triển

TS do Ralph Glover giới thiệu lần đầu vào năm 1986 nhằm giải bài toán phân phối tuyến đường và lập lịch sản xuất. Bài báo gốc “Future Paths for Integer Programming and Links to Artificial Intelligence” đã đặt nền móng cho việc ứng dụng TS trong nhiều lĩnh vực khác như Traveling Salesman Problem (TSP), Quadratic Assignment Problem (QAP) và Vehicle Routing Problem (VRP).

Qua các thập kỷ 1990 và 2000, TS được phát triển thêm với các khái niệm intensification (tập trung tìm kiếm sâu ở vùng hứa hẹn) và diversification (mở rộng diện tìm kiếm). Các thuật toán lai như Tabu–Genetic hay Reactive Tabu Search đã cho thấy hiệu quả vượt trội nhờ khả năng tự điều chỉnh độ dài danh sách cấm và kết hợp cơ chế di truyền.

• 1986: TS nguyên thủy, tập trung vào integer programming.
• 1993: Khái niệm intensification/diversification và aspiration criterion.
• 1994–2000: Reactive TS tự động điều chỉnh tham số.
• 2000–nay: Hybrid TS với Genetic, Ant Colony, Simulated Annealing.

Nguyên lý thuật toán

Thuật toán Tabu Search bắt đầu với lời giải khởi tạo $x_0$ rồi lặp lại quá trình sinh lời giải kế tiếp bằng cách duyệt qua vùng lân cận $N(x)$. Mỗi bước di chuyển (move) được đánh giá theo hàm mục tiêu, sau đó cập nhật lời giải tốt nhất nếu có cải thiện.

Danh sách cấm lưu trữ các di chuyển hoặc thuộc tính của lời giải vừa được thực hiện, với độ dài cố định hoặc biến thiên theo chiến lược. Một di chuyển nằm trong danh sách cấm sẽ không được chọn trừ khi nó thỏa aspiration criterion – tức là tạo ra lời giải tốt hơn tất cả các lời giải đã biết.

Quá trình kết thúc khi đạt số vòng lặp tối đa, hoặc không còn cải thiện sau một ngưỡng số bước nhất định. Kết quả là lời giải gần tối ưu, thường tốt hơn nhiều so với các thuật toán greedy hoặc hill climbing đơn thuần.

Thiết kế vùng lân cận (neighborhood)

Vùng lân cận $N(x)$ được định nghĩa qua các phép biến đổi cơ bản trên cấu trúc lời giải, ví dụ như:

• Swap: đổi vị trí hai thành phần trong chuỗi.
• Insert: rút một phần tử và chèn vào vị trí khác.
• 2-opt / k-opt: loại bỏ k cạnh và tái nối để sinh chuỗi mới.

Kích thước và thành phần của vùng lân cận ảnh hưởng đến hiệu quả tìm kiếm và thời gian tính toán. Vùng quá lớn dẫn đến chi phí đánh giá cao, trong khi quá nhỏ dễ kẹt cục bộ.

Phép biến đổi	Số lời giải sinh ra	Độ phức tạp
Swap	$\frac{n(n-1)}{2}$	O(n²)
Insert	n(n-1)	O(n²)
2-opt	$\frac{n(n-3)}{2}$	O(n²)

Cân bằng giữa khám phá và khai thác đòi hỏi lựa chọn tập hợp phép biến đổi phù hợp và điều chỉnh danh sách cấm để kiểm soát khả năng quay lại cũng như mức độ đa dạng của lời giải.

Cơ chế intensification và diversification

Intensification là chiến lược tập trung tìm kiếm sâu trong vùng lời giải đã cho thấy tiềm năng cao. Khi thuật toán xác định một vùng cận gần lời giải tốt, nó sẽ tăng cường khai thác tại khu vực này bằng cách giảm độ dài danh sách cấm hoặc ưu tiên các phép di chuyển trỏ về vùng lý tưởng.

Diversification ngược lại mở rộng phạm vi tìm kiếm ra các vùng ít được thăm mới, nhằm tránh kẹt cục bộ lâu dài. Thuật toán có thể gán trọng số cao cho các di chuyển xa lời giải hiện tại, khởi tạo lời giải mới bằng cách pha trộn các thành phần từ nhiều vùng khác nhau hoặc tăng độ dài danh sách cấm.

• Intensification: giảm tabu tenure, tập trung biến đổi gần lời giải tốt nhất.
• Diversification: tăng tabu tenure, thêm ngẫu nhiên vào chọn vùng lân cận.
• Aspiration criteria: cho phép vượt tabu nếu lời giải có giá trị f(x) tốt nhất từ trước đến nay.

Chiến lược	Mục tiêu	Thao tác
Intensification	Khai thác sâu	Giảm tabu tenure, tập trung di chuyển
Diversification	Khám phá rộng	Tăng tabu tenure, di chuyển ngẫu nhiên
Aspiration	Vượt cấm	Cho phép nếu f(x) mới tốt hơn

Ứng dụng thực tiễn

Tabu Search đã chứng tỏ hiệu quả cao trong nhiều bài toán tổ hợp và tối ưu hóa thực tế. Trong Vehicle Routing Problem (VRP), TS giúp tìm lộ trình giao hàng với chi phí vận chuyển tối thiểu, cân bằng tải và thời gian giao nhận (ScienceDirect).

Trong Job Shop Scheduling, TS tối ưu lịch trình máy móc trong dây chuyền sản xuất, giảm tổng thời gian hoàn thành (makespan) và độ trễ đơn hàng. Kết quả thực nghiệm trên các bộ dữ liệu tiêu chuẩn cho thấy TS thường đạt giá trị makespan chỉ cách 1–2% so với nghiệm tối ưu.

Ứng dụng khác bao gồm thiết kế mạng viễn thông (min-cut, max-flow), phân chia tần số trong hệ thống di động, và tối ưu hóa năng lượng trong hệ thống truyền tải điện. Tính linh hoạt của TS cho phép điều chỉnh hàm mục tiêu đa dạng và xử lý ràng buộc phức tạp.

Biến thể và phương pháp lai

Hybrid Tabu–Genetic kết hợp cơ chế ghi nhớ cấm của TS với phép lai và đột biến trong Genetic Algorithm, khai thác lợi thế đa dạng di truyền và khả năng khai thác sâu của TS. Các cha mẹ lai tạo thế hệ con được tối ưu cục bộ bởi TS trước khi ghi vào quần thể.

Reactive Tabu Search tự động điều chỉnh độ dài danh sách cấm (tabu tenure) dựa trên diễn biến hàm mục tiêu và tần suất các lời giải lặp lại. Cơ chế này giúp duy trì cân bằng giữa khám phá và khai thác mà không cần tinh chỉnh thủ công tham số (INFORMS).

• TS–GA: lai ghép lời giải, TS tối ưu cục bộ.
• Reactive TS: tự động điều chỉnh tabu tenure.
• Parallel TS: chạy đồng thời nhiều luồng TS trên không gian khác nhau, chia sẻ thông tin cấm và lời giải tốt nhất.

Tiêu chí đánh giá hiệu năng

Chất lượng lời giải được đo bằng khoảng cách so với nghiệm tối ưu hoặc best-known solution (BKS), thường tính dưới dạng tỷ lệ phần trăm (f(x)–f^*)/f^*

Thời gian chạy và tốc độ hội tụ xác định khả năng áp dụng TS vào các bài toán kích thước lớn. Số vòng lặp đến khi không còn cải thiện (stall iterations) là chỉ số quan trọng cho độ bền thuật toán.

• Gap (%) so với optimum/BKS.
• Thời gian tính toán (CPU time).
• Số vòng lặp đến hội tụ không cải thiện.
• Độ ổn định: độ lệch chuẩn của kết quả qua nhiều lần chạy.

Thách thức và hướng nghiên cứu

Thiết lập tham số TS, đặc biệt độ dài danh sách cấm và kích thước vùng lân cận, đòi hỏi tinh chỉnh thủ công và kinh nghiệm. Nghiên cứu gần đây hướng tới tự động hóa qua machine learning để lựa chọn tham số tối ưu theo đặc điểm bài toán.

Ứng dụng TS trong bài toán đa mục tiêu (multi-objective optimization) và ràng buộc phức tạp vẫn còn nhiều khó khăn do cần cân bằng đồng thời nhiều hàm mục tiêu. Phương pháp phân tán và xử lý song song, cùng hybrid với metaheuristic khác, là xu hướng chính để mở rộng khả năng TS.

1. AI-driven parameter tuning: dùng reinforcement learning lựa chọn tabu tenure.
2. Multi-objective TS: tích hợp Pareto front và archiving.
3. Parallel/distributed TS: tăng tốc và mở rộng quy mô bài toán.

Tài liệu tham khảo

• Glover, F. (1986). “Future Paths for Integer Programming and Links to Artificial Intelligence.” Computers & Operations Research, 13(5), 533–549. doi:10.1016/0305-0548(86)90045-2.
• Glover, F., Taillard, É., & de Mast, A. (1993). “A User’s Guide to Tabu Search.” Annals of Operations Research, 41(1–4), 3–28. doi:10.1007/BF02125419.
• Battiti, R., & Tecchiolli, G. (1994). “The Reactive Tabu Search.” ORSA Journal on Computing, 6(2), 126–140. doi:10.1287/ijoc.6.2.126.
• Hertz, A., & de Werra, D. (1991). “The Tabu Search Metaheuristic: How We Use It.” Annals of Operations Research, 41(1–4), 15–38. doi:10.1007/BF02125420.
• Ribeiro, C. C., Hansen, P., & Mladenović, N. (2010). “A Reactive Tabu Search for the Multidimensional Knapsack Problem.” Computers & Operations Research, 37(5), 904–914. doi:10.1016/j.cor.2009.04.018.