Method for solving the binary minimization problem and a variant thereof
AssigneeRaytheon Company
InventorSteven J. Manson
Life of this patent
Estimating the term…
Abstract
A recursive binary splitting and recombination procedure coupled with a specially tailored genetic algorithm provides a solution to the general binary minimization problem with much lower run times than other methods. A minor modification to the procedure solves a variant of the binary minimization problem using an alternate operator logic that is crucial to solving certain combinatorial geometry problems.
Claims42
A method of binary minimization for a complementary pair of truth tables T and F, comprising:
- Iteratively subdividing the T truth table into sub-tables;
- Solving each of the sufficiently small sub-tables independently as a minimized binary sub-equation using a genetic algorithm;
- Regressing back through the decomposition process to apply the genetic algorithm to reunited sub-tables;
- and
- Repeating the solution procedure until the entire T true truth table has been reunited into a minimized binary equation.
A method of binary minimization for a complementary pair of truth tables T and F, comprising:
- Recursively bisecting the T truth table into sub-tables;
- Using a genetic algorithm with trinary logic to optimize the sub-tables;
- and
- Recursively recombining the sub-tables while using the genetic algorithm to optimize each reunited truth table using the previous solutions as a starting point.
A method of binary minimization for a complementary pair of truth tables T and F, comprising:
- Recursively bisecting the T truth table into sub-tables;
- Forming a seed organism by mapping the true and false values in the rows and columns of the T sub-table to values of +1 and −1 in a like number of chromosomes and genes;
- Computing a table of mandatory entries including those T sub-table entries that singularly prevent confusion of a T sub-table row with an F sub-table row;
- Creating a pool of organisms from the seed organism by setting some of the non-mandatory genes to a 0 value representing either true or false;
- Breeding the pool until the population stabilizes;
- Selecting the highest scoring organism;
- and
- Recursively recombining the sub-tables while using the genetic algorithm to optimize each reunited truth table using the previous highest scoring organisms as a starting point.
Dependencies are inferred from the claim text.