Spelbalans är ett viktigt koncept inom spelutveckling, generellt sett så anses datorspel där det finns många olika strategier för att vinna, och där alla är effektiva, vara bättre än spel där det bara finns några få effektiva strategier. För att uppnå bra spelbalans krävs ofta att mycket tid med att testa spelet med speltestare för att hitta strategier som kan förstöra denna balans. Arbetet undersöker om man kan snabba upp speltestningsprocessen genom att låta en evolutionär algoritm automatiskt undersöka ett spels strategirymd, och sedan dra slutsatser på hur spelet skulle ändras för att förbättra spelbalansen. Resultatet pekar på att metoden kan hantera extremfall, men förlorar effektivitet vid en viss gräns. I framtiden kan algoritmens effektivitet förbättras genom att förbättra sättet algoritmen tar ekonomiska faktorer i åtanke.

<p>Testmetoder för tidskritiska applikationer har ofta bara omfattat statiska testmetoder där slutsatser kring applikationens exekveringstider och beteende dras utifrån studier av programkod och underliggande hårdvara. I detta arbete undersöks en dynamisk testmetod för framtagning av indata som med framgång använts i tidigare arbeten för bestämning av extrema exekveringstider hos applikationer. Detta arbete utvärderar tre varianter av denna testmetod för att försöka finna indata till applikationer som kan ge en inom ramen för applikationens möjligheter godtycklig exekveringstid. Detta för att förbättra möjligheterna att styra testning av denna typ av applikationer.</p><p>Arbetet har visat att två av de tre algoritmvarianterna har lyckats tämligen väl med att komma närmare det mål som sattes upp som exekveringstid men inga närmare slutsatser har kunnat dras kring vilka parametrar som påverkat dessa varianters effektivitet.</p>

<p>Artificiella neuronnät (ANN), som tränas för att approximera ett problem, använder träningsdata från problemdomänen. Då denna mängd träningsdata kan vara ofullständig behövs det en analysmetod som visar hur nätverket uppför sig. En sådan analysmetod är invertering av nätverket. Invertering innebär att data som ger ett specifikt resultat i nätverket identifieras. Dessa resultat kan ge exempel som visar på brister eller felaktigheter i nätverket. Det här projektet använder ett ANN som ska klassificera handskrivna siffror. Resultatet från inverteringen visas för en "expertpanel". Panelen får avgöra vilka exempel som inte ska anses vara siffror. De utsorterade exemplen används sedan i en ny mängd träningsdata i syfte att förbättra nätverkets förmåga att klassificera de handskrivna siffrorna. Resultaten från experimentet visar att nätverkets klassificeringsförmåga inte skiljer sig nämnvärt från ett traditionellt tränat ANN. Dock kan det finnas egenheter hos nätverket som har förbättrats och som inte har identifierats i det här projektet.</p>

Testmetoder för tidskritiska applikationer har ofta bara omfattat statiska testmetoder där slutsatser kring applikationens exekveringstider och beteende dras utifrån studier av programkod och underliggande hårdvara. I detta arbete undersöks en dynamisk testmetod för framtagning av indata som med framgång använts i tidigare arbeten för bestämning av extrema exekveringstider hos applikationer. Detta arbete utvärderar tre varianter av denna testmetod för att försöka finna indata till applikationer som kan ge en inom ramen för applikationens möjligheter godtycklig exekveringstid. Detta för att förbättra möjligheterna att styra testning av denna typ av applikationer. Arbetet har visat att två av de tre algoritmvarianterna har lyckats tämligen väl med att komma närmare det mål som sattes upp som exekveringstid men inga närmare slutsatser har kunnat dras kring vilka parametrar som påverkat dessa varianters effektivitet.

Artificiella neuronnät (ANN), som tränas för att approximera ett problem, använder träningsdata från problemdomänen. Då denna mängd träningsdata kan vara ofullständig behövs det en analysmetod som visar hur nätverket uppför sig. En sådan analysmetod är invertering av nätverket. Invertering innebär att data som ger ett specifikt resultat i nätverket identifieras. Dessa resultat kan ge exempel som visar på brister eller felaktigheter i nätverket. Det här projektet använder ett ANN som ska klassificera handskrivna siffror. Resultatet från inverteringen visas för en "expertpanel". Panelen får avgöra vilka exempel som inte ska anses vara siffror. De utsorterade exemplen används sedan i en ny mängd träningsdata i syfte att förbättra nätverkets förmåga att klassificera de handskrivna siffrorna. Resultaten från experimentet visar att nätverkets klassificeringsförmåga inte skiljer sig nämnvärt från ett traditionellt tränat ANN. Dock kan det finnas egenheter hos nätverket som har förbättrats och som inte har identifierats i det här projektet.

