Bài giảng Trí tuệ nhân tạo - Các nguyên lý Heuristics

Nội dung text: Bài giảng Trí tuệ nhân tạo - Các nguyên lý Heuristics

1. TRÍ TU NHÂN TO Các nguyên lý Heuristics
2. Ni dung trình bày 2
   Bài tốn tha mãn ràng buc (Constraint Satisfaction Problems)
   Bài tốn ti ưu
   Tìm kim ca b
   Thut gii leo đi
   Luyn thép
   Thut gii di truyn
3. Bài tốn tha mãn ràng buc 3
   Cho tp các bin V 1, V 2, , V n. Mi bin V i cĩ th nhn các giá tr t min D i
   Mt cu hình là mt phép gán giá tr cho các bin (V 1=d 1, V 2=d 2, , V n=d n), d i thuc D i
   Cho tp các ràng buc C 1, C 2, , C m. Ràng buc là mt yêu cu trên cu hình
   Cu hình hp l là cu hình tha mãn các ràng buc
4. ð th ràng buc 4 Vi Ci
5. Ví d Bài tốn n – Hu 5
6. Ví d Bài tốn tơ màu 6
7. Bài tốn ti ưu hĩa 7
   Mi cu hình hp l cĩ hàm đánh giá Eval(X)
   Tìm cu hình hp l ti ưu (Eval(X) nh nht hoc ln nht)
   Ta ch quan tâm đn vic đt đưc mt cu hình ti ưu mà khơng cn quan tâm đn đưng đi
8. Ví d v bài tốn ti ưu hố 8 Thit k Mch đin Cĩ rt nhiu chip c đnh Cùng s kt ni nhưng tn ít khơng gian hơn
9. Ví d v bài tốn ti ưu hố (tt) 9
10. Tìm kim cc b 10
    Tìm kim cu hình hp l tt. Khơng tìm kim đưng đi.
    T cu hình “hin ti” xem xét các cu hình “lân cn”.
    Khơng đm bo tìm đưc cu hình ti ưu.
    Rt hiu qu.
11. Các vn đ ca tìm kim ca b 11 Mc kt mt cc tr đa phương Khơng th di chuyn ra khi các vùng phng
12. Thut gii leo đi (Thut gii tham ăn) 12 Leo đi: C gng ti đa hố Eval(X) bng cách di chuyn đn cu hình cao nht trong tp di chuyn ca mình – Leo đi dc đng ðt S := trng thái ban đu Lp Tìm trng thái con S’ ca S vi Eval(S’) cao nht Nu Eval(S’) khơng cao hơn Eval(S) thì return S Ngưc li S = S’
13. Ví d 13 a GOAL 2 2 h=0 h=8 c b 2 5 h=5 h=4 h=11 1 8 2 e 3 d f h=8 9 1 9 h=4 START h 1 4 h=6 5 h=12 4 3 p 15 r q h=11 h=6 h=9
14. Các bin th ca leo đi 14
    Leo đi ngu nhiên ðt S := trng thái ban đu Lp sau mt MAX ln c gng nào đĩ Ly mt trng thái con ngu nhiên S’ ca S Nu Eval(S’) cao hơn Eval(S) thì S= S’ Cui lp Return S Sau khi chy vài ln cĩ th đưa đn trng thái đích
15. Các bin th ca leo đi (tt) 15
    Leo đi vi khi to ngu nhiên nhiu ln
    Local beam search:
    Theo dõi k trng thái cùng mt lúc
    Khi to vi k trng thái phát sinh ngu nhiên
    Ti mi ln lp, tt c trng thái con ca k trng thái đưc phát sinh
    Nu xut hin trng thái đích thì dng li; ngưc li chn k trng thái con tt nht t tồn b danh sách và lp li
