Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
The genetic algorithm consists of 5 phases of which 4 are repeated:
In the selection phase, the number of solutions decreases. How is it avoided to run out of the population before reaching a suitable solution?
There are multiple ways to interpret those steps. The most common standard approaches are
select two parents and produce two offspring; repeat until child population is the same size as parent population, and let the children replace their parents unconditionally (generational GA)
same as the above, but allow a few parents to live on instead of a few children if the parents have higher fitness (elitism)
each iteration, select two parents, produce one child, let the child replace a member of the parent population if it is better (steady state GA)
But there are other ways to go. There's an algorithm called CHC that lets the child population get smaller over time, and when it reaches zero, the algorithm triggers a smart restart. The point is there's no single definition for what makes an evolutionary algorithm. It's up to you to decide how to make something that works well for your problem. When you're a beginner though, it's handy to start from known points, like the three I mentioned above.
It is not true that the number of solutions necessarily decreases during the selection phase (if by solutions you mean the number of individuals in the population). The number of solutions is usually constant, i.e., you can start with $N$ individuals, then, every iteration (or generation), you can e.g. select two individuals from the population (typically, the fittest ones, but you can have some more sophisticated selection criteria), then you merge them to create two new individuals (i.e. crossover), which will then replace (with a certain probability) the two least fit individuals from the current population, so the population's size remains constant.
If you are talking about reaching a local minimum, i.e. none of the solutions in the population are "good enough", then, as someone has already suggested, there are potentially multiple ways to address this issue, such as
The correct approach will probably depend on the context.
This is a more complex question than it might initially seem. A genetic algorithm models a biological process,namely population genetics. No biological population evolves to a single cloned individual, a process in genetic algorithms referred to as premature convergence where the population converges to a single non optimal, though possibly locally optimal, solution. The avoidance of premature convergence or the maintenance of population diversity is an important aspect of the genetic model that is often not well addressed, and one that the five step model you detail definitely does not.
The one operator that will maintain diversity is mutation, since it is a purely random operator. However, what the mutation rate should be is highly argued over. A general consensus is that if each chromosome is of length N then the mutation rate should be 1/N. Likewise, the consensus is that 60% of the population should be replaced in each breeding cycle.
However, these settings do not emerge directly from biological reality and premature convergence remains problematic. A more realistic model is to reflect the fact that in biology resources are finite, and to adjust the fitness of individuals proportionate to the number of similar individuals on the assumption that similar individuals are chasing the same resource. The fitness landscape is thus dynamically warped by the changing distribution of the population. You will still have to retain memory of the fittest solution before adjustment. A common solution is to apply cluster analysis to the population, reducing the individual’s fitness by the size of the cluster to which it is allotted. A seminal paper is by Yin and Germay A Fast Genetic Algorithm with Sharing Scheme Using Cluster Analysis Methods in Multimodal Function Optimization `. The assumption is still made that the population is modelling a single biological species. How diversity does not merely maintain diversity but results in a population dividing into separate reproductively isolated species is a question for another day, and one that divides biologists to the current day.
