Siêu heuristic (Metaheuristics)

1. Tổng quan

A. Định nghĩa

Siêu heuristic (Metaheuristics) là chiến lược tìm kiếm kinh nghiệm (heuristic) ở cấp cao hơn (meta) nhằm tìm ra lời giải tốt gần với lời giải tối ưu trong thời gian thực tế đối với các bài toán tối ưu phức tạp, là một khung tối ưu hóa tổng quát (problem-independent) tìm kiếm thông minh trong không gian lời giải mà không bị ràng buộc vào cấu trúc của một bài toán cụ thể.

Lý do căn bản cần đến siêu heuristic là "các bài toán tối ưu trong thực tế lớn đến mức không thể tìm kiếm vét cạn (exhaustive search)". Ví dụ tiêu biểu là bài toán người bán hàng (TSP, Traveling Salesman Problem). Với n thành phố, số lộ trình có thể là (n−1)!/2, và chỉ cần 30 thành phố thì số lộ trình đã lên tới khoảng 4.4×10³¹. Ngay cả máy tính kiểm tra 1 tỷ lộ trình mỗi giây cũng cần thời gian dài hơn tuổi của vũ trụ để xét hết. Với các bài toán NP-hard có số trường hợp bùng nổ tổ hợp như vậy, chưa biết thuật toán nào bảo đảm tìm được lời giải tối ưu toàn cục (global optimum) trong thời gian đa thức. Tuy vậy, không thể từ bỏ tối ưu hóa, nên cần một cách tiếp cận thực dụng tìm "lời giải đủ tốt (good-enough solution) đủ nhanh dù không hoàn hảo". Siêu heuristic chính là câu trả lời đó.

Ý tưởng của siêu heuristic xuất phát từ việc mô phỏng các hiện tượng tự nhiên và vật lý. Nó chuyển thành thủ tục tính toán "cách tự nhiên đã tìm ra lời giải tốt qua thời gian dài" như tiến hóa sinh học, tôi luyện kim loại, đàn kiến tìm thức ăn, đàn chim di chuyển theo bầy. Khác với các quy tắc tham lam (greedy) đơn giản, chúng đôi khi chấp nhận theo xác suất cả những lời giải trước mắt trông có vẻ tệ hơn để quan sát vùng rộng, và khai thác tập trung quanh các lời giải tốt. Chúng được gọi là "siêu" heuristic vì logic điều khiển ở cấp meta (cấp cao hơn) này chỉ huy các heuristic riêng của từng bài toán.

Nguyên lý cốt lõi là cân bằng giữa khám phá (Exploration) và khai thác (Exploitation). Khám phá là hoạt động tìm kiếm rộng các vùng mới chưa đi qua để bảo đảm tính đa dạng, còn khai thác là hoạt động cải thiện tập trung quanh các lời giải tốt đã tìm được để hướng tới hội tụ. Khám phá quá mức thì gần như tìm kiếm ngẫu nhiên và hội tụ chậm, còn khai thác quá mức thì sớm bị mắc kẹt ở tối ưu cục bộ (local optimum) và bỏ lỡ tối ưu toàn cục. Một siêu heuristic tốt điều phối tinh tế sự căng thẳng giữa hai lực này thông qua lịch trình thích nghi: ban đầu thiên về khám phá để quét rộng không gian lời giải, càng về sau càng thiên về khai thác để thu hẹp.

B. Bối cảnh ra đời và sự cần thiết

Tối ưu hóa truyền thống chủ yếu là các phương pháp tìm lời giải chính xác (exact solution) dựa trên tiền đề cấu trúc toán học của bài toán (tính khả vi, tính lồi v.v.) như quy hoạch tuyến tính (LP), quy hoạch nguyên (IP). Tuy nhiên, nhiều bài toán thực tế như lộ trình logistics, lịch sản xuất, thiết kế cấu trúc mạng nơ-ron có hàm mục tiêu không liên tục · phi tuyến hoặc không khả vi, ràng buộc phức tạp, và không gian tìm kiếm khổng lồ. Với các bài toán như vậy, khó áp dụng nguyên vẹn các phương pháp giải chính xác. Siêu heuristic vẫn hoạt động ngay cả khi chỉ đánh giá hàm mục tiêu như một "hộp đen" (đưa lời giải vào thì nhận ra điểm số), nên hầu như không cần giả định nào về cấu trúc bài toán. Chính tính tổng quát và linh hoạt này là bối cảnh khiến luyện kim mô phỏng, thuật toán di truyền, tìm kiếm tabu v.v. được phổ biến rộng rãi từ những năm 1980~1990.

