Gene expression programming algorithm

• US 20030177105A1
• Filed: 03/18/2002
• Published: 09/18/2003
• Est. Priority Date: 03/18/2002
• Status: Active Grant

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Xiao, Weimin, Tirpak, Thomas Michael
• Granted Patent: US 7,127,436 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

A gene expression programming genetic algorithm for performing symbolic regression is provided. The algorithm avoids expression bloating and over fitting by employing a fitness function that depends inversely on the mathematical expression complexity. Members of a population that are evolved by the algorithm are represented as a set arrays (e.g., in the form of a matrix) of indexes that reference operands and operators, thus facilitating selection, mutation, and cross over operations conducted in the course of evolving the population. The algorithm comprises a syntax checking part that may be applied to population members without their having to be converted to executable programs first. An object-oriented programming language data structure is providing for encapsulating basic data for each codon (e.g., operand, operator) used by the algorithm.

Claims

1. A genetic algorithm based method for determining a mathematical expression that describes a set of real world data, the method comprising the steps of:

generating an initial population of representations of mathematical expressions that include a plurality of prime numbers; and

evolving a succession of generations derived from the initial population.

2. The method according to claim 1, wherein the plurality of prime numbers are selected from a predetermined list of prime numbers.

3. The method according to claim 1 wherein the step of evolving the succession of generations includes the steps of:

for a plurality of successive generations, mutating one or more representations of mathematical expressions from a current population of representations of the mathematical expressions by introducing representations of one or more prime numbers.

4. The method according to claim 1 wherein the step of evolving the succession of generations includes the steps of:

for a plurality of successive generations;

generating a set of programs embodying mathematical expressions that are represented in a population of representations of mathematical expressions of a current generation;

executing one or more of the set of programs for one or more sets of test data to obtain one or more results corresponding to the one or more of the sets of programs;

deriving one or more indications of fitness of the one or more of the set of programs from the one or more results;

selecting one or more of the representations from the population of representations of mathematical expressions of the current generation for duplication in a successive generation based on the indications of fitness;

performing one or more crossover operations between pairs of representations in the successive generation.

5. The method according to claim 4 further comprising the steps of:

for one or more of the plurality of the successive generations, mutating one or more representations of mathematical expressions from the current population of representations of the mathematical expressions by introducing representations of one or more prime numbers.

6. The method according to claim 1 wherein the initial population of representations of mathematical expressions comprises:

a set of arrays of indexes, wherein

a plurality of the arrays include a list of indexes representing a mathematical expression; and

a plurality of the indexes refer to elements selected from a group consisting of operators and operands.

7. A genetic algorithm based method for determining a mathematical expression that describes a set of real world data, the method comprising the steps of:

recursively generating a succession of populations of representations of mathematical expressions, wherein each representation includes;

identifications of one or more operators selected from a set of operators; and

identifications of one or more operands selected from a set of operands that includes constants and variables;

wherein each operand in the set of operands, and each operator in the set of operators is associated with a cost;

for each kth population in the succession of populations generating a set of programs that embody mathematical expressions represented in the kth population of representations;

deriving a first measure of fitness of each program in the set of programs by a process including the step of;

running the program on one or more sets of test data and comparing output values to predetermined values to obtain a measure of residual error;

deriving a second measure of fitness of each program in the set of programs by a process including the step of;

summing the cost of each operator and operand in the program; and

selectively duplicating individual representations of mathematical expressions in each successive generation based on the first and second measures of fitness.

8. The method according to claim 7 further comprising the step of:

combining the first measure of fitness with the second measure of fitness to obtain an overall measure of fitness.

9. A genetic algorithm based method for determining a mathematical expression that describes a set of real world data, the method comprising the steps of:

representing each of a succession of populations of mathematical expressions as a set of arrays of indexes, wherein each array represents a mathematical expression and one or more indexes in the set of arrays of indexes point to representations of expression elements selected from a group of elements consisting of operators and operands;

for each kth population of the succession of populations;

generating a program that embodies the mathematical expressions represented by each of one or more of the set of arrays in the population;

deriving a measure of fitness of each program;

selecting one or more high fitness arrays from the set of arrays based on the measure of fitness for carry over to a (k+1)th generation;

performing a cross over operation between one or more of the high fitness arrays carried over to the (k+1)th generation.

10. The method according to claim 9 wherein each index points to an instance of an object-oriented programming language class that encapsulates an identification of an element selected from a group consisting operators and operands.

11. The method according to claim 9 wherein the step of performing a crossover operation includes the sub step of:

exchanging a portion of a high fitness array with a portion of a second array, wherein starting points for the portion of the high fitness array and the portion of the second array are selected at random.

12. The method according to claim 9 wherein the set of arrays is stored as a matrix.

13. A genetic algorithm based method for determining a mathematical expression that describes a set of real-world data, the method comprising the steps of:

recursively generating a succession of generations of a population of sequences of symbols wherein each sequence of symbols represents a mathematical expression;

for each generation determining if each sequence of symbols can be translated into a viable program by;

for each sequence of symbols initializing a required length variable;

starting with a first symbol of each sequence, and for a

succession of kth symbols within each sequence;

increasing the required length variable by a number of symbols necessitated by syntax rules to form a viable operation with the kth symbol;

in the case that the required length variable after incrementing is equal to k reporting valid syntax; and

in the case that the required length variable when added to k exceeds a maximum sequence length reporting invalid syntax.

14. The method according to claim 13 wherein the step of recursively generating the succession of generations includes the sub step of:

randomly altering symbols in one or more sequences of symbols.

15. A method according to claim 13 wherein the step of recursively generating a succession of generations includes the sub step of:

selecting at random one or more points defining bounds of subsequences of symbols for exchange between sequences of symbols in the population.

