Hill Climbing Algorithm là một thuật toán tìm kiếm cục bộ liên tục di chuyển theo hướng tăng dần giá trị để tìm ra đỉnh hoặc giải pháp tốt nhất cho vấn đề. Nó kết thúc khi nó đạt đến giá trị cao nhất mà không có giải pháp nào có giá trị cao hơn.
Hill Climbing Algorithm là một kỹ thuật được sử dụng để tối ưu hóa các vấn đề toán học. Một trong những ví dụ được thảo luận rộng rãi về Hill Climbing Algorithm là Bài toán nhân viên bán hàng đi lại, trong đó chúng ta cần giảm thiểu khoảng cách di chuyển của nhân viên bán hàng.
Nó cũng được gọi là tìm kiếm cục bộ tham lam vì nó chỉ tìm kiếm trạng thái láng giềng tốt ngay lập tức và không vượt ra ngoài điều đó.
Một nút của Hill Climbing Algorithm có hai thành phần là trạng thái và giá trị.
Hill Climbing chủ yếu được sử dụng khi có sẵn kinh nghiệm tốt.
Trong thuật toán này, chúng ta không cần duy trì và xử lý cây tìm kiếm hoặc đồ thị vì nó chỉ giữ một trạng thái hiện tại duy nhất.
Đặc điểm của Leo đồi:
Sau đây là một số tính năng chính của Hill Climbing Algorithm:
- Biến thể Tạo và Thử nghiệm: Leo đồi là biến thể của Phương pháp Tạo và Thử nghiệm. Phương pháp Tạo và Kiểm tra tạo ra phản hồi giúp quyết định hướng di chuyển trong không gian tìm kiếm.
- Cách tiếp cận tham lam: Tìm kiếm Hill Climbing Algorithm di chuyển theo hướng tối ưu hóa chi phí.
- Không quay lui: Nó không quay lại không gian tìm kiếm, vì nó không nhớ các trạng thái trước đó.
Sơ đồ không gian trạng thái cho Leo đồi:
Cảnh quan không gian-trạng thái là một biểu diễn đồ họa của Hill Climbing Algorithm đang hiển thị một biểu đồ giữa các trạng thái khác nhau của thuật toán và Hàm mục tiêu / Chi phí.
Trên trục Y, chúng ta đã sử dụng hàm có thể là hàm mục tiêu hoặc hàm chi phí và không gian trạng thái trên trục x. Nếu hàm trên trục Y là chi phí thì mục tiêu của tìm kiếm là tìm giá trị tối thiểu toàn cục và giá trị tối thiểu cục bộ. Nếu hàm của trục Y là hàm Mục tiêu, thì mục tiêu của tìm kiếm là tìm giá trị cực đại toàn cục và cực đại cục bộ.
Các vùng khác nhau trong cảnh quan không gian trạng thái:
Local Maximum: Cực đại cục bộ là một trạng thái tốt hơn các trạng thái lân cận của nó, nhưng cũng có một trạng thái khác cao hơn nó.
Global Maximum: Tối đa toàn cầu là trạng thái tốt nhất có thể của cảnh quan không gian trạng thái. Nó có giá trị cao nhất của hàm mục tiêu.
Current state: Đó là một trạng thái trong sơ đồ cảnh quan mà một tác nhân hiện đang có mặt.
Flat local maximum: Là không gian phẳng trong cảnh mà tất cả các trạng thái lân cận của các trạng thái hiện tại có cùng giá trị.
Shoulder: Là một vùng cao nguyên có sườn dốc.
Các loại Hill Climbing Algorithm:
- Simple hill Climbing:
- Steepest-Ascent hill-climbing:
- Stochastic hill Climbing:
Xem thêm Phân tích Means-Ends Analysis trong Artificial Intelligence
Simple hill Climbing
Leo đồi đơn giản là cách đơn giản nhất để thực hiện Hill Climbing Algorithm. Nó chỉ đánh giá trạng thái nút lân cận tại một thời điểm và chọn trạng thái đầu tiên tối ưu hóa chi phí hiện tại và đặt nó làm trạng thái hiện tại. Nó chỉ kiểm tra đó là một trạng thái kế thừa và nếu nó thấy tốt hơn trạng thái hiện tại, thì chuyển sang trạng thái khác ở cùng trạng thái đó. Thuật toán này có các tính năng sau:
- Ít tốn thời gian hơn
- Giải pháp kém tối ưu hơn và giải pháp không được đảm bảo
Simple Hill Climbing Algorithm:
- Bước 1: Đánh giá trạng thái ban đầu, nếu là trạng thái mục tiêu thì trả về thành công và Dừng lại.
- Bước 2: Vòng lặp Cho đến khi tìm ra giải pháp hoặc không còn người vận hành mới để áp dụng.
- Bước 3: Chọn và áp dụng một toán tử cho trạng thái hiện tại.
- Bước 4: Kiểm tra trạng thái mới:
- Nếu đó là trạng thái mục tiêu, sau đó trả lại thành công và bỏ thuốc lá.
- Khác nếu nó tốt hơn trạng thái hiện tại thì gán trạng thái mới làm trạng thái hiện tại.
- Nếu không, nếu không tốt hơn trạng thái hiện tại, sau đó quay lại bước 2.
- Bước 5: Thoát.
Steepest-Ascent hill-climbing
Thuật toán leo dốc nhất là một biến thể của Hill Climbing Algorithm đơn giản. Thuật toán này kiểm tra tất cả các nút lân cận của trạng thái hiện tại và chọn một nút lân cận gần nhất với trạng thái mục tiêu. Thuật toán này tiêu tốn nhiều thời gian hơn vì nó tìm kiếm nhiều hàng xóm
Algorithm for Steepest-Ascent hill climbing:
- Bước 1: Đánh giá trạng thái ban đầu, nếu là trạng thái mục tiêu thì trả về thành công và dừng, nếu không thì chuyển trạng thái hiện tại thành trạng thái ban đầu.
- Bước 2: Vòng lặp cho đến khi tìm ra giải pháp hoặc trạng thái hiện tại không thay đổi.
- Hãy để SUCC là một trạng thái sao cho bất kỳ người kế thừa nào của trạng thái hiện tại sẽ tốt hơn nó.
- Đối với mỗi toán tử áp dụng cho trạng thái hiện tại:
- Áp dụng toán tử mới và tạo trạng thái mới.
- Đánh giá trạng thái mới.
- Nếu đó là trạng thái mục tiêu, hãy trả lại và thoát ra, nếu không, hãy so sánh nó với SUCC.
- Nếu nó tốt hơn SUCC, thì hãy đặt trạng thái mới là SUCC.
- Nếu SUCC tốt hơn trạng thái hiện tại, thì hãy đặt trạng thái hiện tại thành SUCC.
- Bước 3: Thoát.
Stochastic hill Climbing
Hill Climbing Stochastic không kiểm tra tất cả những node lân cận của nó trước khi duyệt qua node khác. Thay vào đó, thuật toán này chọn ngẫu nhiên một node lân cận và đưa ra quyết định chọn node đó có trạng thái hiện tại hay trạng thái khác.
Các vấn đề trong Hill Climbing Algorithm:
1. Local Maximum: Cực đại cục bộ là trạng thái cao nhất trong cảnh quan tốt hơn từng trạng thái lân cận của nó, nhưng có một trạng thái khác cũng hiện diện cao hơn trạng thái tối đa cục bộ.
Giải pháp: Kỹ thuật backtracking có thể là một giải pháp tối đa cục bộ trong cảnh quan không gian trạng thái. Tạo danh sách các đường dẫn đầy hứa hẹn để thuật toán có thể kiểm tra lại không gian tìm kiếm và khám phá các đường dẫn khác.
2. Plateau: Plateau là vùng phẳng của không gian tìm kiếm trong đó tất cả các trạng thái lân cận của trạng thái hiện tại đều chứa cùng một giá trị, vì thuật toán này không tìm ra hướng tốt nhất để di chuyển. Tìm kiếm leo đồi có thể bị thất lạc trong khu vực cao nguyên.
Giải pháp: Giải pháp cho bình nguyên là thực hiện các bước lớn hoặc rất ít bước trong khi tìm kiếm, để giải quyết vấn đề. Chọn ngẫu nhiên một trạng thái khác xa trạng thái hiện tại để thuật toán có thể tìm thấy vùng không bình nguyên.
3. Ridges: ridge là một dạng đặc biệt của Local Maximum. Nó có một khu vực cao hơn các khu vực xung quanh của nó, nhưng bản thân nó có một độ dốc và không thể đạt được trong một lần di chuyển.
Giải pháp: Với việc sử dụng tìm kiếm hai chiều hoặc bằng cách di chuyển theo các hướng khác nhau, chúng tôi có thể cải thiện vấn đề này.
Mô phỏng Annealing:
Hill Climbing Algorithm không bao giờ di chuyển đến giá trị thấp hơn được đảm bảo là không hoàn chỉnh vì nó có thể bị mắc kẹt ở mức tối đa cục bộ. Và nếu thuật toán áp dụng một bước đi ngẫu nhiên, bằng cách di chuyển một người kế nhiệm, thì nó có thể hoàn thành nhưng không hiệu quả. Ủ mô phỏng là một thuật toán mang lại cả hiệu quả và tính hoàn chỉnh.
Theo thuật ngữ cơ học Annealing là một quá trình làm cứng kim loại hoặc thủy tinh đến nhiệt độ cao sau đó làm nguội dần dần, do đó, điều này cho phép kim loại đạt đến trạng thái tinh thể năng lượng thấp. Quá trình tương tự được sử dụng trong ủ mô phỏng, trong đó thuật toán chọn một nước đi ngẫu nhiên, thay vì chọn nước đi tốt nhất. Nếu di chuyển ngẫu nhiên cải thiện trạng thái, thì nó đi theo con đường tương tự. Nếu không, thuật toán đi theo con đường có xác suất nhỏ hơn 1 hoặc nó di chuyển xuống dốc và chọn một con đường khác.
