Academic literature on the topic 'Sökalgoritmer'

I det här arbetet undersöks och jämförs två olika sökalgoritmer när de används för implementation av AI-spelare till brädspelet Pentago. De två algoritmerna som användes var alfa-betabeskärning och en nyare algoritm som kombinerar genetiska algoritmer och minimax, kallad genetisk minimax. Utvärderingen av resultaten visar att alfa-betabeskärning passar bättre vid implementation av en AI till Pentago än genetisk minimax. Alfa-betabeskärning med ytterligare optimeringar har potential att lämpa sig väldigt väl för implementation av spelare till Pentago. Ytterligare visar resultaten att genetisk minimax inte är en passande algoritm för AI till Pentago. För eventuella framtida arbeten föreslås ytterligare arbete och förbättringar på implementationen av alfa-betabeskärning. Genetisk minimax har potential att fungera bättre vid implementation av AI till andra brädspel. Därför föreslås även framtida arbeten av implementationer av genetisk minimax inom områden och spel som kan vara mer passande.

Automatisk generering av innehåll till dataspel är ett viktigt forskningsområde eftersom allt mer detaljerat innehåll går att använda. Denna rapport beskriver en studie som jämför två metoder att automatiskt generera kartor för militära strategispel. Den bygger på Stachniak och Steurzlingers (2005) arbete om deformationer av terräng efter ställda kriterier. De använder stokastisk lokalsökning för att hitta lämpliga deformationer. Andra sökmetoder kan användas och den stokastiska lokalsökningen ställs mot en evolutionär sökning i denna studie. Ett program utvecklades som implementerade en evolutionär algoritm och en förenklad variant av Stachniak och Steurzlingers (2005) algoritm. Programmet testkördes med olika indata för att försöka få algoritmerna att prestera sitt bästa så att de kunde jämföras rättvist. Den evolutionära algoritmen visade sig vara effektivast men gav inte tillräckligt bra resultat på utsatt tidsåtgång. Arbetet kan utvecklas genom fler tester och optimeringar.

Att "smarta" brädspelande datorprogram har blivit mycket bättre under de senaste årtiondena har väl knappast kunnat undgå någon. Med brädspel menar jag spel såsom Go, Othello, Backgammon och Schack. Idag spelar program, som körs på en reguljär PC, bättre än de flesta människor. Vad är det som gör dessa program så bra? Hur kan man lära en dator att spela ett så pass komplext spel som Othello på en sådan nivå att ingen människa har en chans att vinna? I detta examensarbete kommer jag att försöka förklara mekanismerna bakom ett toppspelande Othelloprogram. Jag har dessutom implementerat ett eget Othellospelande program som jag använt som testapplikation för att prova olika sökmetoder, metoder för att öka exekveringshastigheten och tekniker för att öka spelskickligheten. Jag kommer att presentera empiriska data där jag utvärderar och jämför flera andra program med mitt eget.

Det blir allt vanligare med att använda webbläsare som plattform för applikationer istället för de konventionella som måste installeras lokalt. Frågan är hur pass bra JavaScript står sig när det kommer till intensiva och tunga algoritmer såsom sökalgoritmer för spel. Finns det optimeringar som kan förbättra tidsåtgången för sökalgoritmer så att användaren i slutändan inte tröttnar på att det tar för lång tid? Med hjälp av ett antal tekniker såsom Typed Arrays försöker det här arbetet påvisa huruvida Typed Arrays kan användas som optimeringsstrategi för en applikation handskriven i JavaScript för att sänka tidsåtgången. Detta arbete syftar till att utvärdera hur användbart av optimeringsstrategier såsom Typed Arrays påverkar tidsåtgången för en förutbestämd sökväg. Flera versioner av en applikation implementeras för att se vilken optimering som är mest lämpad och utvärderas sedermera genom prestandamätning. Resultatet visar att ingen av de valda optimeringsstrategierna gav någon nämnvärd förbättring utan var till vissa delar en försämring jämfört med referensmätningen.

