Cellular array for implementing the set merging function

• US 6,477,519 B1
• Filed: 11/19/2001
• Issued: 11/05/2002
• Est. Priority Date: 11/19/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Shackleford, J. Barry
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/988,124
• Time in Patent Office: 351 Days
• Field of Search: 706/45, 706/13, 707/6, 716/9, 716/2
• US Class Current: 706/45
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

An iterative array of identical cells to implement a crossover function in a genetic algorithm. Each function cell receives two input values and two select values that determine which input value is outputted. By creating an array of these cells, two sets of information of any size can be rapidly and accurately merged to form one set composed of elements of both sets. The cellular array uses identical, repeated cells to implement the crossover function according to precise guidelines. These guidelines are that no data is to be repeated and no data is to be lost, while retaining the order of the parent chromosomes used in crossover.

Claims

1. A merging circuit for use in a crossover step of a genetic algorithm machine, said merging circuit merging at least two parent chromosomes to form a child chromosome, said child chromosome having a plurality of respective elements thereof each selected from at least one of said parent chromosomes, said merging circuit comprising:

an array of cells in a square configuration of rows and columns, the number of cells in each row and column corresponding to the number of elements in said parent and child chromosomes; and

a control select connected to said array, said array, upon receipt of said control select, selecting said plurality of respective elements between said at least two parent chromosomes to form said child chromosome, each of said plurality of respective elements selected by said array being different.

2. The merging circuit according to claim 1, wherein in said array

each cell of said array receives initial values relative to the respective elements of a first and a second parent chromosome, said initial values relative to the respective elements of said first parent chromosome being received in said rows of said array, and said initial values relative to the respective elements of said second parent chromosome being received in said columns of said array;

each said cell of said array selects between said initial values relative to the respective elements of said first and said second parent chromosomes pursuant to said control select; and

each said cell of said array transmits the selected values relative to the respective elements of said first parent chromosome and said second parent chromosome, said selected values relative to the respective elements of said first parent chromosome being transmitted to respective adjacent rows of said array, and said selected values relative to the respective elements of said second parent chromosome being transmitted to respective adjacent columns of said array.

3. The merging circuit according to claim 2, wherein in said merging circuit

said control select is divided into a first and a second part, said first part of said control select selecting respective elements of said first parent chromosome, said second part of said control select selecting respective elements of said second parent chromosome;

and

said child chromosome is formed from said respective elements of said first parent chromosome and said respective elements of said second parent chromosome pursuant to said control select,

wherein said respective elements from said first parent chromosome and from said second parent chromosome are selected pursuant both to said first and to said second part of said control select and to said initial values from said respective elements of said first parent chromosome and from said second parent chromosome.

4. The merging circuit according to claim 3, wherein each respective element of said second parent chromosome is compared to each respective element of said first parent chromosome, and when the two respective elements of said first and second parent chromosomes are equal, then the respective element of said first parent chromosome is used to form the respective elements of said child chromosome.

5. The merging circuit according to claim 2, wherein said control select indicates only respective elements from said first parent chromosome, said respective elements of said first parent chromosome forming said child chromosome pursuant to said control select.

6. The merging circuit according to claim 1, wherein said genetic algorithm machine solves a non-deterministic polynomial problem.

7. The merging circuit according to claim 6, wherein said non-deterministic polynomial problem is selected from the group consisting of:

combinatorial, routing, and ordering problems.

8. The merging circuit according to claim 6, wherein said non-deterministic polynomial problem is a Traveling Salesman Problem.

9. A method for use in a crossover step of a genetic algorithm machine, said method merging at least two parent chromosomes to form a child chromosome, said child chromosome having a plurality of respective elements thereof each selected from at least one of said parent chromosomes, said method comprising steps of:

receiving a plurality of respective elements from said at least two parent chromosomes and a control select, said at least two parent chromosomes and said control select having the same number of respective elements;

selecting the respective elements of said at least two parent chromosomes to transmit pursuant to said control select;

forming said child chromosome from the respective elements of said at least two parent chromosomes, each of the respective elements of said child chromosome being different, and said respective elements of said child chromosome having an order pursuant to the order of respective elements of at least one parent chromosome; and

transmitting said respective elements of said child chromosome.

10. The method according to claim 9, wherein said step of selecting further comprises the steps of:

passing values from the respective elements of a first of said at least two parent chromosomes according to a first part of said control select, wherein said control select is divided into two parts; and

passing values from the respective elements of a second of said at least two parent chromosomes according to the second part of said control select,

wherein said values from the respective elements of the first parent chromosome and from the respective elements of the second parent chromosome are selected pursuant both to said first and to said second part of said control select and to said values from the respective elements of said first and second parent chromosomes.

11. The method according to claim 10, wherein in said step of selecting, each value from the respective elements of said second parent chromosome is compared to each value from the respective elements of said first parent chromosome, and when the two values from the respective elements of the parent chromosomes are equal, then the value from the respective elements of said first parent chromosome is passed.

12. The method according to claim 9, wherein said step of selecting further comprises passing values from respective elements of a first of said at least two parent chromosomes according to said control select, wherein said control select indicates only said values from respective elements of said first of said at least two parent chromosomes.

13. The method according to claim 9, wherein said genetic algorithm machine solves a non-deterministic polynomial problem.

14. The method according to claim 13, wherein said non-deterministic polynomial problem is selected from the group consisting of:

combinatorial, routing, and ordering problems.

15. The method according to claim 13, wherein said non-deterministic polynomial problem is a Traveling Salesman Problem.