Although I’ve already done a page on evolutionary algorithms, I recently came across this video, posted on TikTok, by Marc Ordower, who regularly posts maths challenges. This puzzle is a much better demonstration of the kind of optimisation problems where evolutionary algorithms excel, so I thought I would adapt my code to solve this puzzle.
The overall concept is still the same. We start with a population of randomly generated solutions (I’ve used 100), calculate their ‘fitness’ (which in this case is the number of houses which can be reached by road from the entry point, so the higher the value the better in this case), select the best performing 50% of solutions to either breed together, or mutate, into new individuals which then replace the worst performing 50% of the population. This process is then repeated until hopefully, the best solution appears. As with the previous jigsaw example, the resulting solution is not guaranteed to be the optimal as the algorithm and breeding/mutation operations may not be sufficient to make the jump to the global optimal without first making a worse solution which then gets replaced.
The breeding operation, in this case, is to take a randomly sized rectangle of squares from one solution and place it into a random position in another solution. Instead of breeding, there is a small chance that instead a mutation will occur, which in our case means a random square flips either from a road to a house, or from a house to a road. With each of these operations, there is a strong likelihood of the resulting solution being worse, but that just means it will not be selected for breeding and will be replaced in the next generation.
Below is the simulation to play around with. The challenge was to do better than 25, but you can actually do much better than that! I’ve added some options you can change: generations is just to limit the app from carrying on forever, but you may want to increase it if the grid size has been increased; diagonals change if access to a house is possible diagonally from a road. Interestingly, this has a huge effect on the resulting grid. Turned off, the grid tends to organise itself into long straight roads, but with diagonal access turned on you end up with a much more organic looking street plan, and a different result each time.
Note, due to limitations of screen space, this simulation should ideally be viewed on a desktop machine.
