Triển khai thuật toán leo đồi (Hill Climbing) cho AI bằng Python

Thuật toán leo đồi là một trong những thuật toán tối ưu hóa sớm nhất và đơn giản nhất trong trí tuệ nhân tạo và khoa học máy tính. Nó thuộc nhóm thuật toán tìm kiếm cục bộ (local search), vốn tìm lời giải bằng cách cải thiện dần từng bước nhỏ.

Tên của thuật toán xuất phát từ một phép so sánh trực quan: hãy tưởng tượng một người leo núi bị bịt mắt cố gắng lên đỉnh đồi. Vì không nhìn thấy toàn bộ địa hình, họ chỉ có thể cảm nhận mặt đất ngay xung quanh. Ở mỗi bước, họ đi theo hướng nào dốc lên. Điều này phản chiếu cách thuật toán hoạt động — nó đánh giá các lời giải lân cận và lặp lại việc tiến tới lời giải tốt hơn, nhằm tìm lời giải tối ưu (đỉnh đồi).

Trong bài viết này, chúng ta sẽ tìm hiểu sâu về thuật toán leo đồi, các biến thể của nó, và cách bạn có thể triển khai bằng Python. Nếu bạn mới bắt đầu với AI, hãy xem lộ trình kỹ năng AI Fundamentals để nắm các kiến thức căn bản. 

Thuật toán leo đồi trong AI là gì?

Leo đồi là một cách đơn giản để máy tính giải quyết vấn đề bằng cách tìm lời giải tốt nhất có thể, giống như người leo núi cố gắng lên đỉnh. Trong trí tuệ nhân tạo (AI), chúng ta thường cần tìm lời giải tốt nhất giữa nhiều lựa chọn khả dĩ. Điều này được gọi là tối ưu hóa.

Hãy nghĩ đến trò chơi “nóng và lạnh”. Trong trò này, bạn chỉ có thể kiểm tra xem mình đang “ấm dần” (tốt hơn) hay “lạnh đi” (tệ hơn) khi di chuyển. Leo đồi hoạt động tương tự — nó xem xét các lời giải lân cận và tiến tới những lời giải tốt hơn.

Cách hoạt động theo các bước đơn giản:

1. Bắt đầu với một lời giải bất kỳ
2. Quan sát các lời giải lân cận
3. Nếu có lời giải lân cận tốt hơn, chuyển sang lời giải đó
4. Lặp lại bước 2–3 cho đến khi không thể tìm được lời giải tốt hơn

Ví dụ, nếu bạn muốn dạy robot đi bộ, Leo Đồi có thể:

• Bắt đầu với các chuyển động chân ngẫu nhiên
• Thử các chuyển động hơi khác đi
• Giữ lại những chuyển động giúp robot đi tốt hơn
• Lặp lại cho đến khi tìm được kiểu đi tối ưu

Dù leo đồi không phải lúc nào cũng là phương pháp tiên tiến nhất trong AI, nó là viên gạch nền tảng giúp ta hiểu cách máy tính tự giải quyết vấn đề, tương tự như thuật toán minimax.

Các loại thuật toán leo đồi

Có ba loại chính của thuật toán leo đồi, mỗi loại có cách tìm kiếm lời giải tốt nhất khác nhau:

1. Leo đồi đơn giản (Simple hill climbing)

Leo đồi đơn giản giống như chọn bước đi tốt đầu tiên mà bạn tìm thấy. Ở phiên bản này:

• Thuật toán xem xét từng lời giải lân cận lần lượt
• Ngay khi tìm thấy lời giải tốt hơn, nó chuyển sang ngay
• Không kiểm tra những lựa chọn khác
• Cách này nhanh nhưng có thể bỏ lỡ lời giải tốt hơn ở xa hơn một chút

2. Leo đồi dốc nhất (Steepest-ascent hill climbing)

Phiên bản này kỹ lưỡng hơn leo đồi đơn giản:

• Xem TẤT CẢ các lời giải lân cận trước khi quyết định di chuyển
• Chọn lựa chọn tốt nhất từ tất cả phương án tìm thấy
• Mất nhiều thời gian hơn nhưng thường tìm được lời giải tốt hơn
• Giống như cẩn thận kiểm tra mọi lối đi trước khi bước tiếp

