Tối ưu hóa: chọn phương án tốt nhất

Tối ưu hóa xuất hiện khi ta không chỉ cần một đáp án đúng, mà cần một đáp án tốt nhất có thể theo một tiêu chí nào đó.

Ví dụ gần với sinh viên:

Xếp lịch thi sao cho không có hai môn có nhiều sinh viên học chung bị trùng ca, đồng thời hạn chế một sinh viên phải thi hai ca liên tiếp.
Chọn vị trí đặt quầy tư vấn tuyển sinh trong khuôn viên để sinh viên đi bộ ít nhất.
Chọn tuyến giao đồ ăn quanh ký túc xá sao cho tổng quãng đường ngắn hơn.
Phân bổ thời gian hackathon giữa làm tính năng, kiểm thử và slide thuyết trình để tối đa điểm.

Trong AI, nhiều bài toán có thể nhìn dưới góc độ: có rất nhiều phương án, nhưng không thể hoặc không nên thử hết tất cả.

Ví dụ mở đầu: đặt quầy tư vấn ở đâu?

Giả sử câu lạc bộ muốn đặt một quầy tư vấn trong 1 buổi tuyển thành viên. Sinh viên thường đi qua 4 điểm: cổng trường, thư viện, căn tin và giảng đường A. Mỗi vị trí đặt quầy có tổng khoảng cách ước lượng như sau:

Vị trí đặt quầy	Cổng	Thư viện	Căn tin	Giảng đường A	Tổng khoảng cách
Sân thư viện	120m	20m	180m	100m	420m
Trước căn tin	180m	170m	15m	140m	505m
Sảnh giảng đường A	140m	95m	120m	10m	365m
Cổng phụ	40m	160m	220m	180m	600m

Nếu mục tiêu là giảm tổng khoảng cách, ta chọn sảnh giảng đường A vì $365 < 420 < 505 < 600$ .

Ví dụ này đã có đủ ba thành phần của tối ưu hóa:

Biến quyết định: chọn vị trí đặt quầy.
Hàm mục tiêu: tổng khoảng cách sinh viên phải đi.
Ràng buộc: quầy chỉ được đặt ở các vị trí được nhà trường cho phép.

Ở bài toán thật, số vị trí có thể là hàng trăm, khoảng cách còn phụ thuộc giờ cao điểm, mưa nắng, luồng người đi bộ. Khi đó ta cần thuật toán thay vì tính tay từng dòng.

Tại sao không thể thử hết?

Với bài toán tuyến đường ghé $n$ thành phố (Traveling Salesman Problem), số tuyến có thể là $(n-1)!/2$ :

Số thành phố	Số tuyến có thể	Thử hết mất bao lâu?
5	12	< 1 ms
10	181,440	< 1 giây
15	43,589,145,600	~ 12 giờ nếu thử 1 triệu tuyến/giây
20	6 × 10¹⁶	~ 1,900 năm nếu thử 1 triệu tuyến/giây
50	3 × 10⁶²	không khả thi

Ngay cả với tốc độ rất cao, brute-force nhanh chóng trở nên vô vọng. Đây là lý do ta cần các phương pháp tối ưu thông minh thay vì thử tất cả.

1. Từ bài toán thực tế đến bài toán tối ưu

Một mô hình tối ưu thường có ba thành phần chính:

Biến quyết định: ta được phép thay đổi gì?
Hàm mục tiêu: thế nào là tốt hơn?
Ràng buộc: phương án nào được phép?

Ví dụ, một nhóm sinh viên có 10 giờ để hoàn thiện sản phẩm hackathon:

$x$ : số giờ dành cho tính năng A.
$y$ : số giờ dành cho tính năng B.
Điểm kỳ vọng: $5x + 4y$ .
Tổng thời gian: $x + y \le 10$ .
Có thể còn thêm ràng buộc kiểm thử, nhân lực, thiết bị, v.v.

Ta có thể viết ý tưởng chung là tìm một phương án tốt nhất trong tập phương án hợp lệ:

