Method of using multiple populations with cross-breeding in a genetic algorithm

• US 6,859,796 B1
• Filed: 07/19/2001
• Issued: 02/22/2005
• Est. Priority Date: 07/19/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Seward, Robert Y.
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/907,904
• Time in Patent Office: 1,314 Days
• Field of Search: 706/13, 706/12, 706/8, 705/4
• US Class Current: 706/13
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method is disclosed for processing data to identify optimal solutions to a problem using a genetic algorithm. Multiple populations of data entries, referred to as solutions, are created and kept separate from each other. Solutions are rated based on their desirability. Solutions from one population are combined, or “cross-bred,” with solutions from another population to create offspring solutions. The offspring of the cross-over are associated with one of the parent populations and rated. The most desirable solutions within a population are selected from the parent and offspring solutions to form the next generation of solutions. The remaining solutions may be discarded from the population. The cross-over and selection steps may then be repeated using second-generation solutions to create a third generation. The method may be implemented, for example, to design the layout of a circuit board. Diversity of solutions is increased by keeping the populations separate but allowing cross-breeding.

Claims

1. A method, comprising code executable on a general purpose computer, of selecting a solution for optimum layout of an integrated circuit, comprising:

creating first and second separate populations of parent solutions;

combining at least one of the parent solutions from the first population with at least one of the parent solutions from the second population to create offspring solutions;

adding the offspring solutions to the first population; and

selecting second-generation solutions of the integrated circuit layout for the first population from the offspring solutions and the parent solutions.

2. The method of claim 1, further comprising keeping the second-generation solutions and discarding all remaining solutions in the first population.

3. The method of claim 1, further comprising associating scores with each of the parent solutions and offspring solutions, and wherein the step of selecting comprises selecting the second-generation solutions based on the scores.

4. The method of claim 1, further comprising combining at least one of the second-generation solutions from the first population with at least one second-generation solution from the second population.

5. The method of claim 1, further comprising mutating at least one of the second-generation solutions.

6. The method of claim 1, further comprising keeping the first population separate from the second population.

7. The method of claim 1, wherein the step of combining comprises combining each of the parent solutions in the first population with at least one of the parent solutions in the second population.

8. A computer-readable medium having computer-executable instructions for performing a method on a computer for selecting solution for optimum layout of an integrated circuit, the method comprising:

combining at least one parent solution from a first population with at least one parent solution from a second population to create offspring solutions;

associating the offspring solutions with the first population; and

selecting second-generation solutions of the integrated circuit layout for the first population from the offspring solutions and the first population parent solutions.

9. The medium of claim 8, wherein the method further comprises keeping the second-generation solutions and discarding all remaining solutions in the first population.

10. The medium of claim 8, wherein the method further comprises associating scores with each of the parent solutions and offspring solutions, and wherein the step of selecting comprises selecting the second generation solution based on the scores.

11. The medium of claim 8, wherein the method further comprises combining at least one of the second-generation solutions from the first population with at least one second-generation solution from the second population.

12. The medium of claim 8, wherein the method further comprises mutating at least one of the second-generation solutions.

13. The medium of claim 8, wherein the method further comprises keeping the first population separate from the second population.

14. The medium of claim 8, wherein the step of combining comprises combining each of the parent solutions in the first population with at least one of the parent solutions in the second population.

15. A computer system comprising:

a storage medium; and

a processor for executing a software program stored on the storage medium for selecting a solution for optimum layout of an integrated circuit, the software program comprising a set of instructions for;

combining at least one parent solution from a first population with at least one parent solution from a second population to create offspring solutions;

associating the offspring solutions with the first population; and

selecting second-generation solutions of the integrated circuit layout for the first population from the offspring solutions and first population parent solutions.

16. The system of claim 15, wherein the set of instructions further comprises a set of instructions for keeping the second-generation solutions and discarding all remaining solutions in the first population.

17. The system of claim 15, wherein the set of instructions further comprises a set of instructions for associating scores with each of the parent solutions and offspring solutions, and wherein the step of selecting comprises selecting the second generation solutions based on the scores.

18. The system of claim 15, wherein the set of instructions further comprises a set of instructions for combining at least one of the second-generation solutions from the first population with at least one second-generation solution from the second population.

19. The system of claim 15, wherein the set of instructions further comprises a set of instructions for mutating at least one of the second-generation solutions.

20. The system of claim 15, wherein the set of instructions for combining comprising combining each of the parent solutions in the first population with at least one of the parent solutions in the second population.