Nội dung

ÑAÏI HOÏC QUOÁC GIA TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA THAØNH PHOÁ KHOA ÑIEÄN VAØ ÑIEÄN TÖÛ BOÄ MOÂN ÑIEÀU KHIEÅN TÖÏ ÑOÄNG BAØI GIAÛNG MOÂN HOÏC : Trí Tueä Nhaân Taïo Vaø Heä Chuyeân Gia Thaønh phoá Hoà Chí Minh Ngaøy 7 Thaùng 01 Naêm 2006 Bieân soïan : Tieán só Nguyeãn Thieän Thaønh Baøi giaûng moân Trí tueä nhaân taïo vaø heä chuyeân gia Noäi dung baøi giaûng: CHÖÔNG 1 : TOÅNG QUAN VEÀ TRÍ TUEÄ NHAÂN TAÏO ...........................................................5 1.1) Trí tueä nhaân taïo laø gì ? .......................................................................................................................................5 1.2) Lòch söû phaùt trieån trí tueä nhaân taïo : .................................................................................................................5 1.3) Caùc thaønh phaàn cô baûn cuûa trí tueä nhaân taïo : .................................................................................................6 CHÖÔNG 2 : CAÙC PHÖÔNG PHAÙP GIAÛI QUYEÁT VAÁN ÑEÀ CÔ BAÛN ..................................9 2.1) Khoâng Gian Baøi Toùan :..............................................................................................................................................9 Ví duï 1: Khoâng gian baøi toùan bình ñöïng nöôùc. ..............................................................................................................9 Ví duï 2 : Khoâng gian baøi toùan troø chôi 8 soá. ...............................................................................................................11 Ví duï 3 : Khoâng gian baøi toùan ba tu só vaø ba keû aên thòt ngöôøi.....................................................................................12 Ví duï 4 : Baøi toùan rao soá hoïc (Cryarithmetic)..............................................................................................................14 Ví duï 5 : Baøi toùan haønh trình ngöôøi baùn haøng.............................................................................................................14 2.2) Chieán Löôïc Tìm Kieám : ...........................................................................................................................................14 1) Tìm kieám suy dieãn tieán : ...................................................................................................................................14 2) Chieán löôïc tìm kieám suy dieãn luøi :...................................................................................................................15 2.3) Giaûi Thuaät Tìm Kieám : ............................................................................................................................................16 1) Giaûi thuaät tìm kieám theo chieàu roäng ((Breadth_First_Search):...............................................................................17 2) Giaûi thuaät tìm kieám theo chieàu saâu (Depth First Search) :......................................................................................18 3) Giaûi thuaät tìm kieám truyeàn luøi ( Back Tracking search ) :.......................................................................................19 2.4) Tìm Kieám Heuristic : ...............................................................................................................................................20 1) Heuristic laø gì ?....................................................................................................................................................20 2) Giaûi thuaät tìm kieám Best_First_Search :........................................................................................................21 3) Haøm ñaùnh giaù heuristic :...................................................................................................................................23 2.5) Baøi Toùan Raøng Buoäc :..............................................................................................................................................26 CHÖÔNG 3 : HEÄ CHUYEÂN GIA..............................................................................................28 3.1) Heä chuyeân gia laø gì ? ................................................................................................................................................28 3.2) Caáu truùc heä chuyeân gia :..........................................................................................................................................29 3.3) Thieát Keá Heä Chuyeân Gia : ......................................................................................................................................30 1) Heä chuyeân gia suy dieãn tieán : ...........................................................................................................................31 2) Thieát keá heä chuyeân gia suy dieãn luøi : ..............................................................................................................36 http://www.khvt.com Trang 2 Bieân soaïn: Tieán só Nguyeãn Thieän Thaønh CHÖÔNG 4 : CAÙC PHÖÔNG PHAÙP BIEÅU DIEÃN TRI THÖÙC.................................................41 4.1) Bieåu Dieãn Tri Thöùc Laø Gì ? ....................................................................................................................................41 4.2) Bieåu Dieãn Tri Thöùc Nhôø Logic Vò Töø : ..................................................................................................................42 1) Logic ñeà xuaát :....................................................................................................................................................42 2) Logic vò töø : .........................................................................................................................................................44 3) Giaûi baøi toùan baèng phöông phaùp hôïp giaûi : ....................................................................................................47 4.3) Bieåu Dieãn Tri Thöùc Nhôø Maïng Ngöõ Nghóa : .........................................................................................................49 4.4) Bieåu Dieãn Tri Thöùc Nhôø Frame : ...........................................................................................................................51 4.5) Giôùi Thieäu Veà Ngoân Ngöõ Laäp Prolog : ..................................................................................................................56 1) Caáu truùc chöông trình :.....................................................................................................................................56 2) Caùc loïai toùan töû : .................................................................................................................................................58 3) Xöû lyù danh saùch trong ngoân ngöõ laäp trình Prolog : .......................................................................................59 5.1) ÖÙng Duïng trí Tueä Nhaân Taïo Phaân Tích Baûo Veä Heä Thoáng Naêng Löôïng ñieän : ..............................................73 5.2) Baøi Toùan Robot Tìm Vaøng : ....................................................................................................................................78 5.3) Baøi Toùan Laäp Phöông Aùn Cho Caùnh Tay Robot Xeáp Khoái :..............................................................................81 CHÖÔNG 6 : XÖÛ LYÙ TRI THÖÙC KHOÂNG CHAÉC CHAÉN......................................................86 6.1) Lyù Giaûi Döôùi Ñieàu Kieän Khoâng Chaéc Chaén :.......................................................................................................86 6.2) Xöû Lyù Tri Thöùc Khoâng Chaéc Chaén Duøng Lyù Thuyeát Xaùc Suaát : ......................................................................87 1) Lyù thuyeát xaùc suaát : ...........................................................................................................................................87 2) Lyù giaûi chính xaùc döôùi ñieàu kieän khoâng chaéc chaén duøng xaùc suaát : ............................................................88 3) Lyù thuyeát chaéc chaén :........................................................................................................................................90 4) Lyù giaûi xaáp xæ döôùi ñieàu kieän khoâng chaéc chaén duøng lyù thuyeát soá ño chaéc chaén :.....................................92 6.3) Xöû Lyù Tri Thöùc Khoâng Chaéc Chaén Duøng Logic Môø : .........................................................................................93 1) Taäp môø vaø caùc pheùp toùan treân caùc taäp môø : ..................................................................................................94 2) Quan heä môø vaø caùc pheùp toùan treân quan heä môø : .........................................................................................96 3) Logic môø vaø lyù giaûi xaáp xæ môø :..............................................................................................................................98 4) Cô sôû tri thöùc môø : ................................................................................................................................................100 5) Kyõ thuaät suy dieãn môø : .........................................................................................................................................101 CHÖÔNG 7 : VIEÄC HOÏC MAÙY ................................................................................................104 7.1) Vieäc Hoïc Maùy Laø Gì ?............................................................................................................................................104 7.2) Moâ Hình Hoïc Maùy Treân Cô Sôû Tri Thöùc :........................................................................................................105 1) Giaûi thuaät hoïc gaùm saùt höôùng ñaëc tröng ñeán toång quaùt vaø ngöôïc laïi : ....................................................106 2) Giaûi thuaät hoïc quy naïp caây quyeát ñònh : .......................................................................................................109 3) Hoïc heuristic vôùi giaûi thuaät hoïc quy naïp caây quyeát ñònh :..........................................................................111 Hoïc kì 2 naêm hoïc 2005-2006 Trang 3 Baøi giaûng moân Trí tueä nhaân taïo vaø heä chuyeân gia 4) Khaùi nieäm veà hoïc cuûng coá vaø hoïc khoâng giaùm cuûa moâ hình hoïc treân cô sôû tri thöùc : ...........................112 7.3) Moâ hình Hoïc Maùy Nhôø Maïng Neuron Nhaân Taïo :.............................................................................................114 1) Toång quan veà maïng neuron nhaân taïo : ..............................................................................................................114 2) Maïng truyeàn thaúng vaø giaûi thuaät hoïc lan truyeàn ngöôïc :................................................................................117 http://www.khvt.com Trang 4 Bieân soaïn: Tieán só Nguyeãn Thieän Thaønh Chöông 1 : Toång Quan Veà Trí Tueä Nhaân Taïo 1.1) Trí tueä nhaân taïo laø gì ? Trí tueä nhaân taïo laø lónh vöïc khoa hoïc chuyeân nghieân cöùu caùc phöông phaùp cheá taïo trí tueä maùy sao cho gioáng nhö trí tueä con ngöôøi. Vaøi ñònh nghóa cuûa trí tueä nhaân taïo ñieån hình laø - Heä thoáng maø bieát suy nghó nhö con ngöôøi - Heä thoáng maø bieát haønh ñoäng nhö con ngöôøi Ñeå heä thoáng maø bieát suy nghó vaø haønh ñoäng nhö con ngöôøi thì heä thoáng ñoù phaûi ñöôïc trang bò caùc coâng cuï nhö thính giaùc, tri thöùc, lyù giaûi töï ñoäng, vieäc hoïc, thò giaùc vaø di chuyeån gioáng nhö con ngöôøi. Thoâng thöôøng, caùch giaûi quyeát vaán ñeà cuûa con ngöôøi ñöôïc theå hieän qua boán thao taùc cô baûn ñoù laø - Xaùc ñònh taäp hôïp cuûa caùc ñích - Thu thaäp caùc söï kieän vaø luaät suy dieãn - Cô cheá taäp trung - Boä maùy suy dieãn Nhö vaäy, trí tueä maùy laø gì ? laø caùc khaû naêng giaûi quyeát vaán ñeà cuûa maùy ñoù laø - Haønh ñoäng gioáng nhö con ngöôøi. - Suy nghó gioáng nhö con ngöôøi. - Hoïc gioáng nhö con ngöôøi. - Xöû lyù thoâng tin gioáng nhö con ngöôøi. - Haønh ñoäng vaø suy nghó treân cô sôû logic vaø chính xaùc. 1.2) Lòch söû phaùt trieån trí tueä nhaân taïo : YÙ töôûng cheá taïo trí tueä maùy ñaõ coù töø laâu nhöng maõi ñeán naêm 1950, nhaø toùan hoïc ngöôøi Anh coâng boá coâng trình khoa hoïc cuûa oâng ta ñoù laø “Maùy tính vaø Thoâng minh”, ñaây ñöôïc xem nhö laø moác loch söû baét ñaàu phaùt trieån trí tueä nhaân taïo. Noái theo thôøi ñieåm naøy, caùc chöông trình thoâng minh ñöôïc coâng boá ñoù laø + Naêm 1956, chöông trình giaûi baøi toùan toång quaùt ñaõ ñöôïc xuaát hieän. + Naêm 1958, chöông trình chöùng minh ñònh lyù hình hoïc cuõng ñöôïc khaùm phaù. Hoïc kì 2 naêm hoïc 2005-2006 Trang 5 Baøi giaûng moân Trí tueä nhaân taïo vaø heä chuyeân gia Ñænh cao cuûa vieäc phaùt trieån ôû lónh vöïc naøy phaûi noùi ñeán nhöõng naêm 1960. Duø raèng coøn bò haïn cheá veà trang thieát bò nhöng nhöõng naêm naøy coù nhieàu coâng trình ñöôïc coâng boá nhö + Naêm 1960, ngoân ngöõ Lisp. + Naêm 1961, chöông trình giaûi caùc baøi toùan ñaïi soá sô caáp. + Naêm 1963, chöông trình troø chôi côø vua. + Naêm 1964, chöông trình tính tích phaân. + Naêm 1966, chöông trình phaân tích vaø hoïc noùi. + Naêm 1968, chöông trình ñieàu khieån Robot theo phöông aùn maét vaø tay. + Naêm 1972, ngoân ngöõ Prolog. Töø nhöõng naêm 1969 ñeán naêm 1999, coù nhieàu chöông trình ñöôïc xaây döïng treân caùc heä cô sôû tri thöùc. Thaät vaäy, lónh vöïc trí tueä ñaõ ñi vaøo ñôøi soáng daân duïng töø nhöõng naêm 1980 ñeán naøy. 1.3) Caùc thaønh phaàn cô baûn cuûa trí tueä nhaân taïo : Coù hai thaønh phaàn cô baûn cuûa trí tueä nhaân taïo ñoù laø bieåu dieãn tri thöùc vaø tìm kieám tri thöùc trong mieàn bieåu dieãn. Tri thöùc cuûa baøi toùan coù theå ñöôïc phaân ra laøm ba loïai tri thöùc cô baûn ñoù laø tri thöùc moâ taû, tri thöùc thuû tuïc vaø tri thöùc ñieàu khieån. + Tri thöùc moâ taû : laø loïai tri thöùc moâ taû nhöõng gì maø ñöôïc bieát veà baøi toùan. Loïai tri thöùc naøy bao goàm caùc söï kieän, caùc quan heä vaø caùc tính chaát cuûa baøi toùan. + Tri thöùc thuû tuïc : laø loïai tri thöùc moâ taû caùch giaûi quyeát baøi toùan. Loïai tri thöùc naøy bao goàm luaät suy dieãn hôïp leä, chieán löôïc tìm kieám vaø giaûi thuaät tìm kieám. + Tri thöùc ñieàu khieån : laø loïai tri thöùc ñöôïc xem nhö laø luaät chuû choát ñieàu khieån quaù trình lyù giaûi ñeå daãn ñeán keát luaän. Ñeå bieåu dieãn tri thöùc cuûa baøi toùan nhôø caùc phöông phaùp bieåu dieãn nhö + Phöông phaùp bieåu dieãn nhôø luaät + Phöông phaùp bieåu dieãn nhôø maïng ngöõ nghóa + Phöông phaùp bieåu dieãn nhôø Frame + Phöông phaùp bieåu dieãn nhôø logic vò töø http://www.khvt.com Trang 6 Bieân soaïn: Tieán só Nguyeãn Thieän Thaønh Sau khi tri thöùc cuûa baøi toùan ñaõ ñöôïc bieåu dieãn, kyõ thuaät giaûi baøi toùan trong lónh vöïc trí tueä nhaân taïo laø caùc phöông phaùp tìm kieám trong mieàn ñaëc tröng tri thöùc veà baøi toùan ñoù. Ví duï : Xeùt baøi toùan ngöôøi noâng daân, choàn, ngoãng vaø nguõ coác. Baøi toùan ñaët ra laø ngöôøi noâng daân muoán mang theo vôùi mình moät con choàn, moät con ngoãng vaø moät soá nguõ coác qua beân kia soâng baèng moät chieác thuyeàn. Tuy nhieân, thuyeàn cuûa oâng ta quaù beù chæ coù theå mang theo moät thöù duy nhaát vôùi oâng ta treân moãi chuyeán thuyeàn sang soâng. Neáu oâng ta ñeå laïi choàn vaø ngoãng beân naøy soâng thì choàn seõ aên ngoãng vaø neáu oâng ta ñeå laïi ngoãng vaø nguõ coác thì ngoãng seõ aên heát soá nguõ coác. Haõy saép xeáp caùc chuyeán thuyeàn sao cho ngöôøi noâng daân mang moïi thöù sang beân kia soâng an toøan? Vôùi baøi toùan naøy, ta coù theå bieåu dieãn nhôø thoâng qua caùc phaùt bieåu ngoân ngöõ töï nhieân, tuy nhieân caùch bieåu dieãn naøy khoâng giuùp ta vaïch traàn ra caùc raøng buoäc voán saün coù trong baøi toùan. Caùch bieåu dieãn toát nhaát giuùp ta coù theå vaïch traàn caùc raøng buoäc voán saün coù trong baøi toùan laø xaây döïng moät bieåu ñoà vôùi caùc nuùt coù ñaùnh nhaõn ngöôøi noâng daân mang theo thöù maø oâng ta caàn phaûi mang theo treân moãi chuyeán thuyeàn vaø caùc caïnh lieân keát giöõa caùc nuùt laø caùc ñöôøng muõi teân chæ caùc chuyeán thuyeàn qua laïi soâng. Caùch bieåu dieãn naøy haøm chöùa caùc thaønh phaàn nhö ngöõ töø hoïc, caáu truùc, thuû tuïc vaø ngöõ nghóa. + Ngöõ töø hoïc (Lexical) : laø caùc töø vöïng hôïp leä ñöôïc söû duïng nhö laø caùc kyù hieäu trong bieåu dieãn. + Caáu truùc (Structure) : laø caùc ñöôøng muõi teân lieân keát giöõa caùc nuùt chæ ñònh caùc chuyeán thuyeàn qua laïi soâng. + Thuû tuïc (Procedure) : laø moâ taû caùch giaûi baøi toùan töø nuùt naøy ñeán nuùt kia nhôø thoâng caùc ñöôøng chæ ñònh muõi teân. + Ngöõ nghóa (Semantic) : laø yù nghóa cuûa caùc nuùt vaø caùc caïnh lieân keát thoâng qua caùch giaûi baøi toùan. Bieåu ñoà bieåu dieãn baøi toùan ngöôøi noâng daân, choàn, ngoãng vaø nguõ coác ñöôïc moâ taû nhö hình Hoïc kì 2 naêm hoïc 2005-2006 Trang 7 Baøi giaûng moân Trí tueä nhaân taïo vaø heä chuyeân gia Start Noâng daân Choàn Ngoãng Nguõ coác Noâng daân Choàn Ngoãng Nguõ coác Noâng daân Choàn Ngoãng Nguõ coác Noâng daân Choàn Ngoãng Noâng daân Choàn Noâng daân Choàn Ngoãng Ngoãng Nguõ coác Nguõ coác Noâng daân Choàn Ngoãng Nguõ coác Nguõ coác Noâng daân Choàn Ngoãng Nguõ coác Noâng daân Choàn Ngoãng Nguõ coác Noâng daân Choàn Ngoãng Nguõ coác Finish http://www.khvt.com Trang 8 Bieân soaïn: Tieán só Nguyeãn Thieän Thaønh Chöông 2 : Caùc Phöông Phaùp Giaûi Quyeát Vaán Ñeà Cô Baûn 2.1) Khoâng Gian Baøi Toùan : Tri thöùc cuûa baøi toùan ñöôïc chia ra laøm ba loïai tri thöùc cô baûn ñoù laø tri thöùc moâ taû, tri thöùc thuû tuïc vaø tri thöùc ñieàu khieån, trong ñoù tri thöùc thuû tuïc ñònh nghóa khoâng gian baøi toùan. Khoâng gian baøi toùan coù theå ñöôïc bieåu dieãn baèng khoâng gian traïng traïng thaùi ñoù laø moät bieåu dieãn baèng ñoà thò ñònh höôùng goàm boán thaønh phaàn nhö sau : + S : traïng thaùi ban ñaàu cuûa baøi toùan (döõ lieäu ban ñaàu). + G : taäp caùc traïng thaùi ñích cuûa baøi toùan (döõ lieäu ñích). + N : taäp caùc traïng thaùi khaùc ñöôïc phaùt sinh töø traïng thaùi ban ñaàu ñaït ñeán traïng thaùi ñích ñoù laø caùc nuùt cuûa ñoà thò. + A : Taäp caùc traïng thaùi chuyeån tieáp ñoù laø caùc cung lieân keát giöõa caùc nuùt cuûa ñoà thò nhôø thoâng qua caùc luaät aùp duïng cuûa baøi toùan. Luaät aùp duïng laø luaät maø veá ñieàu kieän cuûa noù hôïp vôùi traïng thaùi hieän coù ñeå veá keát luaän cuûa noù phaùt sinh ra caùc traïng thaùi môùi. Ñöôøng lôøi giaûi cuûa baøi toùan laø ñöôøng baét ñaàu töø traïng thaùi ban ñaàu thoâng qua caùc traïng thaùi khaùc ñöôïc phaùt sinh ñeán moät traïng thaùi naøo ñoù trong taäp caùc traïng thaùi ñích. Ví duï 1: Khoâng gian baøi toùan bình ñöïng nöôùc. Cho hai bình ñöïng nöôùc, moät bình coù dung tích 4 lít vaø moät bình khaùc coù dung tích 3 lít, caû hai bình khoâng coù daáu dung tích. Traïng thaùi ban ñaàu cuûa hai bình laø roãng, duøng moät bôm nöôùc laøm ñaày nöôùc vôùi hai bình. Laøm caùch naøo ñeå coù chính xaùc 2 lít nöôùc trong bình 4 lít ? Vaäy, khoâng gian traïng thaùi cho baøi toùan naøy laø gì ? Giaûi : Cho caëp bieán soá nguyeân (x,y) bieåu dieãn caùc traïng thaùi trong khoâng gian traïng thaùi cho baøi toùan naøy, trong ñoù x laø soá lít nöôùc trong bình 4 lít vaø y laø soá lít nöôùc trong bình 3 lít. Khoâng gian traïng thaùi cho baøi toùan ñöôïc moâ taû baèng caùc thaønh phaàn nhö sau : + Traïng thaùi ban ñaàu cuûa baøi toùan : hai bình ñeàu roãng ñoù laø caëp soá nguyeân (0,0). + Traïng thaùi ñích cuûa baøi toùan : caàn coù chính xaùc 2 lít nöôùc trong bình 4 lít ñoù laø caëp soá nguyeân (2,n), tronng ñoù n laø soá khoâng xaùc ñònh trong bình 3 lít. Hoïc kì 2 naêm hoïc 2005-2006 Trang 9 Baøi giaûng moân Trí tueä nhaân taïo vaø heä chuyeân gia + Traïng thaùi khaùc cuûa baøi toùan : ñoù laø caëp soá nguyeân (x,y) moâ taû caùc traïng thaùi trong khoâng gian baøi toùan. + Traïng thaùi chuyeån tieáp cuûa baøi toùan : ñoù la’ böôùc chuyeån tieáp töø traïng thaùi hieän coù ñeán traïng thaùi môùi nhôø thoâng luaät aùp duïng cuûa baøi toùan. Luaät aùp duïng laø luaät maø veá ñieàu kieän cuûa noù hôïp vôùi traïng thaùi hieän höõu ñeå veá keát luaän cuûa noù phaùt sinh ra traïng thaùi môùi. Taäp caùc luaät giaûi baøi toùan bình ñöïng nöôùc ñöôïc lieät keâ laø Luaät 1 : (x,y/ x < 4 ) → (4,y). Luaät 2 : (x,y/ y < 3 ) → (x,3). Luaät 3 : (x,y/ x > 0 ) → (0,y). Luaät 4 : (x,y/ y > 0 ) → (x,0). Luaät 5 : (x,y/ x + y >= 4 vaø y > 0 ) → (4,y – (4 – x)). Luaät 6 : (x,y/ x + y >= 3 vaø x > 0 ) → (x – (3 –y),3). Luaät 7 : (x,y/ x + y < 4 vaø y > 0 ) → (x + y,0). Luaät 8 : (x,y/x + y < 3 vaø x > 0 ) → (0,x + y) Khoâng gian traïng thaùi cho baøi toùan naøy ñöôïc bieåu dieãn baèng ñoà thò nhö hình (0,0) (4,0) (4,3) (0,0) (0,3) (1,3) (4,3) (0,0) (3,0) (2,n) Vaäy, khoâng gian traïng thaùi cho baøi toùan bình ñöïng nöôùc bao goàm traïng thaùi ban ñaàu, taát caû caùc traïng thaùi khaùc ñaït ñöôïc töø traïng thaùi ban ñaàu nhôø thoâng qua caùc luaät öùng duïng (caùc traïng thaùi chuyeån tieáp ) vaø traïng thaùi ñích cuûa baøi toùan. http://www.khvt.com Trang 10