EFFICIENT STORAGE OF INDIVIDUALS FOR OPTIMIZATION SIMULATION

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

• Current Assignee: International Business Machines Corporation, ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Bell, Robert H. Jr., Cantin, Jason F.
• Granted Patent: US 8,515,882 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Candidate solutions to an optimization problem comprise a set of potential values that can be applied to variables in a problem description. Candidate solutions can be large because of the complexity of optimization problems and large number of variables. The populations of candidate solutions may also be large to ensure diversity and effectiveness in computing a solution. When the populations and the candidate solutions are large for an optimization problem, computing a solution to the optimization problem consumes a large amount of memory. In some instances, several generations of candidate solutions are stored in memory. Compression of the candidate solutions can minimize the memory space consumed to compute a solution to an optimization problem.

Claims

1. A method comprising:

determining a difference comparison key for a plurality of individuals, wherein each of the individuals comprises a candidate solution for an optimization problem;

computing logical differences between the difference comparison key and the plurality of individuals;

compressing each of the logical differences to generate a plurality of compressed individuals; and

using the plurality of compressed individuals in an optimization simulation to generate a solution for the optimization problem.

2. The method of claim 1, wherein said determining the difference comparison key for the plurality of individuals comprises one of selecting one of the individuals as the difference comparison key, generating the difference comparison key based on the individuals, and generating the difference comparison key based on a second plurality of individuals.

3. The method of claim 2, wherein said selecting the difference comparison key comprises one of randomly selecting one of the individuals and selecting a first individual.

4. The method of claim 2, wherein said generating the difference comparison key based on the individuals comprises:

determining a plurality of common values in the individuals; and

generating a difference comparison key that comprises the plurality of common values.

5. The method of claim 2, wherein said generating the difference comparison key based on the second plurality of individuals comprises:

determining a plurality of common values in the second plurality of individuals, wherein a first generation comprises the second plurality of individuals and the first generation precedes a second generation that comprises the plurality of individuals; and

generating a difference comparison key that comprises the plurality of common values.

6. The method of claim 1, further comprising:

determining a new difference comparison key from a second plurality of offspring individuals derived from the plurality of individuals;

computing a second logical difference between the difference comparison key and the new difference comparison key;

computing a plurality of second logical differences between the second plurality of offspring individuals and the second logical difference; and

compressing the plurality of second logical differences to generate a compressed second plurality of offspring individuals.

7. The method of claim 6, further comprising:

determining a plurality of identical values within the plurality of second logical differences; and

rearranging the plurality of identical values within each of the second logical differences to be contiguous within each of the second logical differences to generate rearranged logical differences,

wherein said compressing the plurality of second logical differences comprises compressing each of the rearranged logical differences.

8. The method of claim 1, wherein said using the compressed plurality of compressed individuals in an optimization simulation to generate a solution for the optimization problem comprises:

decompressing a first of the plurality of compressed individuals to generate a first of the logical differences;

generating a first of the individuals based on the first of the logical differences and the difference comparison key; and

evaluating a fitness of the first of the individuals while others of the plurality of compressed individuals remain compressed.

9. The method of claim 8, further comprising:

discarding the first of the logical differences while maintaining the first of the plurality of compressed individuals.

10. The method of claim 1, wherein said compressing each of the logical differences further comprises:

scanning a first of the plurality of individuals for a plurality of consecutive bytes comprised of zeros;

replacing the plurality of consecutive bytes comprised of zeros with a bit indicating a string of bytes comprised of consecutive zeros and a length of the string of bytes comprised of consecutive zeros;

scanning the first of the plurality of individuals for a plurality of bytes that have a non-zero value; and

replacing each of the plurality of bytes that have a non-zero value with a bit indicating a byte including a non-zero value and a value of the byte.

11. The method of claim 1, wherein said compressing each of the logical differences further comprises:

performing a mutation or a crossover on a plurality of compressed logical differences, wherein said compressing is in accordance with sparse vector encoding.

12. The method of claim 1, wherein the plurality of individuals has been preceded by a plurality of earlier pluralities of individuals.