3. Leo đồi ngẫu nhiên (Stochastic hill climbing)

Loại này thêm yếu tố ngẫu nhiên để việc tìm kiếm linh hoạt hơn:

• Thay vì luôn chọn lời giải tốt nhất, nó chọn ngẫu nhiên trong số các lựa chọn tốt
• Lời giải tốt có xác suất được chọn cao hơn
• Tính ngẫu nhiên giúp tránh bị kẹt ở những điểm xấu
• Đôi khi như thử rẽ sang lối khác để xem dẫn tới đâu

Mỗi loại có điểm mạnh riêng và phù hợp với các vấn đề khác nhau. Leo đồi đơn giản nhanh nhưng cơ bản, leo đồi dốc nhất kỹ lưỡng nhưng chậm hơn, còn leo đồi ngẫu nhiên thêm chút ngẫu nhiên hữu ích để tránh mắc kẹt.

Cách thuật toán leo đồi hoạt động

Thuật toán leo đồi hoạt động bằng cách cải thiện nhỏ từng bước cho đến khi tìm được lời giải tốt nhất có thể. Hãy tách nhỏ thành các phần chính.

1. Bắt đầu

Mọi thuật toán leo đồi đều cần một điểm khởi đầu. Hãy nghĩ như chọn vị trí xuất phát khi leo núi. Bạn có thể bắt đầu ngẫu nhiên, hoặc dùng hiểu biết về vấn đề để chọn một điểm khởi đầu tốt. 

Điểm bắt đầu rất quan trọng — chọn tốt, bạn có thể tìm ra lời giải tối ưu nhanh. Chọn tệ, bạn có thể mắc kẹt ở một gò nhỏ thay vì đỉnh núi.

Ví dụ, trong huấn luyện mạng nơ-ron, điểm bắt đầu là chọn trọng số khởi tạo cho các kết nối giữa nơ-ron. Bạn có thể khởi tạo ngẫu nhiên, như bắt đầu leo ở vị trí ngẫu nhiên trên núi. Hoặc dùng các kỹ thuật như khởi tạo Xavier để chọn trọng số thông minh dựa trên cấu trúc mạng. 

Khởi tạo tốt giúp mạng học nhanh hơn và tìm lời giải tốt hơn, còn khởi tạo kém có thể khiến mạng mắc kẹt với độ chính xác thấp không cải thiện được.

2. Xem xét các lời giải lân cận

Khi bắt đầu tìm kiếm, thuật toán đánh giá các lời giải hàng xóm tương tự với vị trí hiện tại. Hãy coi như khám phá khu vực xung quanh bằng những bước nhỏ. Ví dụ, nếu bạn đang tối ưu một tuyến giao hàng giữa các thành phố, và tuyến hiện tại là [A -> B -> C -> D], thuật toán sẽ xem các tuyến tương tự như [A -> B -> D -> C] hoặc [A -> C -> B -> D] để xem có giảm tổng quãng đường hay không. Mỗi thay đổi nhỏ với tuyến đường đại diện cho một lời giải “hàng xóm” có thể tốt hơn lời giải hiện tại.

Để so sánh, thuật toán dựa vào cái gọi là hàm mục tiêu — một công thức toán học gán điểm cho mỗi lời giải khả dĩ.

Hàm này như chiếc la bàn, giúp thuật toán biết hướng nào “lên dốc” tới lời giải tốt hơn và hướng nào “xuống dốc” tới lời giải tệ hơn. Với tuyến giao hàng, hàm mục tiêu sẽ tính tổng quãng đường di chuyển — tổng quãng đường ngắn hơn nghĩa là lời giải tốt hơn. 

Vậy nếu tuyến X dài 100 dặm và tuyến Z dài 90 dặm, tuyến Z sẽ có điểm (thấp) tốt hơn. Thuật toán khi đó biết cần di chuyển theo hướng các lời giải tương tự tuyến Z. Hàm mục tiêu về bản chất biến bài toán tối ưu hóa tuyến đường phức tạp thành một con số đơn giản có thể so sánh và được cực tiểu hóa.

3. Chọn bước tiếp theo

