Adaptive computing systems, computer readable memories and processes employing hyperlinear chromosomes

• US 5,819,244 A
• Filed: 10/02/1995
• Issued: 10/06/1998
• Est. Priority Date: 10/02/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Smith, Brian L.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Rhodes, Jason W.
• Application Number:
  US08/538,508
• Time in Patent Office: 1,100 Days
• Field of Search: 395/13, 706/13, 706/12, 706/14, 706/10
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Hyperlinear chromosomes are arrays of parameters stored in a computer readable memory, for use in implementing a genetic algorithm. Each chromosome may represent the mapping of a problem, including physical parameters, onto constituent genes which are addressed in memory as multiple, intersecting vectors in n-dimensions, where n is >2. A computing system is adapted to perform hyperlinear crossover, reproduction and fitness evaluation on the hyperlinear chromosomes. An adaptive computing system produces optimized control signals based on the attainment of a desired level of fitness of one or more hyperlinear chromosomes.

Claims

1. An adaptive computing system for receiving input information and producing an optimized control signal based on a sequence of simultaneous equations sharing at least some parameters comprising:

a computer readable, population memory for storing groups of parameters, each group corresponding to a member of the population;

means for storing parameters for a member of the population in the population memory at an n dimensional address where n is ≧

2, and wherein parameters of each individual equation of that member are arranged in sequentially addressed memory locations to form low-order schemata relevant to the computation and wherein a parameter common to two or more equations is located at a single memory location which lies at an intersection of the sequentially addressed memory locations constituting the equations which share the parameter;

means for retrieving parameters corresponding to each individual equation from the sequentially addressed memory locations;

a random number generator;

means responsive to the random number generator for dividing into at least two portions, the n dimensional array of addresses defining each of at least two members of the population

and for combining the divided portions of the at least two members of the population to form a new population member;

means for evaluating, on the basis of the input information, the equations defined by the parameters stored for a member of the population to determine the fitness of the member of the population;

means for reproducing population members at least partially in response to the evaluated fitness of the member; and

control means for repetitively retrieving, combining, reproducing, evaluating and storing said population members and for producing an optimized control signal on the attainment of a predetermined level of fitness of one or more members based on the input information,

wherein said means for dividing and for combining comprises;

means for randomly selecting one of the n dimensions;

means for dividing the chromosome into parallel substrings lying along the selected dimension;

means for selecting one of said substrings of the chromosome;

means for randomly selecting a crossover point in the selected substring;

means for dividing the chromosome at the selected crossover point; and

means for creating at least one new chromosome by combining portions of two divided chromosomes.

2. A machine comprising:

a memory which contains data representing a population of hyperlinear program chromosomes in which each hyperlinear program chromosome represents the mapping of physical problem parameters onto program genes which are addressed in memory as multiple, intersecting vectors in n dimensions, where n is ≧

2; and

a processor for selecting, evaluating and creating the population of hyperlinear program chromosomes, the processor comprising;

means for iteratively creating new hyperlinear chromosomes by performing hyperlinear crossover of members of the hyperlinear program chromosome population;

means for evaluating the fitness of the chromosomes to solve the physical problem; and

means for selecting hyperlinear chromosomes for the next generation on the basis of the evaluated fitness of the chromosomes to solve the problem,

wherein said means for iteratively creating new hyperlinear chromosomes comprises;

means for randomly selecting one of the n dimensions;

means for dividing the chromosome into parallel substrings lying along the selected dimension;

means for selecting one of said substrings of the chromosome;

means for randomly selecting a crossover point in the selected substring;

means for dividing the chromosome at the selected crossover point; and

means for creating at least one new chromosome by combining portions of two divided chromosomes.

3. The machine of claim 2, wherein n is equal to 3.

4. The machine of claim 3, wherein the memory is a three-dimensional optical memory in which the data representing each hyperlinear program chromosome is stored in a physical location corresponding to the three-dimensional arrangement of the multiple intersecting vectors.

5. The machine of claim 4, wherein the program genes of the hyperlinear program chromosomes have the same bit length.

6. The machine of claim 2, wherein the physical problem is represented by a sequence of simultaneous equations and wherein the vectors are arranged to form low-order schemata relevant to the computation.

