Rate this post

Trong hướng dẫn Python AI này , chúng ta sẽ thảo luận về những điểm thô sơ của Tìm kiếm Heuristic, một phần không thể thiếu của Trí tuệ nhân tạo.

Chúng ta sẽ nói về các kỹ thuật khác nhau như Các vấn đề về sự thỏa mãn ràng buộc, Leo lên đồi và ủ mô phỏng. Ngoài ra, chúng tôi sẽ triển khai CSP bằng Python.

Vì vậy, hãy bắt đầu Tìm kiếm theo phương pháp Heuristic trong Hướng dẫn về AI.

Tóm tắt nội dung

Tìm kiếm theo phương pháp Heuristic là gì?

Heuristic là một kỹ thuật để giải quyết một vấn đề nhanh hơn các phương pháp cổ điển hoặc để tìm một giải pháp gần đúng khi các phương pháp cổ điển không làm được. Đây là một loại phím tắt vì chúng ta thường đánh đổi một trong những yếu tố tối ưu, đầy đủ, chính xác hoặc chính xác để lấy tốc độ.

Một Heuristic (hoặc một hàm heuristic) xem xét các thuật toán tìm kiếm. Tại mỗi bước phân nhánh, nó sẽ đánh giá thông tin có sẵn và đưa ra quyết định theo dõi nhánh nào.

Nó làm như vậy bằng cách xếp hạng các lựa chọn thay thế. Heuristic là bất kỳ thiết bị nào thường hiệu quả nhưng sẽ không đảm bảo hoạt động trong mọi trường hợp.

Các bài viết liên quan:

Vậy tại sao chúng ta cần heuristics ? Một lý do là tạo ra, trong một khoảng thời gian hợp lý, một giải pháp đủ tốt cho vấn đề được đề cập. Nó không nhất thiết phải là giải pháp tốt nhất – một giải pháp gần đúng sẽ làm được vì điều này đủ nhanh.

Hầu hết các vấn đề là cấp số nhân. Tìm kiếm Heuristic cho phép chúng tôi giảm số này thành một số khá đa thức. Chúng tôi sử dụng điều này trong AI vì chúng tôi có thể sử dụng nó trong các tình huống mà chúng tôi không thể tìm thấy các thuật toán đã biết.

Có thể nói Kỹ thuật Heuristic là phương pháp yếu vì chúng dễ bị bùng nổ tổ hợp.

Kỹ thuật tìm kiếm heuristic trong trí tuệ nhân tạo

Một cách ngắn gọn, chúng ta có thể phân loại các kỹ thuật như vậy của Heuristic thành hai loại:

Kỹ thuật Tìm kiếm Heuristic Trực tiếp trong AI

Các tên khác của chúng là Tìm kiếm mù, Tìm kiếm không có thông tin và Chiến lược kiểm soát mù. Những điều này không phải lúc nào cũng có thể thực hiện được vì chúng đòi hỏi nhiều thời gian hoặc bộ nhớ.

Các bài viết liên quan:

Họ tìm kiếm toàn bộ không gian trạng thái cho một giải pháp và sử dụng một thứ tự tùy ý của các hoạt động. Ví dụ về những điều này là Tìm kiếm đầu tiên theo chiều rộng (BFS) và Tìm kiếm đầu tiên theo chiều sâu (DFS).

Các kỹ thuật tìm kiếm Heuristic yếu trong AI

Các tên khác của những thứ này là Tìm kiếm được thông tin, Tìm kiếm theo phương pháp Heuristic và Chiến lược kiểm soát theo phương pháp Heuristic. Những điều này sẽ hiệu quả nếu được áp dụng đúng cách cho các loại nhiệm vụ phù hợp và thường yêu cầu thông tin về miền cụ thể.

Chúng tôi cần thông tin bổ sung này để tính toán mức độ ưu tiên giữa các nút con để khám phá và mở rộng. Mỗi nút có một hàm heuristic được liên kết với nó. Ví dụ như Tìm kiếm đầu tiên tốt nhất (BFS) và A *.

Trước khi chúng ta chuyển sang mô tả các kỹ thuật nhất định, trước tiên chúng ta hãy xem xét những kỹ thuật mà chúng ta thường quan sát. Dưới đây, chúng tôi nêu tên một số.

BFS(Best-First Search)
A* Search
Hill Climbing
Constraint Satisfaction Problems(CSP)

Leo đồi trong Trí tuệ nhân tạo

