DAA - Thuật toán leo đồi
Các thuật toán được thảo luận trong các chương trước chạy một cách có hệ thống. Để đạt được mục tiêu, một hoặc nhiều con đường đã khám phá trước đó hướng tới giải pháp cần được lưu trữ để tìm ra giải pháp tối ưu.
Đối với nhiều vấn đề, con đường dẫn đến mục tiêu là không liên quan. Ví dụ, trong bài toán N-Queens, chúng ta không cần quan tâm đến cấu hình cuối cùng của các nữ hoàng cũng như thứ tự các nữ hoàng được thêm vào.
Leo đồi
Hill Climbing là một kỹ thuật để giải quyết các vấn đề tối ưu hóa nhất định. Trong kỹ thuật này, chúng tôi bắt đầu với một giải pháp phụ tối ưu và giải pháp được cải thiện lặp đi lặp lại cho đến khi một số điều kiện được tối đa hóa.
Ý tưởng bắt đầu với một giải pháp phụ tối ưu được so sánh với việc bắt đầu từ chân đồi, việc cải thiện giải pháp được so sánh với việc đi bộ lên đồi, và cuối cùng tối đa hóa một số điều kiện so với việc lên đến đỉnh đồi.
Do đó, kỹ thuật leo đồi có thể được coi là các giai đoạn sau:
- Xây dựng một giải pháp tối ưu phụ tuân theo các ràng buộc của vấn đề
- Cải tiến giải pháp từng bước
- Cải thiện giải pháp cho đến khi không thể cải thiện được nữa
Kỹ thuật Hill Climbing chủ yếu được sử dụng để giải các bài toán khó về mặt tính toán. Nó chỉ nhìn vào trạng thái hiện tại và trạng thái tương lai trước mắt. Do đó, kỹ thuật này hiệu quả về bộ nhớ vì nó không duy trì cây tìm kiếm.
Algorithm: Hill Climbing
Evaluate the initial state.
Loop until a solution is found or there are no new operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal -→ quit
better than current state -→ new current stateCải tiến lặp đi lặp lại
Trong phương pháp cải tiến lặp đi lặp lại, giải pháp tối ưu đạt được bằng cách tiến tới giải pháp tối ưu trong mỗi lần lặp lại. Tuy nhiên, kỹ thuật này có thể gặp cực đại cục bộ. Trong tình huống này, không có trạng thái nào gần đó để có giải pháp tốt hơn.
Vấn đề này có thể được tránh bằng các phương pháp khác nhau. Một trong những phương pháp này là ủ mô phỏng.
Khởi động lại ngẫu nhiên
Đây là một phương pháp khác để giải quyết vấn đề của optima cục bộ. Kỹ thuật này thực hiện một loạt các tìm kiếm. Mỗi lần, nó bắt đầu từ trạng thái ban đầu được tạo ngẫu nhiên. Do đó, có thể thu được optima hoặc giải pháp gần như tối ưu so với các giải pháp của các tìm kiếm được thực hiện.
Các vấn đề của kỹ thuật leo đồi
Maxima địa phương
Nếu heuristic không lồi, Hill Climbing có thể hội tụ thành cực đại cục bộ, thay vì cực đại toàn cục.
Ridges và hẻm
Nếu hàm mục tiêu tạo ra một sườn núi hẹp, thì người leo núi chỉ có thể lên đỉnh hoặc xuống hẻm bằng cách chạy zig-zag. Trong trường hợp này, người leo núi cần thực hiện những bước rất nhỏ, đòi hỏi nhiều thời gian hơn để đạt được mục tiêu.
Cao nguyên
Gặp phải sự cố định khi không gian tìm kiếm bằng phẳng hoặc đủ phẳng mà giá trị được trả về bởi hàm mục tiêu không thể phân biệt được với giá trị được trả về cho các vùng lân cận, do độ chính xác được máy sử dụng để biểu thị giá trị của nó.
Độ phức tạp của kỹ thuật leo đồi
Kỹ thuật này không bị các vấn đề liên quan đến không gian, vì nó chỉ xem xét trạng thái hiện tại. Các đường dẫn đã khám phá trước đây không được lưu trữ.
Đối với hầu hết các vấn đề trong kỹ thuật Leo đồi khởi động lại ngẫu nhiên, một giải pháp tối ưu có thể đạt được trong thời gian đa thức. Tuy nhiên, đối với các bài toán NP-Complete, thời gian tính toán có thể theo cấp số nhân dựa trên số lượng cực đại cục bộ.
Các ứng dụng của kỹ thuật leo đồi
Kỹ thuật Hill Climbing có thể được sử dụng để giải quyết nhiều vấn đề, trong đó trạng thái hiện tại cho phép một chức năng đánh giá chính xác, chẳng hạn như Network-Flow, Traveling Salesman problem, 8-Queens, Integrated Circuit design, v.v.
Hill Climbing cũng được sử dụng trong phương pháp học tập quy nạp. Kỹ thuật này được sử dụng trong robot để phối hợp giữa nhiều robot trong một đội. Có nhiều vấn đề khác khi kỹ thuật này được sử dụng.
Thí dụ
Kỹ thuật này có thể được áp dụng để giải quyết vấn đề nhân viên bán hàng đi du lịch. Đầu tiên, một giải pháp ban đầu được xác định là đi thăm tất cả các thành phố chính xác một lần. Do đó, giải pháp ban đầu này không phải là tối ưu trong hầu hết các trường hợp. Ngay cả giải pháp này có thể rất kém. Thuật toán Hill Climbing bắt đầu với một giải pháp ban đầu như vậy và thực hiện các cải tiến cho nó theo cách lặp đi lặp lại. Cuối cùng, một lộ trình ngắn hơn nhiều có thể đạt được.