Cargando…
A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes
Genetic algorithms (GAs) have been used to find efficient solutions to numerous fundamental and applied problems. While GAs are a robust and flexible approach to solve complex problems, there are some situations under which they perform poorly. Here, we introduce a genetic algorithm approach that is...
Autores principales: | , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Public Library of Science
2013
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3818328/ https://www.ncbi.nlm.nih.gov/pubmed/24223800 http://dx.doi.org/10.1371/journal.pone.0078401 |
_version_ | 1782478172237856768 |
---|---|
author | Melo, Hygor Piaget M. Franks, Alexander Moreira, André A. Diermeier, Daniel Andrade, José S. Amaral, Luís A. N. u. n. e. s. |
author_facet | Melo, Hygor Piaget M. Franks, Alexander Moreira, André A. Diermeier, Daniel Andrade, José S. Amaral, Luís A. N. u. n. e. s. |
author_sort | Melo, Hygor Piaget M. |
collection | PubMed |
description | Genetic algorithms (GAs) have been used to find efficient solutions to numerous fundamental and applied problems. While GAs are a robust and flexible approach to solve complex problems, there are some situations under which they perform poorly. Here, we introduce a genetic algorithm approach that is able to solve complex tasks plagued by so-called ''golf-course''-like fitness landscapes. Our approach, which we denote variable environment genetic algorithms (VEGAs), is able to find highly efficient solutions by inducing environmental changes that require more complex solutions and thus creating an evolutionary drive. Using the density classification task, a paradigmatic computer science problem, as a case study, we show that more complex rules that preserve information about the solution to simpler tasks can adapt to more challenging environments. Interestingly, we find that conservative strategies, which have a bias toward the current state, evolve naturally as a highly efficient solution to the density classification task under noisy conditions. |
format | Online Article Text |
id | pubmed-3818328 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2013 |
publisher | Public Library of Science |
record_format | MEDLINE/PubMed |
spelling | pubmed-38183282013-11-09 A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes Melo, Hygor Piaget M. Franks, Alexander Moreira, André A. Diermeier, Daniel Andrade, José S. Amaral, Luís A. N. u. n. e. s. PLoS One Research Article Genetic algorithms (GAs) have been used to find efficient solutions to numerous fundamental and applied problems. While GAs are a robust and flexible approach to solve complex problems, there are some situations under which they perform poorly. Here, we introduce a genetic algorithm approach that is able to solve complex tasks plagued by so-called ''golf-course''-like fitness landscapes. Our approach, which we denote variable environment genetic algorithms (VEGAs), is able to find highly efficient solutions by inducing environmental changes that require more complex solutions and thus creating an evolutionary drive. Using the density classification task, a paradigmatic computer science problem, as a case study, we show that more complex rules that preserve information about the solution to simpler tasks can adapt to more challenging environments. Interestingly, we find that conservative strategies, which have a bias toward the current state, evolve naturally as a highly efficient solution to the density classification task under noisy conditions. Public Library of Science 2013-11-05 /pmc/articles/PMC3818328/ /pubmed/24223800 http://dx.doi.org/10.1371/journal.pone.0078401 Text en © 2013 Melo et al http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited. |
spellingShingle | Research Article Melo, Hygor Piaget M. Franks, Alexander Moreira, André A. Diermeier, Daniel Andrade, José S. Amaral, Luís A. N. u. n. e. s. A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes |
title | A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes |
title_full | A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes |
title_fullStr | A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes |
title_full_unstemmed | A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes |
title_short | A Solution to the Challenge of Optimization on ''Golf-Course''-Like Fitness Landscapes |
title_sort | solution to the challenge of optimization on ''golf-course''-like fitness landscapes |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3818328/ https://www.ncbi.nlm.nih.gov/pubmed/24223800 http://dx.doi.org/10.1371/journal.pone.0078401 |
work_keys_str_mv | AT melohygorpiagetm asolutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT franksalexander asolutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT moreiraandrea asolutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT diermeierdaniel asolutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT andradejoses asolutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT amaralluisanunes asolutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT melohygorpiagetm solutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT franksalexander solutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT moreiraandrea solutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT diermeierdaniel solutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT andradejoses solutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes AT amaralluisanunes solutiontothechallengeofoptimizationongolfcourselikefitnesslandscapes |