7. The machine of claim 2, wherein genes on the extremities of a dimension are addressed as being adjacent to one another.

8. The machine of claim 2, wherein said means for iteratively creating new hyperlinear chromosomes performs hyperlinear crossover based on a random selection of one of the n dimensions of the hyperlinear program chromosome.

9. A machine for providing control output signals to a system responsive to sensed, environmental conditions of the system wherein the system is modeled by a plurality of simultaneous equations which equations share at least some parameters comprising:

memory for storing hyperlinear chromosome populations into which the terms of each of the simultaneous equations are mapped as sequential genes, the hyperlinear chromosomes being n dimensional where n ≧

2;

parallel processing means for simultaneously evaluating the fitness of members of the hyperlinear chromosome population;

means for repetitively generating new hyperlinear chromosomes responsive to the evaluated fitness of the chromosome including means for effecting hyperlinear crossover to produce members of a succeeding generation of hyperlinear chromosomes;

means for selecting one or more of the hyperlinear chromosomes to generate output control signals responsive to current sensed parameters of the system;

wherein said means for effecting hyperlinear crossover comprises;

means for randomly selecting one of the n dimensions;

means for dividing the chromosome into parallel substrings lying along the selected dimension;

means for selecting one of said substrings of the chromosome;

means for randomly selecting a crossover point in the selected substring;

means for dividing the chromosome at the selected crossover point; and

means for creating at least one new chromosome by combining portions of two divided chromosomes.

10. The machine of claim 9, wherein said means for effecting hyperlinear crossover performs hyperlinear crossover based on a random selection of one of the n dimensions of the hyperlinear program chromosome.

11. A process for problem solving residing in a computer system comprising

providing a computer readable memory for storing initial and subsequent hyperlinear chromosome populations, the hyperlinear chromosomes being n dimensional where n ≧

2, and at least one processor for selecting, evaluating and creating hyperlinear chromosome populations and further comprising iterations of a series of steps, each iteration including the steps of

creating new hyperlinear chromosomes including the step of performing hyperlinear crossover of members of the hyperlinear chromosome population;

evaluating the fitness of hyperlinear chromosomes to solve the problem; and

selecting hyperlinear chromosomes for the next generation on the basis of the evaluated fitness of the chromosomes to solve the problem,

wherein the step of performing hyperlinear crossover comprises the steps of;

randomly selecting one of the n dimensions;

dividing the chromosome into parallel substrings lying along the selected dimension;

selecting one of said substrings of the chromosome;

randomly selecting a crossover point in the selected substring;

dividing the chromosome at the selected crossover point; and

creating at least tone new chromosome by combining portions of two divided chromosomes.

12. The process of claim 11, wherein the hyperlinear chromosomes are three-dimensional.

13. The process of claim 12, wherein the step of performing hyperlinear crossover includes the steps of

randomly selecting one of the three dimensions;

dividing the chromosome into parallel substrings lying along the selected dimension;

selecting one of said substrings of the chromosome;

randomly selecting a crossover point in the selected substring;

dividing the chromosome at the selected crossover point; and

creating at least one new chromosome by combining portions of two divided chromosomes.

14. The process of claim 13, wherein the crossover point is selected to coincide with a gene boundary.

15. The process of claim 13, wherein the crossover point is selected to lie within a bit string corresponding to a single gene.

16. The process of claim 11, wherein the hyperlinear chromosomes are comprised of genes of equal bit length and wherein the genes are arranged within the memory as cubes within a rectangular-solid-shaped volume which contains the chromosome.

17. The process of claim 16, wherein the hyperlinear crossover is effected by cleaving rectangular-solid-shaped chromosomes into three-dimensional portions, and recombining portions of the chromosomes to produce a new chromosome having the same dimensions as the parent chromosomes.

18. The process of claim 11, wherein the hyperlinear crossover is selected to occur at the boundary of genes which effect the evaluation of fitness of the chromosome.

19. The process of claim 11, wherein the hyperlinear crossover is selected to occur within a bit string corresponding to genes which effect the evaluation of fitness of the chromosome.

20. The process of claim 11, wherein the hyperlinear crossover is performed based on a random selection of one of the n dimensions of the hyperlinear program chromosome.