Gene expression programming based on hidden markov models
AssigneeMotorola, Inc.
InventorsChi Zhou, Magdi A. Mohamed, Weimin Xiao
Life of this patent
Estimating the term…
Abstract
Computer programs (600, 700, 800, 900, 1000) and a programmed computer (1100) for automatically generating computer programs (i.e. sequences of instructions) are provided. The computer programs (600, 700, 800, 900, 1000) use Hidden Markov Models (400, 500) to generate sequences of program tokens, e.g., Gene Expression Programming chromosomes (100). Parameters of the Hidden Markov Models (400, 500) are numerically optimized, for example, by Differential Evolution with a goal of increasing the fitness of automatically generated programs.
Claims15
A computer readable medium storing a computer program for automatically generating a problem solution, the computer program including program code for:
- generating an initial population of vectors of numerical parameters wherein each vector in the initial population includes initial state probabilities, state-to-state transition probabilities and solution token emission probabilities for a Hidden Markov Model for generating problem solutions;
- for each of a succession of generations recursively derived from said initial population until a stopping criteria is met:
- using each vector in a current generation to stochastically generate a plurality of evolutionary programming chromosomes each of which encodes a potential problem solution;
- evaluating a solution fitness of each potential problem solution encoded in each chromosome;
- ascribing a vector fitness to each particular vector based on at least one solution fitness associated with at least one potential problem solution generated from said particular vector;
- selecting at least one vector for use in forming a successive generation of vectors based on said vector fitness;
- performing evolutionary operations on vectors in said current generation in order to form a next generation of vectors;
- and
- when said stopping criteria has been met outputting information generated by the computer program.
A computer readable medium storing a first computer program automatically generating other computer programs, the first computer program including instructions for:
- generating an initial population of vectors of numerical parameters wherein each vector in the initial population includes initial state probabilities, state-to-state transition probabilities and program token emission probabilities for a Hidden Markov Model for generating computer programs;
- for each of a succession of generations recursively derived from said initial population until a stopping criteria is met:
- using each vector in a current generation to generate at least one evolutionary programming chromosomes which encodes at least one computer program;
- evaluating a program fitness of said at least one computer program encoded in said at least one chromosome;
- ascribing a vector fitness to each particular vector based
- on at least one program fitness associated with said at least one computer program generated from said particular vector;
- selecting at least one vector for use in forming a successive generation of vectors based on said vector fitness;
- performing evolutionary operations on vectors in each current generation in order to form a next generation of vectors;
- and
- when said stopping criteria has been met outputting information generated by the first computer program.
A computer readable medium storing a first computer program for automatically generating a second computer program, the first program including instructions for:
- calling a non-linear, non-differentiable function optimization computer program to optimize parameters of an objective function that includes a Hidden Markov Model for generating a sequence of gene expression programming genes, and wherein said parameters include initial state probabilities, state-to-state transition probabilities, and emission probabilities for said Hidden Markov Model;
- wherein said function optimization computer program calls said objective function and wherein said objective function includes program instructions for:
- generating at least one sequence of Gene Expression Programming genes from said Hidden Markov Model;
- if said at least one sequence of genes encodes a valid program, evaluating a measure of fitness of said valid program;
- returning a function of said measure of fitness to said function optimization computer program.
A computer readable medium storing a first program for automatically generating a second computer program, the first program comprising instructions for:
- initializing parameters of Hidden Markov Model for generating computer programs wherein said parameters include initial state probabilities, state-to-state transition probabilities and program token emission probabilities;
- for each of a succession of generations of gene expression programming chromosomes until a stopping criteria is met:
- using said Hidden Markov model to stochastically generate a current population of gene expression programming chromosomes each of which encodes a computer program;
- evaluating a program fitness of each computer program encoded in each chromosome;
- copying chromosomes into a next generation with frequencies of said chromosomes in said next generation based on said program fitness of each computer program encoded in each chromosome;
- training said Hidden Markov Model according to said next generation in order to determine new parameters for said Hidden Markov Model;
- when said stopping criteria has been met outputting information generated by the first program.
A computer for automatically generating a problem solution, the computer comprising a memory storing software and a microprocessor coupled to the memory, wherein the microprocessor is programmed by the software to:
- generate an initial population of vectors of numerical parameters wherein each vector in the initial population includes initial state probabilities, state-to-state transition probabilities and solution token emission probabilities for a Hidden Markov Model for generating chromosomes encoding potential problem solutions;
- for each of a succession of generations recursively derived from said initial population until a stopping criteria is met:
- use each vector in a current generation to stochastically generate a plurality of evolutionary programming chromosomes each of which encodes a potential problem solution;
- evaluate a solution fitness of each potential problem solution encoded in each chromosome;
- ascribe a vector fitness to each particular vector based on at least one solution fitness associated with at least one potential problem solution generated from said particular vector;
- select at least one vector for use in forming a successive generation of vectors based on said vector fitness;
- perform evolutionary operations on vectors in said current generation in order to form a next generation of vectors;
- and
- when said stopping criteria has been met output information generated by the computer program.
Dependencies are inferred from the claim text.