Sau khi xem các lời giải lân cận, thuật toán cần quyết định bước đi tiếp theo. Nó so sánh điểm của các lời giải lân cận với lời giải hiện tại. Nếu tìm được lời giải tốt hơn, nó chuyển sang đó. Các phiên bản khác nhau của leo đồi đưa ra lựa chọn theo cách khác nhau:

• Phiên bản đơn giản chọn lời giải tốt hơn đầu tiên tìm được
• Phiên bản cẩn trọng kiểm tra tất cả lời giải lân cận trước khi chọn cái tốt nhất
• Phiên bản ngẫu nhiên đôi khi chọn lời giải không hẳn là tốt nhất, giúp tránh mắc kẹt

4. Biết khi nào dừng

Thuật toán cần biết khi nào dừng tìm kiếm lời giải tốt hơn. Thông thường, nó dừng khi một trong các điều sau xảy ra:

1. Không thể tìm được lời giải lân cận nào tốt hơn
2. Đã chạy quá lâu
3. Đã tìm được một lời giải đủ tốt

Khi hoạt động, thuật toán thường theo một nhịp điệu: ban đầu tìm lời giải tốt hơn nhanh, như bước dài trên dốc đứng. Sau đó chậm dần khi gần đỉnh, cải thiện nhỏ dần cho đến khi dừng. 

Đôi khi đường đi trơn tru, nhưng đôi lúc lại gập ghềnh với nhiều lên xuống.

Ưu điểm và hạn chế của leo đồi trong AI

Hãy xem điều gì khiến leo đồi hữu ích và những vấn đề bạn có thể gặp khi dùng nó.

Ưu điểm

Leo đồi là một trong các thuật toán tối ưu hóa dễ hiểu và dễ lập trình nhất. Nó như tuân theo một quy tắc cơ bản: “Nếu cái gì tốt hơn, hãy đi tới đó.” Điều này khiến nó là điểm khởi đầu tuyệt vời cho nhiều vấn đề.

Khi vấn đề đơn giản, leo đồi có thể tìm lời giải tốt nhanh chóng. Nó không lãng phí thời gian khám phá mọi khả năng — chỉ đơn giản là đi theo hướng đi lên.

Thuật toán không cần nhiều bộ nhớ hay sức mạnh tính toán. Nó chỉ cần nhớ vị trí hiện tại và xem các lời giải lân cận, nên phù hợp với nhiều vấn đề thực tế.

Hạn chế

Tất nhiên, như mọi phương pháp, có một số mặt hạn chế: 

1. Mắc kẹt ở các gò nhỏ

Vấn đề lớn nhất của leo đồi là có thể mắc kẹt ở “cực đại cục bộ” — giống như các gò nhỏ khi gần đó thực ra có núi cao. Khi đạt đỉnh của gò nhỏ, nó dừng vì xung quanh đều thấp hơn, dù có thể còn lời giải tốt hơn ở nơi khác.

2. Bề mặt phẳng

Đôi khi thuật toán ở trên vùng phẳng (gọi là bình nguyên), nơi mọi lời giải lân cận đều tương đương. Hãy tưởng tượng tìm điểm cao nhất khi đi trên sân bóng phẳng — rất khó biết hướng nào để đi!

3. Bài toán sống lưng núi (ridge)

Hãy nghĩ tới việc đi dọc theo sống núi hẹp. Thuật toán có thể mất thời gian zigzag qua lại thay vì tiến lên đỉnh. Điều này xảy ra vì mỗi bước ngang trông cũng “tốt” như đi tiếp đúng hướng.

4. Điểm khởi đầu rất quan trọng

Điểm xuất phát có thể tạo khác biệt lớn cho hiệu quả của thuật toán. Như khi leo núi — khởi hành sai chỗ, bạn có thể chẳng bao giờ tìm được đỉnh cao nhất.

Những hạn chế này không có nghĩa leo đồi là lựa chọn tệ — chỉ là chúng ta cần cẩn thận về thời điểm và cách sử dụng. Đôi khi có thể kết hợp với kỹ thuật khác để vượt qua, như sẽ bàn ở phần tiếp theo.

Chiến lược vượt qua hạn chế

Khi dùng leo đồi, ta có thể áp dụng một số chiến lược khéo léo để giải quyết các vấn đề đã nêu. Hãy khám phá hai cách tiếp cận chính giúp leo đồi hiệu quả hơn.