16. Luyn Thép 16 1. ðt X := cu hình ban đu 2. ðt E := Eval(X) 3. ðt i = di chuyn ngu nhiên t moveset 4. ðt E i := Eval(move(X,i)) 5. Nu E < E i thì X := move(X,i) E := E i Ngưc li vi xác sut nào đĩ, chp nhn di chuyn ngay c khi mi chuyn xu hơn: X := move(X,i) E := E i 6. Quay li 3 đn khi kt thúc.
17. Luyn Thép (tt) 17 1. ðt X := cu hình ban đu Chúng ta s chn xác 2. ðt E := Eval(X) sut chp nhn mt di 3. ðt i = di chuyn ngu nhiên t chuyn ti hơn như th moveset nào? 4. ðt E i := Eval(move(X,i)) • Xác sut = 0.1 5. Nu E < E i thì X := move(X,i) • Xác sut gim theo thi gian E := E i Ngưc li vi xác sut nào đĩ, • Xác sut chp nhn di chuyn ngay c khi exp ((E Ei)/ Ti): T i là mi chuyn xu hơn: tham s nghit đ X := move(X,i) E := E i Tương t như quá 6. Quay li 3 đn khi kt thúc. trình làm lnh trong luyn thép vt lý
18. Thut gii di truyn 18
    ðưc gii thiu bi John Holland năm 1975, cho phép thc hin tìm kim ngu nhiên
    Mã hố các li gii tìm năng ca bài tốn bng các nhim sc th
    ðánh giá đ tt ca các li gii qua đ thích nghi ca các nhim sc th
    Lưu tr mt qun th các li gii tim năng
    Thc hin các phép tốn di truyn đ phát sinh các cá th mi đng thi áp dng chn lc t nhiên trên các li gii
19. Thut gii di truyn (tt) 19 Phát sinh Xác đnh đ Tho điu qun th ban thích nghi ca kin kt Kt thúc đu qun th thúc? Bt đu Chn lc Lai ghép Xây dng qun th mi ðt bin Xây dng qun th k tip
20. Mt s cách biu din gen 20
    ð cĩ th gii bài tốn bng thut gii di truyn ta phi gen hĩa cu trúc d liu ca bài tốn. Cĩ hai cách biu din gen: 1. Biu din gen bng chui s nguyên (hay thc) o VD: Bài tốn 8 hu > 12534867 2. Biu din gen bng chui nh phân o VD: Bài tốn 8 hu: dùng 8 x log 28 bit đ biu din o Làm sao biu din nghim thc bng chui nh phân ??? o Tr li: Ri rc hố min tr vi mt đ chính xác cho trưc
21. Các khái nim cơ bn 21
    ð tt ca mt cá th
    Là giá tr ca cá th cho mt vn đ bài tốn c th. Ví d: Trong bài tốn ti ưu cc đi mt hàm f, nu chn mt cá th là mt nghim ca bài tốn thì mt cá th càng tt khi làm cho giá tr hàm càng ln.
    ð xác đnh đưc đ tt ca các cá th ta cn mt hàm đ làm vic này. Hàm này gi là Hàm mc tiêu .
22. Các khái nim cơ bn (tt) 22
    Hàm mc tiêu
    Dùng đ đánh giá đ tt ca mt li gii hoc cá th.
    Hàm mc tiêu nhn vào tham s là gen ca mt cá th và tr ra mt s thc.
    Tùy theo giá tr ca s thc này mà ta bit đưc đ tt ca cá th đĩ .
23. Các khái nim cơ bn (tt) 23
    ð thích nghi ca các cá th (fitness)
    Là kh năng cá th đĩ đưc chn lc vào th h sau hoc là đưc chn lc cho vic lai ghép đ to ra cá th con .
    Vì đ thích nghi là mt xác sut đ cá th đưc chn nên ngưi ta thưng ánh x đ thích nghi vào đon [0,1 ] (đ thích nghi chun) F ( a ) = i i = 1,2 N F ( ai ) N F ( a ) ∑j =1 j