Đầu tiên, hãy nói về Leo đồi trong Trí thông minh nhân tạo . Đây là một phương pháp heuristic để tối ưu hóa các vấn đề về mặt toán học. Chúng ta cần chọn các giá trị từ đầu vào để tối đa hóa hoặc thu nhỏ một hàm thực. Sẽ không sao nếu giải pháp không phải là giải pháp tối ưu toàn cục.

Một ví dụ như vậy về Leo đồi sẽ là Bài toán Người bán hàng Đi du lịch được thảo luận rộng rãi – một bài toán mà chúng ta phải giảm thiểu quãng đường anh ta đi.

Các tính năng của Leo đồi trong AI

Hãy thảo luận một số tính năng của thuật toán này (Hill Climbing):

Nó là một biến thể của thuật toán tạo và kiểm tra
Nó sử dụng cách tiếp cận tham lam

Điều này có nghĩa là nó tiếp tục tạo ra các giải pháp khả thi cho đến khi tìm thấy giải pháp mong đợi và chỉ di chuyển theo hướng tối ưu hóa hàm chi phí cho nó.

Các kiểu leo đồi trong AI

Simple Hill Climbing- Công cụ này kiểm tra từng nút lân cận và chọn nút đầu tiên tối ưu hóa chi phí hiện tại để làm nút tiếp theo.
Leo đồi dốc nhất lên đồi – Điều này kiểm tra tất cả các nút lân cận và chọn nút gần nhất với trạng thái giải pháp.
Stochastic Hill Climbing- Điều này chọn ngẫu nhiên một nút lân cận và quyết định di chuyển đến nó hay kiểm tra một nút khác.

Hãy cùng xem thuật toán leo đồi đơn giản.

Đánh giá trạng thái ban đầu – nếu trạng thái mục tiêu, dừng và trả lại thành công. Khác, làm cho trạng thái ban đầu hiện tại.
Lặp lại cho đến khi đạt được giải pháp hoặc cho đến khi không còn toán tử mới nào để áp dụng cho trạng thái hiện tại:

Chọn toán tử mới để áp dụng cho trạng thái sản xuất mới hiện tại.
Đánh giá trạng thái mới:
- Nếu một trạng thái mục tiêu, hãy dừng lại và trả về thành công.
- Nếu tốt hơn trạng thái hiện tại, hãy đặt nó ở trạng thái hiện tại, tiến hành.
- Ngay cả khi không tốt hơn tình trạng hiện tại, hãy tiếp tục cho đến khi đạt được giải pháp.

Ouput

Các vấn đề với Leo đồi trong AI

Chúng tôi thường gặp một trong ba vấn đề-

Tối đa cục bộ- Tất cả các trạng thái lân cận đều có giá trị thấp hơn hiện tại. Cách tiếp cận tham lam có nghĩa là chúng ta sẽ không chuyển sang trạng thái tồi tệ hơn. Điều này kết thúc quá trình mặc dù có thể đã có một giải pháp tốt hơn. Để giải quyết vấn đề, chúng tôi sử dụng backtracking.
Plateau- Tất cả các hàng xóm của nó đều có giá trị như nhau. Điều này khiến bạn không thể chọn được hướng đi. Để tránh điều này, chúng tôi ngẫu nhiên thực hiện một bước nhảy lớn.
Ridge- Tại một sườn núi, chuyển động theo tất cả các hướng có thể là hướng xuống. Điều này làm cho nó giống như một đỉnh cao và kết thúc quá trình. Để tránh điều này, chúng tôi có thể sử dụng hai hoặc nhiều quy tắc trước khi thử nghiệm.

Constraint Satisfaction Problems (CSP)

Ràng buộc không là gì khác ngoài sự hạn chế hoặc hạn chế. Làm việc với AI , chúng ta có thể cần phải thỏa mãn một số ràng buộc để giải quyết vấn đề. Chúng ta hãy thử giải quyết một vấn đề theo cách này, phải không?

Hãy nói về một hình vuông kỳ diệu. Đây là một dãy số – thường là số nguyên – được sắp xếp trong một lưới vuông. Các số trong mỗi hàng, mỗi cột và mỗi đường chéo cộng lại thành một hằng số mà chúng ta gọi là Hằng số ma thuật . Hãy thực hiện điều này với Python.

def magic_square(matrix):
   size=len(matrix[0])
   sum_list=[]
   for col in range(size): #Vertical sum
       sum_list.append(sum(row for row in matrix))
   sum_list.extend([sum(lines) for lines in matrix])#Horizontal sum
   result1=0
   for i in range(0,size):
       result1+=matrix[i][i]
   sum_list.append(result1)
   result2=0
   for i in range(size-1,-1,-1):
       result2+=matrix[i][i]
   sum_list.append(result2)
   if len(set(sum_list))>1:
       return False
   return True

