Joel Whittle

Computing and Digital Technologies (B&FC) | Year 3 | Degree: Software Engineering (Game Development)

Exploring a Bigger Search Space through Genetic Evolution

Linear regression-based training techniques dominate the state-of-the-art machine learning of neural networks due to the comparatively little computing resources required in comparison to genetic algorithm-based training. However, linear regression-based training is largely restricted in its available search space, tending to converge on a local optimum.

With improvements in technology, genetic algorithm-oriented solutions are becoming increasingly viable, having the potential to explore wider searcher spaces. However, these algorithms are often suspect to convergent populations, limiting their effectiveness. Genetic algorithms typically diversify populations through mutation, however Moriarty and Miikkulainen (1997, p. 376) disputes the effectiveness of mutation operators alone.

Many methodologies mitigate population convergence through techniques designed to insert additional variance in the population. Stanley and Miikkulainen (2002) devised the NEAT methodology, utilising speciation and fitness sharing to explore a larger problem space. This study aims to evaluate speciation by employing NEAT to evolve populations of AI agents with varying levels of speciation. Each population’s fitness and dominance will be benchmarked as they compete in a simulated environment. This study expects to confirm that speciation has the potential to discover more optimal solutions at the expense of decreasing the initial learning gradient. This could contribute to considerations of speciation in future algorithms.

Joel Whittle

More information

Joel Whittle

Computing and Digital Technologies (B&FC) | Year 3 | Degree: Software Engineering (Game Development)

Exploring a Bigger Search Space through Genetic Evolution

References

Google Play (2013) Flappy Bird. [Game] Android. California: Google Play. Stanley, K. Miikkulainen, R. (2002) ‘Evolving Neural Networks through Augmenting Topologies’, Evolutionary Computation, Volume 10, pp.99-127. Unity Technologies. (2021) Unity Real-Time Development Platform | 3D. 2D. VR & AR Engine. Available at: https://unity.com/ (Accessed: 28/02/2021).

Conclusion

With researchers suggesting that neuroevolution will become increasingly viable with improvements in technology, it is prudent to further investigate such methodologies in an effort to further refine them. This research demonstrates how multiple unique solutions to a single problem may be discovered by simulating natural evolution and utilising techniques such as speciation to slow the rate at which populations converge. There are incalculable use cases where the proper application of machine learning may utlimately benefit humanity.

Acknowledgements

Special thanks to Luke Brockbank, Christopher Willits and Lee Holroyd, whose guidance and tutelage during the course of this research has been instrumental. In addition, a special thanks to Dong Nguyen, developer of Flappy Bird for providing inspiration.

There was minimal difference in fitness between speciation thresholds, with each population able to rapidly produce high performant agents.

However, the implementation of speciation consistently allowed for several unique solutions to be discovered.

Furthermore, this research demonstrates how species which were initially considered weak performing, may evolve to be performant if given the oppurtunity.

Analysis

The above describes how two parent Genomes are combined to generate a child Genome. The shared connections (according to Innovation IDs) of the highest performing parent are passed on to the child, in addition to any Excess or Disjoint genes.

The above details how a neural network Phenotype may be generated from a Genome. The topology of the network is inferred from the encoded connection data. Each connection is assigned an Innovation ID on creation. This is to allow the algorithm to consider the compatability between topologies.

The Fitness Sharing equation penalises the fitness of individuals who belong to a populous species. When combined with speciation, these equations slow the convergence of a population towards a local optimum.

Introduction

This research aims to explore how genetic evolution and biology may inspire algorithms to explore a larger search space in an effort to discover solutions to problems. This is in an effort to improve upon current state-of-the-art machine learning techniques which rely on linear regression or backwards propagation to train models. Whilst these techniques may provide performant solutions with speed compared to genetic algorithm based techniques, they have been observed to be limited in their ability to explore a large search space for a solution, thus restricting their potential.

NEAT is a genetic evolution inspired machine learning algorithm which utilises concepts seen in nature such as sexual and asexual reproduction, genetic mutations and survival of the fittest to evolve solutions to problems. In addition, it utilises techniques known as Speciation and Fitness sharing to slow the convergance of a population, increasing the potential that mutltiple unique performant solutions may be discovered. Genetic evolution based techniques are able to insert diversity into a population of models in an effort to explore a larger search space. This can be described with a "hill climbing analogy", where the fitness of a model corresponds to it's height on a hill.

Without sufficient diversity, a population is likely to converge around a local optimum

However, with sufficient diversity, a larger search space may be explored, leading to the potential of better performant solutions to be discovered.

The neural networks recieved their input in accordance to their environment. Each agent had three inputs. a - The normalised height of the bird. b - The normalised distance between the bird and the next tunnel. c - The normalised height of the next tunnel. In addition, each neural network had one output node, which when activated, would initiate a "flap". In accordance with the rules of flappy bird, a bird would be considered dead if it collided with the floor, the top of the screen space. or a tunnel. A birds fitness was equal to its lifespan.

The Speciation Delta is calculated by taking the sum of the differences between features of the two parents and multiplying them by a coefficient. In this equation, the difference between the weights of shared connections in addition to the number of Excess and Disjoint genes are considered. Between each generation, the population is categorised into disting species. If the delta between two specimen is less than the speciation threshold, the specimen are considered to be belonging to the same species.

Methodology

This methodology involves the simulation of populations of NEAT (Stanley and Miikkulainen, 2002) agents in a Flappy Bird environment (Google Play, 2013) and benchmarking their performance. Each bird will have a neural network, which aims to emulate the functionality of a rudimentary brain by sending signals through a network of neurons. The neural networks will recieve input related to the environment whilst the output of a birds neural network will determine wether or not it will flap.

This was developed using Unity3D (Unity Technologies, 2021). The simulations were executed with a range of Speciation Thresholds to explore how speciation impacts the population, with the Speciation Threshold being the maximum Speciation Delta between two speciment at which they can be considered members of the same species.

Each population was initialised with randomised neural network brains. After each generation the birds were categorised into colour coded species. Over the course of multiple generations, the populations fitness is expected to improve as they evolve. The highest performing 50% of each species were chosen to become parents of the next generation. The species of new children were selected in a ratio corresponding to each species average fitness. Each gene had a 1% chance to be mutated. There are a range of mutation types, ranging from the enabling/disabling of a connection, the creation of a new connection and the insertion of a new node, in addition to the random altering of connection weights.

Page saved!

Add default layout Add text Add image/symbol Add audio/video

PAUSE AUDIO PAUSE VIDEO