Speculation count in a genetic algorithm

• US 20050197979A1
• Filed: 01/21/2004
• Published: 09/08/2005
• Est. Priority Date: 01/21/2004
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Anderson, David M., Chen, Thomas W., McGuffin, Tyson R.
• Application Number:
  US10/762,099
• Publication Number:
  US 20050197979A1
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Systems and methods are disclosed for selecting a value set associated with a set of parameters. A genetic algorithm generates at least one generation of speculative chromosomes that represent value set variations of a plurality of value sets. Each generation of speculative chromosomes are assigned a speculative count corresponding to a speculative chromosome generation. Validation is initiated once at least one speculative chromosome has a predetermined speculative count.

Claims

1. A system comprising:

a plurality of value sets represented as a plurality of real chromosomes;

a genetic algorithm that generates at least one generation of speculative chromosomes, the speculative chromosomes representing value set variations of the plurality of value sets, each generation of speculative chromosomes being assigned a speculative count corresponding to a speculative chromosome generation; and

a validator that initiates a validation once at least one speculative chromosome has a predetermined speculative count.

2. The system of claim 1, further comprising a real cost function that determines real costs for the plurality of real chromosomes, and an incremental cost function that determines speculative costs for speculative chromosomes.

3. The system of claim 2, the validation comprising executing the real cost function on the at least one speculative chromosome to provide a real cost associated with the at least one speculative chromosome.

4. The system of claim 1, the genetic algorithm generates a speculative child chromosome from at least one of a first parent chromosome and a second parent chromosome, wherein the speculative child chromosome is assigned a speculative count that is higher than the speculative count of the parent chromosome having the higher speculative count.

5. The system of claim 4, the at least one of a first parent chromosome and a second parent chromosome is selected from at least one of the plurality of real chromosomes and subsequent generations of speculative chromosomes

6. The system of claim 1, further comprising a speculation counter that increments for each new generation of speculative chromosomes generated by the genetic algorithm.

7. The system of claim 6, the validator initiates a validation on at least one speculative chromosome when the speculation counter has achieved a count value equal to the predetermined speculative count.

8. The system of claim 1, further comprising a speculative pool that stores speculative chromosomes and assigned speculative counts.

9. The system of claim 8, the validator initiates a validation once at least one speculative chromosome in the speculative pool has a predetermined speculative count.

10. The system of claim 9, the validator initiates a validation on the entire speculative pool once at least one speculative chromosome in the speculative pool has a predetermined speculative count.

11. The system of claim 1, the plurality of value sets being a plurality of circuit configurations generated by an optimization tool.

12. A method for selecting a value set associated with a set of parameters, the method comprising:

determining real costs for a plurality of real chromosomes that represent a plurality of value sets;

generating at least one generation of speculative chromosomes that represent value set variations of the plurality of value sets;

assigning a speculative count to speculative chromosomes based on a corresponding generation of the speculative chromosome;

approximating speculative costs for the speculative chromosomes; and

repeating the generating of speculative chromosome generations, assigning speculative chromosomes and approximating speculative costs, until at least one speculative chromosome has a predetermined speculative count.

13. The method of claim 12, the determining real costs further comprising executing a real cost function on the plurality of real chromosomes and the approximating speculative costs comprising executing an incremental cost function on the speculative chromosomes.

14. The method of claim 13, the execution of the real cost function comprising optimizing a circuit design, and the plurality of value sets being a plurality of circuit configurations generated by the optimization.

15. The method of claim 14, the speculative chromosomes representing speculative file databases that are circuit configuration variations of real file data bases, each real file data base defines a circuit configuration.

16. The method of claim 12, the generating at least one generation of speculative chromosomes comprising executing a genetic algorithm that employs parent chromosomes selected from at least one of real chromosomes and speculative chromosomes.

17. The method of claim 16, wherein a speculative child chromosome is generated from at least one of a first parent chromosome and a second parent chromosome, wherein the speculative child chromosome is assigned a speculative count that higher than the speculative count of a parent chromosome having a higher speculative count.

18. The method of claim 12, further comprising incrementing a speculation counter for each new generation of speculative chromosomes, a validation being initiated when the speculative counter has a predetermined speculative count.

19. The method of claim 12, further comprising executing a validation of the at least one speculative chromosome when at least one speculative chromosome has a predetermined speculative count, the validation comprising executing a real cost function on the at least one speculative chromosome to provide a real cost associated with the at least one speculative chromosome.

20. The method of claim 12, further comprising storing speculative chromosomes and associated speculative counts in a speculative pool, a validation being initiated when a speculative chromosome in the speculative pool has a predetermined speculative count.

21. The method of claim 20, further comprising validating the entire speculative pool when at least one speculative chromosome has a predetermined speculative count.

22. A computer readable medium having computer executable instructions for performing a method comprising:

generating at least one generation of speculative chromosomes that represent value set variations of a plurality of value sets;

assigning a speculative count to speculative chromosomes based on a corresponding generation of the speculative chromosome; and

repeating the generating of speculative chromosome generations and assigning speculative counts, until at least one speculative chromosome has a predetermined speculative count.

23. The method of claim 22, further comprising approximating costs associated with speculative chromosomes in each speculative chromosome generation.

24. The method of claim 22, further comprising determining real costs associated with at least one speculative chromosome once at least one speculative chromosome has a predetermined speculative count.

25. The method of claim 22, further comprising storing a plurality of speculative chromosomes in a speculative pool, and determining real costs associated with the entire pool once at least one speculative chromosome in the speculative pool has a predetermined speculative count.

26. A system for minimizing a cost associated with a set of parameters representing a solution, the system comprising:

means for determining real costs associated with a plurality of real chromosomes;

means for generating generations of speculative chromosomes with assigned speculative counts corresponding to a generation number of the speculative chromosome, the speculative chromosome being assigned a speculative count that is higher than a parent chromosome from which it is derived; and

means for postponing validation of at least one speculative chromosome, until at least one speculative chromosome has a predetermined speculative count.

27. The system of claim 26, further comprising means for determining a speculative cost for a respective speculative chromosome.

28. The system of claim 26, further comprising means for validating, the means for validating executing a validation by executing the means for determining a real cost on at least one speculative chromosome.

29. The system of claim 28, the means for validating executing the means for determining a real cost on a plurality of speculative chromosomes retained in a speculative pool.