4 ms·

I researched GAs / GPs back in the mid-90s (but then went in a different direction). Is there a paper/presentation that embodies the current best practices/thi

by mdda 11y ago

I researched GAs / GPs back in the mid-90s (but then went in a different direction). Is there a paper/presentation that embodies the current best practices/thinking that you could recommend? I'm not trying to be lazy, it's just that there is clearly a lot of retro thinking among the top search results on the net, and it's difficult to separate the wheat from the chaff...

sevensor 11y ago
With the disclaimer that there are different schools of thought, I can give a basic outline, and provide some references. This pertains mainly to optimizing engineering models, which tend to be continuous or mixed integer. GAs are just OK at combinatorial optimization (although GP is pretty nifty, from what I hear about it). * Steady-state: pioneered to the best of my knowledge by Deb's epsilon-MOEA, steady-state algorithms use function evaluations as soon as they are received, rather than waiting for a whole generation to complete. [1] * Multi-objective: Pareto ranking as dominance relation lets us have multiple objectives [2]. This is good because it gives us a whole bunch of solutions at once and lets us decide which one we want, instead of tweaking objectives and constraints to get an idea of the tradeoffs involved. * Epsilon resolution: comes from an idea by Laumanns et al. [3]. We can have more objectives if we don't care about differences below a certain threshold. Otherwise the Pareto front explodes in size. * Restarting: Proposed by Coello-Coello [4] and demonstrated by his micro-GA, restarting helps you get out of local optima. * Better search operators: Binary crossover doesn't work so well, especially for real-valued decision variables. It took some fancy theoretical footwork involving schema theory and domino convergence to support it. There were a lot of new search operators proposed in the late '90s, the best of which seem to be simulated binary crossover (SBX), and polynomial mutation (PM). [5] * Alternatively, the Differential Evolution search operator [6] works really well too. * Better selection operator: tournament selection beats the pants off of the alternatives [7]. Resources: * Dave Hadka's MOEAFramework [8], which includes open-source multi-objective evolutionary algorithm implementations. * Dave Hadka's dissertation [9], which describes a (regrettably patented) MOEA that's kind of a greatest-hits of good MOEA ideas. * Deb's website [10], which includes questionably-licensed algorithm implementations, as well as a number of technical reports. Links. I'm posting raw bibtex because I'm lazy. [1] @article{deb_2005_emoea, author = { Deb, K. and Mohan, M. and Mishra, S}, year = {2005}, title = {Evaluating the $\varepsilon$-domination based multiobjective evolutionary algorithm for a quick computation of Pareto-optimal solutions.}, journal = {Evolutionary Computation Journal}, volume= {13}, number = {4}, pages ={501--525} } [2] @book{goldberg_1989_book, title={Genetic algorithms in search, optimization, and machine learning}, author={Goldberg, D.E.}, year={1989}, publisher={Addison-Wesley Professional} } [3] @article{laumanns_2002_combining, title={Combining convergence and diversity in evolutionary multiobjective optimization}, author={Laumanns, M. and Thiele, L. and Deb, K. and Zitzler, E.}, journal={Evolutionary computation}, volume={10}, number={3}, pages={263--282}, year={2002}, publisher={MIT Press} } [4] @inproceedings{coello_2001_uga, author = {Carlos A Coello Coello and Gregorio Toscano Pulido}, title = {Multi-Objective Optimization Using a Micro-Genetic Algorithm}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001)}, pages = {274--282}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {2001} } [5] @techreport{deb_1994_sbx, author = {Deb, K. and Agrawal, R. B.}, year = 1994, title = {Simulated binary crossover for continuous search space}, number = { Technical Report IITK/ME/SMD-94027}, institution = {Indian Institute of Technology, Kanpur}, address = {Kanpur, UP, India} } [6] @article{storn_1997_de, author = {Storn, R. and Price, K.}, year = 1997, title = {Differential evolution --- a simple and efficient heuristic for global optimization over continuous spaces}, journal = { Journal of Global Optimization}, volume = 11, number = 4, pages = {341--359} } [7] @inproceedings{back_1994_selection, title={Selective pressure in evolutionary algorithms: A characterization of selection mechanisms}, author={B{\"a}ck, Thomas}, booktitle={Proceedings of the First IEEE Conference on Evolutionary Computation}, pages={57--62}, year={1994}, organization={IEEE} } [8] http://moeaframework.org/ http://moeaframework.org/ [9] https://etda.libraries.psu.edu/ https://etda.libraries.psu.edu/ You'll have to search for it, I'm afraid. The site's not responding for me right now. But his dissertation is publicly available on Penn State's ETD site. [10] http://www.iitk.ac.in/kangal/deb.shtml http://www.iitk.ac.in/kangal/deb.shtml edit: formatting
- sevensor 11y ago
  Here's a better link for [9]: https://etda.libraries.psu.edu/search/1/50/31/author/term=hadka https://etda.libraries.psu.edu/search/1/50/31/author/term=ha...
- sevensor 11y ago
  One other thing: for single-objective real-valued problems, CMAES is very strong. https://en.wikipedia.org/wiki/CMA-ES https://en.wikipedia.org/wiki/CMA-ES is a pretty good source.
- dcre 11y ago
  This is great!
deleted 11y ago
[deleted]

by mdda 11y ago

sevensor 11y ago

With the disclaimer that there are different schools of thought, I can give a basic outline, and provide some references. This pertains mainly to optimizing engineering models, which tend to be continuous or mixed integer. GAs are just OK at combinatorial optimization (although GP is pretty nifty, from what I hear about it). * Steady-state: pioneered to the best of my knowledge by Deb's epsilon-MOEA, steady-state algorithms use function evaluations as soon as they are received, rather than waiting for a whole generation to complete. [1] * Multi-objective: Pareto ranking as dominance relation lets us have multiple objectives [2]. This is good because it gives us a whole bunch of solutions at once and lets us decide which one we want, instead of tweaking objectives and constraints to get an idea of the tradeoffs involved. * Epsilon resolution: comes from an idea by Laumanns et al. [3]. We can have more objectives if we don't care about differences below a certain threshold. Otherwise the Pareto front explodes in size. * Restarting: Proposed by Coello-Coello [4] and demonstrated by his micro-GA, restarting helps you get out of local optima. * Better search operators: Binary crossover doesn't work so well, especially for real-valued decision variables. It took some fancy theoretical footwork involving schema theory and domino convergence to support it. There were a lot of new search operators proposed in the late '90s, the best of which seem to be simulated binary crossover (SBX), and polynomial mutation (PM). [5] * Alternatively, the Differential Evolution search operator [6] works really well too. * Better selection operator: tournament selection beats the pants off of the alternatives [7]. Resources: * Dave Hadka's MOEAFramework [8], which includes open-source multi-objective evolutionary algorithm implementations. * Dave Hadka's dissertation [9], which describes a (regrettably patented) MOEA that's kind of a greatest-hits of good MOEA ideas. * Deb's website [10], which includes questionably-licensed algorithm implementations, as well as a number of technical reports. Links. I'm posting raw bibtex because I'm lazy. [1] @article{deb_2005_emoea, author = { Deb, K. and Mohan, M. and Mishra, S}, year = {2005}, title = {Evaluating the $\varepsilon$-domination based multiobjective evolutionary algorithm for a quick computation of Pareto-optimal solutions.}, journal = {Evolutionary Computation Journal}, volume= {13}, number = {4}, pages ={501--525} } [2] @book{goldberg_1989_book, title={Genetic algorithms in search, optimization, and machine learning}, author={Goldberg, D.E.}, year={1989}, publisher={Addison-Wesley Professional} } [3] @article{laumanns_2002_combining, title={Combining convergence and diversity in evolutionary multiobjective optimization}, author={Laumanns, M. and Thiele, L. and Deb, K. and Zitzler, E.}, journal={Evolutionary computation}, volume={10}, number={3}, pages={263--282}, year={2002}, publisher={MIT Press} } [4] @inproceedings{coello_2001_uga, author = {Carlos A Coello Coello and Gregorio Toscano Pulido}, title = {Multi-Objective Optimization Using a Micro-Genetic Algorithm}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001)}, pages = {274--282}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {2001} } [5] @techreport{deb_1994_sbx, author = {Deb, K. and Agrawal, R. B.}, year = 1994, title = {Simulated binary crossover for continuous search space}, number = { Technical Report IITK/ME/SMD-94027}, institution = {Indian Institute of Technology, Kanpur}, address = {Kanpur, UP, India} } [6] @article{storn_1997_de, author = {Storn, R. and Price, K.}, year = 1997, title = {Differential evolution --- a simple and efficient heuristic for global optimization over continuous spaces}, journal = { Journal of Global Optimization}, volume = 11, number = 4, pages = {341--359} } [7] @inproceedings{back_1994_selection, title={Selective pressure in evolutionary algorithms: A characterization of selection mechanisms}, author={B{\"a}ck, Thomas}, booktitle={Proceedings of the First IEEE Conference on Evolutionary Computation}, pages={57--62}, year={1994}, organization={IEEE} } [8] http://moeaframework.org/ http://moeaframework.org/ [9] https://etda.libraries.psu.edu/ https://etda.libraries.psu.edu/ You'll have to search for it, I'm afraid. The site's not responding for me right now. But his dissertation is publicly available on Penn State's ETD site. [10] http://www.iitk.ac.in/kangal/deb.shtml http://www.iitk.ac.in/kangal/deb.shtml edit: formatting

sevensor 11y ago
Here's a better link for [9]: https://etda.libraries.psu.edu/search/1/50/31/author/term=hadka https://etda.libraries.psu.edu/search/1/50/31/author/term=ha...
sevensor 11y ago
One other thing: for single-objective real-valued problems, CMAES is very strong. https://en.wikipedia.org/wiki/CMA-ES https://en.wikipedia.org/wiki/CMA-ES is a pretty good source.
dcre 11y ago
This is great!

deleted 11y ago

[deleted]