x^\star = \arg\min_{x \in \mathcal{X}} f(x)

Nếu muốn giá trị lớn nhất, ta cực đại hóa $f(x)$ . Nếu muốn chi phí nhỏ nhất, ta cực tiểu hóa $f(x)$ . Các ràng buộc quyết định phần nào của $\mathcal{X}$ là hợp lệ.

2. Search và Optimization khác nhau ở đâu?

Ở topic Search, ta thường quan tâm đến đường đi từ trạng thái đầu đến trạng thái đích.

Ở Optimization, nhiều lúc ta chỉ quan tâm trạng thái cuối có tốt hay không.

Tiêu chí	Search	Optimization
Quan tâm	Chuỗi bước đi	Phương án cuối cùng
Ví dụ	Tìm đường từ A đến B	Chọn vị trí đặt Wi-Fi tốt nhất
Đánh giá	Đường đi có đến đích không?	Phương án có chi phí thấp không?
Không gian	Thường hữu hướng theo đích	Thường cần duyệt/cải thiện

Ví dụ:

Tìm đường từ ký túc xá đến trường: quan tâm tuyến đường - Search.
Chọn vị trí đặt hai điểm Wi-Fi sao cho tổng khoảng cách đến các phòng nhỏ nhất: quan tâm cấu hình cuối - Optimization.

Trong thực tế, ranh giới không tuyệt đối. Nhiều bài toán có thể được mô hình hóa theo nhiều cách khác nhau.

3. Ba hướng chính trong topic này

3.1. Local Search - cải thiện dần một phương án

Ta giữ một phương án hiện tại, tạo ra các phương án gần nó, sau đó di chuyển sang phương án tốt hơn.

Phù hợp khi:

Không gian phương án rất lớn.
Không cần biết đường đi đã tạo ra lời giải.
Một lời giải gần tối ưu đã có giá trị thực tế.

Thuật toán tiêu biểu:

Hill Climbing.
Random Restart.
Simulated Annealing.

3.2. Linear Programming - tối ưu khi mô hình tuyến tính

Nếu hàm mục tiêu và các ràng buộc đều tuyến tính, ta có thể dùng các bộ giải rất mạnh để tìm nghiệm tối ưu.

Dạng cơ bản:

\min_x \; c^T x

với:

A_{ub}x \le b_{ub}, \qquad A_{eq}x = b_{eq}, \qquad l \le x \le u.

Đây là dạng được các thư viện như scipy.optimize.linprog hỗ trợ trực tiếp.

3.3. Constraint Satisfaction - tìm phép gán thỏa ràng buộc

Ta có:

Một tập biến.
Miền giá trị có thể nhận của từng biến.
Các ràng buộc giữa chúng.

Ví dụ xếp lịch thi:

Biến: môn A, B, C, D.
Miền: Thứ Hai, Thứ Ba, Thứ Tư.
Ràng buộc: hai môn có sinh viên học chung không được thi cùng ngày.

Mục tiêu đầu tiên không nhất thiết là “tốt nhất”, mà là tìm được một phép gán hợp lệ.

4. Nghiệm khả thi và nghiệm tối ưu

Hai khái niệm cần tách rõ:

Nghiệm khả thi: thỏa tất cả ràng buộc bắt buộc.
Nghiệm tối ưu: là nghiệm khả thi có giá trị mục tiêu tốt nhất.

Ví dụ lịch thi:

Một lịch không trùng môn là nghiệm khả thi.
Trong số các lịch hợp lệ, lịch giảm số ca thi liên tiếp cho sinh viên có thể được xem là tốt hơn.

Khi đó bài toán từ CSP thuần túy có thể mở rộng thành constraint optimization.

5. Tối ưu chính xác và tối ưu gần đúng

Không phải bài toán nào cũng nên cố tìm nghiệm tối ưu tuyệt đối.