2. Phân loại tổng thể và cấu trúc

Siêu heuristic được chia thành hai dòng chính theo tiêu chí số lời giải được duy trì trong quá trình tìm kiếm. Một là dựa trên lời giải đơn (trajectory-based) cải thiện dần một lời giải, hai là dựa trên quần thể (population-based) đồng thời tiến hóa một tập nhiều lời giải. Dòng thứ nhất vẽ ra quỹ đạo của một điểm di chuyển trong không gian lời giải nên mạnh về tinh chỉnh tìm kiếm cục bộ (local search), còn dòng thứ hai có nhiều lời giải quét không gian song song và trao đổi thông tin với nhau nên có lợi cho tìm kiếm toàn cục và bảo đảm tính đa dạng.

flowchart TB
  M["Siêu heuristic (Metaheuristics)"] --> S["Dựa trên lời giải đơn (Trajectory-based)"]
  M --> P["Dựa trên quần thể (Population-based)"]
  S --> SA["Luyện kim mô phỏng (SA)"]
  S --> TS["Tìm kiếm tabu (Tabu Search)"]
  S --> ILS["Tìm kiếm cục bộ lặp (ILS)"]
  P --> GA["Thuật toán di truyền (GA)"]
  P --> ACO["Đàn kiến (ACO)"]
  P --> PSO["Bầy đàn hạt (PSO)"]
  style M fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style S fill:#fef7e8,stroke:#e0a42f,stroke-width:1px
  style P fill:#eafaf0,stroke:#2fae66,stroke-width:1px

Dòng dựa trên lời giải đơn hiện thực đơn giản và ít tốn bộ nhớ, nhưng vì phụ thuộc vào một quỹ đạo nên phải bổ sung năng lực khám phá bằng cơ chế riêng (chấp nhận theo xác suất trong luyện kim, danh sách cấm trong tabu) thì mới thoát khỏi tối ưu cục bộ. Dòng dựa trên quần thể có nhiều ứng viên tìm kiếm đồng thời các vùng khác nhau và lan truyền thông tin của lời giải tốt trong tập thể nên khám phá rộng một cách tự nhiên, nhưng phải đánh giá hàm mục tiêu cho từng lời giải nên chi phí đánh giá lớn và gánh nặng tinh chỉnh tham số (kích thước quần thể, tỷ lệ lai ghép v.v.) cũng lớn. Trong thực tế, người ta xem xét tính chất bài toán và chi phí đánh giá hàm mục tiêu để chọn một trong hai hoặc kết hợp chúng.

3. Chi tiết các kỹ thuật chính

A. Thuật toán di truyền (GA, Genetic Algorithm)

Thuật toán di truyền mô phỏng tiến hóa sinh học. Mỗi lời giải được mã hóa thành một nhiễm sắc thể (chromosome), đặt một quần thể gồm nhiều lời giải, rồi chọn lọc (selection) các cá thể có độ thích nghi (fitness) cao để tạo thế hệ tiếp theo bằng lai ghép (crossover) trộn gen của hai cha mẹ và đột biến (mutation) thay đổi ngẫu nhiên một số gen. Qua nhiều thế hệ, các lời giải có độ thích nghi cao tồn tại và chất lượng của toàn bộ quần thể được cải thiện dần.

Ở đây, lai ghép chủ yếu đóng vai trò khai thác, còn đột biến đóng vai trò khám phá. Nếu tỷ lệ đột biến quá thấp, quần thể hội tụ sớm (premature convergence) về một điểm và mắc kẹt ở tối ưu cục bộ; nếu quá cao thì trở thành tìm kiếm ngẫu nhiên và không hội tụ. Do đó, tỷ lệ đột biến thường bắt đầu bằng giá trị nhỏ khoảng 0.1~1% rồi điều chỉnh theo tình huống. GA có thể mã hóa lời giải một cách tự do nên được dùng đặc biệt rộng rãi cho tối ưu tổ hợp (lịch trình · bố trí · lộ trình).

