Method and system for reproduction in a genetic optimization process

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.

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.

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.

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.

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.