Bây giờ chúng ta hãy chạy mã này.

magic_square([[1,2,3],[4,5,6],[7,8,9]])

Sai

Đây không phải là một hình vuông ma thuật. Các số trong hàng / cột / đường chéo không cộng lại với cùng một giá trị. Hãy thử một danh sách danh sách khác.

magic_square([[2,7,6],[9,5,1],[4,3,8]])

Đúng

Vì các giá trị cộng lại với hằng số 15 theo mọi hướng, nên chắc chắn, đây là một hình vuông kỳ diệu!

Tìm kiếm chữa bệnh bằng phương pháp ủ mô phỏng

Trong luyện kim, khi chúng ta làm nguội kim loại chậm để kéo chúng xuống trạng thái năng lượng thấp sẽ mang lại cho chúng một lượng sức mạnh mẫu mực. Chúng tôi gọi đây là quá trình ủ. Trong khi nhiệt độ cao quan sát nhiều chuyển động ngẫu nhiên, nhiệt độ thấp nhận thấy ít ngẫu nhiên.

Trong AI, chúng tôi lấy một gợi ý từ điều này để tạo ra một thứ gọi là ủ mô phỏng. Đây là một cách tối ưu hóa mà chúng ta bắt đầu với một tìm kiếm ngẫu nhiên ở nhiệt độ cao và giảm nhiệt độ từ từ.

Cuối cùng, khi nhiệt độ gần bằng không, việc tìm kiếm trở nên thuần túy tham lam. Ở mỗi bước, quá trình này chọn ngẫu nhiên một biến và một giá trị. Nó chỉ chấp nhận nhiệm vụ khi nó là một cải tiến hoặc không dẫn đến xung đột nhiều hơn.

Nếu không, nó sẽ kiểm tra xem nhiệt độ có kém hơn nhiều so với nhiệm vụ hiện tại hay không để chấp nhận nhiệm vụ với một số xác suất.

Lịch ủ xác định nhiệt độ giảm như thế nào khi tiến trình tìm kiếm. Một lịch trình rất phổ biến là làm mát hình học. Nếu chúng ta bắt đầu với nhiệt độ là 10 và nhân với 0,97 sau mỗi bước, thì sau 100 bước, chúng ta sẽ có nhiệt độ là 0,48.

Best-First Search(BFS)

Thường được gọi là BFS, Tìm kiếm đầu tiên tốt nhất là một tìm kiếm được thông báo sử dụng chức năng đánh giá để quyết định vùng lân cận nào hứa hẹn nhất trước khi có thể tiếp tục khám phá. Breadth- and Depth- First Tìm kiếm khám phá những con đường một cách mù quáng mà không lưu ý đến hàm chi phí.

Tuy nhiên, mọi thứ không giống với BFS. Ở đây, chúng tôi sử dụng một hàng đợi ưu tiên để lưu trữ chi phí nút. Hãy hiểu BFS Heuristic Search thông qua mã giả.

Xác định danh sách MỞ với nút đơn s – nút bắt đầu.
Danh sách IF trống, trả về không thành công.
Loại bỏ nút n (nút có điểm tốt nhất) khỏi danh sách, chuyển nó vào danh sách ĐÃ ĐÓNG CỬA.
Mở rộng nút n .
NẾU bất kỳ kế thừa nào cho n là nút mục tiêu, trả về thành công và theo dõi đường dẫn từ nút mục tiêu đến s để trả về giải pháp.
ĐỐI VỚI mỗi nút kế nhiệm:

Áp dụng hàm đánh giá f .
NẾU nút không có trong một trong hai danh sách, hãy thêm nó vào danh sách MỞ.

Lặp lại bước 2.

Vì vậy, tất cả đều nằm trong Kỹ thuật tìm kiếm Heuristic trong AI. Hy vọng bạn thích giải thích của chúng tôi.

Sự kết luận

Do đó, trong hướng dẫn Python AI này, chúng tôi đã thảo luận về Tìm kiếm Heuristic trong AI. Trong khi chúng tôi nêu tên một số kỹ thuật nằm trong đó, chúng tôi cũng thảo luận ngắn gọn về những kỹ thuật như BFS, Hill Climbing, Simulated Annealing và CSP.

Chúng tôi cũng đã triển khai CSP bằng Python. Tuy nhiên, nếu bạn có bất kỳ câu hỏi nào trong Kỹ thuật Tìm kiếm Heuristic, hãy hỏi trong tab nhận xét.

Artificial Intelligence

Tìm kiếm Heuristic trong AI