Kävelyn oppiminen geneettisellä algoritmilla

Abstract

Insinöörityössä oli tarkoituksena perehtyä geneettisten algoritmien toimintaan ja ratkaista niiden avulla sopiva optimointiongelma. Aiheeksi valittiin nelijalkaisen kävelijän kävelyn koneoppiminen geneettisellä algoritmilla. Projekti toteutettiin käyttäen Unity 3D:tä kävelijän ja ympäristön luontiin, ja projektin ohjelmointi toteutettiin C#-kielellä.

Työssä perehdyttiin geneettisten algoritmien historiaan ja niiden yhteyteen evoluutioteoriaan. Evoluutioteoria on perusta geneettisille algoritmeille, joiden ongelmanratkaisumenetelminä käytettiin evoluutiosta tuttuja käsitteitä, kuten geeni, genomi, kromosomi, risteytys, mutaatio ja populaatio.

Työ aloitettiin tutkimalla, kuinka kävelijän sai Unityssa toteutettua. Kävelijän luonnin jälkeen sitä liikuttamaan ohjelmoitiin moottori. Moottori sisälsi muuttujat, joista lopulta muodostui geneettisen algoritmin muovattava kromosomi, eli yksilö ja yksi potentiaalinen ongelman ratkaisu. Geneettisen algoritmin toteutuksessa luotiin ensin alkupopulaatio, jonka yksilöt pisteytettiin ja sitten yhdisteltiin seuraavan populaation luomiseksi. Lisäksi uudet yksilöt altistettiin mahdolliselle mutaatiolle. Uuden populaation iteraatioita luotiin, kunnes tarpeeksi hyvä yksilö ilmaantui tai sukupolvien maksimimäärä tuli täyteen.

Käyttäjäkokemuksen parantamiseksi luotiin populaation parasta yksilöä seuraava kamera, jonka yläreunassa esitettiin simulaation metriikoita. Lisäksi luotiin alkuvalikko, josta käyttäjäpystyi asettamaan simulaatiolle raja-arvoja tai testisimulaatiolle simulaatiosta saatuja ratkaisuja.

Työssä tuli vastaan ongelmia, joista huolimatta projekti saatiin onnistuneesti päätökseen ja saatiin toimiva, geneettistä algoritmia hyödyntävä simulaattori kävelyn koneoppimiselle. Simulaattorin käyttöliittymä mahdollisti ohjelman helppokäyttöisyyden. Tämä projekti antaa ohjeistavan suunnan vastaavanlaisille projekteille, joita tehtäessä voi hyödyntää tässä työssä esitettyjä ongelmia ja kehityskohtia paremman toiminnan saavuttamiseksi.

The objective of this thesis was to familiarize oneself with genetic algorithms. Find out how they work and solve a suitable optimization problem using genetic algorithm. Machine learned walking for a quadruped walker with genetic algorithm was selected as a subject of this thesis. The project was implemented with walkers and environment created with Unity 3D and C# as the programming language.

The history of genetic algorithms and the connection to evolution theory was addressed in this thesis. Evolution theory is the basis of genetic algorithms for which concepts like gene, genome, chromosome, crossover, mutation and population were methods of the problem solving.

The project was started by studying how the walker could be created in Unity. A motor was programmed to move the walker after its creation method was solved. The motor included variables from which an individual, chromosome or potential solution for the problem was formed for the use of genetic algorithm. In the implementation of genetic algorithm, first thing was to create initial population. The individuals of this population were evaluated for their fitness and then recombined to create next population. In addition, the individuals of new population were exposed to a possible mutation. The iterations for creating new population were carried out until an individual with good enough fitness was emerged or the maximum number of generations were reached.

To improve user experience a camera was created to follow the current best individual and also metrics were presented on top of the screen. In addition, a start menu was programmed from which user could set limits for the simulation or input results for a test simulation environment. User interface enabled accessibility of the simulator.

Several problems were encountered in the project but nevertheless the project was completed successfully. As a result, a functional simulator using genetic algorithm was created. This project can be used as a basis for similar projects and make use for encountered problems in their development.