Leo đồi khởi động lại ngẫu nhiên (Random-restart)

Một trong những cách tốt nhất để tránh mắc kẹt ở gò nhỏ là thử leo từ nhiều điểm bắt đầu khác nhau. Cách tiếp cận này gọi là leo đồi khởi động lại ngẫu nhiên, và hoạt động đúng như tên gọi — nếu bị kẹt, hãy bắt đầu lại ở nơi khác.

Hãy nghĩ tới việc tìm ngọn núi cao nhất trong một dãy núi đầy sương mù. Nếu bạn leo ngọn đầu tiên gặp và lên tới đỉnh, có thể bạn bỏ lỡ ngọn cao hơn nhiều ngay gần đó. Nhưng nếu có thể “dịch chuyển” tới nhiều vị trí rồi leo lại, bạn sẽ có cơ hội cao hơn để cuối cùng tìm ra đỉnh cao nhất.

Cách hoạt động: Đầu tiên, chạy thuật toán leo đồi bình thường cho đến khi bị kẹt. Thay vì dừng lại, lưu lời giải tốt nhất đã tìm, rồi bắt đầu lại ở một điểm ngẫu nhiên mới. Lặp lại nhiều lần, và cuối cùng chọn lời giải tốt nhất trong tất cả các lần thử.

Ưu điểm của khởi động lại ngẫu nhiên là đơn giản mà hiệu quả. Mỗi lần khởi động cho bạn cơ hội mới để tìm đỉnh cao nhất. Dù tốn thời gian hơn leo đồi thường, khả năng tìm được lời giải tốt nhất cao hơn nhiều.

Tôi luyện mô phỏng (Simulated annealing)

Dù không hẳn là leo đồi, tôi luyện mô phỏng là một biến thể thông minh giúp giải quyết nhiều vấn đề của leo đồi. Nó lấy cảm hứng từ cách kim loại nguội và cứng lại trong luyện kim. Khi nguội từ từ, các nguyên tử tìm được vị trí tốt hơn, khiến kim loại bền hơn.

Ở cách này, thuật toán đôi khi chấp nhận lời giải tệ hơn một cách chủ đích, đặc biệt lúc đầu. Theo thời gian, nó trở nên kén chọn hơn với các lời giải. Giống như một quả bóng nảy trên bề mặt gồ ghề — lúc đầu có đủ năng lượng để bật qua các gò, nhưng khi mất dần năng lượng, nó dần ổn định ở vị trí tốt.

Cách hoạt động: Ban đầu, thuật toán có thể chấp nhận một lời giải tệ hơn hiện tại với xác suất tương đối cao. Xác suất này phụ thuộc vào hai yếu tố: mức độ tệ hơn và thời gian thuật toán đã chạy. Theo thời gian, xác suất chấp nhận lời giải tệ hơn giảm xuống, và cuối cùng hành xử giống leo đồi thường.

Sức mạnh của tôi luyện mô phỏng là có thể thoát khỏi các gò nhỏ và vùng phẳng, nhất là giai đoạn đầu tìm kiếm. Bằng cách đôi khi chấp nhận lời giải tệ hơn, nó có thể:

• Thoát khỏi cực đại cục bộ (gò nhỏ)
• Vượt qua bình nguyên (vùng phẳng)
• Đi qua sống núi (đỉnh hẹp)
• Khám phá nhiều vùng của không gian lời giải

Ví dụ, bạn muốn sắp xếp nội thất để tối đa hóa không gian. Di chuyển một chiếc ghế có thể tạm thời làm phòng chật hơn, nhưng sau đó cho phép bạn đặt các món khác vào vị trí tốt hơn nhiều. Tôi luyện mô phỏng sẵn sàng thử các bố trí tạm tệ hơn, đặc biệt lúc đầu, để tìm bố trí tổng thể tối ưu.

Những chiến lược này cho thấy đôi khi cách tốt nhất để giải quyết vấn đề không phải lúc nào cũng là bước đi hiển nhiên. Bằng việc thêm yếu tố ngẫu nhiên và “hỗn loạn có kiểm soát”, ta thường có thể tìm lời giải tốt hơn so với con đường thẳng băng.

