Artificiell Intelligens Java - ?· och funktionaliteten för att definiera tillåtna steg kan implementeras…

  • Published on
    13-Sep-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>ArtificiellIntelligensochJava</p><p>Kandidatavhandling</p><p>MatiasMyren,32696</p><p>InstitutionenfrInformationsteknologi</p><p>Vren2011</p></li><li><p>i</p><p>ReferatDet kommer att antas att grunderna i Java r bekanta fr lsaren och sledes</p><p>kommerdessa inteattgs igenom.Dremotkommer frdelarnamedJavanrdet</p><p>gllerattprogrammeraartificiella intelligenseratttasupp.Avhandlingenrdelad i</p><p>tvhuvuddelar,en teoridelochenmerapraktiskt inriktaddel.Teoridelen tarupp</p><p>huvudtankegngarnasomkrvsfrattfrstexempelprogrammenipraktikdelen.</p><p>Definitionenavenproblemrymdochhurdetillstndsomenartificiellintelligenskan</p><p>befinna sig ipresenteras, svendatastrukturerna fr tillstndsgraferochhuren</p><p>tillstndsgraf byggs upp. Skningar genom tillstndgrafer med hjlp av knda</p><p>skalgoritmer, dribland djupfrstskning (depthfirstsearch) och breddfrst</p><p>skning (breathfirstsearch) gs genom. Drefter fljer en genomgng av enkla</p><p>heuristiker fr tillstndsgrafer och hur bstfrstskning (bestfirstsearch)</p><p>definieras.Bakgrunden tillmaskininlrningochhurenartificiell intelligenskan lra</p><p>sig eller bygga upp en tillstndsrymd presenteras med hjlp av exempel och</p><p>generaliseringar.TeorinkommerattframhvasmedhjlpavexempelskrivnaiJava.</p></li><li><p>ii</p><p>Innehllsfrteckning</p><p>Referat............................................................................................................................i</p><p>Innehllsfrteckning......................................................................................................ii</p><p>1.Inledning....................................................................................................................1</p><p>2.Java............................................................................................................................3</p><p>3.Skning......................................................................................................................4</p><p>3.1Breddfrstskningochdjupfrstskning.......................................................5</p><p>3.2Heuristikochbstfrstskning..........................................................................7</p><p>4.Maskininlrning.......................................................................................................11</p><p>4.1Maskininlrningsalgoritmer...............................................................................12</p><p>5.Javaexempelpskning..........................................................................................14</p><p>6.Javaexempelpmaskininlrning.............................................................................16</p><p>7.Avslutning................................................................................................................21</p><p>8.Kllor........................................................................................................................22</p><p>9.Bilaga1....................................................................................................................25</p><p>10.Bilaga2..................................................................................................................29</p></li><li><p>1</p><p>1. InledningIntelligensrettsvrdefinierbartbegreppochrngotsommngaharfilosoferatp</p><p>genomrhundradena.Detfinnstroligtvislikamngadefinitioneravintelligenssom</p><p>det finnspersoner som forskar idet.Tilldeallmnnastedefinitionernahrbland</p><p>annat frmgan att lra sig, att frst vadman lrt sig, att tnka abstrakt, frst</p><p>iderochsprk[1].Medartificiellintelligensmenasalltsenkonstgjordintelligens,</p><p>ngot sommnniskanhar skapat. Fr endator rdet enkelt att frst komplexa</p><p>matematiskaformlerochproblemochsnabbthittaen lsningpdessa,medanen</p><p>mnniskamed livslngerfarenhetavmatematikkanbehvaenbetydligt lngretid</p><p>ellerkanskeinteallsserenlsningpproblemet.Endatorhardockmycketsvrare</p><p>att frstnaturligasprk, tillexempelmeningenHonstalhanshjrta.Meningen</p><p>kan tolkas p tv olika stt; antingen handlar det om krlek eller en organtjuv.</p><p>Vilkendera det gller kan ses ur sammanhanget. En dator som bara gr igenom</p><p>textenserintesammanhangetochkansledesintefrstvadmeningenegentligen</p><p>betyder.Orsakentilldettarattmatematikharklarafastslagnagrnserochregler,</p><p>medannaturligasprkbaserarsigmeraphurngontingsgs,ivilketsammanhang</p><p>ochdekanhadoldameningar[2].</p><p>Hollywoodsfilmerhari40rdrmtuppenbildavartificiellaintelligenser.IStanley</p><p>Kubricks film 2001: Ett rymdventyr frn 1968 finnsdenpsykotiskadatornHAL</p><p>9000somgerensortsbildavvadmanstrvattillattuppn(kanskeinteenpsykotisk</p><p>dator,menenmaskin somuppfyllerde flestakravenpen intelligensoch frstr</p><p>naturliga sprk). Dagens teknologi har inte ntt fram till detta ml nnu, men</p><p>teknologingralltidframtochendagdetkanskeexisterarenartificiell intelligens</p><p>som r jmlikmnniskans hjrna p att lra sig och frst.Men detmste dock</p><p>pekas ut att meningen med en artificiell intelligens inte alltid r att simulera</p><p>mnsklig intelligens.Enartificiell intelligenskan lsaettproblemsomenmnniska</p><p>eller ett djur skulle lsa det. En artificiell intelligens r dock inte bunden till de</p><p>metoderenmnniskaellerettdjurskulleanvndautandenkananvndametoder</p></li><li><p>2</p><p>somrmeramatematikbaseradeochsledesenklarefrenmaskinattarbetamed.</p><p>[3]</p><p>Mlet med denna kandidatavhandling r dock inte att uppfinna ngot</p><p>revolutionerandeutanattgeenbakgrund tillvissaavdealgoritmersomexisterar</p><p>idag, ochmed hjlp av programmeringssprket Java ge exempel p lsningar till</p><p>ngraproblem.Detexisterarvenandrabrasprk frdettandaml, tillexempel</p><p>Prolog och Lisp. Alla tre sprken har sina frdelar, vilket tas upp i kapitel 2.</p><p>DessutomkanmanvenprogrammeramedsammastiliJavasommangriProlog</p><p>ochLisp,mendetr intesagtattmanuppnrsammaoptimeringsgradellerskan</p><p>programmenblisinveckladeattdettaintelnarsig.Javarvendetnyasteavde</p><p>tre sprken och ett av de sprk som anvnds mest i</p><p>informationsteknologiutbildningenochprogramvaruindustrin idag[4],drfrrdet</p><p>intressantattsehurJavakananvndasveninomartificiellintelligensforskningen.</p></li><li><p>3</p><p>2. JavaOmrdet fr artificiell intelligens r vldigt brett, och inget programmeringssprk</p><p>kanansessomdetendatnkbarasprketattprogrammeraenartificiell intelligens</p><p>med. Artificiell intelligens har djupa grunder inommatematiken och drmed har</p><p>venprogrammeringssprksombaserarsigpmatematikutformatsfrattenklare</p><p>kunna representera problem och lsningar [5]. Speciellt kanman nmna Prolog,</p><p>medgrunderinomfrstaordningenspredikatlogik,ochLisp,somrettfunktionellt</p><p>sprk. Java, som r objektorienterat, skiljer sig mrkvrt frn Lisp och Prolog</p><p>speciellt iprogrammeringsstil,mendetvisarsigatt Javasobjektorientering lmpar</p><p>sigocksfratt implementeraenartificiellintelligens[6].Detrvldigtsllansom</p><p>detrsiffrorochstrngarsomenartificiellintelligensinteragerarmed;oftastrdet</p><p>ngonsortssymbolerellertillstndochdessakanenkeltrepresenterasavobjekt i</p><p>Java. Vidare gr det i Java att definiera grnssnitt fr objekt och implementera</p><p>funktioner och klasser som agerar mot grnssnitten [7]. Detta leder till en viss</p><p>abstraktion som ven det r en av Javas styrkor, och programkod kan enkelt</p><p>teranvndasfrolikandaml[6].</p><p>Java r nd inte det ideala sprket fr att programmera en artificiell intelligens</p><p>med.Nrdettillexempelgllerexpertsystem,detvillsgaettprogramsomhrmar</p><p>enmnskligexpertpettspecifiktomrde,srdetPrologsombriljerar.Detgr</p><p>med ett simpelt program skrivet i Prolog att beskriva ett enkelt expertsystem.</p><p>MotsvarandeprogramiJavaskullevaramycketmeraomfattandeochkomplext[6].</p><p>Allt r ndmjligt att implementera i Java,men varjeprogrammeringssprkhar</p><p>sina egna specifika problem som de kan briljeramed att lsa p ett enkelt stt.</p><p>Eftersom Javas styrka ligger i abstraktion, kan skning i tillstndsrymder och</p><p>maskininlrninglsasiJavapettlmpligtstt[6][7].</p></li><li><p>4</p><p>3. SkningTidig forskning inom artificiell intelligens fokuserades mest p optimering av</p><p>skalgoritmer fr tillstndsgrafer. Detta var ett logiskt frsta steg fr en hel del</p><p>uppgifter somen artificiell intelligens ska lsa.Detta grsgenom attdefinieraen</p><p>klarproblemrymdochurdenfentillstndsgraf.Denbstalsningenpproblemet</p><p>hittasgenomeneffektivskninggenomtillstndsgrafen.Skningrsledesgrunden</p><p>frbdeutvecklingavteoretiskamodelleroch lsningarppraktiskatillmpningar</p><p>[5] [8].Med hjlp av bde effektiva algoritmer och heuristik, tilldela vrden till</p><p>tillstndenbaseratphurnraenlsningtillstndetr,kanskningarnaoptimeras.</p><p>vengenomattsparaextradata iminnetkanskningareffektiviserasochsledes</p><p>ger de ett bttre resultat. Extra minneslagring gr sktiden snabbare och kan</p><p>effektiviseraframtidaskningarinomsammatillstndsgraf[6][8].</p><p>FrdelenmedJava idethrskedetrattJavasstd frabstraktionochgrnssnitt</p><p>gr det enklare att implementera olika skalgoritmer som opererar p samma</p><p>tillstndsgraf.Gemensamma faktorer s som representationen av tillstndsgrafen</p><p>och funktionaliteten frattdefiniera tilltnastegkan implementeras ienabstrakt</p><p>klassmedhjlpavJava.Despecifikaskalgoritmernakansedandefinierasskiltoch</p><p>sledesdelapfunktionalitetmellanklasserna.Pdethrsttetkanskalgoritmen</p><p>frittbytasutelleroptimerasutanattgrundfunktionalitetenpverkas.[6][8]</p><p>Det finns tv huvudelement som mste definieras fr att kunna bygga upp en</p><p>tillstndsgraf. Frst och frmst mste det finnas en formell representation av</p><p>tillstnden.Detkantnkasatttillstndenrstegenmotenlsning.Frstatillstndet</p><p>rursprungstillstndet,hurproblemetserut justnu.Drefter frgrenarsiggrafen</p><p>frvarjemjligtsteg tillnsta tillstnd,vilketkanvaraetteller fleraberoendep</p><p>hurstegenmellan tillstndenrdefinieradeochomdet tilltsattsamma tillstnd</p><p>besks flera gnger [6] [8]. Den andra saken som krvs r operatorer fr att</p><p>generera fljande tilltna tillstnd frn ett godtyckligt tillstnd. Beroende p hur</p><p>problemrymden ser ut och detta r direkt beroende p problemet (till exempel</p></li><li><p>5</p><p>tilltnasteg iettspelellerolikaskeden ienkemiskprocess).Stegenkanvenvara</p><p>baseradepheuristik, logisk slutledningellerexempel tagna frn tillgngligadata</p><p>[8].Deolikamjligatillstndenfungerarsomnodernaigrafenmedanoperatorerna</p><p>utgrbgarnamellandeolikatillstnden(seexempelifigur1).Detkanvenkrvas</p><p>att tidigaredata lagrasver vilka tillstnd sombeskts fr attundvika att grafen</p><p>uppreparsigsjlv.</p><p>Figur1.Exempelgrafvermjligatillstnd.</p><p>3.1BreddfrstskningochdjupfrstskningGrunddesignen ibreddfrstskningochdjupfrstskningr iprincipdensamma.</p><p>Bda algoritmerna gr iterativt genom tillstndsgrafen. De brjar frn</p><p>starttillstndetochavslutarmedettmltillstnd,ifallettellerflerasdanaexisterar.</p><p>Ifalldetnuvarandetillstndetalgoritmernabefinnersig i interettmltillstnds</p><p>genereras barntillstnd (child states) till det nuvarande tillstndet, och dessa</p><p>placerasientillstndslista.[6]</p><p>I figur2 finnspseudokodenengenerellskalgoritmsombdebreddfrstskning</p><p>och djupfrstskning fljer. Den huvudsakliga skillnaden mellan de tv</p><p>algoritmernarhurdeopererarptillstndslistan.</p><p>Starttillstnd</p><p>Tillstnd1</p><p>Tillstnd3 Tillstnd4</p><p>Tillstnd2</p><p>Mltillstnd</p></li><li><p>6</p><p>Figur2.Pseudokodfrgenerellskalgoritm.[6]</p><p>Breddfrstskninganvndersigaventillstndslistasom fungerarsomenk;det</p><p>frstatillstndetsomsttsinilistanrocksdetfrstatillstndetsomreturnerasav</p><p>listan.Dettagrattbreddfrstskninggaranterathittardenkortastevgentillett</p><p>mltillstnd,pgrundavattdengr igenomallatillstndpettgodtyckligtdjupd</p><p>innanalgoritmenbrjargigenomtillstndpdjupetd+1[6][7].Djupfrstskning</p><p>serptillstndslistansomenstack.Enstackfungerarsattdetsistatillstndetsom</p><p>lagtstilllistanrdetfrstasomkommerattreturnerasavlistan.Dettaledertillatt</p><p>djupfrstskninggrenmeraaggressivskninggenomgrafen[6][7].Frattka</p><p>chansernaatthittaenrtt lsningbegrnsasoftadjupfrstskningalgoritmentill</p><p>ettmaximalttilltetdjupigrafen,annarsfinnsdetenriskattdjupfrstskninginte</p><p>hittar en rtt lsning [6]. Detmaximala tilltna djupet kas vartefter grafen gs</p><p>igenom ifall ettmltillstnd inte hittades inom det specificerade djupet. Varken</p><p>djupfrstskning eller breddfrstskning tar i beaktande den information som</p><p>detnuvarandeochde tidigare tillstndenharatterbjuda;breddfrstskning tar</p><p>endast ibeaktandestrukturenptillstndsgrafen.Bdaalgoritmernaklassasdrfr</p><p>somoinformeradeskalgoritmer.[6]</p><p>Skning(Starttillstnd){ placerastarttillstndetitillstndslistan; medantillstndslistanintertomgrfljande { Tillstnd=nstatillstnditillstndslistan; Omtillstndetrettmltillstnd Algoritmenavslutasmedframgng; Annars Genereraallabarntillstndtilldetnuvarandetillstndet ochplaceradetillstndsominteharbesktstidigarei tillstndslistan; }}</p></li><li><p>7</p><p>Ifall skrymden r vldigt stor blir det vldigt opraktiskt att anvnda djupfrst</p><p>skningochbreddfrstskning.Tillexempelskrymdenfrspeletschackhar2 tillstnd,vilketretttalstrrenantaletmikrosekundersomgttsedanuniversums</p><p>skapande.Fratthitta lsningar ienstor skrymdkrvsdetenalgoritmsomkan</p><p>hitta, utgende frn tidigare tillstnd och det nuvarande tillstndet, vilka</p><p>barntillstndsomrdemestsannolikaattfortsttamed[5][6].</p><p>3.2HeuristikochbstfrstskningDetfinnsvensttattfrminskatillstndsgrafenfrattgraskningarnasnabbare.</p><p>Ibondschack,meden spelplan som r3x3 rutor stor, kan tillstndsgrafen snabbt</p><p>definieras.Det finnsmaxniodrag iett spel, femdrag respektive fyradrag frde</p><p>bda spelarna. Idet frstadraget finnsdet9olikamjligheter, idetandradraget</p><p>finns det 8 mjligheter och s vidare tills spelplanen r fylld. Antalet noder i</p><p>tillstndsgrafen r d 9! stycken, med andra ord 362 880 stycken. Mentillstndsgrafenkanreducerasmedhjlpavsymmetrinsomuppstr[5].Idetfrsta</p><p>dragetfinnsdetnutreolikamjligheter:mitten,etthrnellerensida.Medhjlpav</p><p>simpelheuristikgrdetvenattgigenomtillstndsgrafenfrbondschackutanatt</p><p>anvndasigavenskalgoritm.Frattheltfrbiseskningmstedetivarjetillstnd</p><p>definieras ett attribut som str fr antalet vinstmjligheter som existerar (se</p><p>exempel i figur 3). Nsta steg i tillstndsgrafen r alltid tillstndet med flest</p><p>vinstmjligheter[7].Dennametodkallasfrbergbestigningsmetoden(HillClimbing</p><p>procedure) [5] och kan liknasmed en blind bergbestigare som alltid vljer den</p><p>brantastesluttningenattklttrauppfrtillsdetintegrattkommahgreupp.Vissa</p><p>bristerexisterardock,metodenspararingenhistoriavervardenvarit.Algoritmen</p><p>kandalltsintegtillbakaitillstndsgrafenochprvaenannanvg ifallden inte</p><p>nrettmltillstnd.Denstrstabristensombergbestigningsmetodenharrattden</p><p>hittar enbart det lokala maximum. Det hittade lokala maximumet kan vara ett</p><p>mltillstnd,mendetrinteskert[5].</p></li><li><p>8</p><p>Figur3.Tillstndsrymdverbondschackmedantaletvinstmjligheterfrvarjetillstndangivet.[9]</p><p>Algoritmenfastnaralltsietttillstndifallalladessbarntillstndharettsmrevrde</p><p>n det nuvarande tillstndet.Detta fall kommer inte fram i bondschackexemplet,</p><p>men tillexempel i lsningav femtonspeletkommerdet framattdetbehvsmera</p><p>bergsbestigarmetoden fr att stadkomma en bstfrstskning. Fr att frenkla</p><p>spelet frminskas spelplanen till3x3 rutor. I spelet, somnukallas frttapusslet,</p><p>finnsttastyckennumreradebrickorochentomplats(seettgodtyckligttillstnd i</p><p>figur4), idenursprungligaversionenvardetta femtonstyckennumreradebrickor</p><p>ochentom.Detendamltillstndetdefinierasven ifigur4.Transaktionermellan</p><p>tillstnddefinierasutgendefrnhurdentommarutankanbytaplatsmedngonav</p><p>deangrnsandebrickorna.</p><p>6 3 4 1 2 37 1 2 4 5 6 5 8 7 8 Godtyckligttillstnd</p><p>Mltillstnd</p><p>Figur4.Exempeltillstndfrttapusslet.</p></li><li><p>9</p><p>Bdedjupfrstskningochbreddfrstskningkananvndasfratthittaframtill</p><p>mltillstndet, men fr att alltid kunna vlja den bsta vgen igenom</p><p>tillstndsgrafen, vilket djupfrstskning och breddfrstskning inte gr,mste</p><p>ngontypavheuristikanvndas[5][7].</p><p>Ifall enbergbestigaralgoritm anvndsp ttapussletdefinieras ett vrde fr varje</p><p>tillstnd.Vrdetrantaletrutorsomrprttplats.Imltillstndetrdettavrde</p><p>nioochidetgodtyckligatillstndet...</p></li></ul>