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

• US 9,165,248 B2
• Filed: 08/24/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/593,850
• Publication Number:
  US 20130173512A1
• Time in Patent Office: 1,152 Days
• Field of Search: None
• 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 method comprising:

tracking 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, determining 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, invoking a local catastrophe on the current generation of the first sub-population;

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

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

2. The method of claim 1, wherein 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.

3. The method of claim 2, wherein said tracking forward progress of the first sub-population across generations thereof comprises tracking 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.

4. The method of claim 1, wherein said determining that forward progress of the first sub-population fails the set of one or more forward progress criteria at the current generation comprises determining 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.

5. The method of claim 1, wherein said invoking the local catastrophe on the current generation of the first sub-population comprises selecting a set of one or more survivor candidate solutions from the current generation of the first sub-population and eliminating remaining ones of the candidates solutions.

6. The method of claim 5 further comprising:

tracking a number of local catastrophes invoked; and

decreasing a number of survivors as the number of local catastrophes increases.

7. The method of claim 1, wherein said re-populating the first sub-population after the local catastrophe comprises performing migration of candidate solutions from others of the plurality of sub-populations.

8. The method of claim 1, wherein said re-establishing the first sub-population after re-populating while constraining migration to the first sub-population comprises iteratively generating successive generations of the first sub-population with candidate solutions from said re-populating the first sub-population while one of:

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

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