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

Robustness of the evolved genomes again communication noise.(A) Comparison of the fitness of the genomes evolved using VEGA against the fitness of the majority rule for 5, 7 and 11. It is visually apparent that for  the evolved genomes are more robust against communication noise than the majority rule. (B) Average updated state of an agent with a high fitness evolved genome with  as a function of the number of neighbors in state one for . The red circles show the updated state of the agent when the initial state is one, and the red dashed line shows results for the majority rule for comparison. The empty circles show the updated state of the agent when the initial state is zero, and the black full line shows results for the majority rule. (C) Same as b, but for . It is visually apparent that the evolved genomes are more conservative than the majority rule — they require larger majorities of neighbors on the opposite state in order to change state.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3818328&req=5

pone-0078401-g004: Robustness of the evolved genomes again communication noise.(A) Comparison of the fitness of the genomes evolved using VEGA against the fitness of the majority rule for 5, 7 and 11. It is visually apparent that for the evolved genomes are more robust against communication noise than the majority rule. (B) Average updated state of an agent with a high fitness evolved genome with as a function of the number of neighbors in state one for . The red circles show the updated state of the agent when the initial state is one, and the red dashed line shows results for the majority rule for comparison. The empty circles show the updated state of the agent when the initial state is zero, and the black full line shows results for the majority rule. (C) Same as b, but for . It is visually apparent that the evolved genomes are more conservative than the majority rule — they require larger majorities of neighbors on the opposite state in order to change state.

Mentions: Interestingly, the evolved rule is more robust against communication noise than the majority rule (Fig. 4). This increased robustness recalls the findings of Seaver et al.[21] reporting that conservative strategies — that is, strategies that give greater weight to an agent's state than to the information received from the neighbors — display greater robustness again communication noise than the corresponding majority rule. In order to investigate whether the higher fitness of the evolved rules mirrors the conservative strategy discussed in Seaver et al.[21], we calculate the average updated state of an agent using a VEGA evolved genome as a function of the agent's initial state and of the number of neighbors in state one.


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)

Robustness of the evolved genomes again communication noise.(A) Comparison of the fitness of the genomes evolved using VEGA against the fitness of the majority rule for 5, 7 and 11. It is visually apparent that for  the evolved genomes are more robust against communication noise than the majority rule. (B) Average updated state of an agent with a high fitness evolved genome with  as a function of the number of neighbors in state one for . The red circles show the updated state of the agent when the initial state is one, and the red dashed line shows results for the majority rule for comparison. The empty circles show the updated state of the agent when the initial state is zero, and the black full line shows results for the majority rule. (C) Same as b, but for . It is visually apparent that the evolved genomes are more conservative than the majority rule — they require larger majorities of neighbors on the opposite state in order to change state.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0078401-g004: Robustness of the evolved genomes again communication noise.(A) Comparison of the fitness of the genomes evolved using VEGA against the fitness of the majority rule for 5, 7 and 11. It is visually apparent that for the evolved genomes are more robust against communication noise than the majority rule. (B) Average updated state of an agent with a high fitness evolved genome with as a function of the number of neighbors in state one for . The red circles show the updated state of the agent when the initial state is one, and the red dashed line shows results for the majority rule for comparison. The empty circles show the updated state of the agent when the initial state is zero, and the black full line shows results for the majority rule. (C) Same as b, but for . It is visually apparent that the evolved genomes are more conservative than the majority rule — they require larger majorities of neighbors on the opposite state in order to change state.
Mentions: Interestingly, the evolved rule is more robust against communication noise than the majority rule (Fig. 4). This increased robustness recalls the findings of Seaver et al.[21] reporting that conservative strategies — that is, strategies that give greater weight to an agent's state than to the information received from the neighbors — display greater robustness again communication noise than the corresponding majority rule. In order to investigate whether the higher fitness of the evolved rules mirrors the conservative strategy discussed in Seaver et al.[21], we calculate the average updated state of an agent using a VEGA evolved genome as a function of the agent's initial state and of the number of neighbors in state one.

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