Combinatorial fitness function circuit
AssigneeHewlett-Packard Development Company, L.P.
InventorJ. Barry Shackleford
Life of this patent
Estimating the term…
Abstract
A fitness function circuit for computing a fitness value for a trial solution to a combinatorial problem accelerates the execution speed of a genetic algorithm machine by evaluating trial solutions at the rate of one evaluated solution per clock cycle. The circuit uses repeated tables of data which describe costs associated with each portion of each trial solution to find the total cost associated with each solution. By increasing memory used and repeating the data tables rather than accessing one table multiple times, and by adding each portion of each trial solution substantially simultaneously, the speed of one evaluated solution per one clock cycle is achieved.
Claims18
A fitness function circuit for determining the fitness of a potential solution for a combinatorial genetic algorithm problem, said fitness circuit comprising:
- a solution register containing said potential solution for said genetic algorithm problem therein, said solution register comprising a plurality of component parts thereof;
- a plurality of data tables, the number of data tables corresponding to the number of said component parts of said solution register, respective data tables having inputs from two respective ones of said component parts of said solution register, each of said data tables comprising a matrix of partial solutions to said combinatorial genetic algorithm problem, the two respective ones of said component parts determining a particular respective partial solution, each of said matrices having identical entries therein;
- and
- an adder connected to each of said plurality of data tables, said adder adding respective partial solutions from each of said plurality of data tables, thereby determining the fitness of said potential solution for said combinatorial genetic algorithm problem.
A method for determining the fitness of a potential solution for a combinatorial genetic algorithm problem, said method comprising the steps of:
- inputting a plurality of potential solution values into a solution register, said solution register comprising a plurality of component parts thereof;
- receiving, after said step of inputting, at each of a plurality of data tables two respective ones of said component parts of said solution register, the number of data tables corresponding to the number of said component parts of said solution register, each of said data tables comprising a matrix of partial solutions to said combinatorial genetic algorithm problem, each of the matrices having identical entries therein;
- indexing said matrices of partial solutions to said genetic algorithm within said plurality of data tables, the two respective ones of said component parts determining respective particular partial solutions within the respective matrices;
- and
- adding, by an adder connected to each of the respective data tables, respective outputs from each of said data tables, whereby the sum of said adder determines the fitness of said potential solution for said combinatorial genetic algorithm problem.
A methodology for determining the fitness of a particular potential solution for a combinatorial genetic algorithm problem from a pool of potential solutions, said methodology comprising steps of:
- (a) inputting a plurality of potential solution values into a solution register, said solution register comprising a plurality of component parts thereof;
- (b) receiving, substantially simultaneously, at each of a plurality of data tables two respective ones of said component parts of said solution register, the number of data tables corresponding to the number of said component parts of said solution register, each of said data tables comprising a matrix of partial solutions specific to said genetic algorithm problem, each of the matrices having identical entries therein;
- (c) indexing said matrices of partial solutions to said genetic algorithm within said plurality of data tables, the two respective ones of said component parts determining respective particular partial solutions within the respective matrices;
- (d) adding, by an adder connected to each of the respective data tables, respective outputs from each of said data tables in parallel, whereby the sum of said adder determines the fitness of said particular potential solution for said genetic algorithm problem;
- (e) comparing the fitness of said particular potential solution to a fitness threshold;
- and
- (f) replacing a prior potential solution from said pool of potential solutions with said particular potential solution if said fitness of said particular potential solution exceeds said fitness threshold, and otherwise deleting said particular potential solution.
Dependencies are inferred from the claim text.