13. The method of claim 1, wherein compressing each of the logical differences to generate a plurality of compressed individuals further comprises:

writing the plurality of compressed individuals to a checkpoint in a persistent storage.

14. A computer program product for compressing and decompressing a plurality of individuals, 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 difference comparison key for the plurality of individuals, wherein each of the individuals comprises a candidate solution for an optimization problem;

decompress a first of a plurality of compressed individuals to generate a first of a plurality of logical differences, wherein each of the compressed individuals represent a candidate solution to an optimization problem; and

evaluate a fitness of the first of the plurality of logical differences while others of the plurality of compressed individuals remain compressed.

15. The computer program product of claim 14, wherein the computer readable program code being configured to evaluate the fitness of the first of the plurality of logical differences while others of the plurality of compressed individuals remain compressed comprises the code being configured to restore the first of the plurality of logical differences to a first of the individuals with a difference comparison key for the plurality of individuals, wherein the first of the plurality of logical differences represents a logical difference between the difference comparison key and the first of the individuals.

16. A computer program product for running an optimization simulator, the computer program product comprising:

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

determine a difference comparison key for a plurality of individuals, wherein each of the individuals comprise a candidate solution for an optimization problem;

compute a plurality of logical differences between the difference comparison key and the plurality of individuals;

compress each of the logical differences to generate a plurality of compressed individuals; and

use the plurality of compressed individuals in an optimization simulation to generate a solution for the optimization problem.

17. The computer program product of claim 16, wherein the computer readable program code being configured to determine the difference comparison key for the plurality of individuals comprises the computer readable program code being configured to perform one of select one of the individuals as the difference comparison key, generate the difference comparison key based on the individuals, and generating the difference comparison key based on a second plurality of individuals.

18. The computer program product of claim 17, wherein the computer readable program code being configured to select the difference comparison key comprises the computer readable program code being configured to perform one of randomly select one of the individuals and select a first individual.

19. The computer program product of claim 17, wherein the computer readable program code being configured to generate the difference comparison key based on the individuals, is further configured to:

determine a plurality of common values in the individuals; and

generate a difference comparison key that comprises the plurality of common values.

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

determine a new difference comparison key from a second plurality of offspring individuals derived from the plurality of individuals;

compute a second logical difference between the difference comparison key and the new difference comparison key;

compute a plurality of second logical differences between the second plurality of offspring individuals and the second logical difference; and

compress the plurality of second logical differences to generate a compressed second plurality of offspring individuals.

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

determine a plurality of identical values within the plurality of second logical differences; and

rearrange the plurality of identical values within each of the second logical differences to be contiguous within each of the second logical differences to generate rearranged logical differences,

wherein the computer readable program code being configured to compress the plurality of second logical differences comprises the computer readable program code being configured to compress each of the rearranged logical differences.

22. An apparatus comprising:

a processor;

a memory unit coupled with the processor; and

an optimization algorithm simulator configured to;

determine a difference comparison key for a plurality of individuals, wherein each of the individuals comprise a candidate solution for an optimization problem;

compute a plurality of logical differences between the difference comparison key and the plurality of individuals;

compress each of the logical differences to generate a plurality of compressed individuals; and

use the plurality of compressed individuals in an optimization simulation to generate a solution for the optimization problem.

23. The apparatus of claim 22, wherein the optimization algorithm simulator being configured to determine the difference comparison key for the plurality of individuals comprises the optimization algorithm simulator being configured to perform one of select one of the individuals as the difference comparison key and generate the difference comparison key based on the individuals.

24. The apparatus of claim 23, wherein the optimization algorithm simulator being configured to select the difference comparison key comprises the optimization algorithm simulator being configured to perform one of randomly select one of the individuals and select a first individual.

25. The apparatus of claim 23, wherein the optimization algorithm simulator being configured to generate the difference comparison key based on the individuals, is further configured to:

determine a plurality of common values in the individuals; and

generate a difference comparison key that comprises the plurality of common values.