Method and system for reproduction in a genetic optimization process

Abstract

A reproduction method and system supports rapid convergence of a genetic optimization process. Mating, mutation, or both may be combined with biased parent selection during each mating season.

What is claimed is:  
     
         1 . A method for reproduction as part of a computer-implemented optimization process based on a genetic model, comprising the steps of: 
 (a) generating a set of mating combinations, each mating combination comprising a first chromosome and a second chromosome selected from a set of chromosomes, each chromosome comprising at least one gene;    (b) assigning a composite score to each mating combination; and    (c) selecting a particular mating combination using a biased random value, the biased random value favoring mating combinations having a favorable composite score, the first and second chromosomes of the particular mating combination comprising first and second parents, respectively.    
     
     
         2 . The method of  claim 1 , wherein assigning a composite score to each mating combination comprises computing the product of a first score associated with the first chromosome and a second score associated with the second chromosome.  
     
     
         3 . The method of  claim 1 , wherein step (c) comprises: 
 sorting the mating combinations from most favorable to least favorable according to their associated composite scores, each sorted mating combination having an associated index;    generating a random value distributed uniformly between zero and one;    raising the random value to a predetermined power greater than one to produce the biased random value;    multiplying the number of mating combinations by the biased random value to compute a selection index; and    selecting as the particular mating combination the mating combination whose index corresponds to the selection index.    
     
     
         4 . The method of  claim 1 , further comprising: 
 preventing the particular mating combination from being selected more than once.    
     
     
         5 . The method of  claim 1 , further comprising: 
 duplicating one of the first parent and the second parent to produce a child chromosome; and    mutating a gene in the child chromosome.    
     
     
         6 . The method of  claim 5 , wherein the gene to be mutated is selected randomly and mutating the gene in the child chromosome comprises randomly modifying the gene in the child chromosome.  
     
     
         7 . The method of  claim 1 , further comprising: 
 mating the first parent with the second parent to produce a child chromosome for a first predetermined fraction of children produced; and    mutating a copy of the first parent to produce a child chromosome for a second predetermined fraction of children produced.    
     
     
         8 . The method of  claim 1 , wherein each gene represents a characteristic of an instance in an integrated circuit, the characteristic comprising one of size and threshold voltage.  
     
     
         9 . A method for reproduction as part of a computer-implemented optimization process based on a genetic model, comprising the steps of: 
 generating a set of mating combinations, each mating combination comprising a first chromosome and a second chromosome selected from a set of chromosomes, each chromosome comprising at least one gene;    assigning a composite score to each mating combination;    sorting the mating combinations from most favorable to least favorable according to their associated composite scores, each sorted mating combination having an associated index;    generating a random value distributed uniformly between zero and one;    raising the random value to a predetermined power greater than one to produce a biased random value;    multiplying the number of mating combinations by the biased random value to compute a selection index; and    selecting the first and second chromosomes of the mating combination whose index corresponds to the selection index as first and second parents, respectively.    
     
     
         10 . The method of  claim 9 , further comprising: 
 preventing the mating combination whose index corresponds to the selection index from being selected more than once.    
     
     
         11 . The method of  claim 9 , further comprising: 
 duplicating one of the first parent and the second parent to produce a child chromosome; and    mutating a gene in the child chromosome.    
     
     
         12 . The method of  claim 11 , wherein the gene to be mutated is selected randomly and mutating the gene in the child chromosome comprises randomly modifying the gene in the child chromosome.  
     
     
         13 . The method of  claim 9 , further comprising: 
 mating the first parent with the second parent to produce a child chromosome for a first predetermined fraction of children produced; and    mutating a copy of the first parent to produce a child chromosome for a second predetermined fraction of children produced.    
     
     
         14 . The method of  claim 9 , wherein each gene represents a characteristic of an instance in an integrated circuit, the characteristic comprising one of size and threshold voltage.  
     
     
         15 . A method for reproduction as part of a computer-implemented process based on a genetic model for optimizing the power consumption and timing of an integrated circuit comprising a plurality of instances, the method comprising: 
 providing a set of chromosomes, each chromosome comprising a plurality of genes representing a set of design choices for the instances in the integrated circuit, each instance being mapped to a first gene representing the size of that instance and a second gene representing the threshold voltage of that instance;    simulating for each chromosome the power consumption and timing performance of an integrated circuit corresponding to the set of design choices specified by the genes in that chromosome;    assigning a score to each chromosome according to its simulated power consumption and timing performance;    generating a set of mating combinations, each mating combination comprising a first chromosome and a second chromosome selected from the set of chromosomes;    assigning a composite score to each mating combination, the composite score comprising the product of the score associated with the first chromosome and the score associated with the second chromosome;    sorting the mating combinations from most favorable to least favorable according to their associated composite scores, each sorted mating combination having an associated index;    generating a random value distributed uniformly between zero and one;    raising the random value to a predetermined power greater than one to produce a biased random value;    multiplying the number of mating combinations by the biased random value to compute a selection index; and    selecting the first and second chromosomes of the mating combination whose index corresponds to the selection index as first and second parents, respectively.    
     
     
         16 . The method of  claim 15 , further comprising: 
 preventing the mating combination whose index corresponds to the selection index from being selected more than once.    
     
     
         17 . The method of  claim 15 , further comprising: 
 duplicating one of the first parent and the second parent to produce a child chromosome; and    mutating a gene in the child chromosome.    
     
     
         18 . The method of  claim 17 , wherein the gene to be mutated is selected randomly and mutating the gene in the child chromosome comprises randomly modifying the gene in the child chromosome.  
     
     
         19 . The method of  claim 15 , further comprising: 
 mating the first parent with the second parent to produce a child chromosome for a first predetermined fraction of children produced; and    mutating a copy of the first parent to produce a child chromosome for a second predetermined fraction of children produced.    
     
     
         20 . A system programmed to perform the following method: 
 (a) providing a set of chromosomes, each chromosome comprising at least one gene;    (b) generating a set of mating combinations, each mating combination comprising a first chromosome and a second chromosome selected from the set of chromosomes;    (c) assigning a composite score to each mating combination; and    (d) selecting a particular mating combination using a biased random value, the biased random value favoring mating combinations having a favorable composite score, the first and second chromosomes of the particular mating combination comprising first and second parents, respectively.    
     
     
         21 . The system of  claim 20 , wherein step (d) of the method comprises: 
 sorting the mating combinations from most favorable to least favorable according to their associated composite scores, each sorted mating combination having an associated index;    generating a random value distributed uniformly between zero and one;    raising the random value to a predetermined power greater than one to produce a biased random value;    multiplying the number of mating combinations by the biased random value to compute a selection index; and    selecting as the particular mating combination the mating combination whose index corresponds to the selection index.    
     
     
         22 . The system of  claim 20 , wherein the method comprises the following additional steps: 
 duplicating one of the first parent and the second parent to produce a child chromosome; and    mutating a gene in the child chromosome.    
     
     
         23 . The system of  claim 20 , wherein the method comprises the following additional steps: 
 mating the first parent with the second parent to produce a child chromosome for a first predetermined fraction of children produced; and    mutating a copy of the first parent to produce a child chromosome for a second predetermined fraction of children produced.    
     
     
         24 . A system for performing reproduction as part of a computer-implemented optimization process based on a genetic model, comprising: 
 means for providing a set of chromosomes, each chromosome comprising at least one gene;    means for generating a set of mating combinations, each mating combination comprising a first chromosome and a second chromosome selected from the set of chromosomes;    means for assigning a composite score to each mating combination; and    means for selecting randomly a particular mating combination such that mating combinations having a favorable composite score are favored, the first and second chromosomes of the particular mating combination comprising first and second parents, respectively.    
     
     
         25 . The system of  claim 24 , wherein the means for selecting randomly a particular mating combination such that mating combinations having a favorable composite score are favored further comprises: 
 means for sorting the mating combinations from most favorable to least favorable according to their associated composite scores, each sorted mating combination having an associated index;    means for generating a random value distributed uniformly between zero and one;    means for raising the random value to a predetermined power greater than one to produce a biased random value;    means for multiplying the number of mating combinations by the biased random value to compute a selection index; and    means for selecting as the particular mating combination the mating combination whose index corresponds to the selection index.    
     
     
         26 . The system of  claim 24 , further comprising: 
 means for duplicating one of the first parent and the second parent to produce a child chromosome; and    means for mutating a gene in the child chromosome.    
     
     
         27 . The system of  claim 24 , further comprising: 
 means for mating the first parent with the second parent to produce a child chromosome for a first predetermined fraction of children produced; and    means for mutating a copy of the first parent to produce a child chromosome for a second predetermined fraction of children produced.    
     
     
         28 . A computer-readable storage medium containing program code to perform reproduction as part of an optimization process based on a genetic model, the computer-readable storage medium comprising: 
 a first code segment configured to generate a set of mating combinations, each mating combination comprising a first chromosome and a second chromosome selected from a set of chromosomes, each chromosome comprising at least one gene;    a second code segment configured to assign a composite score to each mating combination; and    a third code segment configured to select a particular mating combination using a biased random value, the biased random value favoring mating combinations having a favorable composite score, the first and second chromosomes of the particular mating combination comprising first and second parents, respectively.    
     
     
         29 . The computer-readable storage medium of  claim 28 , wherein the third code segment comprises instructions causing the computer to 
 sort the mating combinations from most favorable to least favorable according to their associated composite scores, each sorted mating combination having an associated index;    generate a random value distributed uniformly between zero and one;    raise the random value to a predetermined power greater than one to produce a biased random value;    multiply the number of mating combinations by the biased random value to compute a selection index; and    select as the particular mating combination the mating combination whose index corresponds to the selection index.    
     
     
         30 . The computer-readable storage medium of  claim 28 , further comprising: 
 a fourth code segment configured to duplicate the first parent to produce a child chromosome; and    a fifth code segment configured to mutate a gene in the child chromosome.    
     
     
         31 . The computer-readable storage medium of  claim 28 , further comprising: 
 a fourth code segment configured to mate the first parent with the second parent to produce a child chromosome for a first predetermined fraction of children produced; and    a fifth code segment configured to mutate a copy of the first parent to produce a child chromosome for a second predetermined fraction of children produced.