USING GLOBAL AND LOCAL CATASTROPHES ACROSS SUB-POPULATIONS IN PARALLEL EVOLUTIONARY COMPUTING

• US 20130173512A1
• Filed: 08/24/2012
• Published: 07/04/2013
• Est. Priority Date: 01/04/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cantin, Jason F.
• Granted Patent: US 9,165,248 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• 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.

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.

6. The method of claim 6 further comprising:

tracking a number of local catastrophes invoked; and

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