16. A computer readable medium containing programming instructions for determining a mathematical expression that describes a set of real world data, including programming instructions for:

generating an initial population of representations of mathematical expressions that include a plurality of prime numbers; and

evolving a succession of generations derived from the initial population.

17. The computer readable medium according to claim 16, wherein the programming instructions for evolving the succession of generations include programming instructions for:

selecting the plurality of prime numbers a predetermined list of prime numbers.

18. The computer readable medium according to claim 16 wherein the programming instructions for evolving the succession of generations include programming instructions for:

for a plurality of successive generations, mutating one or more representations of mathematical expressions from a current population of representations of the mathematical expressions by introducing representations of one or more prime numbers.

19. The computer readable medium according to claim 16 wherein the programming instructions for evolving the succession of generations include programming instructions for:

for a plurality of successive generations;

generating a set of programs embodying mathematical expressions that are represented in a population of representations of mathematical expressions of a current generation;

executing one or more of the set of programs for one or more sets of test data to obtain one or more results corresponding to the one or more of the sets of programs;

deriving one or more indications of fitness of the one or more of the set of programs from the one or more results;

selecting one or more of the representations from the population of representations of mathematical expressions of the current generation for duplication in a successive generation based on the indications of fitness;

performing one or more crossover operations between pairs of representations in the successive generation.

20. The computer readable medium according to claim 19 wherein the programming instructions for evolving the succession of generations further comprise programming instructions for:

for one or more of the plurality of the successive generations, mutating one or more representations of mathematical expressions from the current population of representations of the mathematical expressions by introducing representations of one or more prime numbers.

21. The computer readable medium according to claim 16 wherein the initial population of representations of mathematical expressions comprises:

a set of arrays of indexes, wherein

a plurality of the arrays include a list of indexes representing a mathematical expression; and

a plurality of the indexes refer to elements selected from a group consisting of operators and operands.

22. A computer readable medium containing programming instructions for determining a mathematical expression that describes a set of real world data, including programming instructions for:

recursively generating a succession of populations of representations of mathematical expressions, wherein each representation includes;

identifications of one or more operators selected from a set of operators; and

identifications of one or more operands selected from a set of operands that includes constants and variables;

wherein each operand in the set of operands, and each operator in the set of operators is associated with a cost;

for each kth population in the succession of populations generating a set of programs that embody mathematical expressions represented in the kth population of representations;

deriving a first measure of fitness of each program in the set of programs by a process including the step of;

running the program on one or more sets of test data and comparing output values to predetermined values to obtain a measure of residual error;

deriving a second measure of fitness of each program in the set of programs by a process including the step of;

summing the cost of each operator and operand in the program; and

selectively duplicating individual representations of mathematical expressions in each successive generation based on the first and second measures of fitness.

23. The computer readable medium according to claim 22 further comprising programming instructions for:

combining the first measure of fitness with the second measure of fitness to obtain an overall measure of fitness.

24. A computer readable medium containing programming instructions for determining a mathematical expression that describes a set of real world data, including programming instructions for:

representing each of a succession of populations of mathematical expressions as a set of arrays of indexes, wherein each array represents a mathematical expression and one or more indexes point to representations of an expression element selected from a group of elements consisting of operators and operands;

for each kth population of the succession of populations;

generating a program that embodies the mathematical expressions represented by each array in the population;

deriving a measure of fitness of each generated program

selecting one or more high fitness arrays based on the measure of fitness for carry over to a (k+1)th generation;

performing a cross over operation between one or more of the high fitness arrays carried over to the (k+1)th generation.

25. The computer readable medium according to claim 24 wherein each index points to an instance of an object-oriented programming language class that encapsulates an identification of an element selected from a group consisting operators and operands.

26. The computer readable medium according to claim 25 wherein the programming instructions for performing a cross over operation includes programming instructions for:

exchanging a portion of a high fitness array with a portion of a second array, wherein starting points for the portion of the high fitness array and the portion of the second array are selected at random.

27. The computer readable medium according to claim 25 wherein the set of arrays is stored as a matrix.

28. A computer readable medium containing programming instructions for determining a mathematical expression that describes a set of real world data, including programming instructions for:

recursively generating a succession of generations of a population of sequences of symbols wherein each sequence of symbols represents a mathematical expression;

for each generation determining if each sequence of symbols can be translated into a viable program by;

for each sequence of symbols initializing a required length variable;

starting with a first symbol of each sequence, and for a succession of kth symbols within each sequence;

increasing the required length variable by a number of symbols necessitated by syntax rules to form a viable operation with the kth symbol;

in the case that the required length variable after incrementing is equal to k reporting valid syntax; and

in the case that the required length variable when added to k exceeds a maximum sequence length reporting invalid syntax.

29. The computer readable medium according to claim 28 wherein the programming instructions for recursively generating a succession of generations include programming instructions for:

randomly altering symbols in one or more sequences of symbols.

30. A computer readable medium according to claim 28 wherein the programming instructions for recursively generating a succession of generations include programming instructions for:

selecting at random one or more points defining bounds of subsequences of symbols for exchange between sequences of symbols in the population.

31. A computer readable medium having stored there on a data structure comprising:

an objected oriented programming language class including;

a codon name instance variable;

a codon type instance variable for storing a first number that is indicative of a number of codons that are to be associated with a codon specified in the codon name instance variable;

a codon value instance variable for storing a value associated with the codon specified in the codon name instance variable;

a codon cost instance variable for storing a second number that is indicative of a degree to which an operator or operand specified by the codon specified in the codon name instance variable increase complexity of a mathematical expression; and

a codon index instance variable for storing an index associated with each instance of the object-oriented programming language class.