Adaptive cataclysms in genetic algorithms

• US 9,691,021 B2
• Filed: 09/30/2013
• Issued: 06/27/2017
• Est. Priority Date: 05/20/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cantin, Jason F.
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US14/041,161
• Publication Number:
  US 20140344197A1
• Time in Patent Office: 1,366 Days
• CPC Class Codes: G06N 3/12 using genetic models
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

It is determined that a population of candidate solutions for an optimization problem has prematurely converged during a metaheuristic optimization run. A cause for premature convergence of the population is determined based, at least in part, on an analysis of the metaheuristic optimization run. A first cataclysm strategy of a plurality of cataclysm strategies is selected based, at least in part, on one of the cause of the premature convergence and a history of the metaheuristic optimization run. A cataclysm is simulated based, at least in part, on the first cataclysm strategy.

Claims

1. A method comprising:

determining that a population of candidate solutions for an optimization problem has prematurely converged during a metaheuristic optimization run;

determining a cause for premature convergence of the population based, at least in part, on an analysis of the metaheuristic optimization run;

selecting a first cataclysm strategy of a plurality of different cataclysm strategies based, at least in part, on one of the cause of the premature convergence and a history of the metaheuristic optimization run; and

simulating a cataclysm based, at least in part, on the first cataclysm strategy.

2. The method of claim 1 further comprising:

determining that the first cataclysm strategy should be adjusted;

responsive to said determining that the first cataclysm strategy should be adjusted, determining a set of parameters for the first cataclysm strategy; and

adjusting the first cataclysm strategy in accordance with the set of parameters for the first cataclysm strategy;

wherein said simulating the cataclysm based, at least in part, on the first cataclysm strategy comprises simulating the cataclysm in accordance with the adjusted first cataclysm strategy.

3. The method of claim 2, wherein said determining that the first cataclysm strategy should be adjusted comprises determining that a number of generations between convergences is below a threshold.

4. The method of claim 2,

wherein the first cataclysm strategy is a quarantining strategy,

wherein said adjusting the first cataclysm strategy in accordance with the set of parameters for the first cataclysm strategy comprises adjusting a length of a quarantining period.

5. The method of claim 2,

wherein the first cataclysm strategy is a migration strategy,

wherein the migration strategy comprises inserting, into the population, one or more foreign individuals from a first set of one or more foreign populations,

wherein said adjusting the first cataclysm strategy in accordance with the set of parameters for the first cataclysm strategy comprises at least one of:

adjusting a length of a quarantining period;

adjusting a length of a migration delay, wherein one or more foreign individuals are not inserted into the population until after a number of generations indicated by the length of the migration delay; and

selecting one or more foreign individuals from a second set of one or more foreign populations.

6. The method of claim 2,

wherein the first cataclysm strategy is a seeding strategy,

wherein the seeding strategy comprises inserting one or more seeds into the population,

wherein said adjusting the first cataclysm strategy in accordance with the set of parameters for the first cataclysm strategy comprises at least one of:

adjusting a length of a quarantining period;

adjusting a number of seeds inserted into the population;

adjusting when seeds are inserted into the population; and

adjusting which seeds are inserted into the population.

7. The method of claim 2,

wherein the first cataclysm strategy is a biasing strategy,

wherein said adjusting the first cataclysm strategy in accordance with the set of parameters for the first cataclysm strategy comprises changing a bias value from a set of bias values to another value.

8. The method of claim 1 further comprising:

determining that a previously used cataclysm strategy should not be reused; and

wherein said selecting the first cataclysm strategy of the plurality of cataclysm strategies comprises selecting the first cataclysm strategy of the plurality of cataclysm strategies because the first cataclysm strategy is different than the previously used cataclysm strategy.

9. The method of claim 1, wherein the history of the metaheuristic optimization run comprises at least one of a cataclysm count and a convergence rate, wherein the convergence rate is indicated by at least one of a number of generations between convergences and a number of convergences per a number of generations.

10. The method of claim 9, wherein said selecting the first cataclysm strategy of the plurality of cataclysm strategies based, at least in part, on one of the cause of the premature convergence and the history of the metaheuristic optimization run comprises:

determining that the convergence rate is below a threshold;

wherein said selecting the first cataclysm strategy of the plurality of cataclysm strategies is responsive to said determining that the convergence rate is below the threshold.

11. The method of claim 9, wherein said selecting the first cataclysm strategy of the plurality of cataclysm strategies based, at least in part, on one of the cause of the premature convergence and the history of the metaheuristic optimization run comprises:

determining that the convergence rate is above a threshold; and

wherein said selecting the first cataclysm strategy of the plurality of cataclysm strategies is responsive to said determining that the convergence rate is above the threshold.

12. The method of claim 1, wherein the analysis of the metaheuristic optimization run comprises at least one of:

determining that one or more candidate solutions in the population of candidate solutions is associated with one or more tokens;

analyzing the history of the metaheuristic optimization run; and

analyzing a set of genes associated with each of one or more candidate solutions in the population of candidate solutions.

13. The method of claim 1, wherein the different cataclysm strategies comprise a quarantining strategy, a migration strategy, a seeding strategy, and a biasing strategy.

14. The method of claim 1, wherein the first cataclysm strategy of the plurality of different cataclysm strategies comprises a first set of parameters, and wherein a second cataclysm strategy of the plurality of different cataclysm strategies comprises a second set of parameters different from the first set of parameters.

15. The method of claim 14, wherein the first set of parameters and the second set of parameters include different member subsets from a set of parameters consisting of a mass extinction parameter, a quarantining parameter, a migration parameter, a seeding parameter, and a biasing parameter.

16. The method of claim 14, wherein the selecting the first cataclysm strategy comprises:

determining, based on the history of the metaheuristic optimization run, that the second cataclysm strategy was used to perform one or more prior cataclysms using the second set of parameters; and

selecting the first cataclysm strategy in place of the second cataclysm strategy in response to determining that modifying values for the second set of parameters would be less likely to provide fitter candidate solutions than using the first set of parameters from the first cataclysm strategy.

17. The method of claim 14, wherein the second set of parameters comprises a first parameter that randomly mutates one or more of the population of candidate solutions, and wherein the selecting the first cataclysm strategy comprises determining that random mutations of the one or more of the population of candidate solutions would be less likely to provide fitter candidate solutions than using a second cataclysm parameter from the first cataclysm strategy, wherein the second cataclysm parameter comprises one or more of a quarantining parameter, a migration parameter, a seeding parameter, and a biasing parameter.