Cellular array for implementing the set merging function
AssigneeHewlett-Packard Company
InventorJ. Barry Shackleford
Life of this patent
Estimating the term…
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.
Claims15
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.
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.
Dependencies are inferred from the claim text.