OBJECT ORIENTED GENETIC PROGRAMMING

• US 20090319990A1
• Filed: 06/01/2009
• Published: 12/24/2009
• Est. Priority Date: 06/22/2008
• Status: Abandoned Application

• Current Assignee: 7163177 Canada Limited
• Original Assignee: 7163177 Canada Limited
• Inventors: Oppacher, Frank, Fan, Jinfei
• Application Number:
  US12/475,819
• Publication Number:
  US 20090319990A1
• Time in Patent Office: Days
• US Class Current: 717/116
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Methods and systems for performing object oriented genetic programming are provided. According to one embodiment, a population of computer program representations are varied to create a new population by generating additional computer program representations based on those of the computer program representations selected in accordance with a selection strategy. Each computer program representation is modeled as a linear array of genes, each gene having domain-specific values and an action or operation to be performed on the basis of the domain-specific values. It is determined whether any computer program representations of the new population satisfy any predetermined performance criteria. If so, then such computer program representations are identified as potential solutions to the problem at issue; otherwise, subsequent generations are generated until one or more predetermined performance criteria are satisfied.

Claims

1. A method of identifying a computer program solution to a problem at issue in a particular domain, the method comprising:

one or more software modules varying a population of a plurality of computer program representations tangibly embodied within a computer-readable medium to create a new population by generating additional computer program representations based on one or more of the plurality of computer program representations selected in accordance with a selection strategy, each of the plurality of computer program representations modeled as a linear array of genes, each gene of which has associated therewith one or more domain-specific values and an action or operation to be performed on the basis of the one or more domain-specific values;

the one or more software modules determining whether any computer program representations of the new population satisfy one or more predetermined performance criteria;

if the one or more predetermined performance criteria are satisfied by one or more of the computer program representations of the new population, then the one or more software modules identifying the one or more of the computer program representations as potential solutions to the problem at issue;

if none of the computer program representations of the new population satisfy the predetermined performance criteria, then the one or more software modules continuing to generate one or more subsequent generations until the one or more predetermined performance criteria are satisfied; and

wherein the one or more software modules are implemented in one or more processors and one or more computer-readable media of one or more computer systems, the one or more computer-readable media having instructions tangibly embodied therein that are executable by the one or more processors.

2. The method of claim 1, wherein the selection strategy comprises selecting for inclusion within the new population a predetermined or configurable percentage of the population that performs better than a remaining portion of the population as measured by a fitness function.

3. The method of claim 1, wherein the selection strategy comprises randomly choosing a first parent from a first portion of the population and randomly choosing a second parent from a second portion of the population.

4. The method of claim 3, wherein the first portion of the population exhibits performance as measured by a fitness function that is deemed more desirable than performance exhibited by the second portion of the population.

5. The method of claim 3, wherein said generating additional computer program representations comprises generating an offspring to be included within the new population by performing a crossover operation based on the first parent and the second parent.

6. The method of claim 5, further comprising mutating the offspring by randomly replacing at least a portion of the linear array of genes.

7. The method of claim 1, wherein each gene comprises a portion of source code of the corresponding computer program representation.

8. The method of claim 1, wherein each gene comprises data for input to Code Document Object Model statement classes.

9. The method of claim 1, wherein the one or more predetermined performance criteria comprise a measure of proximity between a result generated by a computer program representations of the new population and a predetermined result.

10. The method of claim 1, wherein the action or operation comprises a no-op operation.

11. A computer-readable storage medium tangibly embodying a set of instructions, which when executed by one or more processors of one or more computer systems, cause the one or more processors to:

vary a population of a plurality of computer program representations tangibly embodied within a computer-readable medium to create a new population by generating additional computer program representations based on one or more of the plurality of computer program representations selected in accordance with a selection strategy, each of the plurality of computer program representations modeled as a linear array of genes, each gene of which has associated therewith one or more domain-specific values and an action or operation to be performed on the basis of the one or more domain-specific values;

determine whether any computer program representations of the new population satisfy one or more predetermined performance criteria;

identify the one or more of the computer program representations as potential solutions to the problem at issue if the one or more predetermined performance criteria are satisfied by one or more of the computer program representations of the new population;

continue to generate one or more subsequent generations until the one or more predetermined performance criteria are satisfied if none of the computer program representations of the new population satisfy the predetermined performance criteria.

12. The computer-readable storage medium of claim 11, wherein the selection strategy comprises selecting for inclusion within the new population a predetermined or configurable percentage of the population that performs better than a remaining portion of the population as measured by a fitness function.

13. The computer-readable storage medium of claim 11, wherein the selection strategy comprises randomly choosing a first parent from a first portion of the population and randomly choosing a second parent from a second portion of the population.

14. The computer-readable storage medium of claim 13, wherein the first portion of the population exhibits performance as measured by a fitness function that is deemed more desirable than performance exhibited by the second portion of the population.

15. The computer-readable storage medium of claim 13, wherein said generating additional computer program representations comprises generating an offspring to be included within the new population by performing a crossover operation based on the first parent and the second parent.

16. The computer-readable storage medium of claim 15, wherein the set of instructions further cause the one or more processors to mutate the offspring by randomly replacing at least a portion of the linear array of genes.

17. The computer-readable storage medium of claim 11, wherein each gene comprises a portion of source code of the corresponding computer program representation.

18. The computer-readable storage medium of claim 11, wherein each gene comprises data for input to Code Document Object Model statement classes.

19. The computer-readable storage medium of claim 11, wherein the one or more predetermined performance criteria comprise a measure of proximity between a result generated by a computer program representations of the new population and a predetermined result.

20. The computer-readable storage medium of claim 11, wherein the action or operation comprises a no-op operation.