Local Search và Hill Climbing

Hãy tưởng tượng bạn đang đi bộ trong sương mù dày đặc trên một ngọn núi. Mục tiêu là tìm điểm thấp nhất — nhưng bạn chỉ nhìn thấy một vài bước xung quanh. Chiến lược đơn giản nhất: luôn bước về phía thấp hơn.

Đây chính xác là ý tưởng của local search: không cần nhìn toàn bộ bản đồ, chỉ cần liên tục cải thiện phương án hiện tại dựa trên những lựa chọn gần kề.

Phương pháp này không hoàn hảo — bạn có thể kẹt ở một thung lũng nhỏ trong khi thung lũng sâu hơn nằm ở phía bên kia ngọn đồi. Nhưng nó hoạt động được và thường rất nhanh, đặc biệt khi không gian tìm kiếm quá lớn để duyệt hết.

Ví dụ gần hơn: một nhóm sinh viên muốn chọn thứ tự ghé 6 địa điểm quanh trường để giao áo câu lạc bộ. Mỗi trạng thái là một thứ tự đi, chi phí là tổng quãng đường. Nếu đổi chỗ hai điểm giao gần nhau làm tuyến ngắn hơn, ta nhận tuyến mới. Nếu đổi kiểu nào cũng dài hơn, Hill Climbing dừng — dù có thể một chuỗi đổi chỗ khác sẽ dẫn đến tuyến tốt hơn.

1. Biểu diễn bài toán

Ta cần xác định bốn thứ:

Trạng thái: một phương án hoàn chỉnh ở thời điểm hiện tại.
Láng giềng: các phương án có thể tạo ra bằng một thay đổi nhỏ từ trạng thái hiện tại.
Hàm mục tiêu: điểm số cần tăng (maximize).
Hàm chi phí: chi phí cần giảm (minimize).

Ví dụ đặt Wi-Fi: trường muốn đặt hai điểm phát Wi-Fi để giảm tổng khoảng cách đến sinh viên.

Trạng thái: vị trí của hai bộ phát (ví dụ: phòng 101 và phòng 203).
Láng giềng: di chuyển một bộ phát sang ô bên cạnh.
Chi phí: tổng khoảng cách từ mỗi phòng học đến bộ phát gần nhất.

\text{cost}(s) = \sum_{i=1}^{n} d(\text{room}_i, \text{nearest AP in } s)

Ta muốn tìm trạng thái $s$ có chi phí càng nhỏ càng tốt.

Trực quan: chọn láng giềng nào?

Từ trạng thái hiện tại (chi phí 27), giả sử có sáu láng giềng có thể đến. Local search sẽ chọn láng giềng có chi phí thấp nhất:

Thuật toán chọn N1 (chi phí 23) — thấp nhất trong số các láng giềng và thấp hơn trạng thái hiện tại.

2. Hill Climbing

Hill Climbing là biến thể local search đơn giản nhất: luôn chuyển sang láng giềng tốt hơn, dừng khi không còn láng giềng nào tốt hơn.

current = trạng thái ban đầu

lặp mãi:
    neighbors = tất cả láng giềng của current
    best_neighbor = láng giềng có chi phí thấp nhất

    nếu cost(best_neighbor) >= cost(current):
        return current  # đã kẹt, dừng

    current = best_neighbor

Theo dõi từng bước

Giả sử Hill Climbing khởi đầu từ chi phí 40. Biểu đồ dưới cho thấy chi phí qua 10 bước đầu:

Bước 0–4: chi phí giảm nhanh từ 40 xuống 18.
Bước 4–9: chi phí đứng nguyên tại 18 — thuật toán đã dừng từ bước 4 vì không còn láng giềng nào có chi phí thấp hơn.

Phần “phẳng” ở cuối biểu đồ không phải thuật toán đang tiếp tục chạy — đó là chi phí giữ nguyên sau khi đã dừng. Hill Climbing đã tìm được một local minimum tại bước 4.

Lưu ý quan trọng: Chi phí 18 là local minimum — tốt hơn mọi trạng thái kề nó — nhưng không chắc là global minimum của toàn bộ không gian.

3. Local optimum và global optimum

Đây là nhược điểm cốt lõi của Hill Climbing.

Local optimum: tốt hơn mọi láng giềng trực tiếp — nhưng có thể tồn tại vùng tốt hơn xa hơn.
Global optimum: tốt nhất trong toàn bộ không gian nghiệm.

Cảnh quan chi phí thực tế

Hình dưới minh hoạ 24 trạng thái với nhiều “thung lũng”. Mỗi trạng thái có thể hiểu là một cấu hình đặt Wi-Fi hoặc một tuyến giao hàng khác nhau; các trạng thái cạnh nhau là các phương án có thể chuyển đổi bằng một thay đổi nhỏ.

S5★ (chi phí 18): local minimum — thấp hơn S4(24) và S6(22), nhưng không phải thấp nhất.
S11★ (chi phí 16) và S16★ (chi phí 14): cũng là local minima, tốt hơn S5 nhưng vẫn chưa phải tốt nhất.
S23◆ (chi phí 9): global minimum — thấp nhất trong toàn bộ không gian.