24. Các tốn t cơ bn 24
    Tốn t lai ghép:
    Các cá th đưc chn đ lai ghép da vào da vào đ thích nghi
    Dùng qui tc bàn quay rollete:  Vd: các ta cĩ qun th vi đ thích nghi chun sau STT Cá th ðTN chun 1 0010001 0,4 2 0010101 0,3 3 0101000 0.05 4 1100011 0.25
25. Các tốn t cơ bn (tt) 25
    Tốn t lai ghép:
    Ly giá tr ngu nhiên p ∈ [0,1] đ chn cá th lai ghép, cá th cĩ đ thích nghi cao cĩ xác xut la chn nhiu hơn
    Sau khi la chn mt cp cá th cha m, hốn v các nhim sc th ti v trí ngu nhiên vi xác sut pc
    Tốn t lai ghép cĩ xu hưng kéo qun th v phía các cá th cĩ đ thích nghi cao => cc b đa phương
26. Các tốn t cơ bn (tt) 26
    Tốn t đt bin:
    Giúp li gii cĩ th nhy ra khi các cc tr đa phương
    Vi mi cá th trong qun th, thc hin đt bin vi xác sut pm ti mt v trí ngu nhiên (thơng thưng pm << 0.1) 001 0001 001 1001
27. Ví d: Gii phương trình bc hai 27 • Xác đnh kích thưc qun th: n= 4 • Chn phương pháp mã hĩa nghim:  Xác đnh nghim nguyên trong min tr: [0, 31]  Mã hố theo chui nh phân: s bit mã hố =5 • La chn hàm thích nghi  Hàm thích nghi = 1000 – (X2 – 64), chn nghim cĩ h s thích nghi ~ 1000
28. Ví d: Gii phương trình bc hai (tt) 28 • Xác đnh kích thưc qun th: n= 4 • Chn phương pháp mã hĩa nghim:  Xác đnh nghim nguyên trong min tr: [0, 64]  Mã hố theo chui nh phân: s bit mã hố =5 • La chn hàm thích nghi  Hàm thích nghi = 1000 – (X2 – 64), chn nghim cĩ h s thích nghi ~ 1000
29. Ví d: Gii phương trình bc hai (tt) 29 • Phát sinh tp qun th ban đu STT Nh phân Nghim 1 00100 4 2 10101 21 3 01010 10 4 11000 24
30. Ví d: Gii phương trình bc hai (tt) 30 • Tính h s thích nghi (Fitness) cho qun th STT Nh phân Nghim X2 – 64 H s thích nghi 1 00100 4 48 1048 2 10101 21 377 623 3 01010 10 36 964 4 11000 24 512 488
31. Ví d: Gii phương trình bc hai (tt) 31 • Chn lc nghim và lai ghép Chn nghim 4 và 10 đ tin hành lai ghép vi xác sut pc và v trí pos= 2 44 00100 00 01000 00 88 01 01 01001 01 00101 01 66
32. Ví d: Gii phương trình bc hai (tt) 32 • ðt bin mt cá th Vi mt xác sut p m đt bin li gii th 4 vi v trí pos= 4 00010011 01 66 00111110 41 41
33. Ví d: Gii phương trình bc hai (tt) 33 • Tính li h s thích nghi cho nghim mi và tin hành chn lc STT Nh Nghim X2 – 64 H s thích phân nghi 1 00100 4 48 1048 2 01010 10 36 964 3 01000 8 0 1000 4 01110 14 132 868
34. ðiu cn nm 34
    Hiu bài tốn tha mãn ràng buc, bài tốn ti ưu
    Hiu đưc các thut gii tìm kim cc b
    Hiu đưc thut gii leo đi, leo đi ngu nhiên
    Nm đưc các vn đ ca leo đi
    Hiu đưc các ý tưng đng sau Luyn thép
    Hiu và nm đưc các bưc thc hin ca GA
35. Thc mc 35