Limits...
A solution to the challenge of optimization on ''golf-course''-like fitness landscapes.

Melo HP, Franks A, Moreira AA, Diermeier D, Andrade JS, Amaral LA - PLoS ONE (2013)

Bottom Line: While GAs are a robust and flexible approach to solve complex problems, there are some situations under which they perform poorly.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.

View Article: PubMed Central - PubMed

Affiliation: Departamento de Física, Universidade Federal do Ceará, Fortaleza, Ceará, Brazil.

ABSTRACT
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.

Show MeSH

Related in: MedlinePlus

Implementing variable environment genetic algorithms.(A) To promote a rule with  to , we include  extra neighbors keeping the same output with any combination of these two new neighbors. On the left we see a possible input and its respective output for a  rule. On the right there are the respective possible outputs after generalization. Note that in the generalized rule the new inputs do not affect the rule's output. However, inter-generational mutation and crossover of the genetic material will yield changes in output that make the states of the new neighbors relevant. (B) Flowchart of the variable environment genetic algorithms. See the text for a more detailed description.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3818328&req=5

pone-0078401-g002: Implementing variable environment genetic algorithms.(A) To promote a rule with to , we include extra neighbors keeping the same output with any combination of these two new neighbors. On the left we see a possible input and its respective output for a rule. On the right there are the respective possible outputs after generalization. Note that in the generalized rule the new inputs do not affect the rule's output. However, inter-generational mutation and crossover of the genetic material will yield changes in output that make the states of the new neighbors relevant. (B) Flowchart of the variable environment genetic algorithms. See the text for a more detailed description.

Mentions: Our algorithm comprises two main stages (Fig. 2). The first stage, which we denote the generalization step, takes a selected genome with neighbors and creates a copy, but now with instructions for taking into consideration the information from two additional neighbors (see Fig. 2a for an example). Since the generalized genomes contain the ''base'' genomes, there is no evolutionary pressure to change any of its bits because they already have maximum fitness. After generalization of the selected genomes, we implement the second stage of the algorithm: We make the environment more demanding, creating an evolutionary pressure on the longer genomes.


A solution to the challenge of optimization on ''golf-course''-like fitness landscapes.

Melo HP, Franks A, Moreira AA, Diermeier D, Andrade JS, Amaral LA - PLoS ONE (2013)

Implementing variable environment genetic algorithms.(A) To promote a rule with  to , we include  extra neighbors keeping the same output with any combination of these two new neighbors. On the left we see a possible input and its respective output for a  rule. On the right there are the respective possible outputs after generalization. Note that in the generalized rule the new inputs do not affect the rule's output. However, inter-generational mutation and crossover of the genetic material will yield changes in output that make the states of the new neighbors relevant. (B) Flowchart of the variable environment genetic algorithms. See the text for a more detailed description.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3818328&req=5

pone-0078401-g002: Implementing variable environment genetic algorithms.(A) To promote a rule with to , we include extra neighbors keeping the same output with any combination of these two new neighbors. On the left we see a possible input and its respective output for a rule. On the right there are the respective possible outputs after generalization. Note that in the generalized rule the new inputs do not affect the rule's output. However, inter-generational mutation and crossover of the genetic material will yield changes in output that make the states of the new neighbors relevant. (B) Flowchart of the variable environment genetic algorithms. See the text for a more detailed description.
Mentions: Our algorithm comprises two main stages (Fig. 2). The first stage, which we denote the generalization step, takes a selected genome with neighbors and creates a copy, but now with instructions for taking into consideration the information from two additional neighbors (see Fig. 2a for an example). Since the generalized genomes contain the ''base'' genomes, there is no evolutionary pressure to change any of its bits because they already have maximum fitness. After generalization of the selected genomes, we implement the second stage of the algorithm: We make the environment more demanding, creating an evolutionary pressure on the longer genomes.

Bottom Line: While GAs are a robust and flexible approach to solve complex problems, there are some situations under which they perform poorly.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.

View Article: PubMed Central - PubMed

Affiliation: Departamento de Física, Universidade Federal do Ceará, Fortaleza, Ceará, Brazil.

ABSTRACT
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.

Show MeSH
Related in: MedlinePlus