Evolutionära algoritmer har visat sig vara effektiva för att utveckla spelnivåer. Dock finns fortfarande ett behov av nivåer som både uppfyller de krav som spelen har, samt att nivåerna som skapas ska vara så olika som möjligt för att uppmuntra upprepade spelomgångar. För att åstadkomma detta kan man använda Novelty Search. Dock saknar Novelty Search funktioner som gör att populationen vill uppfylla de krav som nivåerna ska ha. Arbetet fokuserar därför på att jämföra två Novelty Search baserade algoritmer som båda uppmuntrar kravuppfyllning: Feasible Infeasible Novelty Search (FINS) och Pareto based Multi-objective evolutionary algorithm (PMOEA) med två mål: krav och Novelty Search. Studien jämför algoritmerna utifrån tre värden: hur stor andel av populationen som följer de ställda kraven, hur bra dessa individer är på att lösa ett nivårelaterat problem samt diversiteten bland dessa individer. Utöver PMOEA och FINS implementeras även en Novelty Search algoritm och en traditionell evolutionär algoritm. Tre experiment genomförs där nivåernas storlek och antalet krav varierade. Resultatet visar att PMOEA var bättre på att skapa fler individer som följde alla kraven och att dessa individer överlag var bättre på att optimera lösningar än vanlig Novelty Search och FINS. Dock hade FINS högre diversitet bland individerna än alla algoritmerna som testades. Studiens svaghet är att resultatet är subjektivt till algoritmernas uppsättning i artefakten, som sådan borde framtida arbeten fokusera på att utforska nya uppsättningar för att generalisera resultatet.

Scania has been working with statistics for a long time but has invested in becoming a data driven company more recently and uses data science in almost all business functions. The algorithms developed by the data scientists need to be optimized to be fully utilized and traditionally this is a manual and time consuming process. What this thesis investigates is if and how well evolutionary algorithms can be used to automate the optimization process. The evaluation was done by implementing and analyzing four variations of genetic algorithms with different levels of complexity and tuning parameters. The algorithm subject to optimization was XGBoost, a gradient boosted tree model, applied to data that had previously been modelled in a competition. The results show that evolutionary algorithms are applicable in finding good models but also emphasizes the importance of proper data preparation. / Scania har länge jobbat med statistik men har på senare år investerat i att bli ett mer datadrivet företag och använder nu data science i nästan alla avdelningar på företaget. De algoritmer som utvecklas av data scientists måste optimeras för att kunna utnyttjas till fullo och detta är traditionellt sett en manuell och tidskrävade process. Detta examensarbete utreder om och hur väl evolutionära algoritmer kan användas för att automatisera optimeringsprocessen. Utvärderingen gjordes genom att implementera och analysera fyra varianter avgenetiska algoritmer med olika grader av komplexitet och trimningsparameterar. Algoritmen som var målet för optimering var XGBoost, som är en gradient boosted trädbaserad modell. Denna applicerades på data som tidigare hade modellerats i entävling. Resultatet visar att evolutionära algoritmer är applicerbara i att hitta bra modellermen påvisar även hur fundamentalt det är att arbeta med databearbetning innan modellering.

