Using global and local catastrophes across sub-populations in parallel evolutionary computing

• US 9,165,247 B2
• Filed: 01/04/2012
• Issued: 10/20/2015
• Est. Priority Date: 01/04/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cantin, Jason F.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Figueroa, Kevin W
• Application Number:
  US13/343,558
• Publication Number:
  US 20130173511A1
• Time in Patent Office: 1,385 Days
• Field of Search: 706/13
• 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

A parallel genetic algorithm computing process tracks forward progress of a first sub-population across generations thereof. The first sub-population is one of a plurality of sub-populations that form a population of candidate solutions to an optimization problem. At a current generation of the first sub-population, it is determined that forward progress of the first sub-population fails a set of one or more forward progress criteria. In response to determining that the forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation, a local catastrophe is invoked on the current generation of the first sub-population. The first sub-population is re-populated after the local catastrophe is invoked. The first sub-population is re-established after re-populating while constraining migration to the first sub-population.

Claims

1. A computer program product for invoking a global catastrophe on a population in a parallel evolutionary algorithm computing process, the 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;

track forward progress of a population of candidate solutions across generations thereof, wherein the population is divided into a plurality of sub-populations across a plurality of computing entities that iteratively create new generations of the plurality of sub-populations of candidate solutions in search of a solution to an optimization problem;

track local catastrophes invoked on the plurality of sub-populations by respective ones of the plurality of computing entities;

at a current generation of the population, determine that forward progress of the population fails a set of one or more forward progress criteria;

in response to a determination that the forward progress of the population fails the set of one or more forward progress criteria at the current generation,

select parameter values that influence the global catastrophe, wherein the selection is based, at least in part, on the tracked local catastrophes invoked on the plurality of sub-populations,

command the plurality of computing entities to collectively apply the global catastrophe to the plurality of sub-populations in accordance with the parameter values.

2. The computer program product of claim 1, wherein the parameter values that influence the global catastrophe are different for at least one of the plurality of computing entities.

3. The computer program product of claim 1, wherein the parameter values that influence the global catastrophe indicate at least one of degree of mutation, number of survivors, and number of generations to recover.

4. The computer program product of claim 1, wherein the computer usable program code is further configured to postpone the global catastrophe until after a first of the plurality of sub-populations recovers from a local catastrophe invoked on the first sub-population by the computing entity corresponding to the first sub-population.

5. A computer program product for invoking a local catastrophe on a sub-population in a parallel evolutionary algorithm computing process, the 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;

track forward progress of a first sub-population across generations thereof, wherein the first sub-population is one of a plurality of sub-populations that form a population of candidate solutions to an optimization problem for which a solution is being searched by a parallel evolutionary computing process;

at a current generation of the first sub-population, determine that forward progress of the first sub-population fails a set of one or more forward progress criteria;

in response to a determination that the forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation, invoke a local catastrophe on the current generation of the first sub-population;

re-populate the first sub-population after the local catastrophe is invoked; and

constrain migration to the first sub-population while re-establishing the first sub-population after re-population.

6. The computer program product of claim 5, wherein the forward progress corresponds to improvement in at least one of a best fitness metric value of the first sub-population and average of the fitness metric values for the first sub-population across generations of the first sub-population.

7. The computer program product of claim 6, wherein the computer usable program code configured to track forward progress of the first sub-population across generations thereof comprises the computer usable program code configured to track a number of generations of the first sub-population that fail to improve at least one of the best fitness metric value and the average of the fitness metric values for the first sub-population.

8. The computer program product of claim 5, wherein the computer usable program code configured to determine that forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation comprises the computer usable program code configured to determine that an aggregate of the current generation and a plurality of predecessor generations of the first sub-population that have failed to make forward progress exceeds a threshold number of generations for failing to make forward progress.

9. The computer program product of claim 5, wherein the computer usable program code configured to re-populate the first sub-population after the local catastrophe comprises the computer usable program code configured to perform migration of candidate solutions from others of the plurality of sub-populations.

10. The computer program product of claim 5, wherein the computer usable program code configured to constrain migration to the first sub-population while re-establishing the first sub-population after re-population comprises the computer usable program code configured to, while iteratively generating successive generations of the first sub-population with candidate solutions from said re-population, one of:

prevent, for at least some of the successive generations of the first sub-population, migration of candidate solutions into the first sub-population; and

limit migration of candidate solutions into the first sub-population.

11. An apparatus for invoking a local catastrophe on a sub-population in a parallel evolutionary algorithm computing process comprising:

a processor;

a network interface operable to communicate at least fitness metric values;

a local catastrophe unit operable to,

track forward progress of a first sub-population across generations thereof, wherein the first sub-population is one of a plurality of sub-populations that form a population of candidate solutions to an optimization problem for which a solution is being searched by a parallel evolutionary computing process;

at a current generation of the first sub-population, determine that forward progress of the first sub-population fails a set of one or more forward progress criteria;

in response to a determination that the forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation, invoke a local catastrophe on the current generation of the first sub-population;

re-populate the first sub-population after the local catastrophe is invoked; and

constrain migration to the first sub-population while re-establishing the first sub-population after re-population.

12. The apparatus of claim 11 further comprising a machine-readable storage media having program instructions stored thereon, wherein the program instruction embody the local catastrophe unit.

13. The apparatus of claim 11, wherein the local catastrophe unit being operable to constrain migration to the first sub-population while re-establishing the first sub-population after re-population comprises the local catastrophe unit operable to, while iteratively generating successive generations of the first sub-population with candidate solutions from said re-population, one of:

prevent, for at least some of the successive generations of the first sub-population, migration of candidate solutions into the first sub-population; and

limit migration of candidate solutions into the first sub-population.