Triển khai thuật toán leo đồi đơn giản bằng Python

Giờ khi đã hiểu cách cải thiện leo đồi bằng các chiến lược như khởi động lại ngẫu nhiên và tôi luyện mô phỏng, hãy áp dụng vào một bài toán tài chính thực tế: tối ưu hóa danh mục.

Tối ưu danh mục giúp nhà đầu tư quyết định phân bổ tiền vào các khoản đầu tư khác nhau. Khi xây dựng danh mục, họ muốn lợi nhuận cao nhất có thể trong khi rủi ro thấp. Tìm sự cân bằng này rất khó — như tìm công thức hoàn hảo với nhiều nguyên liệu.

Năm 1952, nhà kinh tế Harry Markowitz đưa ra cách thông minh để giải bài toán này. Ông chỉ ra rằng nhà đầu tư có thể giảm rủi ro bằng cách pha trộn các khoản đầu tư không cùng biến động. Điều này gọi là đa dạng hóa — giống như không bỏ tất cả trứng vào một giỏ.

Khi xây dựng danh mục, ta cần xác định ba điều chính:

• Lợi nhuận kỳ vọng (Expected Return)
• Mức độ rủi ro của danh mục (Portfolio Risk)
• Liệu lợi nhuận tiềm năng có xứng đáng với rủi ro (Risk-Adjusted Return)

Leo đồi phù hợp với bài toán này vì các thay đổi nhỏ trong cách phân bổ vốn thường dẫn tới thay đổi nhỏ trong hiệu quả danh mục. Hãy hình dung một ngọn đồi trơn tru nơi mỗi điểm là một cách đầu tư khác nhau. Điểm càng cao thể hiện lựa chọn đầu tư tốt hơn.

Để tìm danh mục tốt bằng Leo Đồi, chúng ta sẽ:

1. Bắt đầu với một phối hợp đầu tư ngẫu nhiên
2. Thử các phối hợp hơi khác để xem có tốt hơn không
3. Tiếp tục cải thiện nhỏ dần cho đến khi không tìm được phương án tốt hơn
4. Dùng phối hợp tốt nhất đã tìm thấy

Bằng cách này, leo đồi có thể giúp nhà đầu tư tìm các danh mục tốt hơn trong hàng triệu khả năng. Nó như một trợ lý thông minh có thể nhanh chóng thử nhiều cách phối hợp đầu tư để tìm ra phương án cân bằng tốt giữa rủi ro và lợi nhuận.

Trước hết, hãy định nghĩa hàm mục tiêu của chúng ta, thước đo hiệu quả danh mục cân bằng giữa lợi nhuận kỳ vọng và rủi ro. Hàm nhận danh sách trọng số danh mục làm đầu vào và trả về một điểm số, điểm càng cao nghĩa là danh mục càng tốt.

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # Expected annual returns for assets (example values)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, etc.

   # Risk (volatility) for each asset
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, etc.

   # Validate input length matches expected returns/volatilities
   if len(state) != len(expected_returns):
       return float("-inf")  # Return worst possible score for invalid states

   # Calculate expected portfolio return
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # Calculate portfolio risk (simplified, not using covariance matrix)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # Penalize if weights don't sum to 1 (invalid portfolio)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # Penalize negative weights (no short selling)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # Combine return and risk with risk aversion factor of 2
   # Higher score is better: maximize return, minimize risk and penalties
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return scoreĐược hỗ trợ bởi

Hàm objective_function ở trên giúp chúng ta đánh giá mức độ tốt của một danh mục đầu tư. Cách hoạt động như sau:

Đầu tiên, hàm nhận một danh sách số biểu thị tỷ lệ phần trăm tiền muốn đầu tư vào các tài sản khác nhau (như cổ phiếu hoặc trái phiếu). Ví dụ, nếu có năm tài sản, ta có thể đầu tư 20% vào mỗi tài sản.

Hàm sử dụng hai thông tin quan trọng:

1. Lợi nhuận kỳ vọng: Chúng ta kỳ vọng kiếm được bao nhiêu từ mỗi tài sản (như 8% hay 12% mỗi năm)
2. Độ biến động: Mức rủi ro của mỗi tài sản — số càng cao nghĩa là giá trị tài sản biến động khó lường hơn (như crypto)

