The Digital Darwinism: How Genetic Algorithms Mimic Evolution

I remember watching this Bill Nye episode as a child, talking about dinosaurs and how they evolved. I was mesmerized by the intricate dance of evolution and how a lizard could become a chicken. The sheer complexity of life, born from simple principles of variation and selection, seemed almost magical. It wasn't until much later, when I delved into the world of computer science, that I realized this "magic" could be replicated—or at least simulated—through genetic algorithms. These algorithms, inspired by Darwin's theory of natural selection, offer a fascinating glimpse into how computational systems can "evolve" solutions to complex problems.

At its core, a genetic algorithm mimics the process of biological evolution. It starts with a population of potential solutions, each represented as a "chromosome" of data. What data we choose changes based on the requirements of the problem. For an example, for an agent trying to survive, their "chromosomes" can be how many pounds of food a day they need to survive and how tall they are to reach food (they are easier to see by other predators). Nevertheless, these solutions are then subjected to a series of operations that mirror natural selection:

• Selection:
  • Just as in nature, where the "fittest" organisms are more likely to survive and reproduce, genetic algorithms evaluate the fitness of each solution. Those that perform better are more likely to be selected for the next generation. This could be how many days the agent has survived so far.
• Crossover (Mating):
  • Selected solutions are paired up, and their "chromosomes" are combined to create new offspring. This process, analogous to sexual reproduction, allows for the mixing and matching of desirable traits. For our ongoing example, an offspring could take the average of food necessity and height from both of its parents.
• Mutation:
  • Occasionally, random changes are introduced into the offspring's chromosomes. These mutations, like genetic mutations in nature, can introduce new variations and potentially lead to improved solutions. This can just be adding or removing some food necessity or height from the offspring.
• Reproduction:
  • The new generation of solutions, consisting of offspring and mutated individuals, is added onto the old generation. This process is repeated over many generations, gradually refining the population towards better and better solutions.

Once interesting aspect of these algorithms is that certain sets of solutions can become extinct over times. For example, let's say 100 computers play rock paper scissors, half of them learned to always play scissors and half of them learned to always play rock. Every round, every computer randomly matches with another computer. If a computer wins or draws, nothing happens. But if they lose, they die. So if we let them play a few rounds, it's obvious that the computer playing scissors will die out, because they don't have a winning strategy. Rocks will always draw or win in this population, but scissors can only draw or lose. You can see this – --> video <– — to learn more about Natural Selection and Extinction in simulations.

The beauty of genetic algorithms lies in their ability to tackle problems that are difficult or impossible to solve using traditional methods. The Traveling Salesman Problem (video), for example, which involves finding the shortest route that visits a set of cities, is especially challenging. Trying to find a solution for a problem with 5 cities would only need to check 120 solutions, but a problem with 15 cities would need to check 1.3 TRILLION solutions. And for 50 cities, the number of solutions would surpass the number of atoms in 100 TRILLION EARTHS! Genetic algorithms can explore this vast solution space and gradually converge on a near-optimal solution in way less time.

Similarly, in the realm of game playing, genetic algorithms have been used to train AI agents to master complex games like "Jump King." By rewarding agents that make progress and punishing those that fail, the algorithm can "evolve" strategies that would be difficult to program manually.

It's truly remarkable how a few simple rules—selection, crossover, and mutation—can give rise to such complex and intelligent behavior. It's reminiscent of Conway's Game of Life, where simple rules governing the behavior of cells can lead to emergent patterns of incredible complexity. This highlights a fundamental principle of complex systems: that simple rules can give rise to emergent complexity.

One downside that I have noticed is that genetic algorithms can be very computationally expensive. As the solution space grows, so does the amount of computing power required to explore it. This is why many genetic algorithm applications are run on high-performance computing clusters. So if you have a population of algorithms trying to find their way through the maze, the bigger and more complicated you make the maze, the more memory/DNA each algorithm needs to have to possibly solve it. Maybe in the future, quantum computing can help make this technique more feasible for large solution spaces!

Another observation that I have made is that the fitness function is critical to the success of a genetic algorithm. If the fitness function is poorly designed, the algorithm may converge on a suboptimal solution, or fail to converge at all. For example, if you are building a robot to go from point A to point B and you say that the more steps the robot makes the better. But the robot may learn just to walk in place forever and not actually walk toward point B.

• What other real-world problems could be solved using genetic algorithms?
• How might genetic algorithms be used to design more efficient and sustainable systems?
• What are the ethical implications of using genetic algorithms to create intelligent machines?

Explore online simulations of genetic algorithms, or try implementing your own simple genetic algorithm to solve a basic problem. Share your experiences and insights in the comments below!