Speculative pool

• US 20050197978A1
• 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/761,478
• Publication Number:
  US 20050197978A1
• 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 provided for selecting a value set associated with a set of parameters. A system is disclosed that includes a real cost function that generates a plurality of real costs corresponding to a plurality of real chromosomes. A real pool maintains the plurality of real chromosomes and associated real costs. An incremental cost function generates a plurality of speculative costs corresponding to a plurality of speculative chromosomes. A speculative pool maintains the plurality of speculative chromosomes and associated speculative costs.

Claims

1. A system comprising:

a real cost function that generates real costs for each of a plurality of value sets represented as a plurality of real chromosomes;

a real pool that comprises the plurality of real chromosomes and associated real costs;

an incremental cost function that generates a plurality of speculative costs corresponding to a plurality of value set variations of at least one of the plurality of real chromosomes, the plurality of value set variations represented as a plurality of speculative chromosomes; and

a speculative pool that comprises the plurality of speculative chromosomes and associated speculative costs.

2. The system of claim 1, further comprising a genetic algorithm that generates the plurality of speculative chromosomes employing parent chromosomes selected from the real pool.

3. The system of claim 2, the genetic algorithm generates at least one subsequent generation of speculative chromosomes employing parents chromosomes selected from at least one of the real pool and the speculative pool.

4. The system of claim 3, the incremental cost function determines speculative costs for the at least one subsequent generation of speculative chromosomes by employing costs associated with at least one parent chromosome and a difference between value sets of a speculative chromosome and the at least one parent chromosome for at least some of the speculative chromosomes in the at least one subsequent generation.

5. The system of claim 4, further comprising a cost control component that replaces speculative chromosomes in the speculative pool with speculative chromosomes of subsequent generations having lower costs than the speculative chromosomes in the speculative pool.

6. The system of claim 1, further comprising a cost control component that orders the plurality of speculative chromosomes in the speculative pool based on speculative costs.

7. The system of claim 1, further comprising a cost control component that orders the plurality of real chromosomes in the real pool based on real costs.

8. The system of claim 1, further comprising a cost control component that initiates a validation of at least one speculative chromosome of the speculative pool, 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 and adding the at least one speculative chromosome to the real pool.

9. The system of claim 8, the cost control component replaces real chromosomes in the real pool with validated speculative chromosomes having lower real costs.

10. The system of claim 1, the real pool further comprising references to value sets stored in memory.

11. The system of claim 1, the speculative pool comprising references to value set variations stored in memory, speculative costs associated with the value set variations, and a speculative generation count corresponding to the value set variation.

12. The system of claim 1, the real cost function comprising an optimization tool for optimizing a circuit design, and the plurality of value sets being a plurality of circuit configurations generated by the optimization tool.

13. The system of claim 12, the real pool cost comprises real file data bases generated by the optimization tool, and the speculative pool comprises speculative file data bases generated by a genetic algorithm, the speculative file databases being circuit configuration variations of the real file data bases.

14. The system of claim 1, wherein N number of speculative chromosomes are retained in the speculative pool, where N is an integer greater than one, and M number of real chromosomes are retained in the real pool, where M is an integer greater than one, such that M is one of equal and not equal to N.

15. A computer-readable medium having stored thereon a data structure comprising:

speculative chromosomes that represent value set variations of at least one parent chromosome that represents a value set, the at least one parent chromosome comprising at least one of a real chromosome and a speculative chromosome;

speculative costs associated with a corresponding speculative chromosomes, the speculative cost being determined for a given speculative chromosome based on a cost of the at least one parent chromosome and a value set variation between the speculative chromosome and the at least one parent chromosome; and

speculative generation counts associated with each speculative chromosomes, the speculation generation count being based on a level of speculation from a real chromosome.

16. The data structure of claim 15, the speculative chromosomes comprising references to value set variations stored in memory.

17. The data structure of claim 15, the at least one parent chromosome comprising a first parent selected from one of a speculative chromosome and a real chromosome and a second parent selected from one of a speculative chromosome and a real chromosome.

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

means for generating a plurality of real chromosomes representing different value sets associated with a set of parameters;

means for determining real costs associated with a plurality of real chromosomes representing different value sets associated with a set of parameters;

means for maintaining the plurality of real chromosomes and associated real costs;

means for generating a plurality of speculative chromosomes from parent chromosomes selected from at least one of the plurality of speculative chromosomes and the plurality of real chromosomes;

means for determining a speculative cost for a respective speculative chromosome based on a cost of at least one parent chromosome and a difference in value sets of the at least one parent chromosome and the respective speculative chromosome; and

means for maintaining the plurality of speculative chromosomes and associated speculative costs.

19. The system of claim 18, the means for generating speculative chromosomes being operative to generate additional generations of speculative chromosomes from parents selected from the at least one of the plurality of speculative chromosomes and the plurality of real chromosomes.

20. The system of claim 19, the means for maintaining the plurality of speculative chromosomes and associated speculative costs further maintaining the speculative generation counts associated with a speculative chromosomes respective generation.

21. The system of claim 19, further comprising means for replacing speculative chromosome maintained in the means for maintaining the plurality of speculative chromosomes and associated speculative costs with speculative chromosomes of subsequent generations having lower speculative costs than the speculative chromosome being replaced.

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

23. The system of claim 22, further comprising means for replacing a real chromosome maintained in the means for maintaining the plurality of real chromosomes and associated real costs with validated speculative chromosomes having lower real costs than the real chromosomes being replaced.

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

generating real costs for each of a plurality of first value sets represented as a plurality of real chromosomes;

storing the plurality of real chromosomes and associated real costs in a real pool;

generating speculative costs for each of a plurality of second value sets represented as a plurality of speculative chromosomes, the speculative chromosomes representing value set variations of the first value sets; and

storing the plurality of speculative chromosomes and associated speculative costs in a speculative pool.

25. The method of claim 24, further comprising executing a genetic algorithm that selects parents from the plurality of real chromosomes to generate the plurality of speculative chromosomes.

26. The method of claim 25, further comprising executing a genetic algorithm that selects parents from at least one of the plurality of real chromosomes and the plurality of speculative chromosomes to generate subsequent generations of speculative chromosomes.

27. The method of claim 26, further comprising replacing speculative chromosomes from the speculative pool with speculative chromosomes from subsequent generations having lower speculative costs.

28. The method of claim 27, further comprising validating at least one speculative chromosome by determining a real cost associated with the at least one speculative chromosome, and replacing the real chromosomes with validated speculative chromosomes having lower real costs.

29. A computer-readable medium having computer-executable instructions for performing the method of claim 24.