Sau đó hàm sẽ:

• Tính tổng lợi nhuận kỳ vọng của danh mục bằng cách nhân lợi nhuận kỳ vọng của từng tài sản với tỷ trọng đầu tư của nó
• Tính tổng rủi ro dựa trên độ biến động của mỗi tài sản
• Kiểm tra tổng tỷ trọng đầu tư có bằng 100% không (phải bằng!)
• Đảm bảo không có tỷ trọng âm (không bán khống)

Cuối cùng, hàm kết hợp tất cả thông tin thành một điểm số. Điểm cao hơn nghĩa là danh mục tốt hơn. Điểm tăng khi lợi nhuận cao và giảm khi rủi ro cao. Điểm cũng giảm mạnh nếu tổng tỷ trọng không bằng 100% hoặc có tỷ trọng âm.

Hàm này sẽ giúp chúng ta tìm phối hợp đầu tư tốt nhất bằng thuật toán leo đồi ở phần sau. Nếu bạn chưa hiểu tường tận hàm mục tiêu, đừng lo — ý chính là nó cho biết mức độ tốt của một phối hợp đầu tư, và ta sẽ dùng nó để tìm ra các phối hợp ngày càng tốt hơn.

Giờ, hãy định nghĩa một hàm mới để tạo các trạng thái danh mục “hàng xóm” bằng cách điều chỉnh nhỏ các trọng số.

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # Small adjustment to weights (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # Transfer weight from asset i to asset j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # Only transfer if enough weight available
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighborsĐược hỗ trợ bởi

Hàm get_neighbors là phần then chốt của thuật toán leo đồi, tạo ra các phân bổ danh mục tương tự bằng cách điều chỉnh nhỏ trọng số hiện tại. Cách hoạt động:

Với mỗi cặp tài sản trong danh mục, hàm tạo một phân bổ mới bằng cách chuyển một lượng nhỏ (1%) từ tài sản này sang tài sản kia. Ví dụ, nếu có năm tài sản, hàm sẽ thử:

• Chuyển 1% từ Tài sản 1 sang Tài sản 2
• Chuyển 1% từ Tài sản 1 sang Tài sản 3
• Chuyển 1% từ Tài sản 1 sang Tài sản 4
• Chuyển 1% từ Tài sản 1 sang Tài sản 5
• Chuyển 1% từ Tài sản 2 sang Tài sản 1 Và cứ thế cho mọi cặp có thể.

Hàm có kiểm tra an toàn để chỉ chuyển khi tài sản nguồn có đủ tỷ trọng (ít nhất 1%). Điều này ngăn trọng số âm, vốn không hợp lý trong danh mục thực tế.

Mỗi điều chỉnh nhỏ như vậy tạo ra một “hàng xóm” — một phân bổ rất giống hiện tại nhưng khác một chút. Thuật toán leo đồi sẽ đánh giá các hàng xóm này để tìm phân bổ danh mục tốt hơn.

Bước điều chỉnh 1% tạo cân bằng tốt giữa việc khám phá các phân bổ khác nhau và giữ thay đổi có kiểm soát. Bước lớn hơn có thể bỏ lỡ lời giải tối ưu, còn bước nhỏ hơn khiến tìm kiếm quá chậm.

Giờ, hãy triển khai thuật toán leo đồi đơn giản:

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # Get neighboring states
       neighbors = get_neighbors(current_state)
      
       # Flag to check if we found a better neighbor
       found_better = False
      
       # Check neighbors one by one (Simple Hill Climbing)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # If we find a better neighbor, move to it immediately
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # If no better neighbor was found, we've reached a peak
       if not found_better:
           break
  
   return current_state, current_valueĐược hỗ trợ bởi

Hàm bắt đầu từ một trạng thái khởi tạo và lặp lại việc chuyển sang các trạng thái lân cận tốt hơn cho đến khi đạt cực đại cục bộ hoặc đạt số vòng lặp tối đa.

Hàm nhận hai tham số:

• initial_state: Điểm xuất phát cho tối ưu hóa, biểu diễn bằng một danh sách giá trị
• max_iterations: Tham số an toàn để tránh vòng lặp vô hạn, mặc định 1000 vòng

Thuật toán hoạt động như sau:

