search

ahmedfgad / GeneticAlgorithmPython

Source code of PyGAD, a Python 3 library for building the genetic algorithm and training machine learning algorithms (Keras & PyTorch).
https://pygad.readthedocs.io
BSD 3-Clause "New" or "Revised" License
1.89k stars 464 forks source link

Variable population size #224

Open timorichert opened 1 year ago

timorichert commented 1 year ago

Dear PyGAD team, Thinking how evolutionary algorithms work, I was wondering if it could make sense to start off with a large population, and reduce the population size over time, to start with more population diversity, and narrowing it down as the algorithm gets closer to the optimum. Making the input parameter sol_per_pop a list to be able to define population size for each generation could be a straightforward implementation. Do you think this is something worth considering? All the best, Timo Richert

ahmedfgad commented 1 year ago

Thanks @timorichert for your suggestion.

At the moment, we expect a fixed-size population. This should be considered for support in the future.

timorichert commented 1 year ago

Thanks for your consideration @ahmedfgad.

vibeeshan025 commented 1 year ago

Just my 2 cents, Though I have extensive experience in implementing my own GA implementations, I am new to your library. Does it really make sense to implement this? Other than a few performance improvements, are we really going to get any advantage in implementing this? Moreover doesn't it lead to more local max solutions if we reduce the population size over time?

@timorichert could you please let us know a good use case for this? I am just curious to know.

ahmedfgad commented 1 year ago

Just my 2 cents, Though I have extensive experience in implementing my own GA implementations, I am new to your library. Does it really make sense to implement this? Other than a few performance improvements, are we really going to get any advantage in implementing this? Moreover doesn't it lead to more local max solutions if we reduce the population size over time?

@timorichert could you please let us know a good use case for this? I am just curious to know.

@vibeeshan025, one motivation I am considering to implement this feature is to dynamically change the parameters over time in case there is little or no improvements. This does not only apply to the population size but to the other parameters. For example, the GA may start with 5 solutions per population. If there is no improvement over K consecutive generations, then the population size increases from 5 to 10. This enables the GA to explore more solutions quickly.

Note sure if @timorichert have something else!

timorichert commented 1 year ago

My thinking was that in the first generation, the population size could be chosen large, simply to cover a large variation of genes and associated fitness.

Many solutions with bad fitness would drop out when reducing the population size to an X times smaller one, and the subsequent optimization over the remaining generations would be much quicker due to the reduced size.

It could potentially improve the chance to find the global maximum by increasing the likelihood to have a solution nearby in the initial population.

I guess it really depends on the optimization problem whether or not this makes sense!?

ahmedfgad commented 1 year ago

Please check this example to change the population size during runtime: https://github.com/ahmedfgad/GeneticAlgorithmPython/blob/master/examples/example_dynamic_population_size.py

juan11iguel commented 6 months ago

Variable population size is a topic of discussion in literature [1]:

In a traditional genetic algorithm (GA), the population size is set by the user to a fixed value at the beginning of the search and remains constant through the entire run. Having to specify this initial parameter value is problematic in many ways. If it is too small the GA may not be able to reach high quality solutions. If it is too large the GA spends unnecessary computational resources. Finding an adequate population size is a difficult task. It has been shown, both theoretically and empirically, that the optimal size is something that differs from problem to problem. Moreover, some researchers have observed that at different stages of a single run, different population sizes might be optimal.

image

It would be interesting to consider adding one or more dynamic population strategies to the library, as far as I know, not even MATLAB's implementation has it.

[1] Lobo, Fernando G., and Cláudio F. Lima. “Adaptive Population Sizing Schemes in Genetic Algorithms.” In Parameter Setting in Evolutionary Algorithms, edited by Fernando G. Lobo, Cláudio F. Lima, and Zbigniew Michalewicz, 185–204. Studies in Computational Intelligence. Berlin, Heidelberg: Springer, 2007. https://doi.org/10.1007/978-3-540-69432-8_9.