Nhập môn Trí tuệ nhân tạo-Bài 3
Chia sẻ bởi Trương Nhân |
Ngày 19/03/2024 |
15
Chia sẻ tài liệu: Nhập môn Trí tuệ nhân tạo-Bài 3 thuộc Công nghệ thông tin
Nội dung tài liệu:
NHẬP MÔN TRÍ TUỆ NHÂN TẠO
@copyrights by Dr Nguyễn Xuân Hoài
Nội Dung
Tìm kiếm có sử dụng thông tin thu nhận trong quá trình tìm kiếm (informed search):
Best-first search
Greedy best-first search
A* search
Heuristics
Local search algorithms.
Hill-climbing search.
Simulated annealing search
Local beam search.
Genetic algorithms.
Ant Colony Optimization.
Mấu chốt của chiến lược tìm kiếm
Chiến lược chọn node để xử lý tiếp theo (Expand).
Best-first search (BFS)
Ý tưởng : Dùng một hàm định giá f(n) for each node
Hàm này phản ánh độ “tốt” của node
Chọn node có độ tốt tối ưu nhất để xử lý tiếp.
Cài đặt:
Dùng hàng đợi ưu tiên. Sắp xếp các node trong hàng theo thứ tự dảm dần của f(n).
Thể hiện cụ thể:
greedy best-first search
A* search.
Tìm đường đi với giá tính theo km
Greedy best-first search
Đặt hàm lượng giá bằng f(n) = h(n) (heuristic) = ước lượng giá đến trạng thái đích.
VD: hSLD(n) = Khoảng cách theo đường chim bay từ n to thành phố đích.
GBFS chọn node “được cho là” gần với node đích để expand.
Ví dụ về GBFS
Ví dụ về GBFS
Ví dụ về GBFS
Ví dụ về GBFS
Đánh giá GBFS
Đủ? Không – Có thể vào vòng lặp quẩn.
Độ phức tạp thời gian? O(bm), Nếu hàm heuristic xấp xỉ tốt trong thực tế thì thời gian chạy sẽ giảm đi rất nhiều
Độ phức tạp không gian? O(bm) – Lưu trữ tất cả các Nodes.
Tối ưu? Không.
A* search
Ý tưởng: Loại bỏ những đường đi có chi phí cao.
Hàm lượng giá f(n) = g(n) + h(n)
g(n) = Chi phí để đến n
h(n) = lướợng giá từ n đến đích
f(n) = ước lượng tổng giá đến đích qua n.
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Heuristics chấp nhận được
heuristic h(n) là chấp nhận được nếu với mọi node n, h(n) ≤ h*(n), trong đó h*(n) là chi phí thực để đi đến đích từ n.
Heuristic chấp nhận được không bao giờ đánh giá chi phí cao quá thực tế.
Ví dụ hSLD(n) là Heuristic chấp nhận được.
Định lý: Nếu h(n) là chấp nhận được, A* là thuật toán cho lời giải tối ưu.
Chứng minh tính tối ưu của A*
Giả sử có đích G2 được tìm ra và lời giải là không tối ưu. giải sử n là node chưa được expand trong fringe sao cho n Nằm trên đường đi tới lời giải tối ưu có đích là G.
f(G2) = g(G2) vì h(G2) = 0
g(G2) > g(G) vì G2 là không tối ưu
f(G) = g(G) vì h(G) = 0
f(G2) > f(G) từ trên
Chứng minh tính tối ưu của A*
f(G2) > f(G) từ trên
h(n) ≤ h^*(n) vì h là chấp nhận được
g(n) + h(n) ≤ g(n) + h*(n)
f(n) ≤ f(G)
Vậy f(G2) > f(n), dẫn tới vô lý A* không thể lựa chọn G2 để expand.
Tính nhất quán của Heuristics
Tín tối ưu của A*
A* xét node theo thứ tự tăng dần của f
Tạo nên "f-contours" của các node
Contour i có tất cả các node với f=fi, trong đó fi < fi+1
Phân tích A*
Đủ? Có (Trừ phi có vô hạn node với f ≤ f(G) ).
Độ phức tạp thời gian? Hàm mũ
Không gian? Lưu trữ tất cả các node
Tối ưu? có
Ví dụ về heuristics chấp nhận được
E.g., 8-puzzle:
h1(n) = Số lượng ô sai vị trí
h2(n) = Tổng khoảng cách theo Mahattan Metric
(i.e., Số lượng ô từ ô hiện tại đến vị trí mong muốn)
h1(S) = ?
h2(S) = ?
Ví dụ về heuristics chấp nhận được
E.g., 8-puzzle:
h1(n) = Số lượng ô sai vị trí
h2(n) = Tổng khoảng cách theo Mahattan Metric
(i.e., Số lượng ô từ ô hiện tại đến vị trí mong muốn)
h1(S) = ? 8
h2(S) = ? 3+1+2+2+2+3+3+2 = 18
So Sánh các Heuristics
Nếu h2(n) ≥ h1(n) với mọi n (cả hai đều chấp nhận được)
thì h2 được coi là mạnh hơn h1
h2 là heuristic tốt hơn
Ví dụ tìm kiếm trên 8-puzzle (số lượng node trung bình phải xét):
d=12 IDS = 3,644,035 nodes
A*(h1) = 227 nodes
A*(h2) = 73 nodes
d=24 IDS = too many nodes
A*(h1) = 39,135 nodes
A*(h2) = 1,641 nodes
Nới lỏng ràng buộc của bài toán
Bài toán có thể nới lỏng bằng cách bớt các ràng buộc trên toán tử
Chi phí cho lời giải tối ưu của bài toán nới lỏng là một Heuristic chập nhận được đối với bài toán gốc.
Ví dụ nếu bài toán 8-puzzle được nới lỏng sao cho có thể dịch chuyển mỗi ô đến nơi tuỳ ý, ta có h1(n) cho lời giải tối ưu.
Nếu bài toán được nới lỏng sao cho mỗi ô có thể dịch chuyển đến ô bất kỳ liền kề thì ta có h2(n) cho lời giải tối ưu.
Tìm kiếm địa phương
Trong nhiều bài toán tối ưu lời giải là trạng thái, thay vì là đường đi.
Không gian trạng thái = Tập các cấu hình đủ.
Tìm cấu hình thoả ràng buộc cho trước, ví dụ, bài toán n-queen, bài toán người du lịch (biểu diễn không gian trạng thái).
Trong trường hợp đó có thể dùng tìm kiếm địa phương.
Tư tưởng: Giữ trạng thái hiện tại và tìm cách làm tốt nó bằng cách tìm trong những trạng thái lân cận của nó.
Ví dụ: n-queens
Tìm kiếm leo đồi
Tìm kiếm leo đồi
Yếu điểm: phụ thuộc vào trạng thái khởi đầu, có thể bị tắc tại cực trị địa phương. (Vấn đề ridge, valley).
Ví dụ bài toán 8-queens
h = số lượng con hậu tấn công lẫn nhau (trực tiếp và gián tiếp)
h = 17 trong hình trên
Ví dụ bài toán 8-queens
Một cực trị địa phương với h = 1.
Bài toán người du lịch
biểu diễn: dãy hoán vị.
h=tổng giá chi phi đường di trên dẫy hoán vị.
Toán tử: đổi chỗ hai đỉnh.
Tìm kiếm địa phương trong tối ưu không ràng buộc
pk - hướng tìm kiếm
hoặc là
Thuật toán giảm gradient
Chọn bước tiếp theo sao cho:
với thay đổi nhỏ của x ta có thể xấp xỉ hàm F(x):
trong đó
Muốn hàm giảm thì:
Giảm nhiều nhất:
Ví dụ
Hình minh hoạ
Simulated annealing (SA) search
Ý tưởng: cho phép những “dịch chuyển tồi” nhưng với xác suất xảy ra nhỏ dần.
Đánh giá SA
Kết quả lý thuyết nếu T giảm đủ chậm thì SA sẽ tìm được cực trị toàn cục với xác suất tiến đến 1.
Ứng dụng trong các bài toán tối ưu tổ hợp, thiết kế VLSI, lập lịch,...
Tìm kiếm địa phương theo chùm
Tìm kiếm địa phương cho k trạng thái thay vì 1.
Bắt đầu với k trạng thái được sinh ngẫu nhiên.
Tại mỗi bước lặp sinh ra n trạng thái mới
Nếu đã thấy đích thì dừngnếu không chọn k trạng thái sinh sinh tốt nhất để thay thế cho k trạng thái cũ
Thuật Toán Gene
Được đưa ra bởi John Holland (1975).
Dựa vào lựa chọn tự nhiên.
Thường sử dụng biểu diễn nhị phân và cấu trúc chromosome cố định.
Lựa chọn dựa vào fitness.
Toán tử gene: Crossover and Mutation (Crossover là chủ yếu).
Crossover
Mutation
0 1 0 1 |1011| 1 1 0
0 1 0 1 |1101| 1 1 0
Inversion
GA= Population + Genetic Search
Tại Sao GAs Tốt?
Building blocks hypothesis and schema theorem (Holland, 1975).
*0010**0*001110****0
00010110100111010010
“GAs operator set a bias towards short, low order and highly fit building blocks”.
Ví dụ cho biểu diễn phi nhị phân
Fitness function: số lượng con hậu không ăn nhau (min = 0, max = 8 × 7/2 = 28)
24/(24+23+20+11) = 31%
23/(24+23+20+11) = 29% etc
Minh Hoạ
Bài toán người du lịch
Biểu diễn các hoán vị
12435
43521
13535
42421
13542
32451
43521
41523
Ant Colony Optimisation
Ant Colony Optimisation
Ant Colony Optimisation
Ant Colony Optimisation
Đọc Thêm
Giáo trình: chapter 3, 4.
OCW (ch2_search1, ch2_search2, ch2_search3).
An Introduction to Genetic Algorithms, M. Mitchell.
Algorithms and Theory of Computation, (chapter 36, 37).
Simulated Annealing and Boltzman Machines, E. Aarts and J. Korst.
New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glove, (Chapter 2).
Local Search in Combinatorial Optimization, E. Aarts and J. Lenstra.
Câu hỏi ôn tập
Cho biết ý nghĩa của việc dùng Heuristics?
Cài đặt các thuật toán GBFS, A*, SA, GAs, LBS, ACO.
Ứng dụng vào giải các bài toán cụ thể.
Nghiên cứu: A*, SA, GAs, ACO.
@copyrights by Dr Nguyễn Xuân Hoài
Nội Dung
Tìm kiếm có sử dụng thông tin thu nhận trong quá trình tìm kiếm (informed search):
Best-first search
Greedy best-first search
A* search
Heuristics
Local search algorithms.
Hill-climbing search.
Simulated annealing search
Local beam search.
Genetic algorithms.
Ant Colony Optimization.
Mấu chốt của chiến lược tìm kiếm
Chiến lược chọn node để xử lý tiếp theo (Expand).
Best-first search (BFS)
Ý tưởng : Dùng một hàm định giá f(n) for each node
Hàm này phản ánh độ “tốt” của node
Chọn node có độ tốt tối ưu nhất để xử lý tiếp.
Cài đặt:
Dùng hàng đợi ưu tiên. Sắp xếp các node trong hàng theo thứ tự dảm dần của f(n).
Thể hiện cụ thể:
greedy best-first search
A* search.
Tìm đường đi với giá tính theo km
Greedy best-first search
Đặt hàm lượng giá bằng f(n) = h(n) (heuristic) = ước lượng giá đến trạng thái đích.
VD: hSLD(n) = Khoảng cách theo đường chim bay từ n to thành phố đích.
GBFS chọn node “được cho là” gần với node đích để expand.
Ví dụ về GBFS
Ví dụ về GBFS
Ví dụ về GBFS
Ví dụ về GBFS
Đánh giá GBFS
Đủ? Không – Có thể vào vòng lặp quẩn.
Độ phức tạp thời gian? O(bm), Nếu hàm heuristic xấp xỉ tốt trong thực tế thì thời gian chạy sẽ giảm đi rất nhiều
Độ phức tạp không gian? O(bm) – Lưu trữ tất cả các Nodes.
Tối ưu? Không.
A* search
Ý tưởng: Loại bỏ những đường đi có chi phí cao.
Hàm lượng giá f(n) = g(n) + h(n)
g(n) = Chi phí để đến n
h(n) = lướợng giá từ n đến đích
f(n) = ước lượng tổng giá đến đích qua n.
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Ví dụ về A* search
Heuristics chấp nhận được
heuristic h(n) là chấp nhận được nếu với mọi node n, h(n) ≤ h*(n), trong đó h*(n) là chi phí thực để đi đến đích từ n.
Heuristic chấp nhận được không bao giờ đánh giá chi phí cao quá thực tế.
Ví dụ hSLD(n) là Heuristic chấp nhận được.
Định lý: Nếu h(n) là chấp nhận được, A* là thuật toán cho lời giải tối ưu.
Chứng minh tính tối ưu của A*
Giả sử có đích G2 được tìm ra và lời giải là không tối ưu. giải sử n là node chưa được expand trong fringe sao cho n Nằm trên đường đi tới lời giải tối ưu có đích là G.
f(G2) = g(G2) vì h(G2) = 0
g(G2) > g(G) vì G2 là không tối ưu
f(G) = g(G) vì h(G) = 0
f(G2) > f(G) từ trên
Chứng minh tính tối ưu của A*
f(G2) > f(G) từ trên
h(n) ≤ h^*(n) vì h là chấp nhận được
g(n) + h(n) ≤ g(n) + h*(n)
f(n) ≤ f(G)
Vậy f(G2) > f(n), dẫn tới vô lý A* không thể lựa chọn G2 để expand.
Tính nhất quán của Heuristics
Tín tối ưu của A*
A* xét node theo thứ tự tăng dần của f
Tạo nên "f-contours" của các node
Contour i có tất cả các node với f=fi, trong đó fi < fi+1
Phân tích A*
Đủ? Có (Trừ phi có vô hạn node với f ≤ f(G) ).
Độ phức tạp thời gian? Hàm mũ
Không gian? Lưu trữ tất cả các node
Tối ưu? có
Ví dụ về heuristics chấp nhận được
E.g., 8-puzzle:
h1(n) = Số lượng ô sai vị trí
h2(n) = Tổng khoảng cách theo Mahattan Metric
(i.e., Số lượng ô từ ô hiện tại đến vị trí mong muốn)
h1(S) = ?
h2(S) = ?
Ví dụ về heuristics chấp nhận được
E.g., 8-puzzle:
h1(n) = Số lượng ô sai vị trí
h2(n) = Tổng khoảng cách theo Mahattan Metric
(i.e., Số lượng ô từ ô hiện tại đến vị trí mong muốn)
h1(S) = ? 8
h2(S) = ? 3+1+2+2+2+3+3+2 = 18
So Sánh các Heuristics
Nếu h2(n) ≥ h1(n) với mọi n (cả hai đều chấp nhận được)
thì h2 được coi là mạnh hơn h1
h2 là heuristic tốt hơn
Ví dụ tìm kiếm trên 8-puzzle (số lượng node trung bình phải xét):
d=12 IDS = 3,644,035 nodes
A*(h1) = 227 nodes
A*(h2) = 73 nodes
d=24 IDS = too many nodes
A*(h1) = 39,135 nodes
A*(h2) = 1,641 nodes
Nới lỏng ràng buộc của bài toán
Bài toán có thể nới lỏng bằng cách bớt các ràng buộc trên toán tử
Chi phí cho lời giải tối ưu của bài toán nới lỏng là một Heuristic chập nhận được đối với bài toán gốc.
Ví dụ nếu bài toán 8-puzzle được nới lỏng sao cho có thể dịch chuyển mỗi ô đến nơi tuỳ ý, ta có h1(n) cho lời giải tối ưu.
Nếu bài toán được nới lỏng sao cho mỗi ô có thể dịch chuyển đến ô bất kỳ liền kề thì ta có h2(n) cho lời giải tối ưu.
Tìm kiếm địa phương
Trong nhiều bài toán tối ưu lời giải là trạng thái, thay vì là đường đi.
Không gian trạng thái = Tập các cấu hình đủ.
Tìm cấu hình thoả ràng buộc cho trước, ví dụ, bài toán n-queen, bài toán người du lịch (biểu diễn không gian trạng thái).
Trong trường hợp đó có thể dùng tìm kiếm địa phương.
Tư tưởng: Giữ trạng thái hiện tại và tìm cách làm tốt nó bằng cách tìm trong những trạng thái lân cận của nó.
Ví dụ: n-queens
Tìm kiếm leo đồi
Tìm kiếm leo đồi
Yếu điểm: phụ thuộc vào trạng thái khởi đầu, có thể bị tắc tại cực trị địa phương. (Vấn đề ridge, valley).
Ví dụ bài toán 8-queens
h = số lượng con hậu tấn công lẫn nhau (trực tiếp và gián tiếp)
h = 17 trong hình trên
Ví dụ bài toán 8-queens
Một cực trị địa phương với h = 1.
Bài toán người du lịch
biểu diễn: dãy hoán vị.
h=tổng giá chi phi đường di trên dẫy hoán vị.
Toán tử: đổi chỗ hai đỉnh.
Tìm kiếm địa phương trong tối ưu không ràng buộc
pk - hướng tìm kiếm
hoặc là
Thuật toán giảm gradient
Chọn bước tiếp theo sao cho:
với thay đổi nhỏ của x ta có thể xấp xỉ hàm F(x):
trong đó
Muốn hàm giảm thì:
Giảm nhiều nhất:
Ví dụ
Hình minh hoạ
Simulated annealing (SA) search
Ý tưởng: cho phép những “dịch chuyển tồi” nhưng với xác suất xảy ra nhỏ dần.
Đánh giá SA
Kết quả lý thuyết nếu T giảm đủ chậm thì SA sẽ tìm được cực trị toàn cục với xác suất tiến đến 1.
Ứng dụng trong các bài toán tối ưu tổ hợp, thiết kế VLSI, lập lịch,...
Tìm kiếm địa phương theo chùm
Tìm kiếm địa phương cho k trạng thái thay vì 1.
Bắt đầu với k trạng thái được sinh ngẫu nhiên.
Tại mỗi bước lặp sinh ra n trạng thái mới
Nếu đã thấy đích thì dừngnếu không chọn k trạng thái sinh sinh tốt nhất để thay thế cho k trạng thái cũ
Thuật Toán Gene
Được đưa ra bởi John Holland (1975).
Dựa vào lựa chọn tự nhiên.
Thường sử dụng biểu diễn nhị phân và cấu trúc chromosome cố định.
Lựa chọn dựa vào fitness.
Toán tử gene: Crossover and Mutation (Crossover là chủ yếu).
Crossover
Mutation
0 1 0 1 |1011| 1 1 0
0 1 0 1 |1101| 1 1 0
Inversion
GA= Population + Genetic Search
Tại Sao GAs Tốt?
Building blocks hypothesis and schema theorem (Holland, 1975).
*0010**0*001110****0
00010110100111010010
“GAs operator set a bias towards short, low order and highly fit building blocks”.
Ví dụ cho biểu diễn phi nhị phân
Fitness function: số lượng con hậu không ăn nhau (min = 0, max = 8 × 7/2 = 28)
24/(24+23+20+11) = 31%
23/(24+23+20+11) = 29% etc
Minh Hoạ
Bài toán người du lịch
Biểu diễn các hoán vị
12435
43521
13535
42421
13542
32451
43521
41523
Ant Colony Optimisation
Ant Colony Optimisation
Ant Colony Optimisation
Ant Colony Optimisation
Đọc Thêm
Giáo trình: chapter 3, 4.
OCW (ch2_search1, ch2_search2, ch2_search3).
An Introduction to Genetic Algorithms, M. Mitchell.
Algorithms and Theory of Computation, (chapter 36, 37).
Simulated Annealing and Boltzman Machines, E. Aarts and J. Korst.
New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glove, (Chapter 2).
Local Search in Combinatorial Optimization, E. Aarts and J. Lenstra.
Câu hỏi ôn tập
Cho biết ý nghĩa của việc dùng Heuristics?
Cài đặt các thuật toán GBFS, A*, SA, GAs, LBS, ACO.
Ứng dụng vào giải các bài toán cụ thể.
Nghiên cứu: A*, SA, GAs, ACO.
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Trương Nhân
Dung lượng: |
Lượt tài: 1
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)