The New Turing Omnibus Chapter 16 Genetic Algorithms

Paul Mucur edited this page Feb 3, 2016 · 8 revisions
Clone this wiki locally

The Chapter

We walked through the chapter together, taking the algorithm given in the book and stepping through it on the whiteboard:

We discussed whether the algorithm would always reach the optimum solution given enough time (as this was unclear in the book) but convinced ourselves that it is possible for a genetic algorithm to get stuck in some local maxima. We visualised this using Tom's interactive plot of a genetic algorithm.

We briefly touched on other related techniques such as simulated annealing (and its inspiration from actual metallurgic annealing).

We discussed various applications of genetic algorithms including:

We also discussed crucial differences between "real" genetics and the algorithm particularly around the probabilities of mutation: in the algorithm, all parts have an equal chance of mutation whereas DNA does not have the same property (and certain mutations are not permitted at all).

Show & Tell

Tom demonstrated his interactive plot of a genetic algorithm which we modified to explore the second problem in the chapter (attempting to reach a "theory of genetic algorithms") and understand the behaviour of the algorithm.

Thanks to James for doing these modifications and for his impressive rapid-fire clicking skills which let us explore the algorithm's "hill climbing" behaviour.

(We also had fun with JavaScript numbers and their precision.)

Chris then demonstrated his visualisation of a genetic algorithm solving the Travelling Salesman Problem:

Retrospective

  • We discussed the relative lack of content in this chapter but agreed that the tangents (particularly around the applications of this technique) still made the meeting valuable;
  • We noted the lack of shepherd in this meeting had a detrimental effect;
  • We debated whether we should take a more practical approach in the meeting but also felt theory-heavy chapters were valuable too;
  • Overall, we attributed the lack of preparation and energy to it being our first meeting after the Christmas period;
  • We decided not to make any changes to our format or abandon the book.

Thanks

Thanks to Leo and Geckoboard for hosting and to Tom and Chris for their visualisation work and to James for driving the laptop.