Linear and non-linear genetic algorithms for solving problems such as optimization, function finding, planning and logic synthesis

• US 20020169563A1
• Filed: 07/06/2001
• Published: 11/14/2002
• Est. Priority Date: 08/10/2000
• Status: Abandoned Application

• Current Assignee: Maria Candida De Carvalho Ferreira
• Original Assignee: Maria Candida De Carvalho Ferreira
• Inventors: de Carvalho Ferreira, Maria Candida
• Application Number:
  US09/899,282
• Publication Number:
  US 20020169563A1
• Time in Patent Office: Days
• US Class Current: 702/20
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The present invention is a mixed (linear and non-linear) genetic algorithm capable of learning and inventing. An initial population of linear chromosomes (linear entities) composed of genes containing the functions and arguments to a problem, is created and expressed as non-linear entities called expression trees. The non-linear entities are then executed, producing results. Then the results are assigned values and the respective individuals (linear entities and respective non-linear entities) are selected to reproduce according to these values. During reproduction, the linear entity or chromosome is subjected to one or several operators, namely, mutation, one-point recombination, two-point recombination, transposition, insertion and gene transposition. This way, new individuals are created which are in their turn executed, initializing a new cycle which is repeated as many times as necessary to discover a solution to the problem.

Claims

1. A genetic algorithm for solving problems such as optimization, function finding, planning and logic synthesis, using populations of individuals wherein the linear chromosome (linear entity) of said individuals has a determined length and is composed of one or more genes composed of a head containing symbols that represent functions and arguments and a tail containing symbols representing arguments, being said chromosome expressed as one or more non-linear sub-entities of different sizes and shapes called sub-expression trees, where said sub-expression trees are linked by a chosen function forming an expression tree which is an hierarchical arrangement of said symbols representing functions and arguments of said genetic algorithm comprising iterations of a series of steps, each iteration comprising the following steps:

expression of each said chromosome as said expression tree;

execution of each said expression tree against a set of fitness cases producing a result by performing each said function according to said hierarchical arrangement of functions and arguments;

assigning each said result to respective expression tree, being said result a measure of the fitness of said corresponding individual in solving the problem;

selecting individuals of said population according to said fitness, having individuals with greater fitness higher probability of being selected;

replicating as much said selected individuals as individuals in said population, wherein each said selected individual reproduces new descendants proportionally to said corresponding fitness being said descendants identical copies of corresponding selected individuals;

choosing and executing one or several operators, wherein each said chosen operator belongs to a set of operators comprising mutation, transposition, insertion, gene transposition, one-point recombination and two-point recombination;

if said chosen operator is mutation, said descendant is modified by changing at least one said symbol of said replicated chromosome for another without disrupting the structural and functional organization of said head and said tail of said genes producing a new descendant;

if said chosen operator is transposition, said descendant is modified by intra-chromosomal transposition of transposition elements randomly chosen among said symbols of said head to the start of a randomly chosen gene of said replicated chromosome without disrupting the structural and functional organization of said head and said tail of said chosen gene producing a new descendant;

if said chosen operator is insertion, said descendant is modified by intra-chromosomal insertion of insertion elements randomly chosen among said symbols of said replicated chromosome to said head of a randomly chosen gene without disrupting the structural and functional organization of said head and said tail of said chosen gene producing a new descendant;

if said chosen operator is gene transposition, said descendant is modified by intra-chromosomal transposition of a randomly chosen entire gene to start of said replicated chromosome producing a new descendant;

if said chosen operator is one-point recombination, at least two said replicated chromosomes are randomly chosen and paired to be modified by exchanging the material downstream the recombination point of said chosen replicated chromosomes producing two new descendants;

if said chosen operator is two-point recombination, at least two said replicated chromosomes are randomly chosen and paired to be modified by exchanging an entire gene producing two new descendants;

adding said new descendants to said population.

2. A genetic algorithm as set forth in claim 1, wherein said selection step further comprises a selection scheme that selects, most of the times, individuals according to said fitness as a random factor is incorporated in said selection scheme.

3. A genetic algorithm as set forth in claim 1, further comprising a selection and replication step wherein the individual with said higher fitness is selected and replicated forming a new descendant.

4. A genetic algorithm as set forth in claim 1, wherein an individual of said population having a pre-established value of fitness is the solution to the problem.

5. A genetic algorithm as set forth in claim 1, wherein the initial population of individuals is randomly generated creating chromosomes composed of one or more genes composed of a head containing symbols that represent functions and arguments and a tail containing symbols representing arguments.

6. In a computer system with a population of programs expressed as expression trees of different sizes and shapes, an iterative genetic algorithm comprising iterations of a series of steps, each iteration of said genetic algorithm comprising the steps:

expression of each said program as said expression tree;

execution of each said expression tree to produce a result;

assigning each said result to respective expression tree, being said result a measure of the fitness of said corresponding program in solving the problem;

selecting programs of said population according to said fitness, having programs with greater fitness higher probability of being selected;