1. Bắt đầu tại initial_state và tính giá trị hàm mục tiêu của nó
2. Mỗi vòng lặp, thuật toán:

• Sinh các trạng thái lân cận bằng get_neighbors()
• Đánh giá từng hàng xóm lần lượt
• Ngay khi tìm được hàng xóm tốt hơn (giá trị mục tiêu cao hơn), chuyển sang trạng thái đó
• Nếu không có hàng xóm nào tốt hơn, đã đạt cực đại cục bộ và kết thúc

Hàm trả về một bộ gồm:

• Trạng thái tốt nhất tìm được (danh sách giá trị)
• Giá trị hàm mục tiêu tương ứng

Biến thể “đơn giản” này là tham lam — nó chuyển sang hàng xóm tốt hơn đầu tiên tìm thấy thay vì đánh giá hết để tìm tốt nhất. Điều này nhanh hơn nhưng có thể bỏ lỡ lời giải tốt hơn.

Thuật toán hữu ích để tìm cực trị cục bộ nhưng có thể mắc kẹt ở đó, bỏ lỡ cực đại toàn cục. Dù vậy, nó vẫn phổ biến nhờ sự đơn giản và hiệu quả.

Hãy thử với một danh mục mẫu:

# Example usage
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f("Initial State: {initial_state}"))
print(f("Best State Found: {best_state}"))
print(f("Best Value: {best_value}"))

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444Được hỗ trợ bởi

Kết quả hiển thị đầu ra khi tối ưu một danh mục bằng thuật toán leo đồi. Bắt đầu từ trọng số ngẫu nhiên cho năm tài sản, thuật toán tìm được bộ trọng số mới cải thiện giá trị hàm mục tiêu. Dù lời giải này tốt hơn ban đầu, nó có thể chỉ là cực đại cục bộ vì thuật toán dừng ở đỉnh đầu tiên tìm được.

Ứng dụng của leo đồi trong AI

Thuật toán leo đồi có nhiều ứng dụng thực tế trong AI và học máy. Hãy điểm qua một số ứng dụng chính:

1. Tối ưu mô hình học máy

Leo đồi hỗ trợ tinh chỉnh mô hình theo nhiều cách:

• Chọn đặc trưng: Tìm tập đặc trưng tốt nhất cho mô hình
• Tinh chỉnh siêu tham số: Tối ưu tham số như learning rate hoặc độ sâu cây
• Huấn luyện mạng nơ-ron: Tinh chỉnh trọng số và kiến trúc
• Nén mô hình: Giảm kích thước mô hình mà vẫn giữ hiệu năng

Ví dụ, khi chọn đặc trưng cho mô hình dự đoán, Leo Đồi có thể bắt đầu với tất cả đặc trưng và dần loại hoặc thêm dựa trên hiệu năng mô hình. Điều này giúp tìm tập đặc trưng tối ưu cân bằng giữa độ chính xác và độ phức tạp.

2. Robotics và lập kế hoạch đường đi

Trong robot, leo đồi hỗ trợ:

• Lập kế hoạch chuyển động: Tìm đường đi hiệu quả trong không gian vật lý
• Tối ưu góc khớp: Xác định vị trí tối ưu cho cánh tay robot
• Bố trí cảm biến: Tối ưu vị trí cảm biến để phủ vùng tối đa
• Quản lý pin: Tối ưu mô hình tiêu thụ năng lượng

Robot hút bụi có thể dùng leo đồi để tìm đường dọn dẹp hiệu quả, liên tục điều chỉnh lộ trình dựa trên vùng đã dọn và pin còn lại.

3. Xử lý ngôn ngữ tự nhiên

NLP bao gồm:

• Tóm tắt văn bản: Tối ưu lựa chọn nội dung tóm tắt
• Word embedding: Tinh chỉnh biểu diễn vector từ
• Phân cụm tài liệu: Tổ chức tài liệu thành các nhóm tối ưu
• Tối ưu công cụ tìm kiếm: Cải thiện xếp hạng kết quả tìm kiếm

Chẳng hạn, trong tóm tắt văn bản, Leo Đồi có thể chọn các câu tối đa hóa lượng thông tin đồng thời giảm trùng lặp.

