CONTROLLING QUARANTINING AND BIASING IN CATACLYSMS FOR OPTIMIZATION SIMULATIONS

• US 20120130929A1
• Filed: 11/24/2010
• Published: 05/24/2012
• Est. Priority Date: 11/24/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cantin, Jason F.
• Granted Patent: US 8,489,526 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 7/00 Computing arrangements based on specific mathematical models

Abstract

Some embodiments are directed to generating a first probability value that represents a percentage of times that first bit values for a given bit position of a first plurality of candidate solutions equate to a pre-defined number, where the first plurality of candidate solutions has converged on a sub-optimal solution during a simulation of an optimization problem using an optimization algorithm. Some embodiments are further directed to generating a second probability value that is inversely biased from the first probability value; and generating a second plurality of candidate solutions with the second probability value, where the second plurality of candidate solutions are inversely biased from the first bit values for the given bit position.

Claims

1. A computer-implemented method comprising:

generating a first probability value that represents a percentage of times that first bit values for a given bit position of a first plurality of candidate solutions equate to a pre-defined number, wherein the first plurality of candidate solutions has converged on a sub-optimal solution during a simulation of an optimization problem using an optimization algorithm;

generating a second probability value that is inversely biased from the first probability value; and

generating a second plurality of candidate solutions with the second probability value, wherein the second plurality of candidate solutions are inversely biased from the first bit values for the given bit position.

2. The computer-implemented method of claim 1, wherein the first probability value is a proportion less than or equal to a numerical value of 1, and wherein generating the second probability value that is inversely biased from the first probability value comprises subtracting the first probability value from the numerical value of 1.

3. The computer-implemented method of claim 1, wherein using the second probability value to generate the second plurality of candidate solutions comprises generating more than approximately fifty percent of the second bit values to be different from the first bit values for the given bit position.

4. The computer-implemented method of claim 1, wherein using the second probability value to generate the second plurality of candidate solutions comprises:

generating a random number within a numerical range, wherein the second probability value represents a percentage that scales to the numerical range;

determining that the random number is within a subset of the numerical range that corresponds to the second probability value;

converting the random number to a bit value of 1 in response to determining that the random number is within the subset of the numerical range that corresponds to the second probability value; and

inserting the bit value of 1 into one of the second plurality of candidate solutions at the given bit position.

5. The computer-implemented method of claim 4, wherein the numerical range is equivalent to a number of the first plurality of candidate solutions.

6. The computer-implemented method of claim 1, wherein using the second probability value to generate the second plurality of candidate solutions comprises:

generating a random number within a numerical range, wherein the second probability value represents a percentage that scales to the numerical range;

determining that the random number is within a subset of the numerical range that corresponds to the second probability value;

converting the random number to a bit value of 0 in response to determining that the random number is within the subset of the numerical range that corresponds to the second probability value; and

inserting the bit value of 0 into one of the second plurality of candidate solutions at the given bit position.

7. The computer-implemented method of claim 1 further comprising:

determining that either the first probability value or the second probability value is beyond a range of one or more specific values; and

modifying either the first probability value or the second probability value to be within the threshold of the one or more specific values before using the second probability value to generate the second plurality of candidate solutions.

8. A computer program product for generating candidate solutions during a simulation of an optimization problem using an optimization algorithm, the computer program product comprising:

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

select at least one candidate solution from a first plurality of candidate solutions that has converged on a suboptimal solution during the simulation of the optimization problem,

quarantine the at least one candidate solution,

perform a cataclysm on the first plurality of candidate solutions,

generate a second plurality of candidate solutions,

compute optimizations to the second plurality of candidate solutions until

pre-specified criteria has been satisfied, and

integrate the at least one candidate solution into the second plurality of candidate solutions after computing the optimizations to the second plurality of candidate solutions.

9. The computer program product of claim 8, wherein the computer readable program code is further configured to integrate the at least one candidate solution into the second plurality of candidate solutions before the second plurality of candidate solutions converges on an additional suboptimal solution.

10. The computer program product of claim 8, wherein the pre-specified criteria comprise a number of generations of optimizations of a population-based optimization algorithm, and wherein the computer readable program code is configured to compute the number of generations of the second plurality of candidate solutions.

11. The computer program product of claim 10, wherein the number of generations is greater than 1 generation and less than approximately 10 generations

12. The computer program product of claim 8, wherein the computer readable program code is configured to integrate the at least one candidate solution into the second plurality of candidate solutions being configured to

store a copy of the at least one candidate solution, and

insert the copy of the at least one candidate solution into the second plurality of candidate solutions after computing the optimizations to the second plurality of candidate solutions for a pre-specified time period.

13. The computer program product of claim 8, wherein the computer readable program code is configured to integrate the at least one candidate solution into the second plurality of candidate solutions being configured to

include the at least one candidate solution in the second plurality of candidate solutions before computing the optimizations to the second plurality of candidate solutions,