Association rule hiding (ARH) is the process of modifying a transaction database to prevent sensitive patterns (association rules) from discovery by data miners. An optimal ARH technique successfully hides all sensitive patterns while leaving all nonsensitive patterns public. However, in practice, many ARH algorithms cause some undesirable side effects, such as failing to hide sensitive rules or mistakenly hiding nonsensitive ones. Evaluating the utility of ARH algorithms therefore involves measuring the side effects they cause. There are a wide array of ARH techniques in use, with evolutionary algorithms in particular gaining popularity in recent years. However, previous research in the area has focused on incremental improvement of existing algorithms. No work was found that compares the performance of ARH algorithms without the incentive of promoting a newly suggested algorithm as superior. To fill this research gap, this project compares three ARH algorithms developed between 2019 and 2022—ABC4ARH, VIDPSO, and SA-MDP— using identical and unbiased parameters. The algorithms were run on three real databases and three synthetic ones of various sizes, in each case given four different sets of sensitive rules to hide. Their performance was measured in terms of side effects, runtime, and scalability (i.e., performance on increasing database size). It was found that the performance of the algorithms varied considerably depending on the characteristics of the input data, with no algorithm consistently outperforming others at the task of mitigating side effects. VIDPSO was the most efficient in terms of runtime, while ABC4ARH maintained the most robust performance as the database size increased. However, results matching the quality of those in the papers originally describing each algorithm could not be reproduced, showing a clear need for validating the reproducibility of research before the results can be trusted. / ”Association rule hiding”, ungefär ”döljande av associationsregler” – hädanefter ARH – är en process som går ut på att modifiera en transaktionsdatabas för att förhindra att känsliga mönster (så kallade associationsregler) upptäcks genom datautvinning. En optimal ARH-teknik döljer framgångsrikt alla känsliga mönster medan alla ickekänsliga mönster förblir öppet tillgängliga. I praktiken är det dock vanligt att ARH-algoritmer orsakar oönskade sidoeffekter. Exempelvis kan de misslyckas med att dölja vissa känsliga regler eller dölja ickekänsliga regler av misstag. Evalueringen av ARH-algoritmers användbarhet inbegriper därför mätning av dessa sidoeffekter. Bland det stora urvalet ARH-tekniker har i synnerhet evolutionära algoritmer ökat i popularitet under senare år. Tidigare forskning inom området har dock fokuserat på inkrementell förbättring av existerande algoritmer. Ingen forskning hittades som jämförde ARH-algoritmer utan det underliggande incitamentet att framhäva överlägsenheten hos en nyutvecklad algoritm. Detta projekt ämnar fylla denna lucka i forskningen genom en jämförelse av tre ARH-algoritmer som tagits fram mellan 2019 och 2022 – ABC4ARH, VIDPSO och SA-MDP – med hjälp av identiska och oberoende parametrar. Algoritmerna kördes på sex databaser – tre hämtade från verkligheten, tre syntetiska av varierande storlek – och fick i samtliga fall fyra olika uppsättningar känsliga regler att dölja. Prestandan mättes enligt sidoeffekter, exekveringstid samt skalbarhet (dvs. prestation när databasens storlek ökar). Algoritmernas prestation varierade avsevärt beroende på indatans egenskaper. Ingen algoritm var konsekvent överlägsen de andra när det gällde att minimera sidoeffekter. VIDPSO var tidsmässigt mest effektiv, medan ABC4ARH var mest robust vid hanteringen av växande indata. Resultat i nivå med de som uppmättes i forskningsrapporterna som ursprungligen presenterat varje algoritm kunde inte reproduceras, vilket tyder på ett behov av att validera reproducerbarheten hos forskning innan dess resultat kan anses tillförlitliga.

Proper modelling of the gravitational fields of irregularly shaped asteroids and comets is an essential yet challenging part of any spacecraft visit and flyby to these bodies. Accurate density representations provide crucial information for proximity missions, which rely heavily on it to design safe and efficient trajectories. This work explores using a spacecraft swarm to maximise the measured gravitational signal in a hypothetical mission around the comet 67P/Churyumov-Gerasimenko. Spacecraft trajectories are simultaneously computed and evaluated using a high-order numerical integrator and an evolutionary optimisation method to maximise overall signal return. The propagation is based on an open-source polyhedral gravity model using a detailed mesh of 67P/C-G and considers the comet’s sidereal rotation. We compare performance on various mission scenarios using one and four spacecraft. The results show that the swarm achieved an expected increase in coverage over a single spacecraft when considering a fixed mission duration. However, optimising for a single spacecraft results in a more effective trajectory. The impact of dimensionality is further studied by introducing an iterative local search strategy, resulting in a generally improved robustness for finding efficient solutions. Overall, this work serves as a testbed for designing a set of trajectories in particularly complex gravitational environments, balancing measured signals and risks in a swarm scenario. / En korrekt modellering av de gravitationsfält som uppstår runt irreguljärt formade asteroider och kometer är en avgörande och utmanande del för alla uppdrag till likartade himlakroppar. Exakta densitetsrepresentationer tillhandahåller viktig information för att säkerställa säkra och effektiva rutter för särsilt närgående rymdfarkoster. I denna studie utforskar vi användningen av en svärm av rymdfarkoster för att maximera den uppmätta gravitationssignalen i ett hypotetisk uppdrag runt kometen 67P/Churyumov-Gerasimenko. Rymdfarkosternas banor beräknas och utvärderas i parallella scheman med hjälp av en högre ordningens numerisk integration och en evolutionär optimeringsmetod i syfte att maximera den totala uppmätta signalen. Beräkningarna baseras på en öppen källkod för en polyhedral gravitationsmodell som använder ett detaljerat rutnät av triangulära polygoner för att representera 67P/C-G och beaktar kometens egna rotation. Vi jämför sedan prestanden för olika uppdragscenarier med en respektive fyra rymdfarkoster. Resultaten visar att svärmen uppnådde en förväntad ökning i täckning jämfört med en enskild rymdfarkost under en fast uppdragsvaraktighet. Dock resulterar optimering för en enskild rymdfarkost i en mer effektiv bana. Påverkan av dimensionshöjningen hos oberoende variabler studeras vidare genom att introducera en iterativ lokal sökstrategi, vilket resulterar i en generellt förbättrad robusthet samt effektivare lösningar. Sammantaget fungerar detta arbete som en testbädd för att studera och utforma rymdfarkosters banor i särskilt komplexa gravitationsmiljöer, samt för att balansera uppmätta signaler och risker i ett svärmscenario.