4. Thị giác máy tính Trong xử lý ảnh và thị giác máy tính

• Phân đoạn ảnh: Tìm ranh giới tối ưu giữa các đối tượng
• Hiệu chỉnh camera: Điều chỉnh tham số camera để cải thiện chất lượng ảnh
• Phát hiện đối tượng: Tối ưu vị trí bounding box
• Ghép đặc trưng: Tìm các điểm tương ứng giữa các ảnh

Một hệ thống nhận diện khuôn mặt có thể dùng leo đồi để tối ưu canh chỉnh đặc trưng khuôn mặt trong bước tiền xử lý.

5. AI trong trò chơi và ra quyết định

Leo đồi giúp trong:

• Tối ưu chiến lược trò chơi: Tìm nước đi thắng lợi trong cờ bàn
• Phân bổ tài nguyên: Tối ưu phân phối tài nguyên trong game chiến lược
• Hành vi NPC: Cải thiện ra quyết định của nhân vật không người chơi
• Sinh cấp độ: Tạo màn chơi cân bằng và thú vị

Các engine cờ vua thường dùng biến thể của leo đồi để đánh giá và tối ưu chuỗi nước đi khi chơi.

6. Kinh doanh và vận hành

Các ứng dụng thực tiễn trong kinh doanh gồm:

• Tối ưu chuỗi cung ứng: Tìm tuyến giao hàng hiệu quả
• Lập lịch tài nguyên: Tối ưu lịch nhân sự hoặc sử dụng máy móc
• Quản lý danh mục: Cân bằng danh mục đầu tư
• Quản lý tồn kho: Tối ưu mức tồn

Một công ty giao hàng có thể dùng leo đồi để liên tục tối ưu tuyến giao dựa trên giao thông và mức độ ưu tiên bưu kiện.

Dù leo đồi có thể không luôn tìm lời giải tối ưu tuyệt đối, sự đơn giản và hiệu quả khiến nó rất hữu ích trong các ứng dụng thực tế. Nó đặc biệt phù hợp khi:

• Cần lời giải nhanh
• Không gian lời giải quá lớn để tìm kiếm vét cạn
• Chấp nhận lời giải xấp xỉ
• Không gian lời giải tương đối trơn tru
• Có thể kết hợp với kỹ thuật khác để có kết quả tốt hơn

Kết luận

Leo đồi là một thuật toán nền tảng trong AI, mang tới cách tiếp cận tối ưu hóa vừa trực quan vừa mạnh mẽ.

Qua phần trình bày, chúng ta thấy cách khái niệm đơn giản về việc lặp lại hướng tới các lời giải tốt hơn có thể áp dụng cho những thách thức phức tạp trong học máy, robot, xử lý ngôn ngữ tự nhiên và vận hành kinh doanh. 

Dù thuật toán có hạn chế như mắc kẹt ở cực trị cục bộ, các chiến lược như khởi động lại ngẫu nhiên và tôi luyện mô phỏng đã được phát triển để khắc phục hiệu quả.

Khi AI tiếp tục phát triển, leo đồi vẫn giữ vai trò quan trọng không chỉ như một công cụ thực tiễn mà còn là bước đệm để hiểu các thuật toán tối ưu phức tạp hơn. Tính trực quan của nó khiến đây là điểm khởi đầu tuyệt vời cho người mới vào lĩnh vực AI, đồng thời tính linh hoạt đảm bảo nó tiếp tục được dùng trong ứng dụng thực tế. 

Dù bạn đang tối ưu trọng số mạng nơ-ron, lập kế hoạch đường đi cho robot, hay quản lý danh mục đầu tư, các nguyên tắc của leo đồi cung cấp góc nhìn giá trị về cách máy tính có thể hệ thống hóa việc tìm các lời giải tốt hơn cho những bài toán khó.

Nếu bạn muốn tìm hiểu thêm về AI và các thuật toán đằng sau, hãy xem các tài nguyên sau:

• Tìm hiểu thuật toán tìm kiếm A*
• Triển khai thuật toán Minimax cho AI bằng Python
• Các trường hợp sử dụng và thuật toán Machine Learning
• Hướng dẫn thuật toán Gradient Boosting
• Lộ trình Developing AI Applications
• Lộ trình AI Fundamentals