Gene expression programming with enhanced preservation of attributes contributing to fitness
First Claim
1. A genetic algorithm based method of finding a mathematical expression for a technical problem, the method comprising:
- generating an initial population of chromosomes wherein each chromosome encodes a mathematical expression and each chromosome includes operand genes and operator genes;
recursively generating a series of generations of populations of chromosomes from the initial population;
for each population of chromosomes;
selecting an elite group of chromosomes based on fitness to solve the technical problem;
identifying one or more groups of genes in each chromosome in the elite group;
determining a ranking of the groups of genes identified in the elite group according to their frequency in the elite group;
based on the ranking selectively retaining, as one or more derived genes, one or more of the groups of genes;
for each of the one or more derived functions, replacing each particular group of genes by a ID identifying the particular group of genes;
performing one or more evolutionary operations on the population of chromosomes to generate a new population of chromosomes; and
outputting information on a high fitness chromosome.
1 Assignment
0 Petitions
Accused Products
Abstract
A Gene Expression Programming method evolves a population of chromosomes which are arrays of integer index references to genes including operand and operator genes. The mathematical expressions are encoded in the chromosomes according to linear Polish notation, according to which expression, trees representing mathematical expression encoded in the chromosomes are developed in a depth-first manner from the sequence of genes in each chromosome. This type of Polish notation makes it more likely that sub-expressions that contribute to fitness will survive evolutionary operations which can be performed at a low computational cost on array chromosomes. Additionally subexpressions or the mathematical structure of subexpressions which are assumed to contribute significantly to fitness based on the frequency of their appearance in elite members are protected from alteration by evolutionary operations, by representing each such mathematical structure by a single derived gene while the evolutionary operations are performed.
19 Citations
27 Claims
-
1. A genetic algorithm based method of finding a mathematical expression for a technical problem, the method comprising:
-
generating an initial population of chromosomes wherein each chromosome encodes a mathematical expression and each chromosome includes operand genes and operator genes;
recursively generating a series of generations of populations of chromosomes from the initial population;
for each population of chromosomes;
selecting an elite group of chromosomes based on fitness to solve the technical problem;
identifying one or more groups of genes in each chromosome in the elite group;
determining a ranking of the groups of genes identified in the elite group according to their frequency in the elite group;
based on the ranking selectively retaining, as one or more derived genes, one or more of the groups of genes;
for each of the one or more derived functions, replacing each particular group of genes by a ID identifying the particular group of genes;
performing one or more evolutionary operations on the population of chromosomes to generate a new population of chromosomes; and
outputting information on a high fitness chromosome. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer readable medium storing a plurality of data structures that serve as population members in a genetic algorithm, wherein each of said data structures comprises:
an array including a plurality of indexes, wherein each index represents genetic programming gene selected from the group consisting of operands and operators, and wherein said plurality of indexes encode expression trees in Polish notation.
-
14. A computer readable medium storing a genetic algorithm based method of finding a mathematical expression for a technical problem, the computer readable medium including instructions for:
-
generating an initial population of chromosomes wherein each chromosome encodes a mathematical expression and each chromosome includes operand genes and operator genes;
recursively generating a series of generations of populations of chromosomes from the initial population;
for each population of chromosomes;
selecting an elite group of chromosomes based on fitness to solve the technical problem;
identifying one or more groups of genes in each chromosome in the elite group;
determining a ranking of the groups of genes identified in the elite group according to their frequency in the elite group;
based on the ranking selectively retaining, as one or more derived genes, one or more of the groups of genes;
for each of the one or more derived functions, replacing each particular group of genes by a ID identifying the particular group of genes; and
performing one or more evolutionary operations on the population of chromosomes to generate a new population of chromosomes; and
outputting information on a high fitness chromosome. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. A genetic algorithm system comprising:
-
a means for generating an initial population of chromosomes wherein each chromosome encodes a mathematical expression and each chromosome includes operand genes and operator genes;
a means for recursively generating a series of generations of populations of chromosomes from the initial population;
a means for selecting an elite group of chromosomes based on fitness to solve the technical problem from each population of chromosomes;
a means for identifying one or more groups of genes in each chromosome in the elite group;
a means for determining a ranking of the groups of genes identified in the elite group according to their frequency in the elite group;
a means for selectively retaining, as one or more derived genes, one or more of the groups of genes based on the ranking;
a means for replacing each particular group of genes by a ID identifying the particular group of genes; and
a means for performing one or more evolutionary operations on the population of chromosomes to generate a new population of chromosomes;
a means for outputting information on a high fitness chromosome.
-
-
27. The system according to claim 27 further comprising:
a means for using a high fitness mathematical expression that is encoded in the high fitness chromosome to perform information processing.
Specification