flowchart LR
  A["Tạo quần thể ban đầu"] --> B["Đánh giá độ thích nghi (Fitness)"]
  B --> C{"Điều kiện dừng?"}
  C -->|"Không"| D["Chọn lọc (Selection)"]
  D --> E["Lai ghép (Crossover)"]
  E --> F["Đột biến (Mutation)"]
  F --> B
  C -->|"Có"| G["Trả về lời giải tốt nhất"]
  style A fill:#e8f0fe,stroke:#2f6fed,stroke-width:1px
  style G fill:#eafaf0,stroke:#2fae66,stroke-width:1px

Ví dụ ứng dụng thực tế, trong thiết kế ăng-ten vệ tinh, NASA đã dùng thuật toán di truyền để tìm ra ăng-ten hiệu năng cao có hình dạng bất đối xứng mà con người khó nghĩ ra bằng trực giác. Như vậy, với các bài toán có không gian thiết kế rộng và trực giác không phát huy tác dụng, GA thể hiện thế mạnh phát hiện những lời giải mà nhà thiết kế con người chưa nhìn thấy.

B. Luyện kim mô phỏng (SA, Simulated Annealing)

Luyện kim mô phỏng lấy tên từ quá trình vật lý làm nguội từ từ kim loại ở nhiệt độ cao để ổn định cấu trúc tinh thể. Khi di chuyển từ lời giải hiện tại sang lời giải lân cận, lời giải tốt hơn luôn được chấp nhận, và lời giải tệ hơn cũng được chấp nhận theo xác suất. Xác suất chấp nhận này càng lớn khi nhiệt độ (T) càng cao và mức độ xấu đi càng nhỏ (dựa trên phân phối Boltzmann), và khi lặp lại thì hạ dần nhiệt độ (cooling schedule) để ngày càng ít chấp nhận lời giải tệ.

Cơ chế "thỉnh thoảng chấp nhận cả lời giải tệ" này là cốt lõi của luyện kim mô phỏng. Ở nhiệt độ cao giai đoạn đầu, thuật toán vượt qua các thung lũng tối ưu cục bộ để khám phá rộng, còn ở nhiệt độ thấp giai đoạn sau thì tập trung khai thác vùng tốt và hội tụ. Nếu hạ nhiệt độ quá nhanh thì khám phá không đủ và mắc kẹt ở tối ưu cục bộ, còn hạ quá chậm thì hội tụ chậm và tính toán kéo dài. Đó là lý do lịch làm nguội (nhiệt độ ban đầu · tỷ lệ giảm) quyết định hiệu năng. Tối ưu hóa bố trí · đi dây bán dẫn VLSI là ví dụ thành công kinh điển của luyện kim mô phỏng. Mã giả dưới đây tóm tắt luồng chấp nhận theo xác suất và làm nguội này.