Hill Climbing từ S1: đi S1(42) → S2(35) → S3(29) → S4(24) → S5(18), dừng ở local minimum.
Hill Climbing từ S8: đi S8(31) → S9(26) → S10(20) → S11(16), dừng ở local minimum khác.
Hill Climbing từ S20: đi S20(24) → S21(18) → S22(12) → S23(9), tìm được global minimum.

Điểm xuất phát quyết định kết quả — đây là lý do local search không đảm bảo tìm được nghiệm tốt nhất.

4. Ba tình huống dễ mắc kẹt

4.1. Local minimum

Mọi láng giềng đều tệ hơn → thuật toán dừng dù chưa tối ưu. Đây là trường hợp S5 trong ví dụ trên.

4.2. Plateau — vùng bằng phẳng

Nhiều láng giềng có cùng chi phí → thuật toán không biết hướng nào thực sự tốt hơn.

Từ S3 đến S8 có cùng chi phí 20. Nếu Hill Climbing đến S3, nó không thể quyết định nên đi tiếp về đâu. Một số biến thể cho phép di chuyển ngang trên plateau (chấp nhận bước ngang), nhưng cần giới hạn số bước ngang để tránh vòng lặp vô tận.

4.3. Ridge — sườn núi hẹp

Để đến vùng tốt hơn, đôi khi phải đi qua một chuỗi bước không cải thiện ngay. Hill Climbing cơ bản không làm điều này — nó từ chối mọi bước không tốt hơn tức thì.

Ví dụ: trong bài toán xếp lịch, hoán đổi hai môn học có thể tạm làm xung đột nhiều hơn, nhưng tạo điều kiện cho một loạt thay đổi tiếp theo giải quyết toàn bộ.

5. Các biến thể và chiến lược

Steepest-ascent (tham lam nhất)

Đánh giá tất cả láng giềng và chọn cái tốt nhất. Chất lượng mỗi bước cao hơn nhưng tốn chi phí đánh giá nếu có nhiều láng giềng.

First-choice (chọn đầu tiên)

Duyệt ngẫu nhiên qua các láng giềng, chọn ngay láng giềng đầu tiên tốt hơn trạng thái hiện tại. Phù hợp khi không gian láng giềng rất lớn — không cần đánh giá tất cả.

Stochastic Hill Climbing

Chọn ngẫu nhiên trong các láng giềng tốt hơn (thay vì luôn chọn tốt nhất). Hai lần chạy từ cùng điểm có thể dẫn đến kết quả khác nhau, giúp khám phá đa dạng hơn.

Random Restart — khởi đầu lại nhiều lần

Chạy Hill Climbing nhiều lần từ các điểm xuất phát ngẫu nhiên khác nhau, lấy nghiệm tốt nhất trong số tất cả.

Biểu đồ này phản ánh đúng bản chất của bài toán có nhiều thung lũng: có lần kẹt ở 18, 16 hoặc 14; có lần đi được tới 12; và có lần tìm được global minimum 9. Chạy 10 lần, Run 2, 5, 9 tìm được global minimum. Chọn nghiệm tốt nhất trong 10 lần → xác suất tìm được nghiệm tốt cao hơn nhiều so với một lần chạy duy nhất.

Local Beam Search

Giữ $k$ trạng thái tốt nhất song song thay vì chỉ một. Ở mỗi bước, sinh tất cả láng giềng của $k$ trạng thái, giữ lại $k$ cái tốt nhất. Giống như chạy $k$ lần Hill Climbing nhưng các “luồng” có thể chia sẻ thông tin — nếu một luồng tìm được vùng tốt, các trạng thái từ đó sẽ được ưu tiên.

6. Cài đặt đơn giản với Python

Dưới đây là Hill Climbing cơ bản cho bài toán tối thiểu hóa:

import random

def hill_climbing(initial_state, get_neighbors, cost_fn, max_steps=10_000):
    """
    Hill Climbing đơn giản: luôn chuyển sang láng giềng tốt hơn.
    
    Args:
        initial_state: trạng thái ban đầu
        get_neighbors: hàm trả về danh sách láng giềng của một trạng thái
        cost_fn: hàm tính chi phí (muốn minimize)
    """
    current = initial_state
    current_cost = cost_fn(current)

    for step in range(max_steps):
        neighbors = get_neighbors(current)
        if not neighbors:
            break

        # Steepest-ascent: chọn láng giềng tốt nhất
        best_neighbor = min(neighbors, key=cost_fn)
        best_cost = cost_fn(best_neighbor)

        if best_cost >= current_cost:
            # Không còn cải thiện được — local minimum
            break

        current = best_neighbor
        current_cost = best_cost

    return current, current_cost


def random_restart(get_initial, get_neighbors, cost_fn, n_restarts=20):
    """Chạy Hill Climbing nhiều lần, lấy kết quả tốt nhất."""
    best_state, best_cost = None, float('inf')

    for _ in range(n_restarts):
        state, cost = hill_climbing(
            get_initial(), get_neighbors, cost_fn
        )
        if cost < best_cost:
            best_state, best_cost = state, cost

    return best_state, best_cost

