Growing and Shrinking Populations

Genetic Algorithms in Elixir — by Sean Moriarity (67 / 101)

👈 Experimenting with Reinsertion | TOC | Local Versus Global Reinsertion 👉

Genetic algorithms can operate on either fixed or variable population sizes. All of the genetic algorithms you’ve implemented so far have had fixed size populations. The distinction between replacement and reinsertion lies in how the population size is affected. Replacement strategies focus specifically on maintaining a fixed population size — they replace old chromosomes with new ones. Reinsertion strategies focus mainly on inserting new chromosomes into a population — they integrate new chromosomes with old ones. Although you’ll often see the terms used interchangeably, their meanings are slightly different.

If you opt for populations of variable size, you need to consider how fast the size of the population changes. For example, if you have a selection rate of 80% and choose to keep the top 30% of chromosomes every generation, your population will grow by 10% every generation. If you start with a population of 100 chromosomes, your population will have 1.37 million chromosomes by the hundredth generation. You’d notice your algorithm quickly stalls and crashes as it consumes all of the memory on the machine.

Alternatively, if you choose to have a selection rate of 80%, but only keep the top 10% of your chromosomes, your population will shrink by 10% every generation. If you start with a population of 100 chromosomes, your population will only have 1 chromosome by the fortieth generation. You’d stop making progress at that point, and more than likely won’t have converged on a good solution.

Your population size is subject to exponential growth or exponential decay if you choose to grow or shrink them according to selection and survival rates. The following graph illustrates how population sizes grow or shrink according to exponential growth or decay:

As you can see, it’s infeasible to maintain a constant rate of growth or decay and maintain progress in your genetic algorithm. Fortunately, there are a few solutions.

One solution is to constrain the growth rate of your population based on the size of your population. If you don’t want your population to get any larger than 1000 chromosomes, you can ensure that both selection and survival rates coincide with a 0% growth rate once your population hits 1000 chromosomes.

Another solution is to alternate growing and shrinking of the population. With odd generations your population grows, and with even populations your population shrinks. This ensures your population size always falls in some reasonable size window.

One final solution is to subject your population to constant growth or decay rather than exponential growth or decay. Rather than grow by 10% each generation, you can choose to explicitly grow by ten chromosomes every generation.

Of course, you can always come up with your own unique solution to addressing exponential growth or decay in population sizes. Most of the populations you work with will function fine with fixed population sizes. In the event you need to vary the size of your population, you’ll need to consider these factors.

👈 Experimenting with Reinsertion | TOC | Local Versus Global Reinsertion 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.