The introduction of initial margin requirements for non-cleared OTC derivatives has made it possible to optimize initial margin when considering a network of trading participants. Applying CMA-ES, this thesis has explored a new method to handle the nonlinear constraints present in the initial margin optimization problem. The idea behind the method and the research question in this thesis are centered around leveraging data created during optimization. Specifically, by creating a linear approximation of the feasible region using support vector machines and in turn applying a repair strategy based on projection. The hypothesis was that by repairing solutions an increase in convergence speed should follow. In order to answer the research question, a reference method was at first created. Here CMA-ES along with feasibility rules was used, referred to as CMA-FS. The proposed method of optimization data leveraging (ODL) was then appended to CMA-FS, referred to as CMA-ODL. Both algorithms were then applied to a single initial margin optimization problem 100 times each with different random seeds used for sampling in the optimization algorithms. The results showed that CMA-ODL converged significantly faster than CMA-FS, without affecting final objective values significantly negatively. Convergence was measured in terms of iterations and not computational time. On average a 5% increase in convergence speed was achieved with CMA-ODL. No significant difference was found between CMA-FS and CMA-ODL in terms of the percentage of infeasible solutions generated. A reason behind the lack of a reduction in violations can be due to how ODL is implemented with the CMA-ES algorithm. Specifically, ODL will lead to a greater number of feasible solutions being available during recombination in CMA-ES. Although, due to the projection, the solutions after projection are not completely reflective of the actual parameters used for that generation. The projection should also bias the algorithm towards the boundary of the feasible region. Still, the performative difference in terms of convergence speed was significant. In conclusion, the proposed boundary constraint handling method increased performance, but it is not known whether the method has any major practical applicability, due to the restriction to only considering the number of iterations and not the computational time. / Införandet av initial margin för non-cleared OTC derivatives har gjort det möjligt att optimera initial margin när ett flertal marknadsdeltagare tas till hänsyn. Denna uppsats har applicerat CMA-ES och specifikt undersökt en ny metod för hantering av de icke-linjära bivillkoren som uppstår när initial margin optimeras. Idén bakom metoden och forskningsfrågan i rapporten bygger på att utnyttja data som generas vid optimering. Detta görs specifikt genom att den icke-linjära tillåtna regionen approximeras linjärt med support vector machines. Därefter används en reparationsstrategi bestående av projicering för att reparera otillåtna lösningar. Hypotesen i uppsatsen var att genom att reparera lösningar så skulle konvergenshastigheten öka. För att svara på forskningsfrågan så togs en referensmetod fram, där CMA-ES och feasibility rules användes för att hantera icke-linjära bivillkor. Denna version av CMA-ES kallades CMA-FS. Sedan integrerades den nya metoden med CMA-FS, denna version kallades för CMA-ODL. Därefter så applicerades båda algoritmer 100 gånger på ett initial margin optimeringsproblem, där olika seeds användes för generering av lösningar i algoritmerna. Resultaten visade att CMA-ODL konvergerade signifikant snabbare än CMA-FS utan att påverka optimeringsresultatet negativt. Med CMA-ODL så ökade konvergenshastigheten med ungefär 5%. Konvergens mättes genom antal iterationer och inte beräkningstid. Ingen signifikant skillnad mellan CMA-ODL och CMA-FS observerades när de jämfördes med avseende på mängden icke-tillåtna lösningar genererade. En anledning varför ingen skillnad observerades är hur den nya metoden var integrerad med CMA-ES algoritmen. Den tilltänkta metoden leder till att fler tillåtna lösningar är tillgängliga när CMA-ES ska bilda nästa generation men eftersom lösningar projiceras så kommer dom inte att reflektera dom parametrar som användes för att faktiskt generera dom. Projiceringen leder också till att fler lösningar på randen av det tillåtna området kommer att genereras. Sammanfattningsvis så observerades fortfarande en signifikant ökning i konvergenshastighet för CMA-ODL men det är oklart om algoritmen är praktiskt användbar p.g.a. restriktionen att enbart betrakta antalet iterationer och inte total beräkningstid.