Tìm kiếm cục bộ
Có một lớp bài toán rất rộng mà ta không quan tâm tới đường đi, chỉ quan tâm tới trạng thái cuối cùng tốt tới đâu. Với những bài toán này, ta dùng tìm kiếm cục bộ: bắt đầu từ một lời giải hoàn chỉnh rồi liên tục đi sang lời giải lân cận tốt hơn.
Khi nào chỉ cần lời giải, không cần đường đi
Hãy so hai câu hỏi. "Đi từ Đà Nẵng ra Huế thế nào?" bắt buộc phải trả lời bằng một chuỗi hành động; nói "cuối cùng bạn ở Huế" thì vô dụng, vì cái ta cần chính là lộ trình. Còn "xếp thời khóa biểu cho 40 lớp sao cho không trùng phòng và không trùng giáo viên" thì đáp án là một bảng lịch: không ai quan tâm bạn xếp lớp nào trước, đã đổi chỗ bao nhiêu lần trong lúc nghĩ.
Khác biệt tưởng nhỏ đó đổi hoàn toàn thuật toán nên dùng. Câu hỏi thứ nhất cần BFS, DFS hay A sao: chúng xây một cây tìm kiếm và lời giải là đường từ gốc tới đích, cái giá là bộ nhớ. Với câu hỏi thứ hai, lưu cả cây là lãng phí thuần túy: ta giữ hàng triệu trạng thái trung gian mà rốt cuộc không dùng tới cái nào. Tìm kiếm cục bộ khai thác đúng chỗ lãng phí ấy: nếu chỉ cần trạng thái cuối, hãy luôn giữ trong tay một lời giải hoàn chỉnh (dù ban đầu tệ) rồi cải thiện dần, vứt bỏ toàn bộ lịch sử. Một cách kiểm tra nhanh xem bài toán thuộc loại nào: thử xáo trộn thứ tự các bước dẫn tới lời giải; nếu lời giải vẫn còn nguyên giá trị thì đường đi không quan trọng.
Thử ngay: leo đồi trên bề mặt ba đỉnh
Dạng đơn giản nhất của tìm kiếm cục bộ gọi là leo đồi: từ chỗ đang đứng, luôn bước sang điểm lân cận cao hơn, và dừng khi quanh mình không còn chỗ nào cao hơn nữa. Hãy tự tay chạy thử trên một bề mặt mục tiêu có ba đỉnh: một cực đại toàn cục ở giữa và hai cực đại địa phương hai bên. Bấm Sau để đi từng bước, kéo thanh điểm xuất phát tới bất kỳ vị trí nào để thấy cùng một thuật toán khi thì chạm đỉnh cao nhất, khi thì kẹt ở một cực đại địa phương; rồi bật tôi luyện mô phỏng để xem việc chấp nhận vài bước xuống giúp thoát bẫy ra sao.
Hai tham số còn lại đáng để bạn nghịch, vì chúng chạm vào chính định nghĩa của thuật toán. Bước nhảy quy định lân cận nằm cách bao xa: nhảy rộng thì nhìn được xa hơn nhưng bỏ sót địa hình ở gần, và điểm dừng có khi không phải đỉnh nào cả. Khởi động lại cho thuật toán thêm vài lần leo từ điểm ngẫu nhiên khác rồi giữ kết quả tốt nhất, một cách vá bẫy cực đại địa phương rẻ tiền mà hiệu quả; bấm Gieo lại để đổi hạt giống ngẫu nhiên và bạn sẽ thấy có hạt cứu được, có hạt vẫn kẹt, vì khởi động lại chỉ là xác suất chứ không phải bảo đảm.
Ý tưởng cốt lõi
Trong BFS, DFS hay A*, lời giải là một chuỗi hành động và đường đi cụ thể rất quan trọng. Nhưng với bài toán như xếp 8 quân hậu, tô màu đồ thị, hay lập lịch, ta chỉ cần biết cấu hình cuối có hợp lệ hay không, còn đặt theo thứ tự nào thì không quan trọng.
Tìm kiếm cục bộ đảo ngược tư duy:
- Trạng thái là một lời giải đầy đủ (có thể chưa tốt), ví dụ vị trí của cả 8 quân hậu.
- Lân cận là tập các trạng thái thu được bằng một thay đổi nhỏ, ví dụ dời một quân sang hàng khác.
- Hàm mục tiêu (gọi là value, viết tắt
V) đo độ tốt của một trạng thái, ví dụ số cặp quân tấn công nhau (cần cực tiểu).
Thuật toán đi bộ trên bề mặt giá trị này, mỗi bước nhảy sang một láng giềng, cố leo tới đỉnh cao nhất (cực đại) hoặc tụt tới đáy sâu nhất (cực tiểu).
Hai lợi ích lớn
- Rất tiết kiệm bộ nhớ. Không cần lưu cây tìm kiếm hay biên, chỉ cần giữ trạng thái hiện tại, nên tốn
O(1)bộ nhớ. So với A* tốnO(b^d)thì đây là khác biệt một trời một vực với bài toán lớn. - Dùng được cho không gian liên tục. Khi biến quyết định là số thực (tham số mô hình học máy, tọa độ vật lý), không gian vô hạn và không liệt kê được. Gradient descent chính là tìm kiếm cục bộ cho trường hợp này.
Cái giá phải trả: tìm kiếm cục bộ không đảm bảo tối ưu và đôi khi không tìm ra lời giải dù nó tồn tại. Nó là công cụ xấp xỉ, cho lời giải đủ tốt chứ không nhất thiết tối ưu.
Ba thứ phải định nghĩa trước khi chạy
Mọi thuật toán trong bài đều giả định ta đã trả lời xong ba câu hỏi thiết kế, và chúng quan trọng hơn việc chọn thuật toán nào.
Thứ nhất, không gian trạng thái: một lời giải được mã hóa ra sao? Với 8 quân hậu, một cách gọn là dùng mảng 8 số, phần tử thứ i là hàng của quân hậu ở cột i; cách mã hóa này đã tự loại bỏ mọi cấu hình có hai hậu cùng cột, tức là thu nhỏ không gian ngay từ đầu.
Thứ hai, hàm lân cận: từ một trạng thái đi được sang những trạng thái nào bằng một thay đổi nhỏ? Lân cận quá hẹp thì thuật toán bò chậm và dễ mắc kẹt; lân cận quá rộng thì mỗi bước tốn kém và thuật toán mất tính cục bộ, gần thành tìm kiếm ngẫu nhiên.
Thứ ba, hàm mục tiêu: đo độ tốt bằng gì? Điểm then chốt là hàm mục tiêu phải phân biệt được các trạng thái sai ở mức độ khác nhau. Nếu nó chỉ trả về 0 khi hợp lệ và 1 khi không hợp lệ thì bề mặt phẳng lì gần như khắp nơi và thuật toán không có tín hiệu nào để leo. Hàm mục tiêu tốt là hàm tạo ra một dốc dẫn về phía lời giải.
Ba định nghĩa này gộp lại tạo ra bề mặt mục tiêu: mỗi trạng thái là một điểm, hàm lân cận nói điểm nào kề điểm nào, hàm mục tiêu cho mỗi điểm một độ cao. Phần còn lại của bài chỉ là các cách khác nhau để đi bộ trên bề mặt đó.
Cảnh quan tìm kiếm và các cái bẫy
Hãy hình dung hàm mục tiêu như một bề mặt đồi núi, với độ cao là giá trị V. Trên bề mặt này có năm khái niệm quan trọng:
| Khái niệm | Mô tả | Vì sao nguy hiểm |
|---|---|---|
| Cực trị toàn cục | Điểm có V tốt nhất trên toàn không gian | Đây là lời giải lý tưởng cần đạt |
| Cực trị địa phương | Điểm tốt hơn mọi láng giềng nhưng không tốt nhất toàn cục | Cái bẫy kinh điển của leo đồi |
| Cao nguyên (plateau) | Vùng phẳng nhiều trạng thái cùng V | Leo đồi không biết đi đâu vì láng giềng đều bằng nhau |
| Sườn dốc (shoulder) | Một cao nguyên nghiêng, có đầu cao hơn | Vượt được nếu cho phép đi ngang |
| Ngọn núi (ridge) | Chuỗi cực trị địa phương kề nhau | Có thể mắc kẹt vĩnh viễn |
Cảnh quan thực tế thường có chiều rất cao (hàng triệu chiều khi huấn luyện mạng nơ-ron), có rất nhiều cực trị địa phương, và không tính được trước: ta chỉ biết V của một trạng thái sau khi đánh giá nó.
Leo đồi (hill climbing)
Leo đồi là thuật toán đơn giản nhất: tại mỗi bước, chọn láng giềng tốt nhất; nếu không láng giềng nào tốt hơn trạng thái hiện tại thì dừng.
Có vài biến thể:
- Leo đồi dốc nhất (steepest-ascent): xét tất cả láng giềng rồi chọn cái tốt nhất.
- First-choice: sinh láng giềng ngẫu nhiên từng cái, chọn cái đầu tiên tốt hơn. Hữu ích khi mỗi trạng thái có rất nhiều láng giềng.
- Stochastic: chọn ngẫu nhiên trong các láng giềng tốt hơn, xác suất tỉ lệ với độ tốt.
Bốn vấn đề kinh điển
- Cực trị địa phương: mọi láng giềng đều tệ hơn nên thuật toán dừng, dù tồn tại trạng thái tốt hơn ở xa.
- Cao nguyên: mọi láng giềng cùng
V, thuật toán không biết chọn hướng nào. - Ngọn núi: để sang đỉnh cao hơn phải đi xuống trước, mà leo đồi thuần không cho phép.
- Thiên lệch khởi đầu: kết quả phụ thuộc nặng vào điểm bắt đầu.
Cách cải tiến
- Đi ngang (sideways moves): cho phép chấp nhận láng giềng cùng
Vmột số bước giới hạn, để vượt cao nguyên hay sườn dốc. - Random restart: khi leo đồi dừng, khởi động lại từ điểm ngẫu nhiên mới, lặp
klần, giữ lời giải tốt nhất. Nếu mỗi lần thành công với xác suấtpthì trung bình cần1/plần khởi động. Trên 8-queens, leo đồi thuần chỉ thành công khoảng 14 phần trăm, nhưng kèm random restart thì lên gần 100 phần trăm.
Vì sao khởi động lại ngẫu nhiên hiệu quả tới vậy? Một lần leo đồi thất bại không phải vì thuật toán tồi, mà vì nó xuất phát từ một điểm nằm trong lưu vực hút của một cực trị địa phương; xuất phát ở lưu vực khác thì cùng thuật toán ấy dẫn tới đỉnh khác. Khi kết quả phụ thuộc một phép thử ngẫu nhiên có xác suất thành công p, cách rẻ nhất để nâng xác suất lên gần 1 là thử nhiều lần độc lập: xác suất thất bại cả k lần chỉ còn (1 - p) lũy thừa k. Mẹo này chỉ còn giá trị khi mỗi lần chạy rẻ và p không quá nhỏ; nếu lưu vực của lời giải tốt cực hẹp thì vấn đề nằm ở cấu trúc bề mặt chứ không ở số lần thử, và ta cần một thuật toán biết thoát bẫy từ bên trong.
Gradient descent chính là leo đồi cho không gian liên tục: láng giềng tốt nhất là đi theo hướng đối gradient. Nó cũng kế thừa mọi vấn đề của leo đồi (cực tiểu địa phương, plateau khi gradient gần 0). Các kỹ thuật như momentum, Adam, learning rate schedule đều là bản cải tiến của leo đồi.
Tôi luyện mô phỏng (simulated annealing)
Tôi luyện mô phỏng lấy cảm hứng từ luyện kim: nung kim loại nóng rồi làm nguội từ từ. Ở nhiệt độ cao, nguyên tử di chuyển mạnh và có thể thoát khỏi cấu trúc xấu; khi nguội dần, chúng ổn định ở cấu trúc năng lượng thấp nhất.
Ý tưởng then chốt là cho phép đi bước xấu với xác suất giảm dần theo nhiệt độ, nhờ đó thoát khỏi cực trị địa phương mà leo đồi mắc kẹt:
- Khi bước cải thiện (delta
Vlớn hơn 0), luôn chấp nhận. - Khi bước xấu (delta
Vnhỏ hơn hoặc bằng 0), chấp nhận với xác suấtexp(delta_V / T).
Quy luật của nhiệt độ T:
Tlớn thìexp(delta_V / T)gần 1, gần như luôn chấp nhận bước xấu, thuật toán khám phá rộng.Ttiến về 0 thìexp(delta_V / T)tiến về 0, hầu như không chấp nhận bước xấu, thuật toán khai thác, gần như là leo đồi.
Vì sao chấp nhận bước xấu lại là ý hay
Nghe qua thì việc cố ý làm lời giải tệ đi có vẻ vô lý. Chìa khóa nằm ở chỗ bước xấu là cái giá bắt buộc để rời khỏi một cực trị địa phương: theo đúng định nghĩa, ở đó mọi láng giềng đều tệ hơn, nên nếu ta ra luật "chỉ đi khi tốt lên" thì ta đã tự khóa mình lại vĩnh viễn. Muốn sang một đỉnh cao hơn bên kia thung lũng, không có cách nào khác ngoài đi xuống trước rồi mới leo lên.
Nhưng cũng không thể chấp nhận bừa mọi bước xấu, vì như vậy thuật toán chỉ là bước đi ngẫu nhiên và không bao giờ hội tụ. Tôi luyện mô phỏng chọn lọc theo hai trục. Trục mức độ xấu: xác suất exp(delta_V / T) giảm rất nhanh khi delta_V càng âm, nên một bước xấu nhẹ dễ được chấp nhận còn một bước xấu tệ hại thì gần như bị từ chối; thuật toán sẵn sàng lội qua rãnh nông nhưng không nhảy xuống vực. Trục thời gian, qua nhiệt độ T: giai đoạn đầu T lớn, thuật toán chấp nhận gần như mọi bước và đi lang thang khắp bề mặt để dò xem vùng hứa hẹn nằm đâu; về sau T nhỏ dần, nó ngày càng kén chọn, ở lại vùng đã tìm được và mài giũa tới đỉnh cục bộ của vùng ấy. Nói ngắn gọn: lang thang trước, chốt sau.
Lịch làm nguội
Hàm quyết định nhiệt độ theo bước gọi là lịch nhiệt độ. Phổ biến nhất là lịch mũ T(t) = T0 * beta**t với beta thường trong khoảng 0.95 tới 0.999. Chọn T0 và beta là cả một nghệ thuật: nguội quá nhanh thì giống leo đồi, nguội quá chậm thì chạy lâu vô lý.
Cách chọn thực dụng bám vào hai vai trò trên. Chọn T0 sao cho ở đầu quá trình, tỷ lệ chấp nhận bước xấu cao nhưng không phải một trăm phần trăm, vì nếu chấp nhận tất thì thuật toán đang đi hoàn toàn ngẫu nhiên. Chọn beta sao cho T xuống gần 0 vừa đúng lúc hết ngân sách bước tính: nguội xong quá sớm thì phần thời gian còn lại chỉ để leo đồi, còn chưa kịp nguội thì thuật toán dừng lúc vẫn đang lang thang. Về lý thuyết, làm nguội đủ chậm thì thuật toán hội tụ tới cực trị toàn cục với xác suất tiến về 1, nhưng "đủ chậm" ở đây chậm tới mức không dùng được: đó là lời bảo đảm về nguyên tắc, không phải hướng dẫn cài đặt. Trong thực hành, hãy luôn ghi nhớ riêng trạng thái tốt nhất từng thấy và trả về nó.
Tìm kiếm chùm và thuật toán di truyền
Leo đồi và tôi luyện chỉ giữ một trạng thái. Hai họ sau giữ nhiều trạng thái song song.
Tìm kiếm chùm cục bộ (beam search)
Beam search giữ k trạng thái cùng lúc. Mỗi bước: sinh toàn bộ láng giềng của cả k trạng thái, rồi chọn k trạng thái tốt nhất trong tập gộp đó làm thế hệ tiếp theo.
Điểm khác với chạy k lần leo đồi độc lập: trong beam search các trạng thái chia sẻ tài nguyên. Nếu một nhánh sinh ra nhiều láng giềng tốt, beam có thể dồn hết k chỗ cho nhánh đó. Đây vừa là điểm mạnh vừa là điểm yếu: thiếu đa dạng có thể khiến beam suy biến thành leo đồi. Biến thể stochastic beam search lấy mẫu k láng giềng theo xác suất tỉ lệ với V để giữ đa dạng tốt hơn.
Thuật toán di truyền (genetic algorithm)
Thuật toán di truyền lấy cảm hứng từ chọn lọc tự nhiên. Nó duy trì một quần thể các cá thể (mỗi cá thể mã hóa thành một chuỗi gọi là nhiễm sắc thể). Mỗi thế hệ gồm ba bước:
- Chọn lọc: chọn các cá thể có
Vcao làm cha mẹ, ưu tiên cá thể tốt hơn. - Lai (crossover): cắt và ghép nhiễm sắc thể của hai cha mẹ để tạo con.
- Đột biến (mutation): thay đổi ngẫu nhiên vài gen của con với xác suất nhỏ (thường 1 tới 5 phần trăm).
Thuật toán di truyền mạnh khi mã hóa nhiễm sắc thể tự nhiên cho bài toán (phép lai có ý nghĩa, không chỉ ngẫu nhiên), và cảnh quan có nhiều cực trị địa phương phân tán. Nó kém khi phép lai không có ý nghĩa, hoặc khi cảnh quan có cấu trúc gradient rõ ràng (lúc đó gradient descent tốt hơn), hoặc khi đánh giá V quá đắt.
Điểm đáng suy nghĩ: phép lai mới là thứ phân biệt thuật toán di truyền với việc chạy song song nhiều lần tôi luyện. Lai chỉ có ý nghĩa nếu lời giải phân rã được thành các khối tốt tương đối độc lập, để ghép nửa tốt của cha với nửa tốt của mẹ có cơ hội cho ra con tốt hơn cả hai. Khi bài toán không có cấu trúc khối như vậy, phép lai chỉ là một kiểu đột biến to và hỗn loạn, còn ta thì phải trả thêm cả loạt siêu tham số mà không được lợi gì.
So với tìm kiếm có hệ thống
| Tiêu chí | Tìm kiếm có hệ thống (BFS, A sao) | Tìm kiếm cục bộ |
|---|---|---|
| Lời giải trả về | đường đi từ trạng thái đầu tới đích | một trạng thái hoàn chỉnh |
| Trạng thái trung gian | chưa hoàn chỉnh, là một phần đường đi | luôn là một lời giải đầy đủ |
| Bộ nhớ | lớn, phải giữ biên và cây tìm kiếm | hằng số, chỉ giữ trạng thái hiện tại |
| Bảo đảm tối ưu | có, nếu heuristic hợp lệ | không |
| Không gian liên tục | không dùng được trực tiếp | dùng được |
| Ngắt giữa chừng | không, dừng sớm thì chưa có lời giải | có, luôn sẵn một lời giải để trả về |
Dòng cuối hay bị bỏ qua mà lại rất giá trị trong hệ thống thật. Tìm kiếm cục bộ ngắt lúc nào cũng được: hết thời gian thì lấy trạng thái tốt nhất đang có mà dùng, chất lượng tăng dần theo thời gian ta cho nó chạy. Ngược lại, A sao bị ngắt giữa chừng thì không trả về được gì cả.
Ứng dụng điển hình
Xếp lịch (thời khóa biểu, lịch trực, phân ca). Trạng thái là một bảng phân công đầy đủ; lân cận là đổi chỗ hai phân công; hàm mục tiêu đếm số ràng buộc bị vi phạm, có trọng số theo mức nghiêm trọng (trùng phòng là vi phạm cứng, giáo viên dạy hai ca liền là vi phạm mềm).
N quân hậu và các bài toán ràng buộc. Với N lớn, liệt kê có hệ thống không khả thi, còn tìm kiếm cục bộ với hàm mục tiêu đếm cặp tấn công nhau giải được rất nhanh. Cùng khuôn mẫu ấy áp cho tô màu đồ thị, sudoku, phân bổ tần số cho trạm phát.
Định tuyến và bài toán người bán hàng. Trạng thái là một hành trình đi qua mọi điểm; lân cận kinh điển là đảo ngược một đoạn con của hành trình; hàm mục tiêu là tổng quãng đường. Bài toán thuộc lớp khó, nên trong công nghiệp người ta hầu như luôn dùng heuristic cục bộ để lấy lời giải đủ tốt trong thời gian chấp nhận được.
"Tìm kiếm cục bộ chỉ là cách nói khác của thử ngẫu nhiên." Không. Thử ngẫu nhiên lấy mẫu độc lập và không dùng thông tin gì từ lần trước. Tìm kiếm cục bộ đi theo dốc của hàm mục tiêu; ngẫu nhiên chỉ là gia vị (chọn điểm khởi đầu, chấp nhận bước xấu), không phải cơ chế chính.
"Tôi luyện mô phỏng luôn tốt hơn leo đồi." Không. Nếu bề mặt chỉ có một đỉnh hoặc rất ít cực trị địa phương, leo đồi kèm vài lần khởi động lại vừa đơn giản vừa nhanh hơn, còn tôi luyện chỉ tốn thời gian lang thang vô ích và bắt bạn chỉnh thêm hai siêu tham số.
"Chạy đủ lâu thì chắc chắn ra tối ưu toàn cục." Chỉ đúng trên giấy, với điều kiện làm nguội chậm tới mức không thực hiện được. Hãy coi mọi thuật toán trong bài là công cụ xấp xỉ.
"Trạng thái cuối cùng là kết quả cần trả về." Sai với tôi luyện mô phỏng, vì nó chấp nhận bước xấu nên trạng thái cuối có thể tệ hơn trạng thái tốt nhất từng đi qua.
Mã nguồn Python
# vi du: leo doi (hill climbing) toi uu mot ham so don gian
# muc tieu: tim x lam cuc dai f(x) = -(x - 3)**2 + 10, dinh tai x = 3
import random
def f(x):
return -(x - 3) ** 2 + 10 # parabola up nguoc, dinh o x = 3
def leo_doi(x0, buoc=0.1, so_lan=1000):
x = x0
for _ in range(so_lan):
# hai lang gieng: di trai va di phai mot buoc nho
ung_vien = [x - buoc, x + buoc]
# chon lang gieng tot nhat
tot_nhat = max(ung_vien, key=f)
if f(tot_nhat) <= f(x):
break # khong lang gieng nao tot hon -> cuc tri dia phuong
x = tot_nhat
return x, f(x)
x, gia_tri = leo_doi(x0=random.uniform(-10, 10))
print("x =", round(x, 3), " f(x) =", round(gia_tri, 3))
Khối dưới đây minh họa tôi luyện mô phỏng cho cùng bài toán, nhưng cho phép thỉnh thoảng đi bước xấu để thoát bẫy.
# vi du: simulated annealing toi uu cung ham f(x) = -(x - 3)**2 + 10
import math
import random
def f(x):
return -(x - 3) ** 2 + 10
def toi_luyen(x0, T0=10.0, beta=0.99, so_buoc=2000):
x = x0
T = T0
tot_nhat = x # ghi nho diem tot nhat tung thay
for _ in range(so_buoc):
if T < 1e-8:
break
# sinh mot lang gieng ngau nhien
ke = x + random.uniform(-1, 1)
delta = f(ke) - f(x) # > 0 nghia la cai thien
if delta > 0 or random.random() < math.exp(delta / T):
x = ke # chap nhan buoc tot, hoac buoc xau theo xac suat
if f(x) > f(tot_nhat):
tot_nhat = x
T = T * beta # lich nhiet do mu: nguoi dan
return tot_nhat, f(tot_nhat)
x, gia_tri = toi_luyen(x0=random.uniform(-10, 10))
print("x =", round(x, 3), " f(x) =", round(gia_tri, 3))
Bài tập thực hành
Bài tập 1: nhận diện bài toán phù hợp
Trong các bài toán sau, bài nào nên dùng tìm kiếm cục bộ, bài nào nên dùng tìm kiếm theo đường đi (BFS, A*)? Giải thích: tìm đường ngắn nhất giữa hai thành phố trên bản đồ; xếp 100 quân hậu không tấn công nhau; chọn siêu tham số tốt nhất cho một mô hình học máy.
Gợi ý
Câu hỏi mấu chốt: đường đi có quan trọng không? Tìm đường giữa hai thành phố cần biết chuỗi các bước nên hợp với A*. Xếp 100 quân hậu và chọn siêu tham số chỉ quan tâm trạng thái cuối, không gian rất lớn, nên hợp với tìm kiếm cục bộ.
Bài tập 2: thêm random restart
Hàm leo_doi ở trên dễ mắc kẹt ở cực trị địa phương nếu hàm mục tiêu có nhiều đỉnh. Hãy viết hàm leo_doi_restart(so_lan_restart) chạy leo_doi nhiều lần từ các điểm khởi đầu ngẫu nhiên khác nhau và trả về kết quả tốt nhất.
Gợi ý
Dùng một vòng lặp lặp lại so_lan_restart lần. Mỗi lần gọi leo_doi với x0 = random.uniform(-10, 10), so sánh giá trị trả về với kết quả tốt nhất hiện có và cập nhật nếu tốt hơn. Cuối cùng trả về cặp (x, gia_tri) tốt nhất.
Bài tập 3: ảnh hưởng của lịch nhiệt độ
Trong hàm toi_luyen, hãy thử beta = 0.5 (nguội rất nhanh) và beta = 0.999 (nguội rất chậm), chạy mỗi cấu hình nhiều lần. So sánh chất lượng lời giải và giải thích kết quả theo lý thuyết khám phá và khai thác.
Gợi ý
beta nhỏ làm nhiệt độ tụt nhanh, thuật toán sớm giống leo đồi nên dễ mắc kẹt. beta gần 1 giữ nhiệt độ cao lâu, khám phá rộng hơn và thường tới gần cực trị toàn cục hơn, nhưng tốn nhiều bước hơn.
Tự kiểm tra
Vì sao tôi luyện mô phỏng thoát được cực trị địa phương còn leo đồi thì không?
Leo đồi chỉ bao giờ đi sang láng giềng tốt hơn, nên khi rơi vào cực trị địa phương (mọi láng giềng đều tệ hơn) thì dừng hẳn. Tôi luyện mô phỏng cho phép chấp nhận bước xấu với xác suất exp(delta_V / T), nhờ đó có thể leo xuống rồi tìm đường sang một đỉnh cao hơn. Khi nhiệt độ giảm dần, xác suất đi bước xấu giảm theo nên thuật toán dần ổn định.
Beam search với k trạng thái khác gì chạy k lần leo đồi độc lập?
Trong k lần leo đồi độc lập, mỗi lần chạy riêng và không chia sẻ thông tin. Trong beam search, sau mỗi bước ta gộp toàn bộ láng giềng của cả k trạng thái rồi chọn k cái tốt nhất, nên các nhánh tốt có thể được dồn thêm tài nguyên. Điều này giúp tập trung vào vùng hứa hẹn, nhưng nếu mất đa dạng thì beam có thể suy biến thành leo đồi.
Bạn định nghĩa hàm mục tiêu cho bài N quân hậu là "trả về 1 nếu cấu hình hợp lệ, 0 nếu không". Leo đồi chạy mãi không tiến bộ. Vì sao?
Vì hàm mục tiêu đó tạo ra một bề mặt phẳng gần như khắp nơi: hầu hết cấu hình đều không hợp lệ nên đều có giá trị 0, và mọi láng giềng của trạng thái hiện tại cũng có giá trị 0. Leo đồi không thấy láng giềng nào tốt hơn nên dừng ngay, hoặc lang thang trên một cao nguyên khổng lồ mà không có hướng nào để đi. Thuật toán không hỏng, tín hiệu mới là thứ hỏng.
Cách sửa: dùng hàm mục tiêu có dốc, ví dụ đếm số cặp quân hậu đang tấn công nhau rồi cực tiểu hóa nó. Khi đó cấu hình có 3 cặp xung đột được đánh giá tốt hơn cấu hình có 7 cặp, và thuật toán có hướng để leo. Bài học tổng quát: hàm mục tiêu phải phân biệt được mức độ sai, chứ không chỉ phân biệt đúng với sai.
Câu hỏi tự kiểm
- 1Bộ nhớ điển hình của tìm kiếm cục bộ như leo đồi là bao nhiêu?
- 2Cái bẫy kinh điển khiến leo đồi thuần dừng lại dù chưa đạt lời giải tốt nhất toàn cục là gì?
- 3Vì sao tôi luyện mô phỏng thoát được cực trị địa phương còn leo đồi thì không?
- 4Với bài N quân hậu, nếu định nghĩa hàm mục tiêu là "1 nếu hợp lệ, 0 nếu không", leo đồi chạy mãi không tiến bộ. Vì sao?
Tóm tắt
Tìm kiếm cục bộ bắt đầu từ một quan sát giản dị: có cả một lớp bài toán mà đường đi tới lời giải hoàn toàn vô nghĩa, chỉ lời giải cuối cùng mới đáng giá. Nhận ra điều đó cho phép ta vứt bỏ cây tìm kiếm, chỉ giữ một trạng thái, đổi lấy bộ nhớ hằng số và khả năng chạy trên những không gian lớn tới mức không liệt kê nổi. Cái giá là mọi bảo đảm về tính tối ưu. Trước khi bàn tới thuật toán, ba thiết kế phải xong: mã hóa trạng thái, hàm lân cận, hàm mục tiêu; trong đó hàm mục tiêu quyết định nhiều nhất vì nó tạo ra cái dốc mà thuật toán leo.
Leo đồi ngây thơ ở chỗ chỉ đi khi tốt lên, nên nó chết đứng ở cực trị địa phương, lạc lối trên cao nguyên, mắc kẹt trên sống núi. Hai lối thoát khác nhau về bản chất: khởi động lại ngẫu nhiên không sửa thuật toán mà thử lại nhiều lần từ những lưu vực khác nhau; còn tôi luyện mô phỏng sửa chính quy tắc bằng cách chấp nhận bước xấu có chọn lọc theo mức độ xấu và theo nhiệt độ, nhờ đó tự chuyển dần từ khám phá sang khai thác. Beam search và thuật toán di truyền mở rộng theo hướng giữ nhiều trạng thái cùng lúc, riêng thuật toán di truyền chỉ thật sự có lý khi lời giải phân rã được thành các khối tốt độc lập để phép lai có nghĩa.
Tìm kiếm cục bộ phù hợp khi đường đi không quan trọng, không gian rất lớn và chấp nhận lời giải gần tối ưu, đổi lại chỉ tốn O(1) bộ nhớ. Leo đồi nhanh nhưng dễ mắc kẹt ở cực trị địa phương, cao nguyên và ngọn núi; random restart và đi ngang giúp giảm bớt. Tôi luyện mô phỏng cho phép đi bước xấu theo nhiệt độ để thoát bẫy, giảm dần từ khám phá sang khai thác. Beam search và thuật toán di truyền giữ nhiều trạng thái song song để tăng cơ hội tìm tới cực trị toàn cục. Không có thuật toán cục bộ nào tốt nhất cho mọi bài toán.