zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Hệ thống thông minh: Phần 3 - Kỹ thuật tìm kiếm Heuristic

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:36

Báo xấu

2
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Hệ thống thông minh: Phần 3 - Kỹ thuật tìm kiếm Heuristic" bao gồm các nội dung chính sau đây: Sinh ra và Kiểm thử (Generate-and-Test); Leo đồi (Hill Climbing); Tìm kiếm tốt nhất đầu tiên; Suy giảm vấn đề; Thỏa mãn ràng buộc (Constraint satisfaction); Phân tích Means-Ends. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Hệ thống thông minh: Phần 3 - Kỹ thuật tìm kiếm Heuristic

KỸ THUẬT TÌM KIẾM HEURISTIC 1
NỘI DUNG • Sinh ra và Kiểm thử (Generate-and-Test) • Leo đồi (Hill Climbing) – Leo đồi đơn giản (Simple Hill Climbing) – Leo đồi dốc đứng (Steepest-Ascent Hill Climbing) – Mô phỏng luyện kim (Simulated Annealing) • Tìm kiếm tốt nhất đầu tiên – Đồ thị OR & Thuật toán tìm kiếm tốt nhất đầu tiên – Thuật toán A* • Suy giảm vấn đề – Đồ thị AND-OR – Thuật toán AO* • Thỏa mãn ràng buộc (Constraint satisfaction) • Phân tích Means-Ends 2
SINH RA VÀ KIỂM THỬ Generate-and-Test • Algo Genarate-and-Test 1. Sinh ra: một « lời giải tiềm năng » có thể ▪ Sinh ra một nút / Sinh ra một đường đi xuất phát từ trạng thái khởi đầu 2. Kiểm thử: « lời giải tiềm năng » được sinh ra là một lời giải? ▪ So sánh nút được sinh ra/ đầu mút cuối của đường đi được sinh ra với các trạng thái đích 3. Nếu tìm thấy một lời giải « thông báo và thoát » nếu không quay lại bước 1. • Nếu quá trình « sinh ra » là có hệ thống, thủ tục « có thể » tìm thấy một lời giải nếu nó tồn tại nhưng « có thể » rất lâu! • Thuật toán « Sinh ra và Kiểm thử » là thuật toán tìm kiếm sâu. – Nếu « sinh ra » có hệ thống (tìm kiếm vét cạn) – Nếu « sinh ra » ngẫu nhiên, không chắc tìm thấy lời giải dù nó tồn tại (thuật toán bảo tàng Anh – British Museum) – « Sinh ra » có hệ thống, bỏ qua một số « lời giải tiềm năng » thiếu hứa hẹn là một giải pháp dung hòa hai thái cực trên (Sinh ra và kiểm thử heuristic) – « Sinh ra và kiểm thử » kết hợp với « Lập kế hoạch » 3
LEO ĐỒI – HILL CLIMBING (1) • Leo đồi là một biến thể của sinh ra và kiểm thử, trong đó thông tin phản hồi từ thủ tục kiểm thử hỗ trợ « bộ sinh » quyết định hướng di chuyển – Trong « Sinh ra và kiểm thử », hàm kiểm thử là hàm Yes-No – Nếu hàm kiểm thử là một hàm heuristic, cung cấp một ước lượng « tính gần » của trạng thái đã cho so với đích, « bộ sinh » sẽ khai thác « thông tin » này để quyết định hướng « khai thác » • Leo đồi thường được sử dụng khi có sẵn một hàm heuristic tốt và thiếu thông tin hữu dụng khác 4
LEO ĐỒI – HILL CLIMBING (2) LEO ĐỒI ĐƠN GiẢN • Algo Simple Hill Climbing 1. Đánh giá trạng thái khởi đầu. Nếu nó là một trạng thái đích, « thông báo kết quả » và thoát, nếu không lấy trạng thái khởi đầu làm trạng thái hiện hành. 2. Lặp lại đến tận khi tìm thấy một lời giải hoặc không còn toán tử nào có thể áp dụng vào trạng thái hiện hành: a) Chọn một toán tử có thể áp dụng vào trạng thái hiện hành nhưng chưa được áp dụng vào trạng thái hiện hành. Áp dụng nó vào trạng thái hiện hành để sinh ra trạng thái mới b) Đánh giá trạng thái mới. i. Nếu nó là một trạng thái đích, « thông báo kết quả » và thoát ii. Nếu nó không là một trạng thái đích nhưng « tốt hơn » trạng thái hiện hành, lấy nó làm trạng thái hiện hành iii. Nếu nó không là một trạng thái đích và không « tốt hơn » trạng thái hiện hành, tiếp tục vòng lặp • Hàm đánh giá « tốt hơn » là phương tiện để đưa « tri thức lĩnh vực » vào quá trình điều khiển. • Phương pháp tìm kiếm sử dụng « tri thức lĩnh vực » được gọi là phương pháp tìm kiếm heuristic. 5
LEO ĐỒI – HILL CLIMBING (3) LEO ĐỒI DỐC ĐỨNG • Algo Steepest_Ascent Hill Climbing 1. Đánh giá trạng thái khởi đầu. Nếu nó là một trạng thái đích, « thông báo kết quả » và thoát, nếu không lấy trạng thái khởi đầu làm trạng thái hiện hành. 2. Lặp lại đến tận khi tìm thấy một lời giải hoặc tất cả các toán tử có thể không làm thay đổi trạng thái hiện hành a) Gọi SUCC là một successor của trạng thái hiện hành b) Đối với mỗi toán tử có thể áp dụng vào trạng thái hiện hành làm: i. Áp dụng toán tử vào trạng thái hiện hành để sinh ra một trạng thái mới ii. Đánh giá trạng thái mới. Nếu nó là trạng thái đích, « thông báo kết quả » và thoát, nếu không, nếu nó tốt hơn SUCC, lấy nó làm SUCC iii. Nếu SUCC tốt hơn trạng thái hiện hành, lấy SUCC làm trạng thái hiện hành 6
LEO ĐỒI – HILL CLIMBING (4) • Thuật toán leo đồi (đơn giản, dốc đứng) có thể rơi vào tình huống: kết thúc nhưng không tìm thấy lời giải, nhưng đạt tới trạng thái không « không thể tốt hơn được nữa »: – Cực trị địa phương (local optimum): Trạng thái tốt hơn tất cả các trạng thái lân cận, nhưng không tốt hơn « các trạng thái xa hơn » Giải pháp: Quay lại một nút trước đó, chọn một hướng đi khác 7
LEO ĐỒI – HILL CLIMBING (5) – Cao nguyên (Plateau) Giải pháp: tạo ra một « bước nhảy » để chuyển sang một phần khác trong KGTK – Chỏm (Ridge): Dạng đặc biệt của cực trị địa phương – không thể vượt qua « chỏm » bởi một phép di chuyển Giải pháp: Áp dụng nhiều hơn một toán tử trước khi kiểm thử 8
LEO ĐỒI – HILL CLIMBING (6) MÔ PHỎNG LUYỆN KIM • Algo Simulated_Annealing 1. Đánh giá trạng thái khởi đầu. Nếu nó là trạng thái đích, « thông báo kết quả » và thoát, nếu không lấy nó làm trạng thái hiện hành (current) 2. Khởi động BEST_SO_FAR là trạng thái hiện hành 3. Khởi động T tương ứng với lịch biểu tôi luyện 4. Lặp lại đến tận khi tìm thấy một lời giải hoặc không còn toán tử nào có thể áp dụng vào trạng thái hiện hành a) Chọn một toán tử chưa được áp dụng lên trạng thái hiện hành, áp dụng nó để sinh ra trạng thái mới (new) b) Đánh giá trạng thái mới: i. Tính: ΔE = value(current) – value(new) ii. Nếu trạng thái new là một trạng thái đích, « thông báo kết quả » và thoát iii. Nếu new không là trạng thái đích nhưng tốt hơn cuurent, lấy new làm current,đặt BEST_SO_FAR là new iv. Nếu new không tốt hơn current, khi đó lấy new làm current với xác suất p’=e-ΔE/T (sinh ra một số ngẫu nhiên r, nếu r < p’ lấy new làm current, nếu không giũ nguyên current) c) Xét lại T theo lịch biểu tôi luyện 5. Return BEST_SO_FAR như thông báo kết quả 9
LEO ĐỒI – HILL CLIMBING (7) MÔ PHỎNG LUYỆN KIM • Lịch biểu tôi luyện gồm 4 thành phần: 1. Giá trị khởi đầu (nhiệt độ ban đầu) 2. Tiêu chuẩn dùng để quyết định giảm nhiệt độ 3. Lượng giảm nhiệt cho mỗi lần giảm nhiệt độ 4. Điều kiện thoát (có thể có/không) • Kinh nghiệm chọn lịch biểu tôi luyện: – thử một vài lịch biểu và quan sát hiệu quả: chất lượng lời giải và tốc độ hội tụ • Lượng giảm nhiệt nhỏ thường cho lời giải chất lượng tốt nhưng hội tụ chậm • Lượng giảm nhiệt lớn thường cho lời giải chất lượng kém nhưng hội tụ nhanh 10
TÌM KIẾM TỐT NHẤT ĐẦU TIÊN (1) OPEN: Priority_Queue of Node; CLOSED: SET of Node; found = 0; • Algo Best_First_search 1. Init OPEN = [Start] 2. While (!found && !Empty(OPEN)) { C = Bestof(OPEN); Delete(C, OPEN); Insert(C, CLOSED); if (isgoal(C)) {; found = 1} else { Sinh ra các succ của C; For (mỗi succ của C) do If NOT member(succ, OPEN) && NOT member(succ, CLOSED) { đánh giá succ;; Insert(succ, OPEN); Parent(succ) = C } Else If (đường đi đến succ qua C tốt hơn đường đi cũ) { parent(succ) = C; cập nhật « giá » của đường đi đến succ và các successor của succ } } } 11
TÌM KiẾM TỐT NHẤT ĐẦU TIÊN (2) THUẬT TOÁN A* • Thuật toán A*, một biến thể của thuật toán tìm kiếm tốt nhất đầu tiên, sử dụng các hàm đánh giá f’, g và h’ – Hàm f’(n) là một ước lượng của hàm f(n) = giá tốt nhất phải trả để đi từ trạng thái khởi đầu tới đích qua trạng thái n – Hàm h’(n) là một ước lượng của hàm « giá » phải trả thực h(n) để đi từ trạng thái n đến đích – Hàm g(n) là giá tốt nhất hiện thời phải trả để đi từ trạng thái khởi đầu đến trạng thái n h’(n) Start n Goal g(n) h(n) f’(n) = g(n) + h’(n) 12
TÌM KiẾM TỐT NHẤT ĐẦU TIÊN (3) THUẬT TOÁN A* • Algo A* 1. OPEN = [Start]; g(Start) = 0; f’(Start) = g(Start) + h’(Start); CLOSED = {}; 1. Lặp lại đến tận khi tìm thấy một TT đích: ▪ Nếu Empty(Open) thông báo FAIL ▪ Nếu không, lấy ra BestNode từ OPEN có giá trị f’ thấp nhất, Nếu BestNode là một TT đích, thông báo kết quả và thoát, nếu không, thêm BestNode vào CLOSED, sinh ra các successors của BestNode. Với mỗi successor, thực hiện các công việc sau: a) g(successor) = g(BestNode) + cost(BestNode, successor) b) Nếu successor=Old & member(Old, OPEN) Nếu g(successor) < g(Old), Parent(Old) = BestNode, g(Old)=g(successor) c) Nếu successor=Old & member(Old, CLOSED) Nếu g(successor) < g(Old), Parent(Old)=BestNode, g(Old)=g(successor), lan truyền sự thay đổi này của Old đến các « con cháu » của nó d) Nếu successor không trùng với nút nào trong OPEN cũng như CLOSED, Parent(successor)=BestNode, Insert(successor, OPEN) 13
TÌM KiẾM TỐT NHẤT ĐẦU TIÊN (4) THUẬT TOÁN A* g(successor)=g(BestNode) + cost(BestNode, successor) g(successor) < g(Old) BestNode OldParent BestNode OldParent Parent(Old) Parent(Old) Successor = Old  OPEN Successor= Old  CLOSED g(Old)=g(successor) g(Succ_Of_Old_1)=g(Old)+cost(Old, Succ_Of_Old_1) … Succ_Of_Old_1 … Succ_Of_Old_k 14
TÌM KiẾM TỐT NHẤT ĐẦU TIÊN (5) THUẬT TOÁN A* h’=12 A 3 6 f’=1 f’=12 f’=18 2 B h’=9 1 D h’=12 f’=1 f’=11 1 h’=10 2 2 C 3 5 8 7 5 E F G h’=6 7 H h’=9 h’=7 1 f’=1 f’=12 f’=14 f’=1 f’=12 h’=9 6 4 9 6 4 9 9 4 I K h’=0 f’=12 h’=5 3 J 2 f’=15 h’=2 15
TÍNH CHẤT CỦA THUẬT TOÁN A* • E là một không gian trạng thái, @1 và @2 là hai thuật toán A* có thể áp dụng vào E. h’1 và h’2 là hai heuristic tương ứng. Ta nói rằng thuật toán @2 được thông tin tốt hơn @1 nếu n, không là trạng thái đích: h’1(n) < h’2(n) • Nếu thuật toán A* @2 được thông tin tốt hơn thuật toán A* @1 thì mỗi trạng thái được triển khai bởi @2 khi áp dụng nó vào E cũng được triển khải bởi @1 khi áp dụng nó vào E. Tập hợp các trạng thái của đồ thị tìm kiếm kết thúc nhận được bởi @2 chứa trong tập hợp các trạng thái của đồ thị tìm kiếm kết thúc nhận được bởi @1 16
SUY GIẢM VẤN ĐỀ (1) Có một xe hơi ăn trộm một xe hơi Kiếm đủ tiền Mua một xe hơi Làm việc Để dành tiền Cướp nhà băng 17
SUY GIẢM VẤN ĐỀ (2) ∫ (x2 + 3x + sin2x cos2x ) dx ∫ x2 dx ∫ 3x dx ∫ sin2x cos2x dx x3 / 3 3 ∫ x dx ∫ (sinx cosx)2 dx ∫ (1-cos2x) cos2x dx 3x2 / 2 ∫ cos2x dx ∫ cos4x dx ∫ (1+cos2x)/2 dx ∫ 1/2 dx ∫ cos2x /2 dx 18
SUY GiẢM VẤN ĐỀ (3) ĐỒ THỊ AND-OR • AO-Graph = < V, E > – V = tập các đỉnh – E = A  O; A  O =  • A = tập các cung AND, mỗi cung AND có nhiều hơn một successor (được biểu diễn bởi « liên kết » các đường nối từ nút xuất đến các successors của nó bởi một « cung tròn »), ý nghĩa là: nút xuất của một cung AND là « giải được » nếu và chỉ nếu tất cả các successors của nó là « giải được » • O = tập các cung OR, mỗi cung OR chỉ có đúng một successor, ý nghĩa là: nút xuất của một cung OR là « giải được » nếu successor của nó là « giải được » – Nút xuất phát trong tìm kiếm đồ thị AND-OR là « giải được » nếu tồn tại một đường đi trong đồ thị, tất cả các nút đầu mút cuối của đường đi đó là các nút « giải được » 19
SUY GIẢM VẤN ĐỀ (4) THUẬT TOÁN SUY GIẢM VẤN ĐỀ • Algo problem reduction 1. Khởi động với đồ thị chỉ gồm nút khởi đầu 2. Lặp lại đến tận khi nút khởi đầu được gán nhãn « giải được » hoặc « giá » của nó vượt quá một giá trị « ngưỡng » FUTILITY a) Duyệt đồ thị, bắt đầu từ nút khởi đầu, đi theo đường đi tốt nhất hiện thời, gom lại các nút trên đường đi chưa được triển khai hoặc được gán nhãn « giải được » b) Lấy ra một nút chưa được triển khai, triển khai nó. – Nếu nó không có successor gán cho nó giá trị FUTILITY – Khác đi, thêm các successors của nó vào đồ thị. Với mỗi successor, tính giá trị f’. nếu f’ của một nút có giá trị 0, gán nhãn « giải được » cho nútđó – Cập nhật ước lượng f’ của nút được triển khai. Lan truyền ngược sự thay đổi này về các « tổ tiên » của nút: » Nếu một nút, tất cả các successors của một cung xuất ra từ nó là các nút « giải được », gán nhãn « giải được » cho nút. » Tại mỗi nút được « viếng thăm » trên đường lan truyền ngược, chọn cung « hứa hẹn » nhất và đánh dấu nó (như bộ phận của đường đi tốt nhất hiện thời), điều này có thể làm thay đổi đường đi tốt nhất hiện hành 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.