Phần quan trọng nhất cần tự viết là get_neighbors và cost_fn — đây là nơi hiểu biết về bài toán đi vào thuật toán.

7. Neighborhood quan trọng không kém thuật toán

Local search tốt hay xấu phụ thuộc mạnh vào cách định nghĩa “láng giềng”.

Ví dụ với bài toán tuyến đường (20 địa điểm cần ghé):

Kiểu neighborhood	Mô tả	Kích thước	Nhận xét
Swap	Đổi chỗ hai địa điểm	$O(n^2)$	Đơn giản, hiệu quả
2-opt	Đảo ngược một đoạn	$O(n^2)$	Chuẩn cho TSP
Or-opt	Dời một cụm 1–3 điểm	$O(n^2)$	Mạnh hơn 2-opt
3-opt	Tái cấu trúc 3 cung	$O(n^3)$	Tốt hơn, tốn hơn

Nếu neighborhood quá nhỏ: mỗi bước rẻ nhưng dễ kẹt, vì không có đường “tắt” ra khỏi local optimum.
Nếu neighborhood quá lớn: nhiều cơ hội hơn nhưng tốn thời gian đánh giá mỗi bước.

Thiết kế neighborhood là một phần của mô hình hóa bài toán, không phải chi tiết kỹ thuật phụ.

8. Khi nào Local Search phù hợp?

Đặc điểm bài toán	Phù hợp?	Ví dụ
Không gian quá lớn để duyệt hết	✅	TSP với 50 thành phố
Chỉ cần nghiệm cuối, không cần đường đi	✅	Xếp lịch, placement
Có thể tính chi phí nhanh	✅	Cost thay đổi nhỏ khi swap
Cần bảo đảm tìm global optimum	❌	Dùng LP hoặc exact solver
Không gian nhỏ, liệt kê được	❌	Dùng brute-force hoặc CSP

Ứng dụng thực tế:

Lập lịch: xếp ca làm việc, lịch thi, lịch bay.
Định tuyến: tuyến giao hàng, mạng viễn thông.
Thiết kế bố trí: đặt máy trong nhà máy, đặt phần tử trên mạch in.
Tối ưu siêu tham số: tìm learning rate, batch size trong Machine Learning.

9. Liên hệ với các phương pháp khác

Gradient Descent là “phiên bản liên tục” của Hill Climbing. Thay vì nhìn các láng giềng rời rạc, Gradient Descent tính đạo hàm $\nabla f(\theta)$ để biết hướng giảm nhanh nhất rồi bước một lượng nhỏ:

\theta_{t+1} = \theta_t - \alpha \nabla f(\theta_t)

Cả hai đều có chung nhược điểm: có thể kẹt tại local minimum. Đó là lý do huấn luyện neural network thường dùng stochastic gradient descent, momentum và learning rate scheduling — các kỹ thuật có linh hồn giống Random Restart và Simulated Annealing.

Simulated Annealing (bài tiếp theo) giải quyết đúng điểm yếu của Hill Climbing: đôi khi chấp nhận một bước xấu hơn để thoát khỏi local optimum.

10. Local Search không đảm bảo điều gì?

Hill Climbing cơ bản không đảm bảo:

Tìm được global optimum.
Hai lần chạy cho cùng kết quả.
Nghiệm tìm được gần tối ưu đến mức nào.

Do đó khi báo cáo kết quả, không nên chỉ chạy một lần rồi kết luận thuật toán “tốt”. Nên chạy nhiều lần và báo cáo:

Best cost: giá trị tốt nhất tìm được.
Mean cost: trung bình qua các lần chạy.
Std dev: mức độ ổn định.
Time: thời gian chạy.

11. Câu hỏi tự kiểm tra

Với bài toán xếp lịch, một “láng giềng” có thể được định nghĩa như thế nào?
Tại sao Random Restart có thể tốt hơn một lần Hill Climbing dài?
Trong biểu đồ 24 trạng thái, vì sao bắt đầu từ S20 tìm được global minimum còn bắt đầu từ S1 thì không?
Gradient Descent và Steepest-ascent Hill Climbing có điểm gì chung và khác nhau?
Nếu một bài toán chỉ có một local minimum và đó cũng là global minimum (hàm unimodal), Hill Climbing có đảm bảo tìm được nghiệm tối ưu không?

Tài liệu tham khảo

Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach, 4th ed., Chapter 4: https://aima.cs.berkeley.edu/
CS50 AI, Lecture 3 - Optimization: https://cs50.harvard.edu/ai/notes/3/
Google OR-Tools User’s Manual, Local Search and Job-Shop Problem: https://acrogenesis.com/or-tools/documentation/user_manual/manual/LS.html
David S. Johnson, Lyle A. McGeoch. “The Traveling Salesman Problem: A Case Study in Local Optimization.” Local Search in Combinatorial Optimization, 1997.

Bản tiếng Anh đang soạn.