T ← T_ban_đầu          # bắt đầu ở nhiệt độ cao
s ← tạo lời giải ban đầu
lặp:
    s' ← tạo lời giải lân cận của s
    Δ ← cost(s') - cost(s)
    if Δ < 0:          # lời giải tốt hơn thì luôn chấp nhận
        s ← s'
    else if rand() < exp(-Δ / T):   # lời giải tệ cũng chấp nhận theo xác suất
        s ← s'
    T ← T × α          # làm nguội (0<α<1), nhiệt độ giảm dần
until điều kiện dừng (T đủ thấp)
return s

C. Đàn kiến (ACO) · bầy đàn hạt (PSO) · tìm kiếm tabu (Tabu Search)

Tối ưu hóa đàn kiến (ACO) mô phỏng trí tuệ bầy đàn: khi kiến mang thức ăn, chúng để lại pheromone trên đường đi, và đường càng ngắn thì pheromone tích tụ càng nhanh để thu hút các con kiến khác. Pheromone do nhiều con kiến (lời giải) để lại tích lũy trên các lộ trình tốt, và tập thể dần dần hội tụ về lời giải tốt. Phù hợp với các bài toán lộ trình · định tuyến mạng.

Tối ưu hóa bầy đàn hạt (PSO) mô phỏng chuyển động theo bầy của đàn chim · đàn cá. Mỗi hạt (lời giải) cập nhật vận tốc và di chuyển bằng cách tham khảo đồng thời vị trí tốt nhất mà chính nó tìm được (pbest) và vị trí tốt nhất của cả bầy (gbest). Trong tối ưu không gian liên tục, nó được dùng rộng rãi vì hiện thực đơn giản và hội tụ nhanh. Tìm kiếm tabu đưa các lời giải vừa ghé thăm gần đây vào danh sách cấm (tabu list) để ngăn ghé lại, qua đó ngăn vòng lặp quẩn quanh một chỗ và buộc thoát khỏi tối ưu cục bộ. Như vậy, mỗi kỹ thuật trả lời cùng một câu hỏi "thoát khỏi tối ưu cục bộ như thế nào" bằng những cơ chế khác nhau.

4. So sánh và tiêu chí lựa chọn

Việc chọn kỹ thuật không nên dựa vào "thuật toán nào tuyệt đối vượt trội" mà phải dựa vào cách tìm kiếm của kỹ thuật nào phù hợp với cấu trúc bài toán. Đây cũng là hàm ý thực tiễn của định lý không có bữa trưa miễn phí (No Free Lunch Theorem): "không có thuật toán đơn lẻ nào tối ưu cho mọi bài toán". Với tối ưu biến liên tục (tối thiểu hóa hàm · tinh chỉnh tham số) thì PSO · luyện kim mô phỏng có xu hướng có lợi, còn với tối ưu tổ hợp coi trọng thứ tự · bố trí (TSP · lập lịch) thì GA · ACO · tabu có xu hướng có lợi.

Điều quan trọng khi so sánh là "vì sao có sự khác biệt". Ví dụ, PSO mạnh trong không gian liên tục vì vị trí · vận tốc của hạt được biểu diễn bằng vector số thực nên có thể di chuyển mượt mà mà không cần gradient, còn ACO mạnh trong bài toán lộ trình vì thông tin tích lũy là pheromone ghi nhớ · tái sử dụng một cách tự nhiên "các đoạn lộ trình tốt". Trong thực tế, thay vì phụ thuộc vào một kỹ thuật duy nhất, người ta kết hợp thế mạnh của từng kỹ thuật theo kiểu lai (hybrid), chẳng hạn dùng GA để khám phá rộng rồi dùng luyện kim mô phỏng · tabu để tinh chỉnh cục bộ.

5. Chuyên sâu — Xu hướng mới nhất và áp dụng thực tiễn

Ngày nay, siêu heuristic đã trở lại như thành phần cốt lõi của pipeline AI/ML. Tiêu biểu là tối ưu hóa siêu tham số (HPO) và tìm kiếm kiến trúc mạng nơ-ron (NAS, Neural Architecture Search). Các siêu tham số như tốc độ học, số tầng, kích thước batch, hay bản thân kiến trúc mạng nơ-ron tạo thành không gian tìm kiếm rời rạc · hỗn hợp không khả vi, nên các siêu heuristic như thuật toán tiến hóa · PSO trở thành công cụ tự nhiên. AmoebaNet của Google v.v. được biết đến là ví dụ dùng tìm kiếm dựa trên tiến hóa để tìm ra cấu trúc sánh ngang hoặc vượt các mô hình do con người thiết kế.

Ngoài ra, thuật toán lai · Memetic và tối ưu đa mục tiêu (Multi-objective) là các hướng nghiên cứu chủ đạo. Thuật toán Memetic kết hợp tìm kiếm toàn cục dựa trên quần thể (GA) với tìm kiếm cục bộ (luyện kim mô phỏng v.v.) để nâng chất lượng hội tụ, và các thuật toán tiến hóa đa mục tiêu như NSGA-II xem xét đồng thời nhiều mục tiêu mâu thuẫn như chi phí · hiệu năng · điện năng để đưa ra tập lời giải tối ưu Pareto (Pareto front). Trong thực tế, các kỹ thuật này được áp dụng cho các bài toán có ràng buộc phức tạp và nhiều mục tiêu như bài toán định tuyến xe (VRP) của doanh nghiệp logistics, lịch sản xuất trong công đoạn bán dẫn, thiết kế mạng viễn thông, tối ưu danh mục đầu tư tài chính. Tuy nhiên, siêu heuristic chỉ cung cấp lời giải gần đúng, nên ở những lĩnh vực mà việc bảo đảm chất lượng lời giải là quan trọng, nên kiểm chứng song song với phương pháp giải chính xác (quy hoạch toán học) hoặc kỹ thuật ràng buộc cận.

6. Những điểm cần cân nhắc và hàm ý (dưới góc nhìn Kỹ sư chuyên nghiệp)

1. Chọn kỹ thuật · tham số dựa trên đặc tính bài toán: Như định lý No Free Lunch đã nói, không có kỹ thuật vạn năng. Phải phân tích trước tính liên tục hay rời rạc, cấu trúc ràng buộc, chi phí đánh giá hàm mục tiêu (mỗi lần đánh giá có cần mô phỏng không v.v.), rồi chọn · tinh chỉnh kỹ thuật và tham số (kích thước quần thể · nhiệt độ · tỷ lệ đột biến) thì mới đạt hiệu năng. Cân nhắc đồng thời các kỹ thuật tự điều chỉnh tham số (self-adaptive).
2. Điều khiển thích nghi cân bằng khám phá-khai thác: Lịch trình động chuyển từ khám phá ở giai đoạn đầu sang khai thác ở giai đoạn sau quyết định thành bại. Chiến lược giám sát dấu hiệu hội tụ sớm (premature convergence) (đa dạng giảm đột ngột) để tăng tỷ lệ đột biến hoặc khởi động lại (restart) là hiệu quả.
3. Đánh đổi giữa chi phí đánh giá và tài nguyên tính toán: Dòng dựa trên quần thể phải đánh giá hàm mục tiêu cho từng lời giải, có thể tăng tốc bằng song song hóa (đánh giá đồng thời nhiều lời giải) nhưng tốn tài nguyên. Với các bài toán có chi phí đánh giá lớn, áp dụng chiến lược xấp xỉ hàm mục tiêu bằng mô hình thay thế (surrogate model) để giảm số lần đánh giá.
4. Bảo đảm chất lượng lời giải gần đúng và dùng song song phương pháp giải chính xác: Siêu heuristic không bảo đảm lời giải tối ưu, nên trong các quyết định liên quan đến an toàn · tài chính, cần kiểm chứng chéo bằng tính cận dưới/cận trên (bound) hoặc quy hoạch toán học để bảo đảm khoảng tin cậy của lời giải.
5. Triển vọng ứng dụng liên kết trong thời đại AI: Sự kết hợp giữa siêu heuristic và học máy như HPO · NAS · tìm kiếm chính sách học tăng cường đang mở rộng, và ngược lại, sự hội tụ học-tối ưu (learn-to-optimize) dùng mô hình đã học làm bộ đánh giá thay thế đang nổi lên như một xu hướng mới.

Tài liệu tham khảo

• Wikipedia, "Metaheuristic" — https://en.wikipedia.org/wiki/Metaheuristic
• Wikipedia, "No free lunch theorem" — https://en.wikipedia.org/wiki/No_free_lunch_theorem
• Wikipedia, "Neural architecture search" — https://en.wikipedia.org/wiki/Neural_architecture_search

Tóm tắt một câu: Siêu heuristic là chiến lược tìm kiếm tổng quát giúp tìm lời giải gần đúng tốt trong thời gian thực tế cho các bài toán tối ưu NP-hard quy mô lớn không thể tìm kiếm vét cạn, mô phỏng hiện tượng tự nhiên · vật lý để thoát khỏi tối ưu cục bộ bằng cân bằng giữa khám phá và khai thác, và ngày nay đang trở lại như công cụ cốt lõi của pipeline AI như HPO · NAS.