Tình huống	Cách tiếp cận hợp lý	Ví dụ
Không gian nhỏ, mô hình rõ	Tìm nghiệm tối ưu chính xác	Lịch thi 5 môn
Bài toán tuyến tính	Dùng LP solver	Phân bổ tài nguyên hackathon
Ràng buộc rời rạc phức tạp	CSP / CP solver	Xếp lịch thi toàn trường
Không gian cực lớn	Local search / heuristic	Tuyến giao hàng 1000 điểm
Cần đáp án nhanh	Chấp nhận nghiệm gần tối ưu	Gợi ý real-time

Một thuật toán cho nghiệm tốt trong 1 giây đôi khi hữu ích hơn một thuật toán tìm nghiệm tốt nhất nhưng chạy hàng giờ.

Một solver mạnh cũng không cứu được một mô hình sai: nếu biến, mục tiêu hoặc ràng buộc không phản ánh bài toán thật, nghiệm “tối ưu” vẫn có thể vô dụng.

6. Một chút lịch sử để thấy mạch phát triển

Năm 1947, George Dantzig phát triển phương pháp Simplex cho quy hoạch tuyến tính, gắn tối ưu hóa với các bài toán phân bổ tài nguyên và lập kế hoạch quy mô lớn.
Năm 1977, Alan Mackworth hệ thống hóa node consistency, arc consistency và path consistency cho mạng ràng buộc.
Năm 1983, Kirkpatrick, Gelatt và Vecchi phổ biến Simulated Annealing bằng cách nối bài toán tối ưu tổ hợp với quá trình ủ nhiệt trong vật lý.
Ngày nay, các solver như HiGHS, Gurobi, CPLEX, SCIP và OR-Tools có thể giải nhiều bài toán rất lớn. Tuy nhiên, để dùng solver đúng, ta vẫn phải biết mô hình hóa biến, mục tiêu và ràng buộc.

7. Liên hệ với Machine Learning

Ở các tuần sau, ta sẽ gặp một nghĩa khác của tối ưu: điều chỉnh tham số mô hình để giảm hàm mất mát.

Ví dụ khi huấn luyện mạng nơ-ron:

\min_{\theta} \; \mathcal{L}(\theta)

Trong đó $\theta$ là tham số của mô hình và $\mathcal{L}$ là hàm mất mát.

Gradient Descent cũng là một thuật toán tối ưu, nhưng thuộc nhóm tối ưu liên tục dựa trên gradient — đạo hàm $\nabla \mathcal{L}(\theta)$ cho biết hướng giảm chi phí nhanh nhất. Topic hiện tại tập trung vào local search, linear programming và constraint satisfaction cho không gian rời rạc.

Loại không gian	Phương pháp tiêu biểu
Rời rạc (xếp lịch, routing)	Local Search, CSP, SA
Liên tục, có gradient	Gradient Descent, Adam
Tuyến tính	LP / Simplex
Hỗn hợp nguyên-liên tục	MILP / CP-SAT

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

Một lịch thi không trùng môn nhưng khiến nhiều sinh viên thi ba ca liên tiếp là nghiệm khả thi hay tối ưu?
Vì sao thử toàn bộ các cấu hình thường không thực tế?
Khi nào nên dùng local search thay vì cố tìm nghiệm tối ưu tuyệt đối?
Điểm khác nhau quan trọng nhất giữa LP và CSP là gì?

Tài liệu tham khảo

Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach, 4th ed., Chapters 4 and 6: https://aima.cs.berkeley.edu/
CS50’s Introduction to Artificial Intelligence with Python, Lecture 3 - Optimization: https://cs50.harvard.edu/ai/notes/3/
Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004: https://web.stanford.edu/~boyd/cvxbook/
George B. Dantzig. “Linear Programming.” Operations Research, 50(1), 2002. https://doi.org/10.1287/opre.50.1.42.17798
Alan K. Mackworth. “Consistency in Networks of Relations.” Artificial Intelligence, 8(1), 1977, 99-118. https://doi.org/10.1016/0004-3702(77)90007-8
S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi. “Optimization by Simulated Annealing.” Science, 220(4598), 1983, 671-680. https://doi.org/10.1126/science.220.4598.671

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