CONTROLLING QUARANTINING AND BIASING IN CATACLYSMS FOR OPTIMIZATION SIMULATIONS

• US 20130275351A1
• Filed: 06/12/2013
• Published: 10/17/2013
• 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,825,573 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 examples are directed to determining a frequency of occurrence of a first value in a component of a first plurality of candidate solutions for an optimization problem where the first plurality of candidate solutions has converged on a sub-optimal solution during a computer simulation that tests fitness of the first plurality of candidate solutions. Some examples are further directed to determining a second value that is inversely biased from the frequency of occurrence of the first value. Some examples are further directed to including the second value in a component of at least a portion of a second plurality of candidate solutions, where the component of the at least the portion of the second plurality of candidate solutions corresponds to the component of the first plurality of candidate solutions.

Claims

1. A computer-implemented method comprising:

determining a frequency of occurrence of a first value in a component of a first plurality of candidate solutions for an optimization problem, wherein the first plurality of candidate solutions has converged on a sub-optimal solution during a computer simulation that tests fitness of the first plurality of candidate solutions;

determining a second value that is inversely biased from the frequency of occurrence of the first value; and

including the second value in a component of at least a portion of a second plurality of candidate solutions, wherein the component of the at least the portion of the second plurality of candidate solutions corresponds to the component of the first plurality of candidate solutions.

2. The computer-implemented method of claim 1, wherein each of the first plurality of candidate solutions has a first arrangement of a first plurality of bits that is equivalent to a second arrangement of a second plurality of bits in the second plurality of candidate solutions, wherein the component of the first plurality of candidate solutions is one of the first plurality of bits, wherein the component of the second plurality of candidate solutions is one of the second plurality of bits, and wherein a bit position of the one of the first plurality of bits within the first arrangement corresponds to a bit position of the one of the second plurality of bits within the second arrangement.

3. The computer-implemented method of claim 1, wherein the determining the frequency of occurrence of the first value comprises computing the frequency of occurrence as a percentage value less than or equal to a numerical value of 1, and wherein the determining the second value that is inversely biased from the frequency of occurrence of the first value comprises subtracting the percentage value from the numerical value of 1.

4. The computer-implemented method of claim 1, wherein the including the second value in the component of the at least the portion of the second plurality of candidate solutions comprises including the second value in more than approximately fifty percent of the second plurality of candidate solutions.

5. The computer-implemented method of claim 1, wherein the including the second value in the component of the at least the portion of the second plurality of candidate solutions comprises:

generating a random number within a numerical range, wherein the second 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 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 value; and

inserting the bit value of 1 into the component of the at least the portion of the second plurality of candidate solutions.

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

7. The computer-implemented method of claim 1, wherein the including the second value in the component of the at least the portion of the second plurality of candidate solutions comprises:

generating a random number within a numerical range, wherein the second 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 value;

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

inserting the bit value of 0 into the component of the at least the portion of the second plurality of candidate solutions.

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

determining that the frequency of occurrence of the first value is beyond a range of one or more specific values; and

modifying the second value to be within the threshold of the one or more specific values before the including the second value in the component of the at least the portion of the second plurality of candidate solutions.

9. An apparatus comprising:

a processing unit; and

a computer readable storage medium configured to store instructions which, when executed by the processing unit, perform one or more operations to

determine a frequency of occurrence of a first value in a position of a first plurality of candidate solutions for an optimization problem, wherein the first plurality of candidate solutions has converged on a sub-optimal solution during a computer simulation that tests fitness of the first plurality of candidate solutions,

determine a second value that is inversely biased from the frequency of occurrence of the first value, and

include the second value in a position of at least a portion of a second plurality of candidate solutions, wherein the position of the at least the portion of the second plurality of candidate solutions corresponds to the position of the first plurality of candidate solutions.

10. The apparatus of claim 9, wherein each of the first plurality of candidate solutions has a first arrangement of a first plurality of bits that is equivalent to a second arrangement of a second plurality of bits in the second plurality of candidate solutions, wherein the position of the first plurality of candidate solutions corresponds to a bit position of one of the first plurality of bits within the first arrangement, and wherein the position of the second plurality of candidate solutions corresponds to a bit position of one of the second plurality of bits within the second arrangement.

11. The apparatus of claim 9, wherein the operation to determine the frequency of occurrence of the first value comprises an operation to compute the frequency of occurrence as a percentage value less than or equal to a numerical value of 1, and wherein the operation to determine the second value that is inversely biased from the frequency of occurrence of the first value comprises an operation to subtract the percentage value from the numerical value of 1.

12. The apparatus of claim 9, wherein the operation to include the second value in the position of the at least the portion of the second plurality of candidate solutions includes operations to:

generate a random number within a numerical range, wherein the second 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 value;

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

insert the bit value of 1 into the position of the at least the portion of the second plurality of candidate solutions.

13. The apparatus of claim 9, wherein the operation to include the second value in the position of the at least the portion of the second plurality of candidate solutions comprises operations to:

generate a random number within a numerical range, wherein the second 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 value;

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

insert the bit value of 0 into the position of the at least the portion of the second plurality of candidate solutions.

14. The apparatus of claim 9, further comprising operations to:

determine that the frequency of occurrence of the first value is beyond a range of one or more specific values; and

modify the second value to be within the threshold of the one or more specific values before the second value is included in the position of the at least the portion of the second plurality of candidate solutions.

15. 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

determine a frequency of occurrence of a first value in a position of a first plurality of candidate solutions for an optimization problem, wherein the first plurality of candidate solutions has converged on a sub-optimal solution during a computer simulation that tests fitness of the first plurality of candidate solutions,

determine a second value that is inversely biased from the frequency of occurrence of the first value, and

include the second value in a position of at least a portion of a second plurality of candidate solutions, wherein the position of the at least the portion of the second plurality of candidate solutions corresponds to the position of the first plurality of candidate solutions.

16. The computer program product of claim 15, wherein each of the first plurality of candidate solutions has a first arrangement of a first plurality of bits that is equivalent to a second arrangement of a second plurality of bits in the second plurality of candidate solutions, wherein the position of the first plurality of candidate solutions corresponds to a bit position of one of the first plurality of bits within the first arrangement, and wherein the position of the second plurality of candidate solutions corresponds to a bit position of one of the second plurality of bits within the second arrangement.

17. The computer program product of claim 15, wherein the computer readable program code is configured to:

compute the frequency of occurrence as a percentage value less than or equal to a numerical value of 1; and

subtract the percentage value from the numerical value of 1.

18. The computer program product of claim 15, wherein the computer readable program code is configured to:

generate a random number within a numerical range, wherein the second 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 value;

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

insert the bit value of 1 into the position of the at least the portion of the second plurality of candidate solutions.

19. The computer program product of claim 15, wherein the computer readable program code is configured to:

generate a random number within a numerical range, wherein the second 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 value;

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

insert the bit value of 0 into the position of the at least the portion of the second plurality of candidate solutions.

20. The computer program product of claim 15, wherein the computer readable program code is configured to:

determine that the frequency of occurrence of the first value is beyond a range of one or more specific values; and

modify the second value to be within the threshold of the one or more specific values before the second value is included in the position of the at least the portion of the second plurality of candidate solutions