Norrmejerier’s supply of raw material fluctuates during different periods of the year. During the months where the company receives the most milk there is a need of an increase in cheese production in order to refine the milk in a more value creating way. To enable an increase in the production the process of the cheese department in Umeå is mapped. To determine the critical parts of the process a month’s production is simulated in a discrete event system.  Today the department produces eight different cheese types of which they aim to carry a constant partition. All process times except the one for the last process step are independent on the cheese type produced. The process time for the last leg differs with up to 70% depending on the cheese type. Hence the total production volume depends on the order in which the different types of cheese are produced, the production sequence.  In this thesis we optimize the production sequence with a genetic search algorithm. Given the predetermined distribution of cheese types a set of production sequences is created which are tested against a model imitating the process. The set of sequences is gradually improved through the genetic algorithm to finally reach a solution considered good enough. This enables us to derive the maximum capacity of the process and determine its bottlenecks.  This study concludes that a production increase of 16,6% can be achieved by additional staff, adjusted work routines and an optimized production sequence. To further increase the production, an increased capacity of the first part of the process is required, that being the pasteurization step. Given an increase in the pasteurization step the next bottleneck would appear in the last part of the process, where the cheese is placed in a salt brine.
Norrmejerier har under året en fluktuerande invägning av råvara som vid toppar ger upphov till ett råvaruöverskott. För att förädla råvaran på ett mer värdeskapande vis finns ett behov av en kapacitetsökning av osttillverkning under de perioder då invägningen är som störst. För att möjliggöra en ökad produktion av ost kartläggs processen på ysteriavdelningen i Umeå. Avdelningen producerar åtta osttyper och önskar bibehålla en förutbestämd fördelning av dessa. Givet fördelningen simuleras en månads produktion i ett diskret händelsesystem där kritiska delar i processen identifieras.  Beläggningstiden för processdelarna på ysteriavdelningen är mer eller mindre oberoende av vilken osttyp som produceras med undantag för det sista processteget där beläggningstiden varierar med upp till 70%. Detta leder till att den totala produktionsvolymen är beroende av i vilken ordning de olika osttyperna produceras.  I denna studie optimerar vi denna ordningsföljd, benämnd produktionssekvens, med en genetisk sökalgoritm. Givet den förutbestämda fördelningen av osttyper skapar vi en mängd produktionssekvenser som testas mot en modell som imiterar processen. Mängden produktionssekvenser utvecklas successivt via den genetiska algoritmen för att kulminera i en tillräckligt bra lösning. Genom att göra detta kan processens flaskhals identifieras och en maxkapacitet härledas.  Studien fastställer att förändringar i bemanning, arbetssätt och en optimerad produk- tionssekvens kan ge en ökad produktion om 16,6%. För ytterligare förbättringar krävs ökad kapacitet på den första processdelen där mjölken pastöriseras. Om kapaciteten utökas uppstår nästa flaskhals i det sista processteget, saltlaken.

 

Befintliga studier har påvisat att genetiska algoritmer presterar bättre om de ges en bra startpopulation. I denna rapport presenteras en lokal sökalgoritm för att skapa en population med fokus på ”vehicle routing”-problem. Algoritmen använder sig av heuristik i en blandning av simulated annealing och tabu search för att skapa individerna till populationen. Utvärderingar av algoritmen på ett praktiskt problem visar att den ger en bra start jämfört med en slumpmässig startpopulation, vilket är vanligt att använda. Resultaten av utvärderingen visar också att algoritmen ger bäst resultat vid mer komplexa problem, medan den har mindre effekt om problemet är enklare.

 

Nyckelord: Simulated annealing, Tabu search, Genetiska algoritmer , ”vehicle routing”-problem.

 

Deterministiska turbaserad tvåspelarspel är ett område som används inom AI forskning för att jämföra AI system. Detta arbete fokuserar på att jämföra teknikerna artificiell neuralt nätverk och alpha-beta pruning i spelet othello. Arbetet undersökte hur dessa tekniker presterar i relation till beräkningstiden. Othello positionerna representeras i en 8 x 8 matris som teknikerna använder för att hitta det optimala draget. Systemen värderades enligt en definierat metod som använder ett befintlig AI system för othello Edax. De testades på 154 othello partier med 77 stycken förbestämda startpositioner. Nätverket tränades med inlärningsdata som bestod av drag från professionella othello matcher och från Edax. Resultatet visade att ABP systemen värderades linjärt mot exponentiell beräkningstid medans ANN systemen värderades konstant mot linjär beräkningstid. Resultatet av ANN systemen tyder på att inlärningsdatan är bristande. Framtida arbete bör använda mer och bättre inlärningsdata.

