Genetic Algorithm for Ship Landing

Introduction

This project followed on from my Chess AI to further develop my skills with game AI.

To do so, I worked on a genetic algorithm whereby the goal was to find the fastest route for a ship to safely land on a platform. 

A genetic algorithm was used to evaluate a large range of possible solutions for good solutions. Genetic algorithms iteratively converge on a solution to a problem in a similar manner to natural selection and evolution, incrementally finding local best solutions to gradually uncover a global best solution.

The genetic algorithm made use of:

• Chromosomes for each ship, defined as an array of actions to move the ship in the four cardinal directions

• Fitness calculation

• Selection

• Crossover

• Mutation

Fitness and Selection

After a run of the algorithm, all results must be parsed for a score based on user define parameters (the goal). To determine this score, a ships end angle, distance from the landing pad, survival time and if they had landed safely were all taken into account to score each set of chromosomes.

Equally, those that landed and those that successfully landed were given appropriate bonuses to their scores, ensuring the algorithms favoured those that landed, preventing the algorithm from targeting ships that had a low survival time because they had crashed quickly.

Using these scores, the algorithms makes use of both Tournament and Elite selection.

Tournament selection involves selection roughly 10% of the chromosomes and then selecting the highest scoring chromosome from that selection. This chromosome would be sent through to the next round and the process would be repeated until the total chromosomes for the next round were the same as the total selected from.

This allows some lower scoring solutions through, preventing early convergence.

Elite selection is where the highest scoring chromosomes are automatically put through the the next round without undergoing the crossover or mutation stages. However, with tournament selection, duplicates may be put through to undergo crossover and mutation as well.

This method ensures local best solutions are not lost. However, the elite pool was limited to 5% of the total chromosomes, where the pool is only filled on finding a successful solution. This ensured against early convergence.

Rank selection was not used as the removal of low-ranking chromosomes can lead to convergence on local best solutions, or reduce the diversity to a stage where the algorithm cannot converge on a successful solution. 

Crossover and Mutation

Crossover includes mixing chromosomes to create new chromosomes to be used on the next run of the program. Uniform crossover was used, whereby for a selected pair of chromosomes, actions of parent two are selected 30% of the time.

Finally, the chromosomes undergo mutation, where randomly selected actions within the chromosome are swapped out for a random action. This was done at a rate of 5%, allowing for a wide range of possible solutions while not losing any evolved solutions.

Once the majority of chromosomes in a a run are successful, the algorithm skips the mutation stage. This is because of the high (5%) mutation rate, which prevented convergence.

What I Learned

During this project i was able to build upon my previous chess AI work to build an algorithm capable of finding a solution to a problem given constraints and a clear goal.

Were I to return to this project, I would experiment with other crossover techniques to determine if other methods were more efficient in producing the global best solution.