Efficient storage of individuals for optimization simulation
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-015/18
G06N-003/00
G06N-003/12
출원번호
US-0948850
(2010-11-18)
등록번호
US-8515882
(2013-08-20)
발명자
/ 주소
Bell, Jr., Robert H.
Cantin, Jason F.
출원인 / 주소
International Business Machines Corporation
대리인 / 주소
DeLizio Gilliam, PLLC
인용정보
피인용 횟수 :
2인용 특허 :
46
초록▼
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 a
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.
대표청구항▼
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
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; andusing 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; andgenerating 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; andgenerating 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; andcompressing 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; andrearranging 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; andevaluating 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; andreplacing 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 non-transitory 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; andevaluate 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 non-transitory 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; anduse 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; andgenerate 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; andcompress 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; andrearrange 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; andan 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; anduse 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; andgenerate a difference comparison key that comprises the plurality of common values.
Carter, Frederick H.; Langley, Steven C.; Wallace, Mark T.; Meredith, Jeffrey T.; Butterworth, Paul E., Apparatus and method for web service message correlation.
Koza, John R.; Bennett, III, Forrest H; Andre, David; Keane, Martin A., Genetic programming problem solver with automatically defined stores loops and recursions.
Vail ; III William Banning, Method and apparatus to synthesize DNA and DNA-like molecular structures by applying electric fields to gaseous mixtures of chemical reactants containing template particulate matter.
Ulyanov,Serguei; Rizzotto,Gianguido; Kurawaki,Ichiro; Panfilov,Serguei; Ghisi,Fabio; Amato,Paolo; Porto,Massimo, Method and hardware architecture for controlling a process or for processing data based on quantum soft computing.
Bell, Jr., Robert H.; Capasso, Thomas Michael; Guthrie, Guy Lynn; Shen, Hugh; Stuecheli, Jeffrey Adam, Method and system for specualtively sending processor-issued store operations to a store queue with full signal asserted.
Bell, Jr., Robert H.; Capps, Jr., Louis Bennie; Cook, Thomas Edward; Daves, Glenn G.; Newhart, Ronald Edward; Paolini, Michael A.; Shapiro, Michael Jay, Multicore processor and method of use that adapts core functions based on workload execution.
Koza John R. (25372 La Rena La. Los Altos CA 94022) Rice James P. (Redwood City CA), Non-linear genetic process for data encoding and for solving problems using automatically defined functions.
Bell, Jr., Robert H.; Capps, Jr., Louis Bennie; Paolini, Michael A.; Shapiro, Michael Jay, Optimizing execution of single-threaded programs on a multiprocessor managed by compilation.
Koza John R. ; Andre David ; Tackett Walter Alden, Simultaneous evolution of the architecture of a multi-part program to solve a problem using architecture altering opera.
Koza John R. ; Andre David ; Tackett Walter Alden, Simultaneous evolution of the architecture of a multi-part program while solving a problem using architecture altering operations.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.