Adaptive cataclysms in genetic algorithms

• US 9,305,257 B2
• Filed: 05/20/2013
• Issued: 04/05/2016
• Est. Priority Date: 05/20/2013
• Status: Expired due to Fees

• 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:
  US13/897,584
• Publication Number:
  US 20140344196A1
• Time in Patent Office: 1,051 Days
• US Class Current: 1/1
• 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 computer program product comprising:

a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising a computer usable program code configured to;

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

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

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

an analysis of the history of the metaheuristic optimization run; and

an analysis of a set of genes associated with each of the one or more candidate solutions in the population of candidate solutions;

select a first cataclysm strategy of a plurality of 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

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

2. The computer program product of claim 1, the computer usable program code is further configured to:

determine that the first cataclysm strategy should be adjusted;

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

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

wherein said computer usable program code configured to simulate the cataclysm based, at least in part, on the first cataclysm strategy is configured to simulate the cataclysm in accordance with the adjusted first cataclysm strategy.

3. The computer program product 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 the number of generations.

4. An apparatus comprising:

a processor; and

a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code executable by the processor to cause the apparatus to;

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

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

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

an analysis of the history of the metaheuristic optimization run; and

an analysis of a set of genes associated with each of the one or more candidate solutions in the population of candidate solutions;

select a first cataclysm strategy of a plurality of 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

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

5. The apparatus of claim 4, wherein the computer usable program code executable by the processor to further cause the apparatus to:

determine that the first cataclysm strategy should be adjusted;

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

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

wherein said computer usable program code executable by the processor to cause the apparatus to simulate the cataclysm based, at least in part, on the first cataclysm strategy is executable by the processor to further cause the apparatus to simulate the cataclysm in accordance with the adjusted first cataclysm strategy.

6. The apparatus of claim 4, 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 the number of generations.