associate a mark with the at least one candidate solution before computing the optimizations to the second plurality of candidate solutions, and

during each of a number of computations performed during the computing of the optimizations to the second plurality of candidate solutions,

detect the mark, and

restrict the at least one candidate solution from interacting with the second plurality of candidate solutions based on the detecting the mark.

14. The computer program product of claim 8, wherein the at least one candidate solution comprises at least one of a plurality of bit strings, and wherein the computer readable program code is configured to generate the second plurality of candidate solutions using an inverted vector of probabilities, wherein the inverted vector of probabilities specifies an inverted bias for bit values in the at least one of the plurality of bit strings.

15. The computer program product of claim 14, the computer readable program code configured to generate the second plurality of candidate solutions using the inverted vector of probabilities being further configured to

convert random numbers to bit values of either 1 or 0 using the inverted vector of probabilities;

and

insert the bit values of either 1 or 0 into bit strings for the second plurality of candidate solutions.

16. A computer-implemented method comprising:

determining that a first plurality of candidate solutions has converged on a suboptimal solution in a search space of a simulation of an optimization problem using an evolutionary algorithm, wherein each of the first plurality of candidate solutions has first bit values, and wherein each of the first bit values corresponds to each of a plurality of bit positions in a sequence;

computing a first vector of first proportion values for the first plurality of candidate solutions, wherein each one of the first proportion values corresponds to each one of the plurality of positions in the sequence, and wherein the each one of the first proportion values represents a percentage of times that corresponding ones of the first bit values for a corresponding one of the plurality of positions equates to a bit value of 1;

subtracting each of the first proportion values from a numerical value of 1 to generate a second vector of second proportion values that are inversely biased from the first proportion values; and

generating a second plurality of candidate solutions using the second proportion values, wherein each of the second plurality of candidate solutions has second bit values, wherein each of the second bit values corresponds to each of the plurality of positions of the sequence, and wherein the second plurality of candidate solutions is inversely biased from the first plurality of candidate solutions.

17. The computer-implemented method of claim 16 further comprising:

generating random numbers within a numerical range, wherein each of the second proportion values represent a percentage that scales to the numerical range;

converting the random numbers to second bit values using the second proportion values; and

generating the second plurality of candidate solutions using the second bit values.

18. The computer-implemented method of claim 17, wherein said converting the random numbers to second bit values using the second proportion values comprises:

determining that one of the random numbers is within a subset of values of the numerical range, wherein the subset of values corresponds to one of the second proportion values; and

converting the one of the random number to a value of 1 in response to determining that the one of the random numbers is within the subset of values of the numerical range.

19. The computer-implemented method of claim 17, and wherein more than approximately fifty percent of the second bit values are different from the first bit values for any of the plurality of bit positions.

20. The computer-implemented method of claim 16, further comprising:

determining that either the first proportion values or the second proportion values are beyond a range of one or more specific values; and

modifying either the first proportion value or the second proportion value to be within the range of the one or more specific values before generating the second plurality of candidate solutions using the second proportion values.

21. An apparatus comprising:

a processing unit;

a network interface; and

a population-based optimization algorithm simulator operable to, via the processing unit,

determine that a first population of first bit strings has converged on a sub-optimal solution during a simulation of an optimization problem using an evolutionary algorithm, wherein the first bit strings represent candidate solutions of the optimization problem;

generate a first proportion value that represents a percentage of times that first bit values for a given bit position of the first bit strings equates to a pre-defined number;

generate a second proportion value that is inversely biased from the first proportion value; and

use the second proportion value to generate a second population of second bit strings, wherein second bit values of the second bit strings, for the given bit position, are, on average, inversely biased from the first bit values.

22. The apparatus of claim 21, wherein the first proportion value is less than or equal to a numerical value of 1, wherein the population-based optimization algorithm simulator is further operable to subtract the first proportion value from the numerical value of 1.

23. The apparatus of claim 21, wherein the population-based optimization algorithm simulator is further operable to

generate more than approximately fifty percent of the second bit values to be different from the first bit values for the given bit position.

24. The apparatus of claim 21, wherein the population-based optimization algorithm simulator is further operable to

generate a random number within a numerical range, wherein the second probability value represents a percentage that scales to the numerical range;

determine that the random number is within a subset of the numerical range that corresponds to the second probability value;

convert the random number to a bit value of 1 in response to determining that the random number is within the subset of the numerical range that corresponds to the second probability value; and

insert the bit value of 1 into one of the second bit strings at the given bit position.

25. The apparatus of claim 21, wherein the population-based optimization algorithm simulator is further operable to

generate a random number within a numerical range, wherein the second probability value represents a percentage that scales to the numerical range;

determine that the random number is within a subset of the numerical range that corresponds to the second probability value;

convert the random number to a bit value of 0 in response to determining that the random number is within the subset of the numerical range that corresponds to the second probability value; and

insert the bit value of 0 into one of the second bit strings at the given bit position.