The scheduling of a tennis school’s operation at a general tennis club is today done manually. This is a time consuming task, usually taking 2-4 weeks for the person responsible. This thesis aims to mathematically formulate the tennis school scheduling problem (TSSP), and to develop a computer based solution procedure to automate the scheduling process. The mathematical formulation of the problem has the structure of an optimization problem and the solution procedure that is developed is a heuristic algorithm for the specific purpose of this problem. Furthermore, a heuristic local search algorithm to improve the initial solution is developed, and the model is then tested on real data in a case study at a padel club in Stockholm. Furthermore, the result from the solution procedure is compared with the manually created schedule by the club on some key parameters from the mathematical model. The computerized solution procedure outperformed the manual scheduling procedure in terms of execution time and most of the times in the objective value of the generated schedule. In terms of the mathematical formulation neither the manually created schedule nor the schedules created by the algorithm gives feasible solutions to the problem. However, the padel club deems the schedules usable and will continue with the ongoing process to implement the model.
Schemaläggning av en tennisskolas verksamhet hanteras vanligtvis av en eller flera ansvariga från tennisklubben och utförs manuellt. Det är en tidskrävande uppgift som kräver uppföljning och återkoppling med alla deltagare, vilket kan ta flera veckor. Den här masteruppsatsen ämnar att matematiskt formulera tennisskolans schemaläggningsproblem, "tennis school scheduling problem" (TSSP), och utveckla en schemaläggningsalgoritm för att heuristiskt lösa TSSP som kan imple-menteras med objektorienterad programmering för att automatisera schemaläggningen. Utöver det är en lokal sökalgoritm framtagen för att förbättra schemat skapat av schemaläggningsalgo-ritmen. Algoritmerna är testade på en padelklubbs träningsverksamhet för att jämföra resultaten från algoritmerna mot deras manuellt framtagna schema. Den automatiserade schemaläggningsal-goritmen är e˙ektivare än att manuellt schemalägga verksamheten gällande tidsåtgång och även ofta i målvärde definierat i matematiska modellen. Baserat på data från padelklubben och så som problemet är uppställt i samråd med dem, möter varken det manuellt framtagna schemat eller det genererat med schemaläggningsalgoritmen, efter förbättringsalgoritmen tillämpats, de krav som är ställda på schemat. Trots det är det genererade schemat brukbart enligt padelklubben och de kommer arbeta med att implementera automatiseringen av schemaläggningen.Den automatiserade processen för att ta fram ett schema är tänkt att användas som ett verk-tyg för en schemaansvarig person. Det kan användas för att generera förslag på scheman baserat på deltagares tillgängligheter, för att bespara personens administrativa arbete med schemaläggnin-gen. Mindre ändringar kan sen göras i ett genererat schema och det är enligt dem själva en stor besparing i arbete jämfört med hur det går till i dagsläget.

Goal-Oriented Action Planning, även kallat GOAP, är ett system för att styra beteende av artificiell intelligens. Systemet använder en sökalgoritm för att besluta vilket beteende som ska köras baserat på ett mål och ett antal åtgärder. Studien målsatte att undersöka vilken sökriktning som var mest lämpad för givet scenario. Undersökningen utfördes med hjälp av en simpel spelprototyp baserat på rollspel med stridsmekaniker. Totalt tre tester utfördes med olika scenarion och alla resulterade i att regressiv sökning var snabbare än progressiv sökning. Resultat för det mest krävande målet visade att progressiv sökning besökte 1724 %, 1100 % och 232 % fler noder än regressiv sökning för respektive test.

This master thesis presents a method to find the optimal speed profile for a dynamic system in the shape of an electric vehicle and any topography using a search algorithm. The search algorithm is capable of considering all the speed choices in a topography presented discretely, in order to find the most energy efficient one. How well the calculations made by the search algorithm represents the reality, depends on the speed and topography resolution and the vehicle energy model. With the correct settings, up to 18.4% of energy can be saved for a given topography compared to having the lowest constant speed allowed. The speed is ranging between 85-95 km/h but the method presented is capable of having any set of speed options, even if the resolution varies from point to point on the road. How to use this method and its properties is explained in detail using text and step for step figures of how the search algorithm iterates.A comparison between allowing regenerative braking and not allowing it is shown in the results. It is clear that there is most energy saving potential where no regenerative braking is allowed.

Mustafa Ali Arat has stopped working at NEVS and moved abroad.