replicating as much said selected programs as programs in said population, wherein each said selected program reproduces new programs proportionally to said corresponding fitness being said new programs identical copies of corresponding selected programs;

choosing and executing one or several operators, wherein each said chosen operator belongs to a set of operators comprising mutation, transposition, insertion, gene transposition, one-point recombination and two-point recombination;

if said chosen operator is mutation, said new program is modified by changing at least one said symbol of said replicated program for another without disrupting the structural and functional organization of said head and said tail of said genes producing a new program;

if said chosen operator is transposition, said new program is modified by intra-chromosomal transposition of transposition elements randomly chosen among said symbols of said head to the start of a randomly chosen gene of said replicated program without disrupting the structural and functional organization of said head and said tail of said chosen gene producing a new program;

if said chosen operator is insertion, said new program is modified by intra-chromosomal insertion of insertion elements randomly chosen among said symbols of said replicated program to said head of a randomly chosen gene without disrupting the structural and functional organization of said head and said tail of said chosen gene producing a new program;

if said chosen operator is gene transposition, said new program is modified by intra-chromosomal transposition of a randomly chosen entire gene to start of said replicated program producing a new program;

if said chosen operator is one-point recombination, at least two said replicated programs are randomly chosen and paired to be modified by exchanging the material downstream the recombination point of said chosen replicated programs producing two new programs;

if said chosen operator is two-point recombination, at least two said replicated programs are randomly chosen and paired to be modified by exchanging an entire gene producing two new programs;

adding said new programs to said population.

7. A genetic algorithm as set forth in claim 6, wherein said selection step further comprises a selection scheme that selects, most of the times, programs according to said fitness as a random factor is incorporated in said selection scheme.

8. A genetic algorithm as set forth in claim 6, further comprising a selection and replication step wherein the program with said higher fitness is selected and replicated forming a new program.

9. A genetic algorithm as set forth in claim 6, wherein a program of said population having a pre-established value of fitness is the solution to the problem.

10. A genetic algorithm as set forth in claim 6, wherein the initial population of programs is randomly generated creating programs composed of one or more genes composed of a head containing symbols that represent functions and arguments and a tail containing symbols representing arguments.

11. In a parallel processing computer system with a population of programs expressed as expression trees of different sizes and shapes where more than one program can be executed simultaneously, a set of parallel genetic algorithms, wherein more than one genetic algorithm of said set of genetic algorithms can be executed simultaneously, each said parallel genetic algorithm comprising iterations of a series of steps, each iteration of said parallel genetic algorithm comprising the steps:

expression of each said program as said expression tree;

execution of each said expression tree to produce a result;

assigning each said result to respective expression tree, being said result a measure of the fitness of said corresponding program in solving the problem;

selecting programs of said population according to said fitness, having programs with greater fitness higher probability of being selected;

replicating as much said selected programs as programs in said population, wherein each said selected program reproduces new programs proportionally to said corresponding fitness being said new programs identical copies of corresponding selected programs;

choosing and executing one or several operators, wherein each said chosen operator belongs to a set of operators comprising mutation, transposition, insertion, gene transposition, one-point recombination and two-point recombination;

if said chosen operator is mutation, said new program is modified by changing at least one said symbol of said replicated program for another without disrupting the structural and functional organization of said head and said tail of said genes producing a new program;

if said chosen operator is transposition, said new program is modified by intra-chromosomal transposition of transposition elements randomly chosen among said symbols of said head to the start of a randomly chosen gene of said replicated program without disrupting the structural and functional organization of said head and said tail of said chosen gene producing a new program;

if said chosen operator is insertion, said new program is modified by intra-chromosomal insertion of insertion elements randomly chosen among said symbols of said replicated program to said head of a randomly chosen gene without disrupting the structural and functional organization of said head and said tail of said chosen gene producing a new program;

if said chosen operator is gene transposition, said new program is modified by intra-chromosomal transposition of a randomly chosen entire gene to start of said replicated program producing a new program;

if said chosen operator is one-point recombination, at least two said replicated programs are randomly chosen and paired to be modified by exchanging the material downstream the recombination point of said chosen replicated programs producing two new programs;

if said chosen operator is two-point recombination, at least two said replicated programs are randomly chosen and paired to be modified by exchanging an entire gene producing two new programs;

adding said new programs to said population.

12. A genetic algorithm as set forth in claim 11, wherein said selection step further comprises a selection scheme that selects, most of the times, programs according to said fitness as a random factor is incorporated in said selection scheme.

13. A genetic algorithm as set forth in claim 11, further comprising a selection and replication step wherein the program with said higher fitness is selected and replicated forming a new program.

14. A genetic algorithm as set forth in claim 11, wherein a program of said population having a pre-established value of fitness is the solution to the problem.

15. A genetic algorithm as set forth in claim 11, wherein the initial population of programs is randomly generated creating programs composed of one or more genes composed of a head containing symbols that represent functions and arguments and a tail containing symbols representing arguments.